Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!mailrus!umix!nancy!eecae!super.upenn.edu!linc.cis.upenn.edu!david
From: david@linc.cis.upenn.edu (David Feldman)
Newsgroups: comp.graphics
Subject: Re: Lines intersecting with a triangle... (3D points)
Message-ID: <3854@super.upenn.edu>
Date: 31 Mar 88 18:32:12 GMT
References: <14212@hc.DSPO.GOV> <1501@vaxb.calgary.UUCP> <14214@hc.DSPO.GOV>
Sender: news@super.upenn.edu
Reply-To: david@linc.cis.upenn.edu.UUCP (David Feldman)
Distribution: na
Organization: University of Pennsylvania
Lines: 54
Keywords: vectors
Summary: use vectors man!!


I don't know if the algorithm I am about to present is the fastest, but it
should work.

Every triangle defines a plane.  The equation of that plane can be derived from
a normal vector to that plane.  A normal vector can be achieved by taking the
cross product of two sides of the traingle (reprented by vectors).  Now, pick
any point on that plane, such as a vertex of the trianlge (x0,y0,z0).  A
vector from this point to any other point (x,y,z) on the plane will be
perpendicular to the normal vector (A,B,C).  Using a dot product,
	A(x-x0) + B(y-y0) + C(z-z0) = 0
	Ax + By + Cz = d   where  d = Ax0 + By0 + cz0
Now, a vector (D,E,F) may be parameterized into a line by the equation set
	x = x1 + tD	y = y1 + tE	z = z1 + tF
where t is the parameter and (x1,y1,z1) is a point on the line.  Substituting
these into the first eqn we find that
	A(x1 + tD) + B(y1 + tE) + C(z1 + tF) = d
	t = d - (Ax1 + By1 + Cz1)
	    ---------------------
	        AD + BE + CF
From t and the line equations we can find the point of intersection.  Now that
you have the intersection point, is it in the triangle?  To find out you can
use cross products.  Construct vectors from each vertex to the intersection
point.  Given one of these vectors (label it V1) constructed to a vertex v1,
construct a second vector from vertex v1 to vertex v2 such that v2 is the next
vertex after v1 in a right-hand-rule procession around the normal to the plane.
Label this second vector V2.  Now, V2 cross V1 will either be parallel or
anti-parallel to the normal.  If the intersection point is in the triangle,
it will be parallel.  You can check this by comparing the signs of the
coordinates of the vectors.  If the cross product is parallel for all vertices
v1, then the point is in the trangle.  Incidentally, this works for any convex
polygon.

Some notes and disclaimers:
	1) I am sure that this is in a book somewhere but I derived it here
		while composing this posting.  It may not be totally
		accurate and make no claims as such.
	2) You needn't perform full cross products.  Anti-parallelism will
		show a sign change in all coordinates.  Therefore, just
		calculate and check one coordinate (which must have a non-zero
		value in the plane's normal vector).
	3) If a cross product yields a zero answer, ignore it.  You can't check
		a sign change against a zero.  A zero means the intersection
		point lies along one of the vector edges of the triangle.
		If this point is outside the triangle, it will be detected on
		one of the other two comparisons.

Hope this helps.

					Dave Feldman
					david@linc.cis.upenn.edu
					david@dsl.cis.upenn.edu
					david@eniac.cis.upenn.edu
					david@xmos.cis.upenn.edu
					etc............