Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!mailrus!rutgers!iuvax!pur-ee!uiucdcs!uiucdcsm!shirley
From: shirley@uiucdcsm.cs.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: ray to triangle
Message-ID: <4400020@uiucdcsm>
Date: 21 Apr 88 03:01:00 GMT
References: <15@<Apr>
Lines: 64
Nf-ID: #R:<Apr:15:uiucdcsm:4400020:000:2209
Nf-From: uiucdcsm.cs.uiuc.edu!shirley    Apr 20 21:01:00 1988




Roy Hashimoto's note reminded me that I forgot to mention a sidenote--
if you can constrain your ray to start at the origin (easy for first 
generation rays-- otherwise it's no-go) you can take a shortcut:

The ray can now be described 'tv' instead of 'o + tv' (o = origin point,
v = view direction, t = parametric distance along ray).  As before, the
parametric equation for the plane containing the triangle is:

          p = p0 + k1*(p1 - p0) + k2*(p2 - p0)

Here p is a point on the plane that varies with k1 and k2, and p1/p2/p3
are the vertices.  The conditions for inside/outside are the same as in
my last response (I apologize if I have changed notation).

We can generalize this to:

         p = k0*p0 + k1*p1 + k2*p2

The point p is inside now if k0/k1/k2 are all positive (the condition
'k1 + k2 < 1' becomes '1 - (k1+k2) > 0' is 'k0 > 0').
Now assume that the ray hits the plane:

         tv = k0*p0 + k1*p1 + k2*p2

since k0/k1/k2 are unknowns we can rewrite:

         v = k0'*p0 + k1'*p1 + k2'*p2 

or

              |p0x p1x p2x|     |k0'|     |vx|
              |p0y p1y p2y|  *  |k1'|  =  |vy|
              |p0z p1z p2z|     |k2'|     |vz|

To solve :

         |k0'|     |p0x p1x p2x|-1    |vx|
         |k1'|  =  |p0y p1y p2y|   *  |vy|
         |k2'|     |p0z p1z p2z|      |vz|

If t is positive then the ray hits inside iff all k's are positive, otherwise
it hits only if they are all negative (a case we probably aren't 
interested in for normal ray tracing applications).

Since we can precompute the inverted matrix, that gives a maximum of
9 multiplies, 6 adds, and 3 compares for each intersection.  Usually we
can get away with fewer operations since all k's must be above 0.

Another thing I forgot to mention in my last response-- k1 and k2 are texture
coordinates for interpolation if colors or normal vectors are defined
at the vertices (if using the method here renormalize k's using condition
that k0 + k1 + k2 = 1.  This also will give t).  The interpolation 
formula is 
     
             (1 - k1 - k2)*c0 + k1*c1 + k2*c2


As a final note, this method was shown to me by Hiroshi Degushi, whose
group implemented this on LINKS-1 hardware in Japan.


Peter Shirley