Show simple item record

dc.contributor.authorChoi, Byeongjunen_US
dc.contributor.authorChang, Byungjoonen_US
dc.contributor.authorIhm, Insungen_US
dc.contributor.editorB. Levy, X. Tong, and K. Yinen_US
dc.date.accessioned2015-02-28T16:12:54Z
dc.date.available2015-02-28T16:12:54Z
dc.date.issued2013en_US
dc.identifier.issn1467-8659en_US
dc.identifier.urihttp://dx.doi.org/10.1111/cgf.12241en_US
dc.description.abstractCompared 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.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.subjectI.3.6 [Computer Graphics]en_US
dc.subjectMethodology and Techniquesen_US
dc.subjectGraphics data structures and data typesen_US
dc.subjectI.3.7 [Computer Graphics]en_US
dc.subjectThree Dimensional Graphics and Realismen_US
dc.subjectRaytracingen_US
dc.titleImproving Memory Space Efficiency of Kd-tree for Real-time Ray Tracingen_US
dc.description.seriesinformationComputer Graphics Forumen_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

  • 32-Issue 7
    Pacific Graphics 2013 - Special Issue

Show simple item record