Compact, fast and robust grids for ray tracing
Ares Lagae | Philip Dutré |
Contact: Ares Lagae
Computer Graphics Forum (Proceedings of the 19th Eurographics Symposium on Rendering), 27(4):1235-1244, June 2008
Abstract
The focus of research in acceleration structures for ray tracing recently shifted from render time to time to image, the sum of build time and render time, and also the memory footprint of acceleration structures now receives more attention. In this paper we revisit the grid acceleration structure in this setting. We present two efï¬cient methods for representing and building a grid. The compact grid method consists of a static data structure for representing a grid with minimal memory requirements, more speciï¬cally exactly one index per grid cell and exactly one index per object reference, and an algorithm for building that data structure in linear time. The hashed grid method reduces memory requirements even further, by using perfect hashing based on row displacement compression. We show that these methods are more efï¬cient in both time and space than traditional methods based on linked lists and dynamic arrays. We also 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.