size_t helpBuildBVH2()

in libraries/hvvr/shared/bvh.cpp [196:249]

• 41 lines of code
• 9 McCabe index (conditional complexity)

size_t helpBuildBVH2(Box2* node, float* temp, const Box** boxes, size_t size) {
    if (size < 2)
        return 0;

    // Look along each axis to determine which contains the lowest cost split.
    int axis = 0;
    size_t index = 0;
    float cost = Infinity;
    scanAxis(index, cost, temp, boxes, size, 0);
    if (scanAxis(index, cost, temp, boxes, size, 1))
        axis = 1;
    if (scanAxis(index, cost, temp, boxes, size, 2))
        axis = 2;

    // Sort the boxes along the axis with the best split.
    std::sort(boxes, boxes + size, [axis](const Box*& a, const Box*& b) {
        return a->lower[axis] + a->upper[axis] <
               b->lower[axis] + b->upper[axis];
    });

    // Recurse on the lower half of the split range.
    size_t offset = 1;
    if (size_t count = helpBuildBVH2(node + offset, temp, boxes, index)) {
        node->boxes[0] = node[offset].bound();
        node->offset(0) = (uint32_t)offset;
        offset += count;
    } else {
        node->boxes[0] = *boxes[0];
        for (size_t i = 1; i < index; i++)
            node->boxes[0] |= *boxes[i];
        node->offset(0) = 0;
    }
    node->size(0) = (uint32_t)index;

    // Recurse on the upper half of the split range.
    if (size_t count = helpBuildBVH2(node + offset, temp + index, boxes + index, size - index)) {
        node->boxes[1] = node[offset].bound();
        node->offset(1) = (uint32_t)offset;
        offset += count;
    } else {
        node->boxes[1] = *boxes[index];
        for (size_t i = index + 1; i < size; i++)
            node->boxes[1] |= *boxes[i];
        node->offset(1) = 0;
    }
    node->size(1) = (uint32_t)(size - index);

    // Should we subdivide further? This controls the balance of tree depth vs leaf size.
    // Check to see if this split costs more than just intersecting the triangles directly.
    // Left side is the cost to intersect the triangles, right side is the cost to intersect the children.
    const float nodeIntersectMultiplier = 2.0f; // intersecting a node costs the same as 2 triangles
                                                // size < cost / node->bound().surfaceArea() + nodeIntersectMultiplier
    return node->bound().surfaceArea() * (float(size) - nodeIntersectMultiplier) < cost ? 0 : offset;
}