uint32_t traverseTiles()

in libraries/hvvr/raycaster/traverse_ref_bvh.cpp [134:217]

• 56 lines of code
• 16 McCabe index (conditional complexity)

uint32_t traverseTiles(
    uint32_t* triIndices, uint32_t maxTriCount,
    TileFrame& frame, uint32_t top, const Frustum& frustum)
{
    (void)maxTriCount;
    if (frustum.degenerate)
        return 0;

    uint32_t triCount = 0;
    while (top > 0) {
        // pop the node stack
        top--;
        // grab a node to test the children of
        const BVHNode* node = frame.stack[top].node;

        // tile frustum vs 4x AABB of children, corresponding bit is set if AABB is hit
        uint32_t mask = frustum.testBVHNodeChildren(*node);

        // no children hit? Move onto the next node
        if (!mask)
            continue;

        // were any of the hit children leaf nodes? If so, add the children to the output list.
        uint32_t leaf = mask & node->boxData.leafMask;
        if (leaf) {
            // spend some additional time to refine the test results
            // this is a tradeoff between extra traversal time, vs extra intersection time/memory
            // if we don't do this, we'll end up with more triangles to test later on
            mask = frustum.testBVHNodeChildrenRefine(*node, mask);

            leaf = mask & node->boxData.leafMask;
            if (leaf) {
                for (int c = 0; c < childCount; c++) {
                    if ((leaf & (1 << c)) == 0)
                        continue; // this child was culled

                    uint32_t triIndexStart = node->boxData.leaf.triIndex[c];
                    uint32_t triIndexEnd = node->boxData.leaf.triIndex[c + 1];
                    for (uint32_t triIndex = triIndexStart; triIndex < triIndexEnd; triIndex++) {
                        assert(triCount < maxTriCount);
                        triIndices[triCount++] = triIndex;
                    }
                }
            }
        }

        // strip leaf nodes from the hit mask, now we only care about the remaining hit internal nodes
        mask &= ~node->boxData.leafMask;
        // if there's nothing left, move onto the next stack entry
        if (!mask)
            continue;

        // This is needed because block cull inserts nodes that contain a child mix of hit leaf nodes and hit internal
        // nodes up to 4 times into the stack. Leaf node children are grouped into a single entry w/ hit mask, internal node
        // children each get their own entry. This test prevents the leaf entry from spawning duplicate copies of the
        // prepopulated sibling internal nodes.
        // mask will be 0 for internal nodes, or the leaf hit mask for nodes which contain leaf children
        if (frame.stack[top].mask)
            continue;

        // conservative min ray bundle distance to children along the primary traversal axis
        float childDist[childCount];
        for (int c = 0; c < childCount; c++) {
            childDist[c] = -((float*)((uintptr_t)node + frustum.distanceEstimateOffset))[c];
        }

        // insert each surviving internal child into the stack, closest node goes at top of stack
        for (int c = 0; c < childCount; c++) {
            if ((mask & (1 << c)) == 0)
                continue; // this child was culled

            uint32_t slot = top++;
            for (; slot > 0; slot--) {
                if (frame.stack[slot - 1].tMin >= childDist[c])
                    break;
                frame.stack[slot] = frame.stack[slot - 1];
            }
            frame.stack[slot].node = node + node->boxData.children.offset[c];
            frame.stack[slot].tMin = childDist[c];
            frame.stack[slot].mask = 0;
        }
    }
    return triCount;
}