Howto Raytracer: Ray / Triangle Intersection Theory

Categories:

Besides sphere and plane intersections another important one is the ray / triangle intersection, because most 3D models consist of triangles or can be converted to such a representation. So let’s learn how to do it to be able to model some complex models.

A triangle $$T$$ can be represented by three points $$v0, v1, v2$$ that define a plane. So first, we check if the ray intersects this plane. I already did a tutorial on ray / plane intersection so I won’t cover it again. If there is such an intersection it means we just have to check if this hitpoint $$P$$ lies within the bounds of the triangle. For this we calculate a different representation of $$P$$ with respect to the triangle: As the point is on the plane, it can be written as $$P = v0 + su + tv$$ for some $$s,t$$ where $$u$$ and $$v$$ are the “edge vectors” incident to $$v0$$.

Once we have found the values for $$s,t$$ the following has to be true for the point to be inside the triangle:

  1. $$0 \leq s,t \leq 1$$
  2. $$s + t \leq 1$$

These constraints on $$s,t$$ essentially define the triangle structure and all in all, the set of points of the triangle is $$ \begin{aligned} T = {P \mid & P \in T_{\text{Plane}} \land P = v0 + s(v1-v0) + t(v2-v0) \land \\ & 0 \leq s,t, \leq 1 \land s + t \leq 1} \end{aligned}$$

Assume we have checked that $$P$$ lies inside the triangle’s plane, then we just have to solve $$P = v0 + su + tv$$ for $$s,t$$, or equivalent $$w = P - v0 = su + tv$$.

Solving the equation

Unfortunately, $$w = su + tv$$ has two unknowns ($$s,t$$) in only one equation, so we have to use a little trick to get two equations out of this. The normal $$n$$ of the triangle can be computed by the cross product of $$u$$ and $$v$$. Let’s now consider the vector $$u^\perp$$ that is both perpendicular to $$u$$ and to $$n$$. This vector lies in the plane and can again be computed by using the cross product, i.e., $$u^\perp = n \times u$$. We can now (dot product-) multiply our equation $$w = su + tv$$ on both sides by $$u^\perp$$:

$$ \begin{aligned} w = su + tv \\ w \cdot u^\perp = s u \cdot u^\perp + t v \cdot u^\perp \\ w \cdot u^\perp = t v \cdot u^\perp \end{aligned} $$

The term $$u \cdot u^\perp$$ is $$0$$, because by definition of $$u^\perp$$ it is perpendicular to $$u$$, and with it the $$s$$ vanishes and we have reduced the equation to only one unknown, so we solve it for $$t$$ by:

$$ \begin{aligned} t = \frac{w \cdot u^\perp}{v \cdot u^\perp} \end{aligned} $$

We do a similar thing to compute $$s$$ by multiplying with $$v^\perp = n \times v$$: $$ \begin{aligned} w = su + tv \\ w \cdot v^\perp = s u \cdot v^\perp + t v \cdot v^\perp \\ w \cdot v^\perp = s u \cdot v^\perp \\ s = \frac{w \cdot v^\perp}{u \cdot v^\perp} \end{aligned} $$

Some optimizations

We can reduce the number of computations by seeing that the denominator used to compute $$s$$ is just the negative of the denominator for $$t$$:$$u\cdot v^\perp = u \cdot (n \times v) = v \cdot (u \times n) = v \cdot (-n \times u) = - v \cdot (n \times u) = - v \cdot u^\perp$$ This gives us the following equations:

$$\begin{aligned} s = \frac{w \cdot v^\perp}{u \cdot v^\perp} && v^\perp = n \times v && w = P - v0 \\ t = \frac{w \cdot u^\perp}{-u \cdot v^\perp} && u^\perp = n \times u & \end{aligned}$$

In the case of raytracing where we shoot a ray through the scene for every pixel, we can save a lot of computation time by caching some of these values. In fact, the only term that depends on the ray is $$w$$, whereas $$u^\perp, v^\perp, u \cdot v^\perp$$ only have to be computed once for each triangle.

Here’s some C# code that implements the ray/triangle intersection test:

using UnityEngine;

public class RTTriangle : RTObject
{
    protected Vector3 v0, v1, v2;
    protected Vector3 normal;
    protected Vector3 u, v;
    protected Vector3 uPerp, vPerp;
    protected float denominatorST;

    public RTTriangle(Vector3 v0, Vector3 v1, Vector3 v2, bool clockwise = false)
    {
        Init(v0, v1, v2, clockwise);
    }
    
    protected void Init(Vector3 v0, Vector3 v1, Vector3 v2, bool clockwise = false)
    {
        this.v0 = v0;
        this.v1 = v1;
        this.v2 = v2;
        u = v1 - v0;
        v = v2 - v0;

        // Unity uses clockwise winding order to determine front-facing triangles
        // Unity uses a left-handed coordinate system
        // the normal will face the front
        // if the direction of the normal is not important to you
        // just remove the clockwise branching
        normal = (clockwise ? 1 : -1) * Vector3.Cross(u, v).normalized;

        uPerp = Vector3.Cross(normal, u);
        vPerp = Vector3.Cross(normal, v);
        denominatorST = Vector3.Dot(u, vPerp);
        if (Mathf.Abs(denominatorST) < Mathf.Epsilon)
        {
            Debug.LogError("Triangle is broken");
            return;
        }
    }

    public override RayTracer.HitInfo Intersect(Ray ray)
    {
        RayTracer.HitInfo info = new RayTracer.HitInfo();

        Vector3 d = ray.direction;
        float denominator = Vector3.Dot(d, normal);

        if (Mathf.Abs(denominator) < Mathf.Epsilon) return info;      // direction and plane parallel, no intersection

        float tHit = Vector3.Dot(v0 - ray.origin, normal) / denominator;
        if (tHit < 0) return info;    // plane behind ray's origin

        // we have a hit point with the triangle's plane
        Vector3 w = ray.GetPoint(tHit) - v0;

        float s = Vector3.Dot(w, vPerp) / denominatorST;
        if (s < 0 || s > 1) return info;    // won't be inside triangle

        float t = Vector3.Dot(w, uPerp) / -denominatorST;
        if (t >= 0 && (s + t) <= 1)
        {
            info.time = tHit;
            info.hitPoint = ray.GetPoint(tHit);
            info.normal = normal;
        }

        return info;
    }
}

You can now import a 3D model consisting of triangles in .obj format, parse the triangles and do your ray test. This is what the result might look like, a lot better than just planes and spheres.