2014-05-23 Tavian Barnes Comments
3D ray/triangle intersections are obviously an important part of much of computer graphics. The Möller–Trumbore algorithm, for example, computes these intersections very quickly. But there is another method that I believe is more elegant, and in some cases allows you to compute the intersection for “free.”
Say your triangle has corners at , , and . If your triangle is not degenerate, those three points define a plane. Writing the vector from to as , and similarly for , the normal vector perpendicular to that plane is given by
Since , , and are all linearly independent, they form an alternative basis for all of 3-space. That is, any point can be represented by a unique triple such that
We can make this space even nicer by translating to the origin, giving
In this space, the three corners of the triangle are at , , and . It is easy to see that a point is within the triangle if and only if , , and .
To transform a point into this nicer space, we can use an affine change of basis matrix
A line defined by can thus be transformed into the new space by
Solving for the intersection point is easy:
And as above, this can be quickly checked with , (and to only count intersections “in front” of the ray).
The beauty of this method is that often, objects are already associated with a transformation matrix, so if you left-multiply that matrix by , the change of basis is performed for free at the same time as other transformations, and only the short block above is needed to actually perform the intersection test. At a cost of 1 division, 2 multiplications, 2 or 3 additions, and some comparisons, that's about as fast as possible without special-casing triangles versus other objects.
Of course, if you're working with lots of triangles (a mesh, for example), you can save memory and time by not associating a transformation matrix with each triangle. In that case, other algorithms such as the one linked above may be faster as they can avoid the two matrix multiplications.
I'm a bit confused about the "cost of 1 division, 2 multiplications, 2 or 3 additions, and some comparisons". Don't you still have to multiply each ray by the matrix P? So even if P is precomputed and stored ahead of time, that's still 16 multiplications and 12 additions, plus the computations of t,u, and v.
Tavian Barnes 2014-08-10
That's in the case that "objects are already associated with a transformation matrix," in which case you have to do a matrix-ray multiplication anyway, so it doesn't count against you. Also I think you've underestimated the cost of a matrix-ray multiplication, it ought to be 18 multiplications and 15 additions.
Hi! I wonder what is nw is 0? I watched sources from the dimension repo, that case is not handled at all:
Could you please explain what to do if nw is 0?
Tavian Barnes 2017-01-31
Geometrically, if is zero, then the line is exactly parallel to the plane of the triangle. For this degenerate case, it's easiest to just return "no intersection." There are a few sub-cases:
- : Then we'll have , so fails and we return
- : We'll have , so again fails and we return
- : We get . Depending on and ,
- or : Then , , so at least one of or fails and we return
- or : Results in or , so again one of or fails and we return
- and : That means , so fails and we return
Without explicitly handling the case, the properties of IEEE floating point arithmetic have given us the desired behaviour in all cases.