Macro 64-regions for uniform grids on GPU

Uniform grids are a spatial subdivision acceleration structure well suited for ray tracing. They are known for their fast build times and ease of use, but suffer from slow traversals in the presence of empty space. To address this issue, we present macro 64-regions, a new GPU based approach for finding and storing empty volumes in an underlying uniform grid. This allows for fast traversals through regions that do not contain scene geometry. Further, unlike previous solutions to this problem, we do not store a hierarchical structure and therefore the traversal steps are simplified. Because macro 64-regions are dependent on an underlying grid, we also introduce an improvement in the grid construction process. Our method does not rely on sorting as previous methods do, but instead uses atomic operators to manage bookkeeping during the build. Using our proposed methods, we show a substantial improvement in build time, trace time, as well as an improvement in the consistency of rendering times for randomly generated views