Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!pasteur!ucbvax!hplabs!sdcrdcf!trwrb!aero!roy
From: roy@aero.ARPA (Roy Hashimoto)
Newsgroups: comp.graphics
Subject: Re: ray to triangle
Message-ID: <29203@aero.ARPA>
Date: 19 Apr 88 00:08:35 GMT
References: <15@<Apr> <4400019@uiucdcsm>
Reply-To: roy@aero.UUCP (Roy Hashimoto)
Organization: The Aerospace Corporation, El Segundo, CA
Lines: 104

Here is my ray-triangle intersection algorithm.  I won't claim
that it's unique, but I haven't seen it in any texts.  On the
other hand, with thousands of people writing ray tracers, it's
hard to believe that anything is really new.  Stop me if you've
heard this one...

A ray can be defined parametrically as

	    (x0,y0,z0) + t*(dx,dy,dz), t > 0

where (x0,y0,z0) is the initial point and (dx,dy,dz) is a direction
vector.  The triangle primitive can similarly be partially defined
by

     (xp,yp,zp) + t1*(v1x,v1y,v1z) + t2*(v2x,v2y,v2z), t1,t2 > 0

where (xp,yp,zp) is a vertex, and the two direction vectors are
obtained by subtracting that vertex from each of the remaining two.
Note that this is only a partial definition, as additional restrictions
must be placed on t1 and t2.

An intersection occurs where these vector equations are satisfied
simultaneously, and it is easy to write a set of equations in
t, t1, and t2.  Only solutions with t, t1, and t2 all positive are
of interest, and this limitation is useful to pare the computation.

Solving the system with Cramer's formula requires the calculations
of four determinants.  Careful ordering of the calculations involved
will reduce the amount of work for rays that miss.

Referring to the four determinants as D (coefficients only), D*t,
D*t1, and D*t2, by playing with the expressions for D and D*t, we
can see that:

1.  They share the terms:
                     vy1*vz2 - vy2*vz1
                    vx1*vz2 - vx2*vz1
                    vx1*vy2 - vx2*vy1

2.  These terms are independent of the ray.

3.  These terms, with one sign change, form a normal vector of
the triangle.

Since a normal probably must be stored anyway for shading purposes,
why not store this one?  It is true that usually a normalized vector
is more appropriate, so storing a scaling factor to convert to a
normalized vector would be helpful.  Now D and D*t can be calculated
using 6 multiplies and 7 adds (I count subtracts=adds).

If D = 0, or D and D*t have opposite signs, there is no positive
t solution, and all remaining calculations can be eliminated.  If
the signs are the same, compute D*t1.  As far as I know, there are
no shortcuts, and D*t1 will take 9 multiplies and 5 adds.

If D*t1 has a different sign from D and D*t, there is no appropriate
solution, and this terminates the test.  If not, go ahead with
D*t2, another 9 multiplies and 5 adds, and check the signs again.

Assuming all the signs match, the ray satisfies the conditions for
the partially defined triangle.  The remaining constraint is:

          			 t1 + t2 < 1

which is equivalent to

		   abs(D*t1) + abs(D*t2) < abs(D)

which requires 2 adds and maybe some sign changes.  All the rays
that pass this stage have been determined to intersect the triangle.
The only remaining information required is the intersection point,
which can be found by finding t with 1 division and substituting
in our original ray equation, requiring 3 multiplies and 3 adds.

Making the following assumptions:

1.  Comparison of D and D*t eliminates half the rays (they point
away from the plane containing the triangle).

2.  Comparison with D*t1 eliminates half the remaining rays (wrong
half-plane).

3.  Comparison with D*t2 eliminates two-thirds of the remaining
rays (a series of randomly chosen angles of random triangles
should average 60 degrees).

4.  No rays are eliminated in the t1 + t2 < 1 constraint.

then the expected calculation per test is 13.0 multiplies, 11.2
adds, and 0.1 divisions.

It is very important to note that these assumptions work for
random rays and random triangles, which is not generally correct
for real ray tracers.  The use of bounding boxes or other methods
of object or ray coherence will also invalidate these results.
However, I have used this algorithm for a number of different
approaches, and it is quite fast and doesn't require a lot of
additional storage.

I would appreciate hearing any comments on this technique, or,
better still, on any faster algorithms.

Roy T. Hashimoto
The Aerospace Corporation
roy@aerospace.aero.org