uint32_t traverseBlocks()

in libraries/hvvr/raycaster/traverse_ref_bvh.cpp [42:132]
63 lines of code
17 McCabe index (conditional complexity)

uint32_t traverseBlocks(BlockFrame& frame, const BVHNode* node, const Frustum& frustum) {
    if (frustum.degenerate)
        return 0;

    uint32_t top = 0; // stack size, excluding the node we're currently processing
    float tMin = 0.0f; // distance estimate for the current node
    while (true) {
        // block frustum vs 4x AABB of children, corresponding bit is set if AABB is hit
        uint32_t mask = frustum.testBVHNodeChildren(*node);
        // spend some additional time to refine the test results
        mask = frustum.testBVHNodeChildrenRefine(*node, mask);

        // mask is currently bitmask of which children are hit by the frustum
        if (!mask)
            goto POP;

        uint32_t leaf = mask & node->boxData.leafMask;
        if (leaf) {
            mask &= ~leaf;

            // insert leaf nodes into the bottom of the stack
            uint32_t slot = top++;
            for (; slot > 0; slot--) {
                if (frame.stack[slot - 1].tDelta <= 0) // is the next-lowest slot on the stack a leaf node?
                    break;
                frame.stack[slot] = frame.stack[slot - 1];
            }
            frame.stack[slot].node = node;
            frame.stack[slot].tDeltaBytes = leaf;
            frame.stack[slot].tMinTemp = tMin;
        }

        // mask is currently bitmask of which non-leaf children are hit by ray
        if (!mask)
            goto POP;

        // 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];
        }

        // size of children along the primary traversal axis
        // assumes BVHNode stores float xMax[4] at a multiple of 32 bytes, immediately followed 16 bytes later by xNegMin[4]
        // (and the same for y and z)
        int maxOffset =
            frustum.distanceEstimateOffset & ~16; // remove neg/pos sign choice from distanceEstimateOffset to get Max
        int negMinOffset = maxOffset + 16;        // offset to get NegMin
        float childSize[childCount];
        for (int c = 0; c < childCount; c++) {
            childSize[c] = 
                ((float*)((uintptr_t)node + maxOffset))[c] +
                ((float*)((uintptr_t)node + negMinOffset))[c];
        }

        // insert each child into the stack, sorting such that the top of the stack is the node
        // with the largest dimensions along the primary traversal axis
        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].tDelta <= childSize[c])
                    break;
                frame.stack[slot] = frame.stack[slot - 1];
            }
            frame.stack[slot].node = node + node->boxData.children.offset[c];
            frame.stack[slot].tDelta = childSize[c];
            frame.stack[slot].tMinTemp = childDist[c];
        }

POP:
        // up to 4 entries can replace the current entry:
        // 3 internal nodes + 1 set of leaf nodes, or
        // 4 internal nodes
        if (
            // Don't flatten too much of the hierarchy before tile cull, that could break the advantage of a BVH.
            top >= BlockFrame::stackSize - childCount ||
            // We processed everything, and nothing remains
            top == 0 ||
            // We processed everything, and only leaf nodes remain
            (frame.stack + top - 1)->tDeltaBytes <= childMaskAll) {
            return top;
        }

        top--;
        node = (frame.stack + top)->node;
        tMin = (frame.stack + top)->tMinTemp;
    }
}