We present our latest work, "Stochastic Subsets for Bounding Volume Hierarchy (BVH) Construction", which recently won an Honorable Mention at Eurographics 2023.
Our work leverages the field of stochastic sampling to offer both a new approach to optimizing acceleration structures, and to decrease the construction cost of high quality, but costly, top-down BVH builders.
Top-down BVH builders iteratively refine data subdivision by reordering and organizing all primitives in multiple passes, proceeding from the root to the leaves of the hierarchy. For the highest quality top-down BVH builders, this yields an O(nlogn) complexity. By observing the fact that the upper levels of the hierarchy represent a coarser, aggregated view of the data, we formulate a complexity model based on using only a subset of primitives to construct these upper levels, and show a significant speedup in construction time.
Obtaining a representative subset of the data that faithfully represents the overall scene features is a critical component of our approach. Since the upper levels of the tree are some of the most visited nodes during BVH traversal, it is crucial that they are of high quality. To achieve this goal, we embed spatial distribution and primitive size information in a simple CDF (cumulative distribution function), from which we can easily sample our subset through stratified sampling. This approach guarantees that the whole scene is well represented and primitives that have higher impact on the tree quality are selected.
The remaining primitives are then clustered on the leaves of the partially built tree, and further processed to obtain the final acceleration structure. This operation is easily parallelizable and can take full advantage of the capabilities of GPUs. Compared to the best top-down BVH builders on GPU, we achieve up to a 2x device-time speedup while maintaining similar traversal speed in most cases.
Ray-tracing is becoming a ubiquitous graphics technology, from movie production all the way to smartphones. While the former aims to build the best quality acceleration structures at high-cost, the latter must rely on cheaper construction methods that historically have not yielded the same traversal quality, in order to satisfy millisecond compute budgets. By lowering the cost of building the upper levels of the tree, we contribute to closing the gap between these two worlds, achieving high quality at a much faster construction speed.