Construction of efficient kd-trees for static scenes using voxel-visibility heuristic

In the ray-tracing community, the surface-area heuristic (SAH) is used as a de facto standard strategy for building high-quality kd-trees. Although widely accepted as the best kd-tree construction method, it is based only on the surface-area measure, which often fails to reflect effectively the rendering characteristics of a given scene. This paper presents new cost metrics that help produce improved kd-trees for static scenes by considering the visibility of geometric objects, which can affect significantly the actual distribution of rays during ray tracing. Instead of the SAH, we apply a different heuristic based on the new concept of voxel visibility, which allows more sophisticated estimation of the chance of a voxel being hit by rays. The first cost metric we present aims at constructing a single kd-tree that is used to trace both primary and secondary rays, whereas the second one is more relevant to secondary rays, involving reflection/refraction or shadowing, whose distribution properties differ from those for primary rays. Our experiments, using both CPU-based and GPU-based computation with several test scenes, demonstrate that the presented cost metrics can reduce markedly the cost of ray-traversal computation and increase significantly the overall frame rate for ray tracing.

Graphical abstractFigure optionsDownload full-size imageDownload high-quality image (274 K)Download as PowerPoint slideHighlights► New cost metrics for building improved kd-trees for ray-tracing static scenes. ► ‘Voxel visibility’ for a better estimation of the chance of voxel being hit by rays. ► Construction of acceleration hierarchy based on the voxel visibility. ► Enhanced ray-tracing performance over the SAH based kd-trees.