Menu
For a ray tracer project, I've been researching algorithms dealing with finding the intersection between rays and triangles (defined by three vertices). What I've found so far is that the Möller-Trumbore (MT) algorithm is used universally.
So my questions are 1) Are there any alternatives to MT or is the algorithm deemed to be the fastest way to calculate intersections? 2) If yes, is MT proven to be optimal or could someone conceivably invent an even faster algorithm?
Edit: I see now that my question is very similar to Ray-triangle intersection
989
The Möller–Trumbore ray-triangle intersection algorithm, named after its inventors Tomas Möller and Ben Trumbore, is a fast method for calculating the intersection of a ray and a triangle in three dimensions without needing precomputation of the plane equation of the plane containing the triangle.
The ray can intersect the triangle or miss it. If the ray is parallel to the triangle there is not possible intersection. This situation occurs when the normal of the triangle and the ray direction are perpendicular (and the dot product of these two vectors is 0).
To find the intersection between a line and a triangle in 3D, follow this approach: Compute the plane supporting the triangle, Intersect the line with the plane supporting the triangle: If there is no intersection, then there is no intersection with the triangle.
There is a paper from 2016 where the authors claim
Running under ideal experimental conditions, our algorithm is always faster than the standard Möller and Trumbore algorithm, and faster than a highly tuned modern version of it except at very high ray-triangle hit rates.
Source: Doug Baldwin and Michael Weber, Fast Ray-Triangle Intersections by Coordinate Transformation, Journal of Computer Graphics Techniques (JCGT), vol. 5, no. 3, 39-49, 2016
Available online http://jcgt.org/published/0005/03/03/
108
Be cautious of the Weber algorithm. While it may be faster, I'm seeing a good amount of intersections falsely identified as not intersecting. The paper states:
This series of calculations can terminate early if t is too small or large to represent a valid intersection, or if b1 is out of the range that permits an intersection.
I've seen about 2-3% of my mesh fail early because 't' was too small. I'm still troubleshooting, but it looks like the inverse of P is causing my rotated direction vector to be too large, equating to a small 't'.
On the other hand, you can also get false intersections with the MT algorithm if epsilon isn't set correctly.
23
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
