Construction of Efficient Kd-Trees for Static Scenes Using Voxel-visibility Heuristic

Byeongjun Choi, Byungjoon Chang, Insung Ihm
Department of Computer Science and Engineering, Sogang University, 35 Baekbeom-ro, Mapo-gu, Seoul 121-742, Korea
Computers & Graphics, Vol. 36, Issue 1, pp. 38-48, 2012


   title={Construction of Efficient Kd-Trees for Static Scenes Using Voxel-visibility Heuristic},

   author={Choi, B. and Chang, B. and Ihm, I.},

   journal={Computers & Graphics},





   publisher={Elsevier Ltd}


Download Download (PDF)   View View   Source Source   



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 re ect 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 re ection/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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: