Ray-Tracing: Rendering a Triangle

Ray-Triangle Intersection: Geometric Solution

Reading time: 11 mins.

Ray-triangle Intersection: Geometric Solution

**Figure 1:** The intersection of a ray and a triangle. The triangle lies in a plane. The value $t$ is the distance from the ray origin to the intersection point.

In the previous paragraphs, we learned how to calculate a plane's normal. Next, we need to determine the position of point $P$ (in some illustrations, we also used "Phit"), the point where the ray intersects the plane.

Step 1: Finding P

We know that $P$ is somewhere on the ray defined by its origin $O$ and its direction $R$. We used $D$ in the previous lesson, but we will use $R$ in this lesson to avoid confusion with the term $D$ from the plane equation. The parametric equation of the ray is (equation 1):

$$P = O + tR$$

Where $t$ is the distance from the ray origin $O$ to $P$. To find $P$, we must find $t$ (refer to Figure 1). What else do we know? We have already computed the plane's normal and the plane equation (2), which is (refer to the chapter on ray-plane intersection from the previous lesson for more details):

$$ \begin{array}{l} Ax + By + Cz + D = 0 \\ D = -(Ax_0 + By_0 + Cz_0) \end{array} $$

Where A, B, C are the components (or coordinates) of the normal to the plane ($\mathbf{N}_{\text{plane}} = (A, B, C)$), and $D$ is the distance from the origin (0, 0, 0) to the plane. The variables x, y, and z represent the coordinates of any point on this plane.

Knowing the plane's normal and that the triangle's vertices (V0, V1, V2) lie in the plane, it is possible to compute $D$. Let's choose V0 for this purpose:

float D = -dotProduct(N, v0);
// Or, if you want to compute the dot product directly:
float D = -(N.x * v0.x + N.y * v0.y + N.z * v0.z);

We also know that point $P$, the intersection point of the ray and the plane, lies within the plane. Consequently, we can substitute $\mathbf{P}$ (equation 2) for $O + tR$ in equation 1 and solve for $t$ (equation 3):

$$ \begin{array}{l} A(O_x + tR_x) + B(O_y + tR_y) + C(O_z + tR_z) + D = 0 \\ t = -\frac{(A \cdot O_x + B \cdot O_y + C \cdot O_z + D)}{(A \cdot R_x + B \cdot R_y + C \cdot R_z)} \\ t = -\frac{\mathbf{N} \cdot \mathbf{O} + D}{\mathbf{N} \cdot \mathbf{R}} \end{array} $$

float t = -(dot(N, orig) + D) / dot(N, dir);

With $t$ computed, we can now calculate the position of $P$:

Vec3f Phit = orig + t * dir;

Before checking if the point is inside the triangle, there are two very important cases that we need to consider.

The Ray And The Triangle Are Parallel

If the ray and the plane are parallel, they will not intersect (refer to Figure 2). For robustness, we must handle this case should it occur. This situation is straightforward to identify: if the triangle and the ray are parallel, then the triangle's normal and the ray's direction are perpendicular.

**Figure 2:** Several situations can occur. The ray can intersect the triangle, miss it, or be parallel to it. No intersection is possible when the ray is parallel to the triangle. This situation occurs when the normal of the triangle and the ray direction are perpendicular (and the dot product of these two vectors is 0).

We know that the dot product of two perpendicular vectors is 0. Referring to the denominator of equation 3 (the term below the line), we compute the dot product between the triangle's normal $N$ and the ray direction $R$. Our code must be robust to prevent a potential division by 0. When this term equals 0, the ray is parallel to the triangle, indicating no intersection. Hence, before calculating $t$, we first evaluate $N \cdot R$; if the result is 0, the function will return false, indicating no intersection.

The Triangle is "Behind" the Ray

**Figure 3:** If a triangle is "behind" the ray, it shouldn't be considered for an intersection. Whenever the value of $t$ computed with equation 3 is less than 0, the intersection point lies behind the ray's origin and should be discarded. In that case, there is no intersection.

