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 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 ==============================================================================