A Neural Builder for Spatial Subdivision Hierarchies
I. Evangelou, G. Papaioannou, K. Vardis, A. Gkaravelis
Visual Computer 2023, proc. CGI 2023
Abstract. Spatial data structures, such as k-d trees and bounding volume hierarchies, are extensively used in computer graphics for the acceleration of spatial queries
in ray tracing, nearest neighbour searches and other tasks. Typically, the splitting strategy employed during the construction of such structures is based on the greedy
evaluation of a predefined objective function, resulting in a less than optimal subdivision scheme. In this work, for the first time, we propose the use of unsupervised
deep learning to infer the structure of a fixed-depth k-d tree from a constant, subsampled set of the input primitives, based on the recursive evaluation of the cost
function at hand. This results in high-quality upper spatial hierarchy, inferred in constant time and without paying the intractable price of a fully recursive tree
optimisation. The resulting fixed-depth tree can then be further expanded, in parallel, into either a full k-d tree or transformed into a bounding volume hierarchy,
with any known conventional tree builder. The approach is generic enough to accommodate different cost functions, such as the popular surface area and volume heuristics.
We experimentally validate that the resulting hierarchies have competitive traversal performance with respect to established tree builders, while maintaining minimal
overhead in construction times.
Content: Paper, Presentation
