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 TT can be represented by three points v0,v1,v2v0, 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 PP lies within the bounds of the triangle. For this we calculate a different representation of PP with respect to the triangle: As the point is on the plane, it can be written as P=v0+su+tvP = v0 + su + tv for some s,ts,t where uu and vv are the "edge vectors" incident to v0v0.

triangle representation

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

  1. 0s,t10 \leq s,t \leq 1
  2. s+t1s + t \leq 1

These constraints on s,ts,t essentially define the triangle structure and all in all, the set of points of the triangle is T={PPTPlaneP=v0+s(v1v0)+t(v2v0)0s,t,1s+t1} \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 PP lies inside the triangle's plane, then we just have to solve P=v0+su+tvP = v0 + su + tv for s,ts,t, or equivalent w=Pv0=su+tvw = P - v0 = su + tv.

#Solving the equation

Unfortunately, w=su+tvw = su + tv has two unknowns (s,ts,t) in only one equation, so we have to use a little trick to get two equations out of this. The [normal](https://en.wikipedia.org/wiki/Normal_28geometry28geometry29) nn of the triangle can be computed by the cross product of uu and vv. Let's now consider the vector uu^\perp that is both perpendicular to uu and to nn. This vector lies in the plane and can again be computed by using the cross product, i.e., u=n×uu^\perp = n \times u. We can now (dot product-) multiply our equation w=su+tvw = su + tv on both sides by uu^\perp:

w=su+tvwu=suu+tvuwu=tvu \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 uuu \cdot u^\perp is 00, because by definition of uu^\perp it is perpendicular to uu, and with it the ss vanishes and we have reduced the equation to only one unknown, so we solve it for tt by:

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

We do a similar thing to compute ss by multiplying with v=n×vv^\perp = n \times v: w=su+tvwv=suv+tvvwv=suvs=wvuv \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 ss is just the negative of the denominator for tt:uv=u(n×v)=v(u×n)=v(n×u)=v(n×u)=vuu\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:

s=wvuvv=n×vw=Pv0t=wuuvu=n×u\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 ww, whereas u,v,uvu^\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. raytracer triangles 3d model