Ray Tracing Devlog 4 - Ray Triangle Intersection

Ray tracing can calculate images off many different types of primitives - spheres, cyliners, cones, and more. To start out with, we will limit our intersection needs to a triangle. As the basis for our calculation we will be using the algorithm as laid out by Tomas Möller and Ben Trumbore in Fast, Minimum Storage Ray/Triangle Intersection.

I'll leave it as a reader exercise to check out the paper in full, but let's discuss some of the pertinent math.

A ray, denoted above as R, consists of an origin point and a direction vector - both containing x, y, and z coordinates. The t in the above equation refers to time, it represents how far along a ray you would find the intersected object. This is important to ray-tracing because 1) if an object is very far away (or behind you) it wouldn't appear in the image and 2) if a ray intersects multiple objects we can determine the smallest t which should belong to the object in front.

As the Möller/Trumbore paper notes, previous algorithms calculate a ray-triangle intersection by checking if the ray would hit the plane that the triangle sits on and then testing if the intersection point is within the triangle. The obvious downsides here are the additional storage space for the plane and that you have to make an additional calculation for the plane as opposed to just the triangle.

The authors new intersection takes advantage of barycentric coordinates. The gist here is that T(u, v) defines a point in the barycentric coordinate system. For that point to be within the triangle, u and v must be such that u >= 0, V >= 0, and u + v <= 1. You should also note in the following definition that V0, V1, and V2 represent the three vertices that define the triangle.

Broadly speaking, if we set the equation to the ray equal to the equation for the triangle, we can determine where they intersect. From there, we can solve for our three unknowns - u, v, and t.

\begin{bmatrix}
   -D, & V_1 - V_0, & V_2 - V_1
\end{bmatrix}\begin{bmatrix}
   t \\ u \\ v
\end{bmatrix} = O - V_0

We've now rearranged the terms as shown above. We can now solve for t, u, and v as a linear system of equations. And since we're solving for a linear system of equations, we can use Cramer's rule to get t, u, and v by themselves on one side of the equation.

\begin{bmatrix}
   t \\ u \\ v
\end{bmatrix} = \dfrac{1}{\begin{bmatrix}-D, & E_1, & E_2\end{bmatrix}}
\begin{bmatrix}
	\begin{bmatrix}T, & E_1, & E_2\end{bmatrix} \\
	\begin{bmatrix}-D, & T, & E_2\end{bmatrix} \\
	\begin{bmatrix}-D, & E_1, & T\end{bmatrix}
\end{bmatrix}

\begin{bmatrix}
   t \\ u \\ v
\end{bmatrix} = \dfrac{1}{(D \times E_2) \cdot E_1}
\begin{bmatrix}
	\begin{bmatrix}T, & E_1, & E_2\end{bmatrix} \\
	\begin{bmatrix}-D, & T, & E_2\end{bmatrix} \\
	\begin{bmatrix}-D, & E_1, & T\end{bmatrix}
\end{bmatrix}

As in the paper, we've used some shorthand such that: E1 = V1 - V0, E2 = V2 - V0 and T = O - V0. Now that we've covered why the ray triangle intersection algorithm should work, let's cover how we're going to implement it.

• In the previous day, we kept all of our code in one file. That was fine for our simple project, but won't be easy to follow as the project grows. My own coding practice stays pretty close to the idea of compression-oriented programming as laid out by Casey Muratori. I recommend reading the blog post, but the basic gist (aside from speaking out against OOP) is to only move code about - either to add abstractions or for general organization purposes - when you actually need it as opposed to in advance.

  Looking at our code now, we have two candidates for things to move around - struct definitons for our Vec objects and the draft parser for an OBJ file. Today, we're going to add code for ray triangle intersection. Looking ahead, I know that we're going to write intersection code for other primitives as well. So we'll move the ray-primitive intersection code to it's own submodule as well.

  Let's go ahead and move the Vec definitions to a place where the can be commonly shared across Rust modules. I'm fine with some repeated code, but repeating basic definitons like these will only leave room for unforced errors later.

  First, let's move the Vec definitions into a new file called common_structs/mod.rs. It's important to note here the difference between loading a child module and a sibling crate. We want common_structs to be shared across all aspects of our project, so we'll refer to it as a sibling crate. Check the code snippet below for an illustration of the difference.

  // file structure
  -- common_structs
      - mod.rs
  -- obj_parser
      - mod.rs
  - main.rs
  
  // from main.rs
  pub mod common_structs;
  use common_structs::{Vec2f, Vec3f};
  
  // from obj_parser/mod.rs
  use crate::common_structs::{Vec2f, Vec3f};
  

  The Rust convention used to require that there be a module declaration file called mod.rs. The latest standard as of this writing (Rust 2018) does not require this, but we will adhere to it where it makes sense since it helps communicate project flow. Also, note that I'm importing with {Vec2f, Vec3f} instead of an *. You absolutely can use the wildcard. I haven't deep dived in how Rust does it's linking, so there may be a difference there, but I chose the more explicit route as a purely stylistic route. Lastly, note that in order you to access common_structs from obj_parser, you must make it available from main.rs - i.e. with pub mod common_structs;.

  // rust code
  

• // cpp code