Möller–Trumbore intersection algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]

C++ Implementation[edit]

The following is an implementation of the algorithm in C++:

bool RayIntersectsTriangle(Vector3D rayOrigin, 
                           Vector3D rayVector, 
                           Triangle* inTriangle,
                           Vector3D& outIntersectionPoint)
{
    const float EPSILON = 0.0000001; 
    Vector3D vertex0 = inTriangle->vertex0;
    Vector3D vertex1 = inTriangle->vertex1;  
    Vector3D vertex2 = inTriangle->vertex2;
    Vector3D edge1, edge2, h, s, q;
    float a,f,u,v;
    edge1 = vertex1 - vertex0;
    edge2 = vertex2 - vertex0;
    h = rayVector.crossProduct(edge2);
    a = edge1.dotProduct(h);
    if (a > -EPSILON && a < EPSILON)
        return false;
    f = 1/a;
    s = rayOrigin - vertex0;
    u = f * (s.dotProduct(h));
    if (u < 0.0 || u > 1.0)
        return false;
    q = s.crossProduct(edge1);
    v = f * rayVector.dotProduct(q);
    if (v < 0.0 || u + v > 1.0)
        return false;
    // At this stage we can compute t to find out where the intersection point is on the line.
    float t = f * edge2.dotProduct(q);
    if (t > EPSILON) // ray intersection
    {
        outIntersectionPoint = rayOrigin + rayVector * t; 
        return true;
    }
    else // This means that there is a line intersection but not a ray intersection.
        return false;
}

See also[edit]

Links[edit]

References[edit]

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