Stochastic Subsets for BVH Construction

Lorenzo Tessari, Addis Dittebrandt, Michael Doyle and Carsten Benthin

Computer Graphics Forum Vol. 42 Issue 2 (Proceedings of Eurographics) 2023, Honourable Mention

Overview of our proposed method. From the (a) input primitives, we (b) generate a subset, over which we (c) construct an initial BVH topology using an existing BVH constructor (a top-down builder for example). This step benefits from the smaller primitive count. The remaining primitives are (d) inserted into the leaves. We then (e) continue the construction process for each leaf.

Abstract

BVH construction is a critical component of real-time and interactive ray-tracing systems. However, BVH construction can be both compute and bandwidth intensive, especially when a large degree of dynamic geometry is present. Different build algorithms vary substantially in the traversal performance that they produce, making high quality construction algorithms desirable. However, high quality algorithms, such as top-down construction, are typically more expensive, limiting their benefit in real-time and interactive contexts. One particular challenge of high quality top-down construction algorithms is that the large working set at the top of the tree can make constructing these levels bandwidth-intensive, due to O(n log(n)) complexity, limited cache locality, and less dense compute at these levels. To address this limitation, we propose a novel stochastic approach to GPU BVH construction that selects a representative subset to build the upper levels of the tree. As a second pass, the remaining primitives are clustered around the BVH leaves and further processed into a complete BVH. We show that our novel approach significantly reduces the construction time of top-down GPU BVH builders by a factor up to 1.8×, while achieving competitive rendering performance in most cases, and exceeding the performance in others.

Downloads

Paper

Supplemental

Slides (pptx)

Slides (pdf)

Embree GPU code

pbrt-v3 CPU code

Bibtex

@article {2023_stochbvh,
    journal = {Computer Graphics Forum},
    title = {{Stochastic Subsets for BVH Construction}},
    author = {Tessari, Lorenzo and Dittebrandt, Addis and Doyle, Michael J. and Benthin, Carsten},
    year = {2023},
    publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
    ISSN = {1467-8659},
    DOI = {10.1111/cgf.14759}
}