The Moller – Trumbor algorithm is an algorithm for determining the intersection of a straight line (ray) and a triangle in three-dimensional space, the operation of which does not require preliminary calculation of the equation of a plane containing a triangle. [1] This algorithm can also be used in computer graphics to implement ray tracing using polygonal meshes consisting of triangles. [2]
Named after the authors - Tomas Möller and Ben Trumbore.
C ++ Implementation
The following is an implementation of the algorithm in C ++ using the GLM library:
#include <glm / glm.hpp>
using namespace :: glm ;
// orig and dir specify the beginning and direction of the ray. v0, v1, v2 are the vertices of the triangle.
// The function returns the distance from the beginning of the ray to the intersection point 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 ;
// Calculation of the normal vector to the plane
vec3 pvec = cross ( dir , e2 );
float det = dot ( e1 , pvec );
// The beam is parallel to the 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 ;
}
Links
- ↑ Fast, Minimum Storage Ray / Triangle Intersection , Möller & Trumbore. Journal of Graphics Tools, 1997.
- ↑ Möller-Trumbore algorithm . scratchapixel. Date of appeal October 25, 2015.