需要预先学习：

1. 层次包围结构

两个看似无关的问题，其实是同一件事：

  • 剔除总结 里的视锥剔除，每帧要拿每个物体的包围体测六个平面——物体一多，CPU 逐个测试本身就成为开销；
  • 光线追踪 里每条光线要与每个三角形求交——三角形数乘以光线数，直接相乘完全不可接受。

两者的共同点：绝大多数测试的结果都是"没有命中"，但每一次"没有"都要花一次测试的代价换回来。层次包围结构（hierarchical bounding structure）的思路是让"没有"变得成片：把物体按空间位置组织成一棵树，每个节点用包围体框住它负责的所有内容；光线或视锥与某个节点的包围体不相交，整棵子树一次排除。单次查询的复杂度从 O(n)O(n) 降到 O(log⁡n)O(\log n)。

按"切的东西"不同，层次结构分两大族：

族类 切的是什么 代表结构
空间划分（spatial subdivision） 空间本身 均匀网格、八叉树、BSP 树、k-d tree
物体划分（object subdivision） 物体的集合 BVH

注：剔除总结 提到过的场景图（scene graph）虽然也是"树 + 包围体"，但它表达的是物体间的变换父子关系（父物体移动带动子物体），不是加速结构，本篇不展开。

2. 包围体：松与紧的权衡

层次结构的每个节点都要回答同一个问题："这次查询有没有可能碰到我负责的内容？"回答它靠的是包围体（bounding volume）。可选的形状从松到紧大致排成一列：

包围体 紧密度 求交成本 特点
包围球 最松 最低 旋转不变，物体怎么转都不用重算
AABB 较松 低 slab 法逐轴求区间（见 光线追踪），物体旋转后需重算
OBB 较紧 较高 随物体旋转，长条形物体贴合度远好于 AABB
k-DOP 更紧 中 用 k 组斜半空间夹住物体，AABB 是 k=3 的特例
凸包 最紧 最高 精确贴住物体，构建与测试都贵，实践中少用

选择是纯粹的权衡：越紧的包围体让树越"准"（误命中越少，深入子树的次数越少），但每次测试越贵。实践中 AABB 是绝对主流——测试足够便宜、足够好算，且树结构带来的指数级收益远大于单个包围体松紧的线性差异。

还有一个后面要用到的性质：包围体的表面积越大，一条随机方向的光线击中它的概率越高。这直觉上说得通——盒子越大，越容易挡住路。这个"表面积 ↔ 命中概率"的对应关系是 SAH 构建策略（见后文）的理论基础。

3. 空间划分结构

空间划分结构递归地切空间本身：每个节点对应一块空间区域，子节点把这块区域继续细分。区域之间不重叠，合起来恰好是父区域。

3.1 均匀网格

均匀网格（uniform grid）是最朴素的方案：把空间切成大小相同的立方体格子，每个物体登记到它覆盖的所有格子里。查询一条光线时，沿着光线方向逐格前进（一种 3D 直线光栅化），只与途经格子里的物体求交。

它不建树，构建近乎免费，每物体 O(1)。但格子的粒度是个两难：

  • 格子太大：一个格子里挤满物体，逐格前进退化成逐物体测试；
  • 格子太小：大物体（长墙、地板）横跨成百上千个格子，登记开销与内存爆炸，而大部分格子空无一人——“体育场里一只茶壶”（teapot in a stadium）说的就是这种空间密度极不均匀的场景。

网格适合"物体小而均匀分布"的场合（粒子、弹幕），密度悬殊的场景就力不从心了。

3.2 八叉树

八叉树（octree）把空间递归地八等分：每个节点对应一个立方体区域，切成 2×2×2 八个子立方体，物体分给完全包含它的子节点。一个物体跨在几个子区域的边界上怎么办？两种处理：

  • 上浮：物体存放在能完全容纳它的最浅节点里。物体只存一份，但高层节点会积累跨边界的物体，包围体变松；
  • 下沉重复：物体切开登记进每个相交的子节点。查得准，但同一份图元在树里存了多份。

这是所有空间划分结构的共同痛点：空间与物体不是一一对应的，切割面总要切到一些物体身上。四叉树（quadtree）是八叉树的二维版本，同样的思想切平面，常用于地形、开阔场景的剔除。

