Hierarchical Bitmask Implicit Grids for Efficient Point-in-Volume Queries on the GPU

Abstract

We propose “Hierarchical Bitmask Implicit Grids”, a novel, memory-efficient spatial index data structure for querying bounding volumes based on a contained point, targeting real-time use cases on GPUs. Like grid structures based on 3D arrays, implicit grids allow for nearly array-like direct lookups of cells without traversal through a spatial tree structure. However, the space complexity of this structure is O(n) with respect to resolution as opposed to O(n^3), which allows for dramatically higher resolutions than would be feasible with a 3D array. We demonstrate the effectiveness of this data structure by applying it to two example use cases: light culling and decal rendering. We measure both cases with ray tracing and multi-view rendering. We show that with tens of thousands of entries, our data structure can be built in 0.1–0.2 milliseconds, being ∼2.9x faster than the compared state-of-the-art decal method and orders of magnitude faster than dense 3D arrays, while delivering a t least similar or even up to doubled rendering performance.