Hierarchical Bitmask Implicit Grids for Efficient Point-In-Volume Queries on the GPU
2024, Ikkala, J., Lauttia, T., Jääskeläinen, P. and Mäkitalo, M., In Proceedings of the 19th International Conference on Computer Graphics Theory and Applications (GRAPP).
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 at least similar or even up to doubled rendering performance.