Multi-Level Hashed Grids for Ray Tracing
Vasco S. Costa, João Madeiras Pereira, Joaquim Armando Jorge · 2009
Grids have some of the lowest ray tracing acceleration structure build times. This is because acceleration structure construction is analogous to a sorting algorithm. The ideal behavior for a sorting algorithm is to have O(N) time complexity regarding the number of elements. Grids also have O(N) construction time complexity regarding the number of primitives unlike other commonly used acceleration structures, such as kd-trees or bounding volume hierarchies, which have an O(N logN) lower bound. This trait makes grid ray tracing interesting for many applications including animation. Recent algorithmic developments have also made it possible to achieve one-level grid construction, with low memory requirements, by compressing empty grid cells. Unfortunately one-level grids achieve lower render time performance than recursive structures such as multi-level grids. We present a method for rapidly building a grid with similarly good render time performance and using less memory than classic multi-level grids. We demonstrate that this method is a remarkably effective solution for interactive ray tracing of large scanned models. CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism—Raytracing; I.3.6 [Computer Graphics]: Methodology and Techniques—Graphics data structures and data types;