Möller–Trumbore intersection algorithm

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.[1] Among other uses, it can be used in computer graphics to implement ray tracing computations involving triangle meshes.[2]

Pseudocode

Assuming a Vec3 datatype and the SUB (element-wise subtraction), CROSS, and DOT operations, the following C program describes the algorithm:

#define EPSILON 0.000001

int triangle_intersection( const Vec3   V1,  // Triangle vertices
                           const Vec3   V2,
                           const Vec3   V3,
                           const Vec3    O,  //Ray origin
                           const Vec3    D,  //Ray direction
                                 float* out )
{
  Vec3 e1, e2;  //Edge1, Edge2
  Vec3 P, Q, T;
  float det, inv_det, u, v;
  float t;

  //Find vectors for two edges sharing V1
  SUB(e1, V2, V1);
  SUB(e2, V3, V1);
  //Begin calculating determinant - also used to calculate u parameter
  CROSS(P, D, e2);
  //if determinant is near zero, ray lies in plane of triangle or ray is parallel to plane of triangle
  det = DOT(e1, P);
  //NOT CULLING
  if(det > -EPSILON && det < EPSILON) return 0;
  inv_det = 1.f / det;

  //calculate distance from V1 to ray origin
  SUB(T, O, V1);

  //Calculate u parameter and test bound
  u = DOT(T, P) * inv_det;
  //The intersection lies outside of the triangle
  if(u < 0.f || u > 1.f) return 0;

  //Prepare to test v parameter
  CROSS(Q, T, e1);

  //Calculate V parameter and test bound
  v = DOT(D, Q) * inv_det;
  //The intersection lies outside of the triangle
  if(v < 0.f || u + v  > 1.f) return 0;

  t = DOT(e2, Q) * inv_det;

  if(t > EPSILON) { //ray intersection
    *out = t;
    return 1;
  }

  // No hit, no win
  return 0;
}

See also

References

  1. ↑ Fast, Minimum Storage Ray/Triangle Intersection, Möller & Trumbore. Journal of Graphics Tools, 1997.
  2. ↑ "Möller-Trumbore algorithm". scratchapixel. Retrieved 2015-10-25.
  3. ↑ Ray Intersection of Tessellated Surfaces: Quadrangles versus Triangles, Schlick C., Subrenat G. Graphics Gems 1993


This article is issued from Wikipedia - version of the 6/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.