Efficient construction of bounding volume hierarchies into a complete octree for ray tracing

This paper proposes an efficient construction scheme for bounding volume hierarchies based on a complete tree. This construction offers up to 4× faster construction times than binned‐surface area heuristic and offers competitive ray traversal performance. The construction is fully parallelized on x86 CPU architectures; it takes advantage of the eight‐wide vector units and exploits the advance vector extensions available for current x86 CPU architectures. Additionally, this work presents a clustering algorithm for grouping primitives, which can be computed in linear time O ( n ). Furthermore, this construction uses the graphics processing unit to perform intensive operations efficiently.