In theory, solving ray and triangle intersections is not all that difficult. What makes the ray-triangle intersection complex is the multitude of different cases that we must account for. To write a robust routine that handles all these cases quickly and efficiently can be tricky. For this reason, the topic has been the subject of a lot of research and debate in the CG community. It is also generally one of the most important and critical routines in a ray-tracer. In this lesson we will stick to the basic techniques; foundations upon which more advanced methods are built.
A geometric primitive is a representation of a 3D object in a rendering program. For example, if we want to represent a sphere, we can define it by the position of its center, and its radius as explained in the previous lesson. Complex objects, similarly, can be modeled by more complex geometric primitives like polygons, NURBS or Bezier patches, subdivision surfaces etc. Each one of them is useful for representing certain types of 3D objects. For example, NURBS are good for objects with smooth surfaces. Polygons, on the other hand, are useful for geometric shapes like buildings. Triangles are not really a geometry type of their own. Rather, they are a subset of the polygon primitive type. We will see in a later lesson that a polygonal object, though, is easily convertible into triangles.
Why Do We Like Triangles so Much?
Computing the intersection of a ray with a primitive such as a sphere, is not difficult. However, since it is difficult to model most 3D objects with spheres alone, it is necessary to use some other types of primitive to represent more complex objects (objects of arbitrary shape). Nothing stops us from using polygonal meshes or NURBS surfaces with our renderer, but computing the intersection of a ray with these primitive can be difficult and slow. On the other hand, computing the intersection of a ray with a triangle is a fairly simple operation which can also be well optimized. It may not be as fast as computing an intersection between a ray and a sphere, but at least it will be better than rendering the intersection of ray with a NURBS surface. This is a compromise we are willing to make.
Instead of working 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 every triangle in this mesh. By doing so, we reduce the ray-object intersection to a single, advantageously fast, routine. Converting a Bezier patch into a triangle mesh is a much simpler task than computing multiple ray-Bezier patch intersections. In our code, the consequence of this strategy is that every time we implement a new geometric primitive type, we will have to write a routine that will convert that type into a triangle mesh as opposed to write a routine to compute the intersection of a ray with this primitive. All the objects of a scene will be therefore internally represented as triangle meshes. Most ray-tracers (at least production ones) use this approach.
What Is a Triangle?
A triangle is defined by three vertices (or points) whose positions are defined in three-dimensional space (figure 1). One point can only represent a location in space. With two points, we can define a line. With three points, we can define a surface (and a plane). By construction, a triangle is coplanar; the three vertices define a plane and all three vertices lie in the same plane. This is not necessarily the case for polygons with more than three vertices; four points define a quad even when these four points are not in the same plane (which is entirely possible). However, we can convert the quad into two coplanar triangles as depicted in figure 2. This technique can be applied to polygon which an arbitrary number of vertices: this process is call triangulation (we will be learn about rendering polygon meshes in the next lesson).
How Do We Compute the Intersection of a Ray With a Triangle?
Over the few decades, several algorithms have been developed to compute the intersection between a ray and a triangle (research on this topic is still going and papers keep being published on a regular basis). In this lesson, we will teach two of these techniques. The first technique requires just basic logic and elementary linear algebra to implement. The second technique, considered as one of the fastest ray-triangle intersection algorithm, was proposed by Möller-Trumbore in 1997 in a paper titled, "Fast, minimum storage ray-triangle intersection". Although it requires a more advanced understanding of linear algebra, we will do our best to work through it.
We can decompose the ray-triangle intersection test into a two steps problem:
- Does the ray intersect the plane defined by the triangle?
- If so, does the intersection point lie inside the triangle?
Let's see how we can answer these two questions.