3.3 BSP 树

BSP 树（Binary Space Partitioning，二叉空间划分）用任意朝向的平面递归二分空间——不再限于轴对齐。切割平面通常直接选场景中的多边形所在平面，于是树的"前侧"与"后侧"恰好对应几何的前后关系：从任意视角出发，按"远子树 → 自身 → 近子树"的顺序遍历，就得到严格的从后到前的绘制序——这是画家算法的完美替代，也是早期 FPS 引擎（Quake 系）室内场景可见性处理的基础。

代价是构建：切割平面要精心挑选（尽量少切动物体、尽量均衡），好的构建很贵；而且物体一旦移动，树的划分就失去意义。BSP 是静态场景专属的结构。

3.4 k-d tree

k-d tree（k 维树，三维场景就是 3d-tree）是 BSP 的轴对齐版：每个节点沿某一个坐标轴放一个切割平面，位置任意，把空间严格二分：

         ┌─ x 轴切：x = 3
         │        ┌─ y 轴切：y = 1
空间 ────┤
         │        └─ y 轴切：y = 5
         └─ x 轴切：x = 9

k-d tree 对光线查询有一个独一无二的优势：空间被不重叠地划分，光线穿过树天然有序。光线先到达的区域先被访问，一旦命中立即终止——而 BVH 的子节点包围盒允许重叠，两个子树都可能命中，往往都要走一遍。因此 k-d tree 曾长期统治离线渲染器（PBRT 的经典实现）。

它的软肋同样明显：构建昂贵（通常也要靠 SAH 选切割平面，代价高于 BVH 构建），且物体移动后无法局部修补——空间划分定了，物体却不在原位了。k-d tree 属于静态场景。

3.5 四种结构对比

结构 划分方式 构建成本 动态更新 适合
均匀网格 均匀切块 近乎免费 容易（重登记格子） 均匀分布的小物体
八叉树 递归八等分 中 较难 密度不均的空间查询
BSP 树 任意平面 贵 几乎不可用 静态几何的严格前后序
k-d tree 轴对齐任意位置 贵 几乎不可用 静态场景光线求交

4. BVH：把物体组织成树

层次包围盒（BVH，Bounding Volume Hierarchy，见 光线追踪 的构建与遍历基础）是物体划分的代表：递归切的是物体的集合——把三角形按空间邻近性分成两组，各自求包围盒，再递归分组。空间划分与物体划分的一字之差，带来几个本质区别：

  • 图元只存一份。每个三角形属于恰好一个叶节点，不存在跨边界登记多份的问题；
  • 节点包围盒允许重叠。两组物体的包围盒可以有公共区域，这不影响正确性，只影响效率；
  • 物体可以动。一个物体移动，只需让它所在路径上的节点包围盒"长大"一点，树的结构不必推翻（见后文 refit）。

4.1 构建：分割策略与 SAH

光线追踪 里用"最长轴中点分割"演示了自顶向下的构建框架，这里展开分割策略本身。朴素的两种：

  • 等量分割（equal split）：按最长轴坐标排序，从中间切成数量相等的两半。优点是树一定平衡；缺点是空间上一侧可能稀疏、一侧密集，切出来的包围盒又大又重叠；
  • 中点分割（center split）：以包围盒中心为界分成两侧。对"一坨物体 + 一条离群长条"的分布会切出一侧为空——空的一侧继续切还是空，最坏时递归不收敛。

两者都没回答真正的问题：哪种分割让光线求交最快？SAH（Surface Area Heuristic，表面积启发式）直接对求交代价建模。它基于两个假设：

  1. 访问一个内部节点要付一次遍历代价 CtravC_{trav}（包围盒求交）；
  2. 测试一个图元要付一次求交代价 CisectC_{isect}。

于是一个候选分割的期望代价是：

Csplit=Ctrav+SA(L)SA(P) NL Cisect+SA(R)SA(P) NR CisectC_{split} = C_{trav} + \frac{SA(L)}{SA(P)}\, N_L\, C_{isect} + \frac{SA(R)}{SA(P)}\, N_R\, C_{isect}

