Dual-Split Trees

Symposium on Interactive 3D Graphics and Games (I3D 2019)

The Best Conference Paper Award

Daqi Lin, Konstantin Shkurko, Ian Mallett, Cem Yuksel

Abstract

We introduce the dual-split tree, a newtree-based acceleration structure for ray tracing. Each internal node of a dual-split tree uses two axis-aligned planes to either split the parent node into two child nodes or to mark the empty regions of the node. This allows child bounding boxes to overlap when desired. Thus, our dual-split tree is capable of representing space partitioning identical to any given bounding volume hierarchy. Our dual-split tree provides a significant reduction in the required acceleration structure storage by eliminating the redundant bounding planes that are commonplace in bounding volume hierarchies, providing better performance and storage savings than similar previous methods. As a result, we achieve improved rendering performance with dual-split trees, as compared to bounding volume hierarchies with a comparable level of optimization using identical or similar space partitioning.

dst-teaser

Comparison of the number of ray-plane and ray-triangle intersection tests generated by the primary rays using identical space partitioning between the BVH and our dual-split tree for the San Miguel scene shown on the right. The results show that our dual-split tree representation substantially reduces the number of ray-plane intersection tests during ray traversal with only a minor increase in the number of ray-triangle intersection tests.

[Paper - Preprint] [Supplemental Document]



Acknowledgements

This material is supported in part by the National Science Foundation under Grant No. 1409129. Crytek Sponza is from Frank Meinl at Crytek and Marko Dabrovic, Vegetation and Hairball are from Samuli Laine, San Miguel is from Guillermo Leal Laguno and Powerplant is from University of North Carolina. Dragon Sponza is from Cem Yuksel, who combined Dragon from the Stanford Computer Graphics Laboratory with Crytek Sponza.

BibTeX

@inproceedings{lin2019dual,
   author       = {Daqi Lin and Konstantin Shkurko and Ian Mallett and Cem Yuksel},
   title        = {Dual-Split Trees},
   booktitle    = {Symposium on Interactive 3D Graphics and Games (I3D 2019)},
   year         = {2019},
   location     = {Montreal, Quebec, Canada},
   url          = {https://doi.org/10.1145/3306131.3317028},
   doi          = {10.1145/3306131.3317028},
   publisher    = {ACM Press},
   address      = {New York, NY, USA},
}