BVH 层次包围盒加速光线追踪

项目目标

实现 BVH（Bounding Volume Hierarchy，层次包围盒） 加速结构，将暴力 O(n) 的光线-场景求交优化到 O(log n)，并通过实际渲染对比验证性能提升。

这是光线追踪系列（02-06 至今）的重要里程碑——解决了随场景规模增大性能急剧下降的根本问题。

核心概念

为什么需要 BVH？

朴素光线追踪对每条光线都要遍历场景中所有物体求交，时间复杂度是 O(n)。当场景有 1000 个球体时，每条光线需要做 1000 次求交测试。

BVH 通过构建层次树结构解决这个问题：

             [根节点 AABB]
            /             \
   [左子树 AABB]      [右子树 AABB]
   /          \          /       \
[球A AABB]  [球B AABB] ...      ...

光线先与包围盒求交（很快），如果不相交就跳过整棵子树，大幅减少无效测试。

实现过程

1. AABB 轴对齐包围盒

核心是高效的 Slab 方法求交：

bool AABB::intersect(const Ray& ray, double t_min, double t_max) const {
    for (int i = 0; i < 3; i++) {
        double inv_d = 1.0 / ray.direction[i];
        double t0 = (min_pt[i] - ray.origin[i]) * inv_d;
        double t1 = (max_pt[i] - ray.origin[i]) * inv_d;
        if (inv_d < 0) std::swap(t0, t1);
        t_min = std::max(t_min, t0);
        t_max = std::min(t_max, t1);
        if (t_max <= t_min) return false;  // 提前退出
    }
    return true;
}

每个轴两次乘法，极其高效。

2. SAH 构建策略

最朴素的构建是按中值分割——但 SAH（Surface Area Heuristic，表面积启发式）更优。

SAH 的思路：最优的分割应该最小化后续求交的期望代价。数学上等价于：

1	Cost(split) = 0.125 + (count_left × Area_left + count_right × Area_right) / Area_parent

实现时用 12 个桶均匀分割候选点，选代价最小的：

int sah_split(...) {
    const int NUM_BUCKETS = 12;
    Bucket buckets[NUM_BUCKETS];
    
    // 分配球体到桶
    for (int i = start; i < end; i++) {
        int b = bucket_index(spheres[i].center, axis);
        buckets[b].count++;
        buckets[b].bbox = AABB::merge(...);
    }
    
    // 评估每个分割点代价
    double costs[NUM_BUCKETS - 1];
    for (int i = 0; i < NUM_BUCKETS - 1; i++) {
        costs[i] = sah_cost(left_buckets, right_buckets);
    }
    
    // 找最小代价
    return best_split(costs);
}

3. BVH 遍历

bool intersect_node(int node_idx, ...) {
    // 先测 AABB，不中则整棵子树跳过
    if (!node.bbox.intersect(ray, t_min, t_max)) return false;
    
    if (node.is_leaf) {
        return spheres[node.sphere_idx].intersect(...);
    }
    
    // 先左后右，维护当前最近距离
    bool hit_left = intersect_node(node.left, ...);
    if (hit_left) t_max = rec_left.t;  // 剪枝！
    bool hit_right = intersect_node(node.right, ...);
    
    return hit_left || hit_right;
}