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

• Published in: Computers & graphics 2012-02, Vol.36 (1), p.38-48
• Main Authors: Choi, Byeongjun, Chang, Byungjoon, Ihm, Insung
• Format: Article
• Language: English
• Subjects: Cost metric; Kd-tree construction; Ray tracing; Surface area heuristic; Voxel visibility
• ISSN: 0097-8493; 1873-7684
• DOI: 10.1016/j.cag.2011.11.007

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. [Display omitted] ► 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.