Geometric Tests - 3D Math Primer for Graphics and Game Development - page 734

A.16 Intersection of a Ray and a Triangle

The ray-triangle intersection test is very important in graphics and com-
putational geometry. In the absence of a special raytrace test against a
given complex object, we can always represent (or at least approximate)
the surface of an object as a triangle mesh and then raytrace against this
triangle mesh representation.
Here we use a simple strategy from Badouel [4]. The first step is to com-
pute the point where the ray intersects the plane containing the triangle.
Section A.9 showed how to compute the intersection of a plane and a ray.
Then we test to see whether that point is inside the triangle by computing
the barycentric coordinates of the point, as discussed in Section 9.6.4.
To speed up this test, we use a few tricks:

• Detect and return a negative result (no collision) as soon as possible.

This is known as “early out.”

• Defer expensive mathematical operations, such as division, as long

as possible. This is done for two reasons. First, if the result of the
expensive calculation is not needed (for example, if we took an early
out), then the time we spent performing the operation was wasted.
Second, it gives the compiler plenty of room to take advantage of
the operator pipeline in modern processors. If an operation such as
division has a long latency, then the compiler may be able to look
ahead and generate code that begins the division operation early. It
then generates code that performs other tests (possibly taking an early
out) while the division operation is under way. Then, at execution
time, if and when the result of the division is actually needed, the
result will be available or at least partially completed.

• Only detect collisions where the ray approaches the triangle from the

front side. This allows us to take a very early out on approximately
half of the triangles. Intersecting with both sides is slightly slower.

Listing A.4 implements these techniques. Although it is commented
in the listing, we have chosen to perform some floating point comparisons
“backwards” since this behaves better in the presence of invalid floating
point input data and NaNs (Not a Number).

f l o a t r a y T r i a n g l e I n t e r s e c t (
c o n s t V e c t o r 3 &r a y O r g , / / o r i g i n o f t h e r a y

c o n s t V e c t o r 3 &r a y D e l t a , / / r a y l e n g t h and d i r e c t i o n

c o n s t V e c t o r 3 &p0 , / / t r i a n g l e v e r t i c e s

c o n s t V e c t o r 3 &p1 , / / .

c o n s t V e c t o r 3 &p2 , / / .

f l o a t minT / / c l o s e s t i n t e r s e c t i o n found so f a r .

/ / ( S t a r t w i t h 1 . 0 )