Compact, Fast and Robust Grids for Ray Tracing

dc.contributor.authorLagae, Aresen_US
dc.contributor.authorDutre, Philipen_US
dc.date.accessioned2015-02-21T17:06:20Z
dc.date.available2015-02-21T17:06:20Z
dc.date.issued2008en_US
dc.description.abstractThe 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 efficient 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 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. 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 efficient 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.en_US
dc.description.number4en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume27en_US
dc.identifier.doi10.1111/j.1467-8659.2008.01262.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages1235-1244en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2008.01262.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleCompact, Fast and Robust Grids for Ray Tracingen_US
Files