其中 SA(P)SA(P) 是父节点包围盒表面积，SA(L)SA(L)、SA(R)SA(R) 是两侧子盒的表面积，NLN_L、NRN_R 是两侧的图元数。SA(L)SA(P)\frac{SA(L)}{SA(P)} 正是"随机光线击中左盒的概率"（前文表面积性质的直接引用）：一侧的概率大且图元多，它就贡献更多的期望求交。AABB 的表面积好算：

SA=2(xy+yz+zx),x,y,z 为盒子的三条边长SA = 2(xy + yz + zx), \quad x,y,z \text{ 为盒子的三条边长}

遍历所有候选分割，取 CsplitC_{split} 最小的一个。候选位置不可能枚举连续值，实践中用 binning（分桶）：把父包围盒沿某轴切成 8~16 个桶，每个物体按质心落进桶里，枚举"桶边界"作为候选分割——每个轴只有十几个候选，整个构建保持近似线性：

// 伪代码：SAH + binning 选分割
Split find_best_split(const vector<Triangle>& tris, const AABB& box)
{
    Split best;                         // 记录最优分割：轴 + 桶边界
    float best_cost = cost_of_leaf(tris.size());    // 与"不再分割"比较

    for (int axis = 0; axis < 3; ++axis)
    {
        int buckets[NUM_BUCKETS];
        AABB bucketBox[NUM_BUCKETS];
        fill_buckets(tris, box, axis, buckets, bucketBox);

        // 枚举桶边界：前 i 个桶为左侧，其余为右侧
        for (int i = 1; i < NUM_BUCKETS; ++i)
        {
            AABB left = union_of(bucketBox, 0, i);
            AABB right = union_of(bucketBox, i, NUM_BUCKETS);

            float cost = C_TRAV
                       + (surface_area(left)  * count(buckets, 0, i)) / surface_area(box) * C_ISECT
                       + (surface_area(right) * count(buckets, i, N)) / surface_area(box) * C_ISECT;

            if (cost < best_cost)
            {
                best_cost = cost;
                best = {axis, i};
            }
        }
    }
    return best;    // 若没有任何分割优于当叶节点，返回"不分割"
}

SAH 的构建结果明显好于中点法：它天然避开空侧（概率为零的一侧不贡献代价），也天然在密度高的地方切得更细。

4.2 遍历：先近后远

光线追踪 给出的遍历是"两个子树都递归"。完整的版本有一个重要优化——有序遍历（ordered traversal）：

  1. 先与两个子节点的包围盒求交，得到各自的进入距离 tmint_{min}；
  2. 先访问近的一侧——近侧的命中点一定比远侧更近；
  3. 近侧返回后得到当前最近命中 thitt_{hit}，若远侧的 tmin>thitt_{min} > t_{hit}，远侧整棵子树直接跳过。
// 伪代码：BVH 有序遍历（与 [[光线追踪]] 基础版的差异在第三步）
bool intersect_bvh(const Ray& ray, const Node* node, Hit* hit)
{
    float tl, tr;
    bool inL = intersect_ray_aabb(ray, node->left ->box, &tl);
    bool inR = intersect_ray_aabb(ray, node->right->box, &tr);
    if (!inL && !inR) return false;

    const Node* first  = (inL && (!inR || tl <= tr)) ? node->left  : node->right;
    const Node* second = (first == node->left)                  ? node->right : node->left;
    float t_second = (first == node->left) ? tr : tl;

    bool hitAny = intersect_bvh(ray, first, hit);       // 先走近侧

    // 远侧的进入点已经比最近命中还远 -> 整棵远子树不可能更近，剪掉
    if (inR && inL && t_second < hit->t)
        hitAny |= intersect_bvh(ray, second, hit);

    return hitAny;
}

注：k-d tree 的空间严格不重叠，这个"先近后远 + 提前终止"是完备的——命中即停；BVH 子盒可能重叠，远侧无法彻底跳过，只能被 thitt_{hit} 裁剪。这是两者遍历效率此消彼长的根源。

4.3 动态场景：refit 与 rebuild

