Ray Tracing: Rendering a Triangle
Keywords: ray-triangle intersection test, ray-tracing, barycentric coordinates, back-face culling, scalar triple product, determinant, Möller-Trumbore algorithm.Want to report bugs, errors or send feedback? Write at feedback@scratchapixel.com. You can also contact us on Twitter and Discord. We do this for free, please be kind. Thank you.

News (August, 31): We are working on Scratchapixel 3.0 at the moment (current version of 2). The idea is to make the project open source by storing the content of the website on GitHub as Markdown files. In practice, that means you and the rest of the community will be able to edit the content of the pages if you want to contribute (typos and bug fixes, rewording sentences). You will also be able to contribute by translating pages to different languages if you want to. Then when we publish the site we will translate the Markdown files to HTML. That means new design as well.

That's what we are busy with right now and why there won't be a lot of updates in the weeks to come. More news about SaP 3.0 soon.

We are looking for native Engxish (yes we know there's a typo here) speakers that will be willing to readproof a few lessons. If you are interested please get in touch on Discord, in the #scratchapixel3-0 channel. Also looking for at least one experienced full dev stack dev that would be willing to give us a hand with the next design.

Feel free to send us your requests, suggestions, etc. (on Discord) to help us improve the website.

And you can also donate). Donations go directly back into the development of the project. The more donation we get the more content you will get and the quicker we will be able to deliver it to you.

5 mns read.

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.

Geometric Primitives

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?

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

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?

Figure 2: a quad is not necessarily coplanar is the four vertices it is made of are not lying in the same plane (as depicted on the right). To solve this problem we can triangulate quads 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) 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:

Let's see how we can answer these two questions.