Sung-Eui Yoon,Sean Curtis, and Dinesh Manocha
Video encoded with XviD MPEG4 (29 MB)
Exploding dragon benchmark: Three images are shown from a dynamic simulation of a bunny breaking a dragon. This scene consists of 252K triangles and undergoes drastic topological changes. We use our algorithm to selectively restructure an axis-aligned bounding box (AABB) tree during each frame. Our ray tracing algorithm based on selective restructuring is able to achieve 65-1000% performance improvement over prior ray tracing algorithms that are based on AABB-trees.
We present a novel algorithm to selectively restructure bounding volume hierarchies (BVHs) for ray tracing dynamic scenes. We derive two new metrics to evaluate the culling efficiency and restructuring benefit of any BVH. Based on these metrics, we perform selective restructuring operations that efficiently reconstruct small portions of a BVH instead of the entire BVH. Our approach is general and applicable to complex and dynamic scenes, including topological changes. We apply our selective restructuring algorithm to improve the performance of ray tracing dynamic scenes that consist of hundreds of thousands of triangles. In our benchmarks, we observe up to an order of magnitude improvement over prior BVH-based ray tracing algorithms.
Basic restructuring operation: Our algorithm selects a node pair (n_1, n_2), whose BVs overlap considerably (show on the left). Our restructuring operations takes the union of primitives contained in sub-BVH(n_1) and sub-BVH(n_2), re-partitions the primitives into two new nodes, \hat{n_1} and \hat{n_2}, and recursively process the sub-BVHs of the new nodes. The complexity of this operation is O(k \log k), where k = |n_1|_{tri} + |n_2|_{tri}. This is in contrast with other restructuring algorithms where k = |n_A|_{tri}, where n_A is the lowest common ancestor of n_1 and n_2.
We would like to thank Naga Govindaraju for sharing his breaking dragon simulation data. Also, we would like to thank Christian Lauterbach for sharing his BVH-based ray tracing codes. Also, we would like to thank Ingo Wald, Ming Jang, Hanan Samet, and anonymous reviewers for their constructive feedback and suggestions. Finally, we also would like to thank Peter Lindstrom for his support and comments on this work.
CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
(919) 962-1749
geom@cs.unc.edu