From arenberg@csed-pyramid.UUCP Thu Oct 20 14:24:30 1988
Path: leah!bingvaxu!sunybcs!rutgers!gatech!purdue!decwrl!mejac!gryphon!cadovax!trwrb!arenberg
From: arenberg@trwrb.UUCP (Jeff Arenberg)
Newsgroups: comp.graphics
Subject: Re: Ray/Triangle Intersection with Barycentric Coordinates
Keywords: How we do it.
Message-ID: <827@csed-pyramid.trwrb.UUCP>
Date: 20 Oct 88 18:24:30 GMT
References: <2925@utah-gr.UUCP>
Reply-To: arenberg@csed-pyramid.UUCP (Jeff Arenberg)
Organization: TRW EDS, Redondo Beach, CA
Lines: 77
Posted: Thu Oct 20 11:24:30 1988


Ok, here is how I handle this calculation in my ray tracing program.  I
think it is quite effecient.

Let a triangle be represented in the following manner :

		   |\
		   |  \
		p1 |    \
		   |      \
  O ------------>  |________\
       p0              p2

where p0 is the vector from the origin to one vertex and p1, p2 are the
vectors from the first vertex to the other two vertices.

Let N =   p1 X p2  be the normal to the triangle. 
          -------
	| p1 X p2 |

Construct the matrices

    b =  |  p1  | ,  bb = inv(b) = | bb[0] |
	 |  p2  |                  | bb[1] |
	 |  N   |                  | bb[2] |

and store away bb.

Let the intersecting ray be parameterizes as

    r = t * D + P

Now you can quickly intersect the ray with the triangle using the following
psuedo code. ( . means vector dot product)

    Den = D . bb[2]
    if (Den == 0) then ray parallel to triangle plane, so return
    
    Num = (p0 - P) . bb[2]

    t = Num / Den
    if (t <= 0) then on or behind triangle, so return
    
    p = t * D + P - p0

    a = p . bb[0]
    b = p . bb[1]
    
    if (a < 0.0 || b < 0.0 || a + b > 1.0) then not in triangle and return

    b1 = 1 - a - b     /* barycentric coordinates */
    b2 = a
    b3 = b


The idea here is that the matrix bb transforms to a coordinate frame where
the sides of the triangle form the X,Y axes and the normal the Z axis
of the frame and the sides have been scaled to unit length.  The variable Den
represents the dZ component of the ray in this frame.  If dZ is zero, then
the ray must be parallel to the X,Y plane.  Num is the Z location of
the ray origin in the new frame and t is simply the parameter in both
frames required to intersect the ray with the triangle's plane.  Once t is
known, the intersection point is found in the original frame, saved for
latter use, and the X,Y coordinates of this point are found in the
triangle's frame.  A simple comparison is then made to determine if the
point is inside the triangle.  The barycenter coordinates are also easily
found.

I haven't seen this algorithm in any of the literature, but then I haven't
really looked either.  If anyone knows if this approach has been published
before, I'd really like to know about it.

Jeff Arenberg
-------------------------------------------------------------
UUCP : ( ucbvax, ihnp4, uscvax ) !trwrb!csed-pyramid!arenberg
GEnie: shifty
-------------------------------------------------------------