🪴 鸽子的图书馆

BVH 树

15分钟阅读

WARNING

文章作者：Deepseek v4 flash

编辑：我

校对：你

BVH 树入门

——空间划分的经典方案之一。

什么是 BVH

BVH（Bounding Volume Hierarchy） 是一种树形数据结构，用于高效管理三维空间中的几何体集合。

基本思路：用包围盒包裹几何体，然后将这些包围盒按空间邻近关系组织成一棵树。查询时通过包围盒的相交测试来剪枝，跳过不可能相交的区域。

有点像快递分拣——先按城市分，再按街道分，最后找到具体地址。

核心概念

包围体

BVH 的节点存储一个包围体（Bounding Volume），用来快速判断”这个区域有没有可能相交”。常见类型：

类型缩写特点相交测试复杂度
轴对齐包围盒AABB各轴对齐，计算简单O(1)
有向包围盒OBB可旋转，贴合更紧O(1)，稍复杂
包围球Sphere只有一个球心+半径O(1)，最简单
k-DOPk-DOP多方向切片，贴合精准O(k)

实际应用中最常用的是 AABB，实现简单、测试快。

AABB 的定义

AABB 用两个点表示：min(x, y, z) 和 max(x, y, z)。相交测试即检查两个 AABB 在各轴上是否有重叠区间：

bool intersect(AABB a, AABB b) {
    return a.max.x >= b.min.x && a.min.x <= b.max.x
        && a.max.y >= b.min.y && a.min.y <= b.max.y
        && a.max.z >= b.min.z && a.min.z <= b.max.z;
}

BVH 的树结构

一棵 BVH 树由两种节点组成：

  • 内部节点（Inner Node）：存储包围体 + 左右子节点指针
  • 叶节点（Leaf Node）：存储包围体 + 几何体列表
         [Root AABB]
         /         \
    [L AABB]    [R AABB]
    /     \      /     \
  TriA   TriB  TriC   TriD

每个节点的包围体必须完全包裹其子树下的所有几何体。这是 BVH 的不变量。

节点数据结构

struct BVHNode {
    AABB bounds;       // 包围盒
    int left;          // 左子节点索引，-1 表示叶节点
    int right;         // 右子节点索引
    int firstPrim;     // 叶节点：首个图元索引
    int primCount;     // 叶节点：图元数量
};

剪枝机制详解

剪枝的基本逻辑

所谓”剪枝”，指的是在遍历过程中跳过那些不可能包含目标结果的子树。

BVH 利用的性质很简单：如果一条光线（或一个查询体）与某个节点的包围盒不相交，那么该节点下的所有几何体都不可能相交。 因此可以直接跳过整个子树，无需遍历其中的任何图元。

这一步节省的是”逐个测试图元”的开销——包围盒的相交测试比图元相交测试快得多。

剪枝的具体流程

以光线追踪为例：

  1. 测试根节点包围盒：若不相交 → 整个场景无交点 → 直接返回
  2. 测试子节点包围盒：若与左子节点相交，与右子节点不相交 → 只遍历左子树，右子树整棵跳过
  3. 到达叶节点：只测试该叶节点内的少数图元

暴力遍历与 BVH 遍历的对比（假设场景有 N 个图元）：

方法测试次数复杂度
暴力遍历测试 N 个图元O(N)
BVH 遍历测试 O(log N) 个包围盒 + 少量图元O(log N)

对于 N=100 万的场景，暴力遍历要测 100 万次图元相交。BVH 可能只测 20 个包围盒 + 几个图元。差距在这里。

剪枝的几种触发条件

  • 光线-AABB 不相交：光线与节点包围盒无交点，该子树直接跳过
  • 最近交点剪枝（Closest Hit）：已找到 t = 2.0 的交点，某子节点包围盒的最小距离为 3.0，则跳过该子节点。因为即使该子树内有交点，距离也比已找到的远
  • 视锥体裁剪：节点的包围盒完全在视锥体之外，跳过该子树

光线遍历 + 剪枝代码示例

