Ray-Tracing: Rendering a Triangle

Why Are Triangles Useful?

Reading time: 5 mins.

In theory, solving ray and triangle intersections is not overly difficult. However, the complexity of ray-triangle intersection arises from the multitude of different cases that must be accounted for. Writing a robust routine that handles all these cases quickly and efficiently can be challenging. For this reason, the topic has been extensively researched and debated within the CG community. It is also generally one of the most critical routines in a ray-tracer. In this lesson, we will focus on the basic techniques and foundations upon which more advanced methods are built.

Geometric Primitives

A geometric primitive represents a 3D object in a rendering program. For instance, to represent a sphere, we can define it by the position of its center and its radius, as explained in the previous lesson. Similarly, complex objects can be modeled by more complex geometric primitives such as polygons, NURBS or Bezier patches, subdivision surfaces, etc. Each one is useful for representing certain types of 3D objects. For example, NURBS are suitable for objects with smooth surfaces, while polygons are useful for geometric shapes like buildings. A triangle is not a distinct geometry type but rather a subset of the polygon primitive type. We will learn in a later lesson that a polygonal object is easily convertible into triangles.

Why Do We Like Triangles so Much?

**Figure 1:** geometry of a triangle. A triangle is defined by three vertices that define a plane. The normal is perpendicular to this plane. A ray (in yellow) intersects this triangle.

Calculating a ray's intersection with a primitive such as a sphere is straightforward. However, modeling most 3D objects solely with spheres is impractical, necessitating the use of other types of primitives to represent more complex objects (of arbitrary shape). While there is no restriction on using polygonal meshes or NURBS surfaces in our renderer, computing the intersection of a ray with these primitives can be difficult and time-consuming. Conversely, computing the intersection of a ray with a triangle is a relatively simple operation that can be well-optimized. It may not be as fast as ray-sphere intersections, but it is more efficient than rendering the intersection of a ray with a NURBS surface. This compromise is one we are willing to accept.

Instead of dealing with complex primitives such as NURBS or Bezier patches, we can convert every object into a triangle mesh and compute the intersection of a ray with each triangle in this mesh. This approach simplifies the ray-object intersection to a single, advantageously fast routine. Converting a Bezier patch into a triangle mesh is much simpler than computing multiple ray-Bezier patch intersections. Consequently, in our code, whenever we implement a new geometric primitive type, we will need to write a routine to convert that type into a triangle mesh rather than a routine to compute the intersection of a ray with the primitive. Thus, all objects in a scene will be internally represented as triangle meshes. Most ray tracers (especially those used in production) adopt this strategy.

What Is a Triangle?

**Figure 2:** A quad is not necessarily coplanar. The four vertices it comprises do not lie in the same plane (as depicted on the right). To solve this problem, quads can be triangulated, as we know that triangles are necessarily coplanar (on the left, the right quad is converted into two triangles).

A triangle is defined by three vertices (or points) positioned in three-dimensional space (Figure 1). A single point can represent a location in space. With two points, we can define a line. Three points allow us to define a surface—and specifically, a plane. By construction, a triangle is coplanar; its three vertices delineate a plane, with all three vertices residing within the same plane. This is not necessarily true for polygons with more than three vertices; a quad, defined by four points, may not be coplanar when these points do not reside in the same plane. However, quads can be converted into two coplanar triangles, as illustrated in Figure 2. This technique, known as triangulation, can be applied to polygons with any number of vertices and will be further explored in the context of rendering polygon meshes in the next lesson.

How Do We Compute the Intersection of a Ray With a Triangle?

Over the past few decades, numerous algorithms have been developed to compute the intersection between a ray and a triangle, with research on this topic continuing and new papers being published regularly. In this lesson, we will introduce two of these techniques. The first technique utilizes basic logic and elementary linear algebra for implementation. The second technique, considered one of the fastest for ray-triangle intersection, was proposed by Möller-Trumbore in 1997 in their paper "Fast, minimum storage ray-triangle intersection". While this method requires a more advanced understanding of linear algebra, we will strive to explain it comprehensively.

We can break down the ray-triangle intersection test into two steps:

Does the ray intersect the plane defined by the triangle?
If so, does the intersection point fall within the triangle?

Let's explore how we can address these two questions.