Efficient kd-tree construction for ray tracing using ray distribution sampling
详细信息 查看全文
- 作者：Xiao Liang ; Hongyu Yang ; Yanci Zhang ; Jun Yin ; Yue Cao
- 关键词：Kd ; tree ; Ray distribution ; On ; demand construction ; Ray tracing
- 刊名：Multimedia Tools and Applications
- 出版年：2016
- 出版时间：December 2016
- 年：2016
- 卷：75
- 期：23
- 页码：15881-15899
- 全文大小：1,502 KB
- 刊物类别：Computer Science
- 刊物主题：Multimedia Information Systems
Computer Communication Networks
Data Structures, Cryptology and Information Theory
Special Purpose and Application-Based Systems - 出版者：Springer Netherlands
- ISSN：1573-7721
- 卷排序：75
文摘
Although regarded as a standard heuristic for constructing a kd-tree, Surface Area Heuristic (SAH) suffers from degrading traversal performance as well as unnecessary acceleration structure construction due to its assumption of uniform ray distribution. In this paper, first, we propose a Grid based Ray Distribution Heuristic (GRDH) to construct a high quality kd-tree. The information of ray distribution is sampled and recorded in a sparse grid, which is also utilized to partition primitives efficiently. The heuristic only evaluating traversal cost on limited splitting candidates, is fast and easy to be implemented. Then, we introduce a novel ray tracing pipeline with two-pass construction and two-pass tracing routine to enable an on-demand construction algorithm. In the pipeline, after constructing a partially structured kd-tree, rays are classified by whether triggering transitions to construct unstructured leaf nodes, and being traced in different tracing passes. For on-demand construction, this raises the barrier of interleaving with traversal routine, as well as enables the algorithm to be flexible on multi-core computation platform. Additionally, GRDH is also combined into on-demand construction for high traversal performance. The experimental results demonstrate that the on-demand GRDH construction algorithm can achieve a speedup of 1.63 ~ 1.95 in overall frame performance for scenes with more than 360K primitives.