11

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

3 Answers 3

11

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/

3
5

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.

2
  • 1
    You're right. Apparently these kinds of false intersections are known as "fireflies" and both MT and Weber's algorithms has a fair amount of them. You can see some examples of them in this question stackoverflow.com/questions/44808194/… May 12, 2018 at 12:45
  • 1
    @BjörnLindqvist I did find a paper "Watertight Ray/Triangle Intersection" by Woop, Benthin and Wald that might be a good compromise. The results in terms of 'fireflies' and time both look promising. Here's the link if you're curious. jcgt.org/published/0002/01/05/paper.pdf May 12, 2018 at 18:43
1

I'm not convinced that either Balwin-Weber or Möller-Trumbore are faster by any significant margin over Woop, et al. Even if they're relatively close in a single instance, if you amortize the cost of the ray geometry {r0, rd} permuting the {x, y, z} dimensions, you have the pre-computed axis permutation and scaling for each ray / triangle system: {p0, p1, p2, r0, rd}

Applying the affine transforms to the bring the triangle into that ray space yields intersection tests that are effectively 2D. More importantly, you are testing the barycentric (u, v, w) independently, rather than relying on the w = (1 - u - v) condition, which can never be 'water-tight'. In the extreme case, the paper uses double-precision to resolve any edge cases. These bounds could probably be made tighter with FMA operations as described here, which are ubiquitous on modern CPUs and GPUs. The PBRT code has adopted this algorithm.

Both CPU and GPU sides are amenable to SIMD / swizzle methods for permutations.

2
  • 1
    This is an old question. :) After posting it, I went on to benchmark various ray-triangle intersection algorithms myself for an article I never got around to finish. Möller-Trumbore was indeed faster than both Woop's and Baldwin-Weber's algorithms. At least when implemented using SIMD instructions in the Embree framework. But the Havel-Herout algorithm was a bit faster than all the others. Especially on coherent ray packages. Dec 25, 2022 at 13:18
  • Performance diff wasn't that big, iirc MT was about 5% faster than the rest and HH an additional 5% faster than MT. For incoherent rays memory latencies dominated and the difference was very very small. Dec 25, 2022 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.