WSEAS Transactions on Information Science and Applications
Print ISSN: 1790-0832, E-ISSN: 2224-3402
Volume 11, 2014
An Efficient Kd-tree Building Algorithm base on VRDH for Ray Tracing
Authors: , ,
Abstract: The Surface Area Heuristic (SAH) is regarded as a standard heuristic for building acceleration structure for ray tracing. However, its assumption of uniform ray distribution is a gross simplification and might lead to unnecessary intersection tests. In this paper, we consider ray distribution and propose a novel heuristic based on Visual Ray Distribution Heuristic (VRDH) to build a high-quality kd-tree. Because only the rays intersecting with primitives will contribute to final image, we distinguish types of rays according to intersection results and improve cost metric through only estimating traversal cost of visual rays. Since the knowledge of ray distribution is only available during tracing process, temporal coherence is exploited. We construct an auxiliary 3D grid structure to sample visibility. The knowledge in grid in frame k is employed to build kd-tree of frame k + 1. Additionally, the boundaries of voxels in grid are regarded as main splitting candidates as well as two strategies are presented to choose more optimal splitting planes. The experimental results indicate that our algorithm can reduce the number of ray-primitive intersection tests by 20%-66%, meanwhile make a speedup of approximately 20% for scene with 300K primitives for overall frame performance.
Search Articles
Pages: 112-121
WSEAS Transactions on Information Science and Applications, ISSN / E-ISSN: 1790-0832 / 2224-3402, Volume 11, 2014, Art. #12