Bounding Volume Hierarchy
The raytracing acceleration structure used is a bounding volume hierarchy. The code is based on an implementation from NVidia under the Apache license, with some code adapted from Embree as well. This code includes spatial splits to make it more competitive with kd-trees.
On top of that, we added support for instancing, motion blur, building a QBVH to use SIMD instructions, and support for dynamically updating the BVH through refitting and a two-level BVH.
The BVH is built based on the surface area heuristic (SAH) and spatial splits. Build performance is optimized with binning and multithreading.
For instancing and dynamic updates, we build a two level BVH. The BVH's are built independently for each mesh, and then a top level object BVH instances these meshes. This reduces tree quality but for instances leads to lower memory usage and for dynamic updates faster rebuilds as object as are transformed, added or removed. For traversal, the nodes from two levels are still packed into a single array.
With offline rendering, the triangles of non-instanced objects are transformed and placed in the top level of the tree.
If no new objects or triangles are added, rather than rebuilding the BVH entirely, we can refit it with the new coordinates. This means we keep the same tree structure, and only update the bounding boxes. As the coordinates deviate further from the original, the tree quality goes down.
QBVH and OBVH
On the CPU, SIMD instructions do 4 float operations at once, so to take advantage of this we can use a BVH with 4 child nodes and intersect their bounding boxes in one go. We also intersect 4 triangles at once.
Support for intersecting 8 child nodes and triangles was added as well, to take advantage of AVX instructions.