An Evaluation of Parallel Grid Construction for Ray Tracing Dynamic Scenes

We describe and analyze several ways to parallelize the rebuild of a grid acceleration structure used for interactive ray tracing of dynamic scenes. While doing so, we also analyze memory system performance on a multi-core multi-processor system. In particular, we present a scalable sort-middle approach that uses a minimum amount of synchronization, scales to many CPUs, and becomes performance limited only by memory bandwidth. This algorithm is capable of rebuilding grids within a fraction of a second, enabling interactive ray tracing of large multi-million triangle scenes