bool trace(Ray ray, BVHNode* nodes, int root) {
    struct StackItem { int nodeIdx; };
    StackItem stack[64];
    int stackPtr = 0;
    stack[stackPtr++] = {root};
 
    while (stackPtr > 0) {
        StackItem item = stack[--stackPtr];
        BVHNode& node = nodes[item.nodeIdx];
 
        // 剪枝点：包围盒不相交，整颗子树跳过
        if (!ray.intersectAABB(node.bounds)) continue;
 
        if (node.primCount > 0) {
            // 叶节点：测试所有图元
            for (int i = node.firstPrim; i < node.firstPrim + node.primCount; i++) {
                if (ray.intersectPrimitive(primitives[i])) return true;
            }
        } else {
            // 内部节点：按距离排序压栈
            // 近节点后出栈（先被遍历），有助于提前找到交点、触发剪枝
            float distL = ray.distanceToAABB(nodes[node.left].bounds);
            float distR = ray.distanceToAABB(nodes[node.right].bounds);
            if (distL < distR) {
                stack[stackPtr++] = {node.right};
                stack[stackPtr++] = {node.left};
            } else {
                stack[stackPtr++] = {node.left};
                stack[stackPtr++] = {node.right};
            }
        }
    }
    return false;
}

构建方法

1. 自顶向下（Top-Down）

最常用的构建方式。流程：

  1. 计算当前节点所有图元的包围盒
  2. 选择一个划分轴和划分位置
  3. 按划分将图元分成两组
  4. 递归处理两组子图元

划分策略一般使用 SAH（Surface Area Heuristic）。

2. 自底向上（Bottom-Up）

先为每个图元创建叶节点，然后反复合并邻近节点。构建慢但树质量高，常用于离线预处理场景。

3. 插入式构建（Incremental）

动态插入图元到已有 BVH 中。适合动画物体、动态场景。

三种构建方法对比

方法构建速度树质量适用场景
自顶向下（Top-Down）快中等-好静态场景、实时渲染
自底向上（Bottom-Up）慢最好离线烘焙、预处理
插入式（Incremental）中等中等动态场景、动画物体

SAH（Surface Area Heuristic）详解

SAH 要解决的问题

自顶向下构建的关键问题是：如何在每个节点处选择划分位置，使得最终树的遍历代价最小？

朴素的做法取中点或中位数划分，但这不考虑几何体的空间分布。SAH 通过量化估算”遍历这棵子树的期望代价”，来选择最优划分。

SAH 代价公式

C(p) = C_trav + p_L * N_L * C_isect + p_R * N_R * C_isect

其中：

符号含义典型值
C(p)在位置 p 处划分的总期望代价—
C_trav遍历一个内部节点的固定开销（压栈、测试包围盒等）1.0 ~ 2.0
C_isect测试一个图元相交的开销1.0（归一化基准）
N_L左子节点的图元数量—
N_R右子节点的图元数量—
p_L光线穿过左子节点包围盒的条件概率SA(L) / SA(P)
p_R光线穿过右子节点包围盒的条件概率SA(R) / SA(P)
SA(X)节点 X 包围盒的表面积—

核心思想：概率 p_L 和 p_R 用表面积比来近似。一个包围盒的表面积越大，一条随机光线穿过它的概率就越高。

概率 p 为什么用表面积比

在三维空间中，假设光线方向均匀分布，一条光线与一个凸体相交的概率正比于该凸体的表面积。对于包围盒 AABB，其表面积为：

SA = 2 * (width * height + height * depth + width * depth)

因此，光线穿过子节点包围盒（而非直接穿过父节点包围盒的空隙）的条件概率近似为：

p_L = SA(L) / SA(P)
p_R = SA(R) / SA(P)

这个近似成立的前提是光线方向均匀分布。对于实际场景，这一近似在统计意义上是合理的。

SAH 的完整使用流程

Step 1：确定候选划分

对当前节点的图元集合，沿每个轴（X、Y、Z）生成一组候选划分位置。常用做法：

  • 取所有图元包围盒的中心坐标作为候选
  • 或等间隔采样（如分 32 个 bin）

以图元中心为候选，能保证划分位置落在图元分布密集的区域附近。

Step 2：计算每个候选位置的 SAH 代价

对每个候选位置 p，需要知道：

  • 左子节点图元数量 N_L 和包围盒表面积 SA(L)
  • 右子节点图元数量 N_R 和包围盒表面积 SA(R)

这可以通过先对所有图元按轴排序，然后从左到右扫描增量计算。

Step 3：选择代价最小的划分

bestCost = INF
bestAxis = -1
bestPos = -1

