Abstract
Ray tracing is becoming more and more the method of choice for both offline global illumination simulations as well as interactive visualizations. Because intersecting a ray with all objects in a scene is usually very expensive, almost all ray tracers rely on acceleration structures, trading preprocessing time and memory for faster ray-object intersections.
The uniform grid was one of the first proposed acceleration structures. Over time, several other acceleration structures, such as bounding volume hierarchies and kd-trees, have been introduced. For static scenes, kd-trees are by many considered the best acceleration structure. Uniform grids usually perform worse than kd-trees, mainly because they are not adaptive. For dynamic scenes however, there is no consensus. The acceleration structure has to be rebuilt every frame, and rather than minimizing render time, the time to image, the sum of the build time and the render time, has to be minimized. Building a grid can be done in linear time, while other popular acceleration structures require super linear time. For dynamic scenes, a shorter build time can compensate for a longer render time. Therefore, a grid can result in a shorter time to image than other acceleration structures that are usually considered superior.
Algorithms are typically CPU-bound or memory-bound. The execution time of an algorithm that is CPU-bound mainly depends on the speed of the CPU, while the execution time of an algorithm that is memory-bound mainly depends on the access speed of the memory. Memory-bound algorithms can be made significantly faster just by reducing the memory footprint of the data they work on. Building a grid is memory-bound, while rendering is CPU-bound. Therefore, reducing the memory footprint of a grid can results in shorter build times.
Uniform grids were used in one of the first systems for interactive ray tracing. Recent work on grids for ray tracing concentrated on fast traversal, parallelizing the build process, and choosing the grid size. In this work, we present two efficient methods for representing and building a grid.
The compact grid method consist of a static data structure for representing a grid with minimal memory requirements, more specifically exactly one index per grid cell and exactly one index per object reference, and an algorithm for building that data structure in linear time, that does not require additional memory.
The hashed grid method consists of a static data structure for representing a grid that reduces memory requirements even further, by using perfect hashing based on row displacement compression, and a fast algorithm for building that data structure.
Figure 1 shows several results. For example, the time to image and memory usage for the 1.89 GB David model is respectively 10.21 s and 379.94 MB using the hashed grid method. We show that the compact grid method and the hashed grid methods are more efficient in both time and space than traditional methods based on linked lists and dynamic arrays. We also investigate parallell grid building and rendering, we compare with other acceleration structures using the recent bwfirt benchmark, and we present a more robust grid traversal algorithm. We show that, for applications where time to image or memory usage is important, such as interactive ray tracing and rendering large models, the grid acceleration structure is an attractive alternative.
