Sweep SAH builder

[ib00]

What paper is the sweeping SAH BVH builder based on?

Is it better than PLOC?

[madmann91]

The sweep SAH builder is based on the ideas in "Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies", by I. Wald et al. The important difference is that the algorithm in this library avoids sorting the primitives again at each build step, by using a stable partition algorithm and an array of flags to mark the side each primitive belongs to. I came up with this idea independently when working on BVH building around 2015, but later found it in other pieces of literature, e.g. "Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees", by P. Ganestam et al. I would bet that this idea has been discovered by others as well, potentially even earlier.

[madmann91]

Oh, I realized I forgot to answer your second question. The answer to that is: It depends, but most likely yes. The sweep SAH builder is usually considered the "gold standard", because it produces very good trees, and because of its top-down nature, it tends to prevent large amounts of overlap between the node's bounding boxes, unlike PLOC (which is bottom-up). As you know, overlapping bounding boxes may cause performance issues if the overlap is large enough to cause many rays to enter both children of a node.

[madmann91]

Note however that PLOC is easy to parallelize (particularly on GPUs), while a sweep SAH builder, due to its top-down nature, is harder to implement on GPU hardware. The implementation of the Mini-tree builder in this library uses the sweep SAH builder to build the mini trees, and later to build the top-level tree on top. This is an efficient way to parallelize this algorithm.

[ib00]

This would explain why some libraries (eg, AMD's HIPRT) is using PLOC to build BVHs.