BVH 加速结构

Bounding Volume Hierarchy (BVH) 是光线追踪中最重要的加速结构之一。

概述

BVH 通过将场景中的物体组织成层次包围盒树，将光线求交的时间复杂度从 O(N) 降低到 O(log N)。

SAH 分割策略

Surface Area Heuristic (SAH) 是选择最优分割位置的代价函数：

$$C = C_{trav} + \frac{SA(L)}{SA(N)} \cdot |L| \cdot C_{isect} + \frac{SA(R)}{SA(N)} \cdot |R| \cdot C_{isect}$$

其中：

$SA$ 表示包围盒表面积
$|L|$, $|R|$ 分别是左右子树的图元数量
$C_{trav}$ 是遍历节点代价
$C_{isect}$ 是求交测试代价

构建算法

BVH 构建 (SAH)

输入: 图元集合 P 输出: BVH 根节点

if |P| ≤ 叶子阈值 then
return 创建叶子节点(P)
end if
选择分割轴 (x/y/z) 使 SAH 代价最小
将 P 分割为 P_left, P_right
node.left ← BVH-Build(P_left)
node.right ← BVH-Build(P_right)
return node

遍历算法

BVH 遍历 (栈式)

输入: 光线 R, BVH 根节点 root 输出: 最近相交点 hit

stack.push(root)
while stack 非空 do
node ← stack.pop()
if R 与 node.aabb 不相交 then continue
if node 是叶子 then
```
测试 R 与 node 中所有图元
```
else
```
stack.push(node.left)
```
```
stack.push(node.right)
```
end if
end while

性能分析

场景	球体数	暴力求交	BVH 求交	加速比
Demo	10	10	4	2.5×
Random	100	100	7	14×
Complex	1000	1000	10	100×

代码实现

cpp

// BVH 节点结构
struct BVHNode {
    AABB bounds;
    int left;    // 左子节点索引（负数表示叶子）
    int right;   // 右子节点索引
    int start;   // 叶子节点：图元起始索引
    int count;   // 叶子节点：图元数量
};

// BVH 遍历 kernel
__device__ bool traverse_bvh(
    const Ray& ray,
    const BVHNode* nodes,
    const Sphere* spheres,
    HitRecord& closest_hit
) {
    int stack[64];
    int stack_ptr = 0;
    stack[stack_ptr++] = 0;  // 根节点

    while (stack_ptr > 0) {
        int node_idx = stack[--stack_ptr];
        const BVHNode& node = nodes[node_idx];

        if (!intersect_aabb(ray, node.bounds)) continue;

        if (node.left < 0) {  // 叶子节点
            for (int i = 0; i < node.count; ++i) {
                // 测试图元求交
            }
        } else {
            stack[stack_ptr++] = node.left;
            stack[stack_ptr++] = node.right;
        }
    }
    return closest_hit.valid;
}

参考资料

[Wald 2007] "On fast Construction of SAH-based BVH"
[Aila & Karras 2010] "Understanding Ray Traversal Efficiency on GPUs"

BVH 加速结构 ​

概述 ​

SAH 分割策略 ​

构建算法 ​

遍历算法 ​

性能分析 ​

代码实现 ​

参考资料 ​