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]

C++ Implementation

Following is an implementation of the algorithm im C++ using the glm math library:

#include <glm/glm.hpp>
using namespace::glm;

// orig and dir defines the ray. v0, v1, v2 defines the triangle.
// returns the distance from the ray origin to the intersection or 0.
float
triangle_intersection(const vec3& orig,
                      const vec3& dir,
                      const vec3& v0,
                      const vec3& v1,
                      const vec3& v2) {
    vec3 e1 = v1 - v0;
    vec3 e2 = v2 - v0;
    // Calculate planes normal vector
    vec3 pvec = cross(dir, e2);
    float det = dot(e1, pvec);

    // Ray is parallel to plane
    if (det < 1e-8 && det > -1e-8) {
        return 0;
    }

    float inv_det = 1 / det;
    vec3 tvec = orig - v0;
    float u = dot(tvec, pvec) * inv_det;
    if (u < 0 || u > 1) {
        return 0;
    }

    vec3 qvec = cross(tvec, e1);
    float v = dot(dir, qvec) * inv_det;
    if (v < 0 || u + v > 1) {
        return 0;
    }
    return dot(e2, qvec) * inv_det;
}

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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.