CODEWITHSUNDEEP
algorithmlinear-algebraintersectionraytracing
Gaslight Deceive Subvert
Gaslight Deceive Subvert

Reputation: 20354

Is Möller-Trumbore ray intersection the fastest?

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

Upvotes: 13

Views: 13478

Answers (3)

Brett Hale
Brett Hale

Reputation: 22308

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.

Upvotes: 2

Jan-Michael Tressler
Jan-Michael Tressler

Reputation: 659

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.

Upvotes: 5

plasmacel
plasmacel

Reputation: 8530

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/

Upvotes: 12

Related Questions