for each axis (X, Y, Z):
    对图元按该轴排序
    for each candidate position p on this axis:
        cost = C_trav + (SA(L)/SA(P)) * N_L * C_isect + (SA(R)/SA(P)) * N_R * C_isect
        if cost < bestCost:
            bestCost, bestAxis, bestPos = cost, axis, p

if bestCost < N * C_isect:
    在 bestAxis 的 bestPos 处划分
else:
    停止划分，当前节点作为叶节点

如果 SAH 代价大于”不划分直接作为叶节点”的代价（即 N * C_isect），则停止递归。这是 SAH 的终止条件。

SAH 划分示例

场景：有 4 个三角形，其包围盒中心坐标如下：

图元中心 X中心 Y中心 Z
A0.20.50.5
B0.30.50.5
C0.70.50.5
D0.80.50.5

父节点包围盒：X 范围 [0, 1]，Y 范围 [0, 1]，Z 范围 [0, 1] → 父节点表面积 SA(P) = 2 * (11 + 11 + 1*1) = 6

沿 X 轴考察两个候选划分位置：

候选划分 X=0.5（A、B 在左，C、D 在右）

  • 左子节点：A、B，包围盒 X 范围 [0.2, 0.3] → SA(L) = 2 * (0.11 + 11 + 0.1*1) = 2 * (0.1 + 1 + 0.1) = 2.4
  • 右子节点：C、D，包围盒 X 范围 [0.7, 0.8] → SA(R) = 2 * (0.11 + 11 + 0.1*1) = 2.4
  • p_L = 2.4/6 = 0.4，p_R = 2.4/6 = 0.4
  • 设 C_trav = 1，C_isect = 1
  • C = 1 + 0.4 * 2 * 1 + 0.4 * 2 * 1 = 1 + 0.8 + 0.8 = 2.6

候选划分 X=0.5，但按中心坐标分组不同（A 在左，B、C、D 在右）

  • 左子节点：A，N_L = 1，SA(L) ≈ 2 * (01 + 11 + 0*1) ≈ 2 （近似退化为一个面）
  • 右子节点：B、C、D，N_R = 3，包围盒 X 范围 [0.3, 0.8] → SA(R) = 2 * (0.51 + 11 + 0.5*1) = 2 * (0.5 + 1 + 0.5) = 4
  • p_L = 2/6 ≈ 0.333，p_R = 4/6 ≈ 0.667
  • C = 1 + 0.333 * 1 * 1 + 0.667 * 3 * 1 = 1 + 0.333 + 2.001 = 3.334

第一种划分的代价 2.6 更低，因此选择将 A、B 分到左子树，C、D 分到右子树。

时间复杂度对比

方法划分策略构建时间复杂度遍历时间复杂度（期望）
等分划分取中点O(N log N)O(N)（退化情况）
中位数划分按中位数O(N log N)O(log N)
SAH 划分最小化代价O(N log² N)O(log N)，常数更小

SAH 的构建成本更高（需要多次排序和扫描），但生成的树遍历效率更高。对于静态场景（一次构建、多次遍历），SAH 是划算的。

BVH 的优劣

优势劣势
支持动态更新（重建或局部更新）不能保证严格的空间有序性
树结构天然支持递归遍历退化情况下近似链表（O(n)）
与物体分布无关，仅与空间位置有关重叠的包围盒降低剪枝效率
实现简单，硬件友好SAH 构建需要额外计算

应用场景

  • 光线追踪：GPU Ray Tracing 的核心加速结构
  • 碰撞检测：物理引擎中检测物体间的碰撞
  • 视锥体裁剪：快速剔除不可见的物体
  • 最近邻搜索：在三维空间中找到最近点

光线追踪领域几乎把 BVH 用到了极致，硬件 RT Core 底层也是 BVH 遍历器。

实现建议

  1. 使用数组代替指针：BVHNode nodes[] 比 new BVHNode 更高效
  2. 缓存友好的布局：子节点连续存储，减少缓存未命中
  3. 扁平化存储：内部节点和叶节点用统一结构体
  4. 栈替代递归：避免递归调用开销和栈溢出

扁平数组 + 索引引用是一种常见的工程实践。

总结： BVH 通过包围盒剪枝将图元相交测试从 O(N) 降到 O(log N)。SAH 用表面积比估算遍历代价，指导构建时选择最优划分位置，是实践中效果最好的构建策略之一。

最近的笔记