Accelerating ray tracing using constrained tetrahedralizations

Tracing a ray through a scene and finding the closest intersection with the scene geometry is a fundamental operation in computer graphics. During the last two decades, significant efforts have been made to accelerate this operation, with interactive ray tracing as one of the major driving forces. At the heart of a fast method for intersecting a scene with a ray lies the acceleration structure. Many different acceleration structures exist, but research has focused almost exclusively on a few well-tried and well-established techniques: regular and hierarchical grids, bounding volume hierarchies and kd-trees. Spectacular advances have been made, which have contributed significantly to making interactive ray tracing a possibility. However, despite the success of these acceleration structures, several problems remain open. Handling deforming and dynamic geometry still poses significant challenges, and the local vs. global complexity of acceleration structures is still not entirely understood. One therefore wonders whether other acceleration structures, that leave the beaten path of efficient grids, bounding volume hierarchies and kd-trees, can provide viable alternatives.

Next to computer graphics, the ray shooting problem is also studied in computational geometry. Ray shooting queries against a large collection of polyhedra are answered by tracing the ray through a simplicial complex such as a constrained tetrahedralization. This is a well-known technique, see e.g. the chapter Ray shooting and lines in space by Pellegrini in Handbook of Discrete and Computational Geometry. However, relevant work in computational geometry is usually theoretical, and practical implementations and experimental results are typically not available.

In this work we explore the idea of accelerating the operation of intersecting a scene with a ray using constrained tetrahedralizations. This is illustrated in figure 1. A constrained tetrahedralization of a scene is a tetrahedralization that respects the faces of the scene geometry. The closest intersection of a ray with a scene is found by traversing this tetrahedralization along the ray, one tetrahedron at a time, until a constrained face is encountered. We show that constrained tetrahedralizations are a viable alternative to state-of-the-art acceleration structures, such as kd-trees, and that constrained tetrahedralizations have a number of interesting and unique properties that set them apart from traditional acceleration structures. Constrained tetrahedralizations are not hierarchical yet adaptive; the complexity of traversing them is a function of local geometric complexity rather than global geometric complexity; constrained tetrahedralizations support deforming geometry without any effort (see figure 2); and they have the potential to unify several data structures currently used in global illumination.

Although constrained tetrahedralizations are not a silver bullet, and although they are in general not yet faster than the most optimized kd-trees, constrained tetrahedralizations offer several new perspectives on acceleration structures for ray tracing and deserve attention.