doi: 10.4304/jsw.9.3.596-604
A Fast Kd-tree Construction for Ray Tracing based on Efficient Ray Distribution
- 1 College of Computer Science, Sichuan University, Chengdu, China
- 2 College of Computer Science, Southwest Petroleum University, Chengdu, China
- 3 National Key Laboratory of Fundamental Science on Synthetic Vision, Chengdu, China
Abstract
Construction of effective acceleration structure isan essential and challenging problem in ray tracing. Thesurface area heuristic (SAH), regarded as the standard costfunction for construction, is based on the assumption thatrays are uniformly distributed. This simplification ignoringactual ray distribution results in a reduction both onconstruction and rendering performance. Unlike previousmethods, we exploit ray distribution during construction intwo steps. First, we propose an improved cost metric forconstructing an efficient kd-tree by exploiting the visibleprimitives to approximate the ray distribution. Then, wedevice a stream based partial construction to prune theinvisible primitives from building as early as possible, andimprove memory access coherence. We also introduce atermination criterion for two-levels hierarchicalconstruction to balance the construction time and memoryconsumption. Our experiments demonstrate that thealgorithm can produce a kd-tree more efficient than thestandard SAH, and a significant reduction on constructiontime and memory consumption.
Keywords
- ray tracing
- the SAH
- ray distribution
How to Cite
Xiao Liang, Hongyu Yang, Yinling Qian, and Yanci Zhang, "A Fast Kd-tree Construction for Ray Tracing based on Efficient Ray Distribution," Journal of Software, vol. 9, no. 3, pp. 596-604, 2014. https://doi.org/ 10.4304/jsw.9.3.596-604
Copyright & License
Copyright © 2014 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).