From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: comp.graphics.algorithms
Subject: Re: HELP! Intersection algorithm
Date: 13 Feb 1996 08:04:12 GMT

In article <4fhtie$7l1@news.NetVision.net.il>,
Alex Kontorovich - Software Support <alex@bones> wrote:

>There is a set of triangles (each vertex is given by triple
>(x,y,z) of coordinates) which forms a 3d closed complex body 
>and there is a segment of line (given by two points: begin and 
>end) which intersects this body. How can we detect for each point
>of this segment if it is inside or outside of this body?

If the line segment goes from  B  to  E, then the points on it
are of the form  B*(1-t) + E*t  where  t  ranges from  0  to  1.
The ray from  B  through  E  is the same set of points but with all
positive  t.

For each face, find the value of  t, if one exists, where the face
meets this ray. If the values of  t  so obtained are sorted as
t1 > t2 > ... > t_n > 0,  then the points on the ray which are outside
the body are those with either
	     t > t1  or
	t2 > t > t3  or
	t4 > t > t5  or ...
Once you have made this determination, of course, you may discard the
information about values of  t  greater than  1, if indeed you care
only about the line segment.

For a simple figure there will be few intervals (e.g. a convex shape
leads to at most two points of intersection  t1 > t2. ) If you have no
such geometric information, I don't see how you can avoid considering
just about all the faces (imagine a line segment piercing the folds
of an accordian).

You will have to be careful about degenerate cases: if the ray lies in the
same plane as one of the triangles, for example, or if just
grazes the edge of a polygon without passing through the surface.

dave

==============================================================================