2014-05-30 Tavian Barnes Comments
In my last post, I talked about a beautiful method for computing ray/triangle intersections. In this post, I will extend it to computing intersections with triangle fans. Since meshes are often stored in a corner table, which is simply an array of triangle fans, this gives an efficient algorithm for ray tracing triangle meshes.
The aforementioned algorithm computes ray/triangle intersections with 1 division, 20 multiplications, and up to 18 additions. It also required storing an affine transformation matrix, which takes up 4/3 as much space as just storing the vertices. But if we have many triangles which all share a common vertex, we can exploit that structure to save time and memory.
Say our triangle fan is composed of triangles , , , etc. As before, we compute
Computing the change of basis from here to the next triangle is even easier. We want to find new coordinates such that
Two things are apparent: the first is that there is no further translation to perform because both coordinate systems have their origin at . The second is that only depends on . This means the matrix that takes us to the new basis has the special form
so we only need to store two of its columns, and transforming the ray into the new space can be done much faster than with a full matrix multiplication. The following transformation is applied to both the ray origin and direction:
In the end, for a triangle fan with vertices, the ray intersection can be computed with
The multiplications and additions are also easily vectorisable. The storage requirement is floating-point values, which is equivalent to storing all the vertices and precomputed normals.
Pretty cool, I wonder if this can be extended to triangle strips as well. That one might be a lot more challenging though.
$$ Also I wonder if these dollar signs will break your page with a MathJax injection. I imagine it's more intelligent than that.
Tavian Barnes 2014-05-30
Haha yeah the MathJax is all done with a WordPress plugin, I write [latex]m^at_h[/latex] and it prettifies it. I'm hoping it doesn't scan the page and replace $m^at_h$ with MathJax.
And you're right, it looks hard to do this well with triangle strips because they don't all share a common vertex. The above still works except the translation comes back which wastes time and space.