Möller-Trumbore Ray-Triangle Intersection

1. The Core Idea: Where the Ray Meets the Triangle

To start, let's define the problem. A ray is defined by its origin $O$ and direction $D$, giving any point $P$ along it as:
$P(t)=O+tD$

A triangle is defined by three vertices, let's call them $V_0$, $V_1$, and $V_2$. Any point $P$ inside this triangle can be described using barycentric coordinates $u$ and $v$:
$P(u,v)=(1-u-v)V_0+u{V}_1+v{V}_2$
Here, $u$ and $v$ are weights. For a point to be inside the triangle, we must have $u\ge 0$, $v\ge 0$, and $u+v\le 1$.

The genius of the Möller-Trumbore algorithm is to find a point where these two representations are equal. By setting $P(t)=P(u,v)$, we can solve for the three unknowns: the ray distance $t$ and the barycentric coordinates $u$ and $v$.

The first step is to rearrange this equality into a standard system of linear equations. This involves some vector algebra that your linear algebra background will make very familiar.

After the derivation, you should arrive at a matrix equation that looks like this:

Let's denote the triangle edges as $E_1=V_1-V_0$ and $E_2=V_2-V_0$, and the vector from the ray origin to the first vertex as $T=O-V_0$. The system becomes:

This is a standard 3x3 system of linear equations, which is exactly what we need to solve.

2. Solving the System with Cramer's Rule

To solve for $t,u,$ and $v$, the algorithm uses Cramer's Rule, which expresses the solution for each variable as a ratio of determinants. A key insight for performance is that the determinant of a 3x3 matrix whose columns are vectors can be calculated using the scalar triple product.

For a matrix with column vectors $\mathbf{a},\mathbf{b},\mathbf{c}$, the determinant is:
$\det (\mathbf{a},\mathbf{b},\mathbf{c})=(\mathbf{a}\times \mathbf{b})\cdot \mathbf{c}$

The video below provides an excellent review of the mathematical machinery, including Cramer's rule and the scalar triple product, before applying them to our problem.

With that review, let's see how these tools are applied to solve our specific system of equations.

The final result gives us explicit formulas for $t,u,$ and $v$ using only vector operations (cross products and dot products) on known quantities: the ray and the triangle vertices.

3. From Math to Code: Implementation

Now we can translate the mathematical solution into a C++ function. The implementation is essentially a series of calculations and checks.

Here is the logic in pseudocode:

1. Compute triangle edge vectors $E_1$ and $E_2$.
2. Compute the vector $P$ as $D\times E_2$. The determinant is then $(P\cdot E_1)$.
3. If the determinant is close to zero, the ray is parallel to the triangle plane. No intersection.
4. Compute $u$. If $u<0$ or $u>1$, the hit point is outside the triangle. No intersection.
5. Compute $v$. If $v<0$ or $u+v>1$, the hit point is outside the triangle. No intersection.
6. If all tests pass, an intersection exists! Compute $t$.
7. Finally, check if $t$ falls within the ray's valid distance range (e.g., t > t_min and t < t_max). If it does, we have a valid hit.

Let's watch a detailed walkthrough of how this logic translates into code.

Here's a C++ implementation skeleton based on the Scratchapixel and Scotty3D resources. This is what you will be integrating into your triangle::hit method, which will override the virtual hit method in your hittable abstract base class.

// Within your triangle class, which inherits from hittable
bool triangle::hit(const ray& r, double t_min, double t_max, hit_record& rec) const {
    // Vertices of the triangle are p0, p1, p2
    vec3 e1 = p1 - p0;
    vec3 e2 = p2 - p0;

    vec3 pvec = cross(r.direction(), e2);
    double det = dot(e1, pvec);

    // If the determinant is near zero, the ray lies in the plane of the triangle.
    // We can use an epsilon value for this check.
    const double epsilon = 1e-8;
    if (fabs(det) < epsilon)
        return false;

    double inv_det = 1.0 / det;

    vec3 tvec = r.origin() - p0;
    double u = dot(tvec, pvec) * inv_det;

    if (u < 0.0 || u > 1.0)
        return false;

    vec3 qvec = cross(tvec, e1);
    double v = dot(r.direction(), qvec) * inv_det;

    if (v < 0.0 || u + v > 1.0)
        return false;

    // We have a hit! Calculate t and check if it's within the ray's valid range.
    double t = dot(e2, qvec) * inv_det;

    if (t > t_min && t < t_max) {
        // Yes, it's a valid hit. Populate the hit_record.
        rec.t = t;
        rec.p = r.at(t);
        // We'll compute the normal in the next lesson. For now, a placeholder is fine.
        vec3 outward_normal = unit_vector(cross(e1, e2));
        rec.set_face_normal(r, outward_normal); 
        // We will also use u,v later for texture coordinates and smooth shading.
        return true;
    }

    // The intersection is outside the valid t-range.
    return false;
}

Notice the check if (t > t_min && t < t_max). This is crucial. In your hittable_list, you need to find the closest intersection. As you test objects, you will update t_max to be the t of the closest hit found so far. This ensures that any subsequent hits further away are ignored, which is a key optimization. This practice is highlighted in the Scotty3D resource (LINK).

Conclusion

Congratulations! You have just dissected one of the most fundamental algorithms in ray tracing. You are now equipped to render far more than just spheres.

Key Takeaways:

• The Möller-Trumbore algorithm elegantly solves for a ray-triangle intersection by finding where the ray's parametric equation and the triangle's barycentric coordinate equation are equal.
• It formulates the problem as a 3x3 system of linear equations, which is efficiently solved using Cramer's Rule and the scalar triple product.
• The implementation is a sequence of fast vector operations and early-out checks (det, u, v) that make the algorithm highly performant for the common case where rays miss objects.
• The output includes not just the intersection distance t, but also the barycentric coordinates u and v, which will be invaluable.

Next Steps

We've successfully determined if and where a ray hits a triangle. But what about the appearance? Right now, we can only assign a flat normal to the whole triangle, which would make a mesh look faceted.

In the next lesson, we will leverage the u and v coordinates we just calculated to compute barycentric coordinates of the intersection point. This will allow us to interpolate data—specifically vertex normals—across the triangle's surface, enabling the smooth shading you see on virtually all modern 3D models.