Improving Memory Space Efficiency of Kd‐tree for Real‐time Ray Tracing. (25th November 2013)

• Record Type: Journal Article
• Authors: Choi, B.; Chang, B.; Ihm, I.
• Is Part Of: Computer graphics forum. Volume 32:Number 7(2013)
• Page Start: 335
• Page End: 344
• Publication Date: 2013-11-25
• Subjects: I.3.6 [Computer Graphics]: Methodology and Techniques—Graphics data structures and data types. -- I.3.7 [Computer Graphics]: Three‐Dimensional Graphics and Realism—Raytracing; Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.12241
• Languages: English
• ISSNs: 0167-7055

Abstract

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.