The other Pathtracer 2: The triangle

Following on the idea of my last post, today we're building on a very important matter: Intersecting triangles. Or more specifically, intersecting one triangle. This is not covered in many ray tracing tutorials, and that's a shame. Adding triangle intersection is the corner stone for a lot of interesting functionality (like loading full meshes), and it's actually a very simple thing to do.
All the relevant code is in this commit.

The Algorithm

There are several possible algorithms for intersecting triangles, with varying degrees of complexity and performance. For example see this wikipedia article or, if you have access to gdcvault, this talk by Earl Hammon (which has a ton of valuable material).
However. since my goal here is to get a working implementation quickly and easily, I will explain the algorithm that I find most intuitive. In later posts, we will be revisiting it for performance improvements, and even then, it will be useful to have a solid base line to benchmark against.

So the idea is to do intersection in two parts: First, we find whether our ray segment intersects the triangle plane, and if it does, then we see if the intersection point lies inside the triangle.

Part one is basic geometry, and can be decomposed in two parts as well: Find the plane defined by the three vertices of the triangle, then intersect the plane with our ray.

auto edge0 = v[1]-v[0];
auto edge1 = v[2]-v[1];
auto normal = normalize(cross(edge0,edge1));
auto planeOffset = dot(v[0],normal);

In regular production code, we should handle the case of a degenerate triangle, where cross(edge0,edge1) can't be normalized, but for now we will behave ourselves and just not make weird triangles. We can already see a possible optimization path: since none of the above depends on the ray, we could cache the plane definition, instead of recomputing it for every ray. Not now, anyway.

Now, when a line segment (our ray between tMin and tMax) intersects a plane, it means that the two end points of it are on different sides of the plane.

And we can detect that with little more than a pair of dot products

auto p0 = r.at(tMin);
auto p1 = r.at(tMax);
 
auto offset0 = dot(p0, normal);
auto offset1 = dot(p1, normal);
 
if((offset0-planeOffset)*(offset1-planeOffset) <= 0.f)

knowing we are in the plane, we use those same offsets to find the intersection point p

float t = tMin + (tMax-tMin)*(planeOffset-offset0)/(offset1-offset0);
auto p = r.at(t);

To find out if the point is actually inside the triangle, we're taking the vector that goes from each vertex to the intersection point, and taking the cross product with the edge that comes out of that same vertex.

If and only if the intersection point is inside the triangle, all "vertex normals" will point in the same direction. If we're consistent with our winding order, we can even use this to detect front-facing and back facing triangles by dot product with the plane normal we computed earlier, but we won't do that now.

auto c0 = cross(edge0,p-v[0]);
auto c1 = cross(edge1,p-v[1]);
if(dot(c0,c1) >= 0.f)
{
 auto edge2 = v[0]-v[2];
 auto c2 = cross(edge2,p-v[2]);
 if(dot(c1,c2) >= 0.f)
 {
  collision.t = t;
  collision.p = p;
  collision.normal = normal;
  collision.material = m;
  return true;
 }
}

That's it. The whole code for triangle intersection is about 30 lines, and very straight forward. So fear the triangle no more! and add it to your ray tracers for extra fun.

What's next

Well, obviously after making one triangle, all you can do is ... many triangles!