uint32_t helpBuildBVH4()

in libraries/hvvr/shared/bvh.cpp [343:425]
69 lines of code
26 McCabe index (conditional complexity)

uint32_t helpBuildBVH4(Box4*& out, const Box2* node, BoxPlus* parentCache, uint32_t first) {
    // Post-order traversal: visit the children first.
    BoxPlus cache[6];
    uint32_t cacheSize = 0;
    if (node->offset(0))
        cacheSize += helpBuildBVH4(out, node + node->offset(0), cache + cacheSize, first);
    else
        cache[cacheSize++] = BoxPlus{node->boxes[0], first, first + node->size(0), 0, 0};
    if (node->offset(1))
        cacheSize += helpBuildBVH4(out, node + node->offset(1), cache + cacheSize, first + node->size(0));
    else
        cache[cacheSize++] =
            BoxPlus{node->boxes[1], first + node->size(0), first + node->size(0) + node->size(1), 0, 0};

    // If we get fewer than 4 nodes from our children, pass them to our parent.
    if (cacheSize < 4) {
        for (uint32_t i = 0; i < cacheSize; i++)
            parentCache[i] = cache[i];
        return cacheSize;
    }

    // We got 4 or more candidates from
    uint32_t j0Best = 4;
    uint32_t j1Best = 5;
    if (cacheSize > 4) {
        // Cache-size more than 4, find the set of 4 that produce the smallest box and pass the rest.
        // Try to minimize the total depth by favoring passing nodes with higher depth.
        std::sort(cache, cache + cacheSize, [](const BoxPlus& a, const BoxPlus& b) { return a.depth > b.depth; });
        float minCost = Infinity;
        if (cacheSize == 5) {
            for (uint32_t j0 = 0; j0 < 5; j0++) {
                Box box = Box::empty();
                for (uint32_t i = 0; i < 5; i++)
                    if (i != j0)
                        box |= cache[i].box;
                if (minCost > box.surfaceArea()) {
                    minCost = box.surfaceArea();
                    j0Best = j0;
                }
            }
        } else {
            for (uint32_t j1 = 1; j1 < 6; j1++)
                for (uint32_t j0 = 0; j0 < j1; j0++) {
                    Box box = Box::empty();
                    for (uint32_t i = 0; i < 6; i++)
                        if (i != j0 && i != j1)
                            box |= cache[i].box;
                    if (minCost > box.surfaceArea()) {
                        minCost = box.surfaceArea();
                        j0Best = j0;
                        j1Best = j1;
                    }
                }
        }
    }

    // Allocate a new box from the output list.
    BoxPlus* outBoxes = (--out)->boxes;
    // Add the box we just created to our parent's cache.
    BoxPlus* parent = parentCache++;
    *parent = BoxPlus{Box::empty(), 0, 0, (uint32_t)(out - (Box4*)nullptr), 0};
    for (uint32_t i = 0; i < cacheSize; i++) {
        if (i == j0Best || i == j1Best) {
            // Push the evected boxes into the parent's cache.
            *parentCache++ = cache[i];
            continue;
        }
        // Add these children to the allocated box and update the bounding box.
        if (cache[i].offset)
            cache[i].offset -= (uint32_t)(out - (Box4*)nullptr);
        if (cache[i].depth + 1 > parent->depth)
            parent->depth = cache[i].depth + 1;
        parent->box |= cache[i].box;
        *outBoxes++ = cache[i];
    }
    // Sort each box such that the leaves are first and nodes of the same type are sorted by surface area.
    std::sort(out->boxes, out->boxes + 4, [](const BoxPlus& a, const BoxPlus& b) {
        return (a.offset == 0 && b.offset != 0) ||
               ((a.offset == 0 || b.offset != 0) && a.box.surfaceArea() > b.box.surfaceArea());
    });
    // Return the total number of boxes we added to our parent's cache (our cache - 4 + 1 (the new node)).
    return cacheSize - 3;
}