# cili_wabbit: Thanks, Mummy: 3d S&H alg

Started by Jan 10 2000 06:37 PM

,
No replies to this topic

###
#1
Members - Reputation: **122**

Posted 10 January 2000 - 06:37 PM

um, i can sort of see how that goes now, THANKS!! cili_wabbit !!, i was ABOUT to scold you for ur "easiness":
Mummy: a suggestion. not sure if it works exactly, it is a scary alg. it does 3d S&H clipping (go to the link if u don't know what that is), like it or not (it may be slow, but its practical), but like i said, you can just transform the poly and do 2d S&H. Also use the bounding sphere idea for rough cutting. 3D S&H:
the idea is the same as 2d S&H, take the poly, clip it against each of the planes by clipping each line seg in it (you have to send the resulting poly to the next function in order each time)
first an alg to find the intersection point of a line seg (v1 to v2) and a plane:
there is a very descent way of doing that WITH your Hesse form, i got a hint of it from my Math teacher (well, they are good for some things! ) here it is:
v1:=1st vert in seg, v2:=2nd vert in seg, P:=plane vertex, N:=plane normal(hesse),t:=time/blend factor,v2v1:=vect v1 to v2
let W(t) = v1 + t*(v2v1) (3d line eq) and Vt = vector P to Wt, now solve for 't' so that Vt is perpindicular to the Hesse normal, so Vt o N = 0.
this comes out to be:
(v1xNx+v1yNy+v1zNz - PxNx-PyNy-PzNz) /
(v2x-v1x+v2y-v1y+v2z-v1z) == t
which is:
(v1 o N - P o N) /
(v2x-v1x+v2y-v1y+v2z-v1z) == t
YOU will have to check these calcs, but i'm sure the eq is possible.
THIS equation holds for all cases, giving you 't', the time factor of the vector line. NOW you get Wt, which is the intersection point:
Wt = v1 + t(v2v1)
Now, make six functions, one for each plane. each function will accept a ptr to a poly struct, v1 and v2. init 2 poly structs to empty, call the first plane clipping func as many times as there are segments (you will have to do vertex wrap around on the last seg), pass it one of the empty structs and the v1 and v2 of the seg. call the next clipping func with the current poly, pass it the other empty poly, and keep alternating (see the link to get the idea, its 2d, but same principle).
Now the leftplane clipping:
find the Wt for the seg,
check if Wt is between the two segment vertices (comp x,y,z). if it isn't, the seg is either on one side or the other, find out which by ur Hesse alg, if it is outside, just forget about it, its totally out. if inside, add v2 to the temp poly. if Wt is between the two, find out which of the vertices is outside and which is inside. if v1 is out, add Wt and v2, if v2 is out, only add Wt. i don't know myself why this order, but it works in 2d, should work in 3d. do this for all six funcs. IN the end you have the final poly, u can just check if there are any vertices in it or not.
sheeeezzz, maybe i should write an article
Finally, the postmortem, i guess... IF this works in the first place (or it could be another 'intuition' of mine), i don't know whether it is any faster than just transforming the poly and doing 2d H&S clipping. like it or not.
i'd like to credit Dale Hoffman, my Calculus 124 teach, for the intersection alg, and Jerome for info from that website.
i'm also working on another alg that uses eq for convex polys and eq for a solid... but its a long shot, anyone want to fry their brains with me?
oh, &&& somebody confirm:
is this a valid eq for any convex poly of N verts??:
V1,V2,V3...Vi:=poly vertices
N:=num poly verts
W:=the tested arbitrary vector from origin to (x,y,z)
F(i):=function defined later
Sum of (F(i)) from i = 1 to N == 360 (degrees)
F(i) = {if i == N, the smallest angle between W->Vi & W->V0
else, the smallest angle between W->Vi & W->Vi+1}
Thanks in advance!!
Alex.
**once again, the link:
http://pages.infinit.net/jstlouis/3dbhole/
Edited by - AlexM on 1/11/00 12:40:55 AM