Multithreaded builds have less memory efficient node ordering

[BoyBaykiller]

When building a top-down BVH in a depth first manner the left of the left child comes after the right child:

                   /     \
           left-> 42      43 <-right
                 / \      / \ 
left of left-> 44   45   321 322

This means whenever we traverse down left (half of the time) we just have to read the next nodes in the array which may be in some cache already.

However the current multithreaded builds don't have this nice ordering because an atomic counter is used:

tinybvh/tiny_bvh.h

Line 2534 in 4b5b649

if (threadedBuild) n = atomicNewNodePtr->fetch_add( 2 ); else n = newNodePtr, newNodePtr += 2;

So we may end up with something like this instead:

                   /     \
           left-> 42      43 <-right
                 / \      / \ 
left of left-> 612 613  266 267

Depth first vs "atomic order" makes a small difference in my GPU PathTracer: 187fps vs 182fps.

The fix is to remove atomic counter and compute deterministic node offsets assuming 1PPL (primitive per leaf):

leftOfLeft = right + 1
leftOfRight = right + 2 * leftTriCount - 1

Since that produces gaps in case 1PPL is not true a simple/fast in-place compaction step should be added afterwards.

Overall this is not a big deal and using atomic counter is simple, so might as well keep it but I just wanted to bring this up. Maybe for other people.

On a side note, there is a potential optimization opportunity I thought of: Because traversing down the left path is more memory friendly, the child with the larger surface area (more likely to be hit) should always be placed left.

[jbikker]

Thanks for your detailed comment.
Regarding the ordering of nodes: Your analysis is correct; threaded builds have a non-deterministic node ordering. You can call BVH::Compact after construction to remedy this; this function removes holes but also sorts nodes in a deterministic order.
The 1PPL approach (commonly used in GPU builders) is another way to achieve this, but applying SAH for subtree collapse in a post process yields trees of lower quality than applying it during the top-down build. It would of course be interesting to get this confirmed and implement both approaches, especially considering that the subtree collapse is potentially cheaper than BVH::Compact, which requires a temporary copy of the entire tree.
The optimization you mention in a side note is interesting; I can indeed imagine this to make a difference, at a minor cost during construction. Research on the memory layout of BVHs does show inconsistent (and in any case: limited) results. Perhaps this is best done as a post-process, for specific hardware?

[BoyBaykiller]

Nice, BVH::Compact does fix it.

---

but applying SAH for subtree collapse in a post process yields trees of lower quality than applying it during the top-down build

Even though the deterministic node offset computation assumes 1PPL we can still use SAH-based termination criteria during the build, so no node collapse needed. This of course creates "empty subtrees" at the bottom of the tree where nodes would have been if we did 1PPL but these can be compacted without any allocations:

static int RemoveEmptySubtrees(BuildResult blas)
{
    int nodeCounter = 2;

    Span<int> stack = stackalloc int[128];
    int stackPtr = 0;
    stack[stackPtr++] = 1;
    while (stackPtr > 0)
    {
        ref GpuBlasNode parentNode = ref blas.Nodes[stack[--stackPtr]];

        ref readonly GpuBlasNode leftNode = ref blas.Nodes[parentNode.TriStartOrChild + 0];
        ref readonly GpuBlasNode rightNode = ref blas.Nodes[parentNode.TriStartOrChild + 1];

        int leftNodeId = nodeCounter + 0;
        int rightNodeId = nodeCounter + 1;

        blas.Nodes[leftNodeId] = leftNode;
        blas.Nodes[rightNodeId] = rightNode;

        parentNode.TriStartOrChild = leftNodeId;
        nodeCounter += 2;

        if (!rightNode.IsLeaf) stack[stackPtr++] = rightNodeId;
        if (!leftNode.IsLeaf) stack[stackPtr++] = leftNodeId;
    }

    return nodeCounter;
}

[BoyBaykiller]

Because traversing down the left path is more memory friendly, the child with the larger surface area (more likely to be hit) should always be placed left.

Apparently there is a short paper on it: Ordered Depth-first Layouts for Ray Tracing.

The optimization can easily be added to SweepSAH because all you have to do is flip the bools for the partitioning table and do an extra stable partition on the split-axis. Although for tinybvh a general post-process that does this for all builders seems preferable.

However, as you said, the benefits are very minimal/non-existent. The only scene where I can measure a "significant" difference is Sponza, 7 bounces, RR, 1022x781. So I am not sure this is actully worth it in realistic scenarios:

Opt      : 196fps
Baseline : 194fps
De-Opt   : 192fps

where "De-Opt" is placing them in the opposite way of what Opt does.