# 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]

## Calculation

### Definitions

The ray is defined by an origin point ${\displaystyle O}$ and a direction vector ${\displaystyle {\vec {v}}}$. Every point on the ray can be expressed by ${\displaystyle {\vec {r}}(t)=O+t{\vec {v}}}$, where the parameter ${\displaystyle t}$ ranges from zero to infinity. The triangle is defined by three verticies, named ${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$, ${\displaystyle v_{3}}$. The plane that the triangle is on, which is needed to calculate the ray-triangle intersection, is defined by a point on the plane, such as ${\displaystyle v_{1}}$, and a vector that is orthogonal to every point on that plane, such as the cross product between the vector from ${\displaystyle v_{1}}$ to ${\displaystyle v_{2}}$ and the vector from ${\displaystyle v_{1}}$ to ${\displaystyle v_{3}}$:

${\displaystyle {\vec {n}}\cdot (P_{1}-P_{2})=0}$, where ${\displaystyle {\vec {n}}=(v_{2}-v_{1})\times (v_{3}-v_{1})}$, and ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$ are any points on the plane.

### Check if the ray is parallel to the triangle

First, find out if the ray intersects with the plane that the triangle is on, and if it does, find the coordinates of that intersection. The only way that the ray will not intersect the plane is if the ray's direction vector is parallel to the plane.[3] When this happens, the dot product between the ray's direction vector and the plane's normal vector will be zero. Otherwise, the ray does intersect the plane somewhere, but not necessarily within the triangle.

### Check if the ray-plane intersection lies outside the triangle

Using barycentric coordinates, any point on the triangle can be expressed as a convex combination of the triangle's verticies: ${\displaystyle P=wv_{1}+uv_{2}+vv_{3}}$

The coefficients must be non-negative and sum to 1, so w can be replaced with ${\displaystyle 1-u-v}$:

{\displaystyle {\begin{aligned}P&=(1-u-v)v_{1}+uv_{2}+vv_{3}\\P&=v_{1}+u(v_{2}-v_{1})+v(v_{3}-v_{1})\end{aligned}}}, where ${\displaystyle P}$ is any point on the plane. Observe that ${\displaystyle {\vec {e_{1}}}=v_{2}-v_{1}}$ and ${\displaystyle {\vec {e_{2}}}=v_{3}-v_{1}}$ are vectors on the edge of the triangle, and together, they span a plane (which goes through the origin). Each point on that plane can be written as ${\displaystyle ue_{1}+ve_{2}}$ and can be translated by ${\displaystyle v_{1}}$ to "move" that point onto the plane that the triangle is on.

To find ${\displaystyle u}$ and ${\displaystyle v}$ for a particular intersection, set the ray expression equal to the plane expression, and put the variables on one side and the constants on the other.

{\displaystyle {\begin{aligned}O+tD&=v_{1}+u(v_{2}-v_{1})+v(v_{3}-v_{1})\\O-v_{1}&=-tD+u(v_{2}-v_{1})+v(v_{3}-v_{1})\end{aligned}}}

This is a system of linear equations with three equations (one each for ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle z}$) and three unknowns (${\displaystyle t}$, ${\displaystyle u}$, and ${\displaystyle v}$), and can be represented as a matrix-vector multiplication.

${\displaystyle {\begin{bmatrix}\vert &\vert &\vert \\-d&(v2-v1)&(v3-v1)\\\vert &\vert &\vert \end{bmatrix}}{\begin{bmatrix}t\\u\\v\end{bmatrix}}=O-v_{1}}$

This equation will always have a solution when the matrix has three linearly independent column vectors in ${\displaystyle \mathbb {R} ^{3}}$ and is thus invertible. This happens if and only if the triangle verticies aren't collinear and the ray isn't parallel to the plane.

The algorithm can use Cramer's Rule to find the ${\displaystyle t}$, ${\displaystyle u}$, and ${\displaystyle v}$ values for an intersection, and if it lies within the triangle, the exact coordinates of the intersection can be found by plugging in ${\displaystyle t}$ to the ray's equation.

## C++ implementation

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;    // This ray is parallel to this triangle.
f = 1.0/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;
}


## Java implementation

The following is an implementation of the algorithm in Java using javax.vecmath from Java 3D API:

public class MollerTrumbore {

private static final double EPSILON = 0.0000001;

public static boolean rayIntersectsTriangle(Point3d rayOrigin,
Vector3d rayVector,
Triangle inTriangle,
Point3d outIntersectionPoint) {
Point3d vertex0 = inTriangle.getVertex0();
Point3d vertex1 = inTriangle.getVertex1();
Point3d vertex2 = inTriangle.getVertex2();
Vector3d edge1 = new Vector3d();
Vector3d edge2 = new Vector3d();
Vector3d h = new Vector3d();
Vector3d s = new Vector3d();
Vector3d q = new Vector3d();
double a, f, u, v;
edge1.sub(vertex1, vertex0);
edge2.sub(vertex2, vertex0);
h.cross(rayVector, edge2);
a = edge1.dot(h);
if (a > -EPSILON && a < EPSILON) {
return false;    // This ray is parallel to this triangle.
}
f = 1.0 / a;
s.sub(rayOrigin, vertex0);
u = f * (s.dot(h));
if (u < 0.0 || u > 1.0) {
return false;
}
q.cross(s, edge1);
v = f * rayVector.dot(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.
double t = f * edge2.dot(q);
if (t > EPSILON) // ray intersection
{
outIntersectionPoint.set(0.0, 0.0, 0.0);
return true;
} else // This means that there is a line intersection but not a ray intersection.
{
return false;
}
}
}