物体移动后，旧 BVH 的包围盒不再正确。两类应对：

  • Refit（重新拟合）：树结构不动，从叶到根重算每个节点的包围盒，一趟 O(n)O(n)。极快，但有退化效应——物体各自乱动后，节点的包围盒被迫"迁就"所有孩子，越长越松，查询效率持续下滑；
  • Rebuild（重建）：推倒重来，构建一棵全新的 SAH 树。质量最好，构建一次的代价不低。

实时应用（游戏、物理引擎）的常规打法是混合：每帧（或每物体移动时）refit，隔一段时间或检测到退化时 rebuild；更进一步的是渐进式重建——把重建工作切成小片，每帧做一片，摊平尖峰。BVH 能这么灵活，正是物体划分的红利：图元与节点的归属关系是"登记制"，包围盒松一点无伤正确性。k-d tree 没有这个待遇——空间划分一旦定死，物体一移动整个前提就塌了。

这也是 BVH 统治实时领域的根本原因：RTX 显卡上硬件光线追踪遍历的就是 BVH，游戏引擎的碰撞检测、剔除也几乎清一色 BVH 或八叉树。

4.4 紧凑表示：线性 BVH

树节点用指针连接，是 CPU 的习惯、GPU 的噩梦：指针无法搬上显存，且节点散布堆上，缓存行利用率低。线性 BVH 把树压进一个数组：

  • 节点按深度优先顺序连续排布；
  • 不存指针，左孩子固定是 当前下标 + 1，右孩子存一个 skip 偏移（跳过整棵左子树到达的位置）；
  • 叶节点不存图元列表，存图元数组的区间 [start, count)——图元重排成与叶节点一一对应的连续段。
深度优先排布（数字为数组下标）：
 0: 内部          左 = 1，右 = 4（skip 3）
 1: 内部          左 = 2，右 = 3（skip 1）
 2: 叶 [0, 2)     图元 0~1
 3: 叶 [2, 3)     图元 2
 4: 叶 [3, 5)     图元 3~4

数组： [0 内部][1 内部][2 叶][3 叶][4 叶]     ← 节点连续，无指针
图元： [t0 t1 | t2 | t3 t4]                   ← 与叶节点区间对应

一个节点可以压到 32 字节（AABB 六个 float + 两个索引 + 图元计数），整棵树就是一块连续显存。GPU 遍历用显式栈（数组模拟），跳过子树时直接 i += skip——RTX 的硬件遍历单元、诸离线渲染器的 GPU 后端，内核里都是这副模样。

5. 层次结构用在哪里

应用 查询内容 常用结构
光线追踪求交 光线 × 图元 BVH（实时 / GPU）、k-d tree（离线）
视锥 / 遮挡剔除 视锥六平面 × 物体 BVH、八叉树（见 剔除总结）
碰撞检测 broad phase 物体包围盒 × 物体包围盒 BVH、空间哈希（网格的哈希变体）
射线拾取（picking） 鼠标射线 × 物体 直接复用渲染 / 物理的 BVH
大规模粒子 点 × 邻域 均匀网格、空间哈希

值得注意的一点是结构复用：场景的 BVH 建一次，剔除、拾取、光追查询可以共用——它们本质上都是"空间里的东西跟一个查询体相交吗"。现代引擎的 GPU driven pipeline 更是把 BVH 搬上 GPU，剔除与求交在 compute shader 里并行完成。

6. 总结

结构 切什么 图元存储 构建 动态 典型场景
均匀网格 空间（均匀） 可能多份 免费 易 均匀小物体
八叉树 空间（八等分） 上浮或多份 中 难 稀疏剔除
BSP 空间（任意面） 可能切开 贵 不可 静态前后序
k-d tree 空间（轴对齐面） 可能多份 贵 不可 静态光追
BVH 物体集合 恰好一份 SAH 中等 refit / rebuild 几乎全部实时场景

选型的几条主线：

  1. 静态还是动态——静态可考虑 k-d tree 的极致查询效率；动态一律 BVH（或八叉树）；
  2. 分布均匀吗——均匀的小物体用网格/空间哈希更便宜；密度悬殊用层次结构；
  3. 查询多样吗——剔除、拾取、光追共用一棵 BVH，比各建各的划算。

所有这些结构背后是同一个想法：与其逐个回答"这个有没有可能命中"，不如把空间里的东西先分好堆，让一次否定剪掉一大片——把逐个检查变成成片排除。