Until now, we have assumed the triangle is always in front of the ray. However, what if the triangle is located behind the ray while the ray maintains its direction? Typically, the triangle should not be visible in such scenarios. Equation 3 can yield a valid result even when the triangle is "behind" the ray; in these cases, $t$ is negative, placing the intersection point in the opposite direction of the ray's travel. Failing to account for this "error" could mistakenly include the triangle in the final image, which is undesirable. Therefore, we must verify the sign of $t$ before confirming the intersection as valid. If $t$ is less than 0, the triangle is behind the ray's origin relative to the ray's direction and is not visible, warranting a return value of false for no intersection. Conversely, if $t$ is greater than 0, the triangle is "visible" to the ray, and we may proceed to the next step.

Step 2: Is P Inside or Outside the Triangle?

Now that we have identified the point $P$, which is where the ray intersects with the plane, we still need to determine whether $P$ is inside the triangle (indicating the ray intersects the triangle) or outside it (indicating the ray misses the triangle). Figure 2 illustrates these possibilities.

**Figure 4:** C and C' point in opposite directions.

**Figure 5:** If P is on the left side of A, the dot product N.C is positive. If P is on the right side (P'), N.C' is negative. The vector C is computed from v0 and P (C=P-v0).

**Figure 6:** To determine if P is inside the triangle, we can test if the dot product of the vector along the edge and the vector defined by the first vertex of the tested edge and P is positive (meaning P is on the left side of the edge). If P is on the left of all three edges, then P is inside the triangle.

The solution to this problem is straightforward and called the inside-outside test. We have already encountered this term in the lesson on rasterization, where the test was applied to 2D triangles. Here, we adapt it for 3D triangles. Imagine having a vector A aligned with the x-axis (Figure 4), and suppose this vector is aligned with one edge of our triangle (the edge defined by the two vertices v0-v1). The second edge, B, is defined by vertices v0 and v2 of the triangle, as shown in Figure 4. Calculating the cross product of these two vectors yields a result that points in the same direction as the z-axis and the triangle's normal.

$$ \begin{array}{l} A=(1, 0, 0)\\ B=(1, 1, 0)\\ C_x = A_y \cdot B_z - A_z \cdot B_y = 0\\ C_y = A_z \cdot B_x - A_x \cdot B_z = 0\\ C_z = A_x \cdot B_y - A_y \cdot B_x = 1 \cdot 1 - 0 \cdot 1 = 1\\ C = (0, 0, 1) \end{array} $$

If the vertex v2 were mirrored across the x-axis, having coordinates (1, -1, 0), the cross-product AxB' would result in C'=(0, 0, -1).

$$ \begin{array}{l} A=(1, 0, 0)\\ B'=(1, -1, 0)\\ C_x = A_y \cdot B'_z - A_z \cdot B'_y = 0\\ C_y = A_z \cdot B'_x - A_x \cdot B'_z = 0\\ C_z = A_x \cdot B'_y - A_y \cdot B'_x = 1 \cdot -1 - 0 = -1\\ C' = (0, 0, -1) \end{array} $$

Because C and N point in the same direction, their dot product is positive. Conversely, because C' and N point in opposite directions, their dot product is negative. This test reveals that if a point $P$, which lies in the plane of the triangle (such as vertex V2 or the intersection point), is on the left side of vector A, then the dot product between the triangle's normal and vector C is positive (C is the result of the cross-product between A and B, where A = v1 - v0 and B = P - v0). However, if $P$ is on the right side of A (as with V2'), this dot product is negative. As shown in Figure 5, point $P$ is inside the triangle when it lies on the left side of A. To apply the technique described to the ray-triangle intersection problem, we perform the left/right test for each triangle edge. If point $P$ is on the left side of vector C for all three edges of the triangle (where C is defined as v1-v0, v2-v1, and v0-v2, respectively), then $P$ is assuredly inside the triangle. If the test fails for any edge, $P$ lies outside the triangle's boundaries. Figure 6 illustrates this process.

Here is an example of the inside-outside test in pseudocode:

Vec3f edge0 = v1 - v0;
Vec3f edge1 = v2 - v

1;
Vec3f edge2 = v0 - v2;
Vec3f C0 = P - v0;
Vec3f C1 = P - v1;
Vec3f C2 = P - v2;
if (dotProduct(N, crossProduct(edge0, C0)) > 0 && 
    dotProduct(N, crossProduct(edge1, C1)) > 0 &&
    dotProduct(N, crossProduct(edge2, C2)) > 0) return true; // P is inside the triangle

Note the similarities between this method and the method used in the rasterization lesson to determine if a pixel overlaps a (2D) triangle.

Let's write the complete ray-triangle intersection test routine code. First, we'll compute the triangle's normal, then test if the ray and the triangle are parallel. If they are parallel, the intersection test fails. If not, we compute $t$, from which we can determine the intersection point $P$. If the inside-out test is successful (testing if $P$ is on the left side of each of the triangle's edges), then the ray intersects the triangle, and $P$ is within the triangle's boundaries, making the test successful.

bool rayTriangleIntersect(
    const Vec3f &orig, const Vec3f &dir,
    const Vec3f &v0, const Vec3f &v1, const Vec3f &v2,
    float &t)
{
    // Compute the plane's normal
    Vec3f v0v1 = v1 - v0;
    Vec3f v0v2 = v2 - v0;
    // No need to normalize
    Vec3f N = v0v1.crossProduct(v0v2); // N
    float area2 = N.length();
 
    // Step 1: Finding P
    
    // Check if the ray and plane are parallel
    float NdotRayDirection = N.dotProduct(dir);
    if (fabs(NdotRayDirection) < kEpsilon) // Almost 0
        return false; // They are parallel, so they don't intersect!

    // Compute d parameter using equation 2
    float d = -N.dotProduct(v0);
    
    // Compute t (equation 3)
    t = -(N.dotProduct(orig) + d) / NdotRayDirection;
    
    // Check if the triangle is behind the ray
    if (t < 0) return false; // The triangle is behind
 
    // Compute the intersection point using equation 1
    Vec3f P = orig + t * dir;
 
    // Step 2: Inside-Outside Test
    Vec3f C; // Vector perpendicular to triangle's plane
 
    // Edge 0
    Vec3f edge0 = v1 - v0; 
    Vec3f vp0 = P - v0;
    C = edge0.crossProduct(vp0);
    if (N.dotProduct(C) < 0) return false; // P is on the right side
 
    // Edge 1
    Vec3f edge1 = v2 - v1; 
    Vec3f vp1 = P - v1;
    C = edge1.crossProduct(vp1);
    if (N.dotProduct(C) < 0) return false; // P is on the right side
 
    // Edge 2
    Vec3f edge2 = v0 - v2; 
    Vec3f vp2 = P - v2;
    C = edge2.crossProduct(vp2);
    if (N.dotProduct(C) < 0) return false; // P is on the right side

    return true; // This ray hits the triangle
}

This "inside-outside" technique works for any convex polygon. Repeat the method used for triangles for each edge of the polygon. Compute the cross-product of the vector defined by the two edges' vertices and the vector defined by the first edge's vertex and the point. Then, compute the dot product of the resulting vector and the polygon's normal. The sign of the resulting dot product determines if the point is on the right or left side of that edge. Iterate through each edge of the polygon. There's no need to test the other edges if one fails the test.

Note, this technique can be optimized if the triangle's normal and the value $D$ from the plane equation are precomputed and stored for each triangle in the scene.

What's next?

In this chapter, we have introduced a technique to compute the ray-triangle intersection test using simple geometry. However, there's more to the ray-triangle intersection test that we haven't covered yet, such as determining whether the ray hits the triangle from the front or the back. We can also compute what are known as the intersection point's barycentric coordinates. These coordinates are essential for tasks such as applying a texture to the triangle.