Improving Memory Space Efficiency of Kd-tree for Real-time Ray Tracing
| dc.contributor.author | Choi, Byeongjun | en_US |
| dc.contributor.author | Chang, Byungjoon | en_US |
| dc.contributor.author | Ihm, Insung | en_US |
| dc.contributor.editor | B. Levy, X. Tong, and K. Yin | en_US |
| dc.date.accessioned | 2015-02-28T16:12:54Z | |
| dc.date.available | 2015-02-28T16:12:54Z | |
| dc.date.issued | 2013 | en_US |
| dc.description.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. | en_US |
| dc.description.seriesinformation | Computer Graphics Forum | en_US |
| dc.identifier.issn | 1467-8659 | en_US |
| dc.identifier.uri | https://doi.org/10.1111/cgf.12241 | en_US |
| dc.publisher | The Eurographics Association and Blackwell Publishing Ltd. | en_US |
| dc.subject | I.3.6 [Computer Graphics] | en_US |
| dc.subject | Methodology and Techniques | en_US |
| dc.subject | Graphics data structures and data types | en_US |
| dc.subject | I.3.7 [Computer Graphics] | en_US |
| dc.subject | Three Dimensional Graphics and Realism | en_US |
| dc.subject | Raytracing | en_US |
| dc.title | Improving Memory Space Efficiency of Kd-tree for Real-time Ray Tracing | en_US |