Improving Memory Space Efficiency of Kd-tree for Real-time Ray Tracing
No Thumbnail Available
Date
2013
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd.
Abstract
Compared with its competitors such as the bounding volume hierarchy, a drawback of the kd-tree structure is that a large number of triangles are repeatedly duplicated during its construction, which often leads to inefficient, large and tall binary trees with high triangle redundancy. In this paper, we propose a space-efficient kd-tree representation where, unlike commonly used methods, an inner node is allowed to optionally store a reference to a triangle, so highly redundant triangles in a kd-tree can be culled from the leaf nodes and moved to the inner nodes. To avoid the construction of ineffective kd-trees entailing computational inefficiencies due to early, possibly unnecessary, ray-triangle intersection calculations that now have to be performed in the inner nodes during the kd-tree traversal, we present heuristic measures for determining when and how to choose triangles for inner nodes during kd-tree construction. Based on these metrics, we describe how the new form of kd-tree is constructed and stored compactly using a carefully designed data layout. Our experiments with several example scenes showed that our kd-tree representation technique significantly reduced the memory requirements for storing the kd-tree structure, while effectively suppressing the unavoidable frame-rate degradation observed during ray tracing.
Description
@article{10.1111:cgf.12241,
journal = {Computer Graphics Forum},
title = {{Improving Memory Space Efficiency of Kd-tree for Real-time Ray Tracing}},
author = {Choi, Byeongjun and Chang, Byungjoon and Ihm, Insung},
year = {2013},
publisher = {The Eurographics Association and Blackwell Publishing Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.12241}
}