空间数据结构

总体分类（19.1 节）

• 空间细分型：BSP 树、八叉树把整个场景空间细分并编码，所有叶节点空间之和等于整个场景，叶节点通常不重叠（松散八叉树例外）。BSP 树多为不规则细分（分割面位置可任意），八叉树是规则细分（均匀分割），后者虽受限但常因此更高效。
• 包围型：BVH 不细分空间，只包住几何体周围的区域，每层不必覆盖整个空间。
• 构建可能很贵，取决于几何量和期望质量；近年的进展让某些情况下可以实时构建，延迟求值和增量更新还能进一步降低构建时间。

包围体层次 BVH（19.1.1 节）

包围体 (BV) 是比所含物体简单得多的形状（球、AABB、OBB、k-DOP），本身不参与显示，只作为代理加速渲染、拾取、查询。BVH 中每个节点的 BV 包住其整棵子树的几何体，根节点的 BV 包住整个场景；实践中常"自底向上"构建，让父 BV 包住子 BV（对球来说，直接包子树几何体会更紧但更贵）。

BSP 树（19.1.2 节）

用平面把空间一分为二并递归。按特定方式遍历，可从任意视点把内容由前到后排序：轴对齐 BSP 是近似排序，多边形对齐 BSP 是精确排序。

• 轴对齐 BSP（k-d 树）：场景先被一个 AABB 包住，每层选一条轴，用垂直平面分割。分割面固定在中点叫均匀细分（节点内存位置由树中位置隐式决定），可变位置叫非均匀细分（树更平衡）。跨越分割面的物体可以：存在当前层（只有一份拷贝、删除简单，但小物体会卡在上层，低效）；放进两个子节点（大物体包围更紧）；或真正切成两份。遍历时先走视点所在一侧，得到粗略的前到后顺序，可用于遮挡剔除和减少过度绘制；反过来先走另一侧得到粗略的后到前顺序，用于透明排序；把视点换成光线起点即可做光线测试。
• 多边形对齐 BSP：选一个多边形，用它所在平面把其余多边形分成两组，被平面穿过的多边形切成两块，递归直到所有多边形入树。构建耗时，通常离线计算一次并存储，最好平衡。它能对静态/刚体几何给出严格的遮挡顺序：先判断相机在根平面哪一侧，另一侧的集合整体在后面，递归即可得到严格的后到前序，从而可用不需要 z-buffer 的画家算法。早年没有硬件 z-buffer 时在游戏中流行，如今偶尔用于碰撞检测与相交测试。注意它给出的是遮挡顺序而不是距离顺序：遮挡顺序更靠后的多边形可能离视点更近。

八叉树与松散八叉树（19.1.3 节）

八叉树同时沿三轴在盒子中心分割出 8 个等大子盒，递归终止条件可以是最大深度或盒内图元数。二维版本是四叉树，适合沿第三轴分类没什么好处的场合。八叉树不需要存分割面位置，存储更紧凑、遍历访问的内存更少；但轴对齐 BSP 有时因分割面放得更好而更快——没有总体最优的方案，取决于几何特性、访问模式和硬件，往往内存布局的局部性和缓存友好程度最重要。

只在叶节点存物体会导致物体被存进多个叶节点；改为放进"能完整容纳它的最小盒子"又会让位于中心的小物体被放进根节点。松散八叉树 (loose octree) 把边长 $l$ 的盒子放大为 $kl$（$k>1$），中心不变，使跨越分割面的物体变少、能放得更深。每个物体只插入一个节点，删除很简单。取 $k=2$ 时插入与删除都是 $O(1)$：由物体大小即可知道它能完整放入哪一层（由质心决定放进哪个盒子）；$k<2$ 时物体可能需要上移。它适合包围动态物体，代价是 BV 效率下降、失去强排序；物体逐帧移动很少时原盒子往往仍然有效，所以每帧只需更新少数动画物体。分配完成后可再给每个节点算一个紧 AABB，实际上就变成了 BVH，同时避免把物体切到多个节点。

缓存感知与缓存无关表示（19.1.4 节）

内存带宽与 CPU 算力差距逐年增大，数据结构必须考虑缓存。

• 缓存感知 (cache-aware)：已知缓存块大小（如 64 字节）时尽量压缩节点。例如 k-d 树节点只用 32 位：最低 2 位表示叶节点或三种分割轴之一，高 30 位对叶节点是物体列表指针、对内部节点是精度略低的浮点分割值，于是一个 64 字节缓存块能放下 4 层深、15 个节点的二叉树，第 16 个槽记录子节点的存在与位置。
• 缓存无关 (cache-oblivious)：对任意缓存大小都表现良好、与平台无关。van Emde Boas 布局递归地在一半高度 $\lfloor h/2 \rfloor$ 处切树：上半部分为 $T_0$，从 $T_0$ 叶节点出发的子树为 $T_1,\dots,T_n$，每棵子树再按同样方式递归，直到只剩单节点：

递归切分到某一层时，一组相邻子树恰好装进缓存，比自上而下逐层列出所有节点的跳跃式访问好得多。一般而言缓存无关布局分两步：聚类与簇排序。Yoon 等人针对 BVH 和 BSP 树用概率模型同时考虑父子局部性与空间局部性，贪心地聚类，只改变节点顺序就获得可观的性能提升。

场景图（19.1.5 节）

场景图（glTF 中叫节点层次）是面向用户的树，除几何外还挂载纹理、变换、LOD、渲染状态（材质）、光源等。例如光源放在内部节点只影响其子树；材质作用于子树并可被子节点覆盖。

• 层次动画：改变内部节点的变换即可变换整棵子树，如车轮自转、整车前进。
• 实例化与 DAG：多个节点指向同一子节点时成为有向无环图，可在不复制几何的情况下放置多个实例，节省内存，GPU 也能用实例化 API 快速绘制。
• 更新：变换从根向叶传播、矩阵相乘后存储在节点里；变换改变后 BV 失效，需从叶向根回传更新。过于松散的结构会让这些更新极其复杂，所以常避免 DAG，或只允许共享叶节点。基于 JavaScript 的 API（如 WebGL）中尤其要把尽量多的工作搬到 GPU、减少回读到 CPU。
• 空间化 (spatialization)：场景图节点通常有 BV，本身就像 BVH；还可以在用户场景图之外另建一个专门用于剔除或拾取的结构（BSP 树或 BVH），由于叶节点（大部分模型所在）是共享的，额外开销相对较低。

下图概括各结构的关系与主要用途：

flowchart TD
  A["空间数据结构"] --> B["空间细分"]
  A --> C["包围型: BVH"]
  A --> D["场景图: 模型关系, 变换, 状态"]
  B --> E["轴对齐 BSP / k-d 树: 粗略前后序"]
  B --> F["多边形对齐 BSP: 严格遮挡序"]
  B --> G["八叉树 / 四叉树: 规则细分"]
  G --> H["松散八叉树: 动态物体 O1 插入"]
  C --> I["视锥剔除, 光线求交, 碰撞检测"]
  D --> J["空间化: 另建 BVH 或 BSP 加速剔除"]

如上图：细分型结构擅长排序与区域查询，BVH 擅长剔除和求交，场景图负责组织内容，必要时用"空间化"与专用加速结构配合。

取舍小结

• 层次结构让查询更快，但构建与更新有代价；动态物体多时宜选松散八叉树、BVH refit 或时间包围体。
• 一些游戏引擎干脆不用层次 BVH，只对每个物体存一个 BV 组成线性列表，更容易用 SIMD 和多线程实现（见 剔除技术）。
• 没有万能结构，内存布局和缓存行为往往比理论复杂度更关键。

GEA 的视角：作为"场景图"的空间划分（卷 II 11.5.3）

• 为什么需要：大多数几何不在视锥内，逐个做视锥剔除非常浪费。理想的数据结构能快速丢掉远离视锥的大片区域，还能帮助排序几何（为 z 预通道从前往后，或为完整着色按材质）（卷 II 11.5.3）。
• 名称：这类结构常叫场景图，源自影视渲染器和 Maya 等 DCC 工具中的图结构；但游戏的场景图不一定是图，通常是某种树。例子有四叉树、八叉树、BSP 树、kd 树和空间哈希。注意这与本页「场景图」一节（RTR4 19.1.5，指带变换、材质等的层次结构）不是同一个概念：GEA 这里说的是用于剔除和排序的空间划分。
• 四叉树/八叉树：递归分成四个象限（通常用竖直、轴对齐的平面，象限为正方形或矩形，也可以是任意形状），图元存在叶子上，按区域内图元数决定是否继续细分，使每个叶子的图元数大致均匀。可存网格实例、地形子区域或大型静态网格的单个三角形。从根往下检查各区域是否与视锥相交，不相交就停止遍历该分支，通常 $O(\log n)$。八叉树是三维版本，每层分八份（卷 II 11.5.3.1）。
• BSP 树：每层用一个平面把空间一分为二，平面常取场景中某个三角形所在平面；与平面相交的三角形被切成三个新三角形（GEA 的说法；严格说，平面恰好穿过一个顶点时只切成两个），使每个三角形完全在前、完全在后或与平面共面。kd 树是 BSP 思想在 k 维上的推广（卷 II 11.5.3.2）。
• BSP 的后向前遍历：从根开始，相机在节点平面前方时，先访问背面子树，再画与平面共面的三角形，最后访问正面子树；在后方时反过来。这样得到严格的后向前顺序，与相机朝向无关，还需另做视锥剔除。GEA 说早期没有 z-buffer 的《Doom》靠它实现画家算法（见 光栅化 中的画家算法）。
  • 原书问题：《Doom》的 BSP 划分的是二维地图上的线段（linedef 被切成 seg），不是三角形；墙壁渲染也是从前往后：遍历 BSP 时先画离相机近的子扇区，用已画墙段的屏幕列遮挡表裁掉后面的墙，整列填满后就不再画，从而避免过度绘制；只有精灵 (sprite) 才按从远到近排序绘制（Wikipedia「Doom engine」Binary space partitioning / Drawing the walls 两节；Fabien Sanglard《Game Engine Black Book: DOOM》）。所以《Doom》用 BSP 得到的是前到后顺序加遮挡裁剪，而不是画家算法。
• BVH：像四叉树/八叉树一样层次地划分空间，GEA 在卷 II 12.6.5.2 结合光线追踪详细讨论，并指出它也可作为光栅化引擎的场景图（卷 II 11.5.3.3）。

这些与本页 RTR4 的 BVH、BSP 树、八叉树各节一致，GEA 更侧重渲染引擎应用层的用法。

GEA 第 12 章的补充：用于光线投射的 BVH（卷 II 12.6.5.2、12.9.3）

• GEA 从光线投射效率的角度介绍 BVH：给每个三角形包上球或 AABB 等更容易做相交测试的包围体，只有包围体测试通过才做更贵的光线-三角形测试；再把固定数目的相邻包围体逐层合并成树，直到整个场景只有一个根包围体（卷 II 12.6.5.2）。
• 投射时从根开始，只访问包围体测试通过的子树，到叶子才测三角形。暴力算法复杂度 $O(RT)$（$R$ 条光线、$T$ 个三角形），用 BVH 降到 $O(R\log T)$，加上光线-包围体测试本来就比光线-三角形测试便宜，总成本显著下降。
• 好的 BVH：包围体紧贴几何、占内存小、测试快；每棵子树体积尽量小，兄弟节点重叠尽量少；树要平衡，使每一步都能剪掉尽量多的几何；构建时要在分支度（每节点子数）与高度之间取舍。这与本页「包围体层次 BVH」一节的要求一致。
• 静态关卡几何的 BSP 树、四叉树、八叉树、包围球层次以及光追用的 TLAS/BLAS，通常都在资产调理阶段生成（卷 II 12.9.3）。

GEA 第 14 章的补充：碰撞检测中的空间划分（卷 II 14.3.6）

• 物体多时暴力两两测试是 $O(n^2)$，所以碰撞引擎用空间哈希、空间细分或层次包围体减少测试对数（卷 II 14.3.6）。
• 八叉树、BSP 树、kd 树、球树等层次结构的作用在于：沿一个分支向下时，该分支中的对象不可能与兄弟分支中的对象碰撞（卷 II 14.3.6.2）。
• 宽相常用扫描剪除，它不是树结构，而是沿三条主轴对 AABB 端点排序，再利用帧间相干性（卷 II 14.3.6.3）。
• 与本页（RTR4，渲染视角）不同，GEA 在这里关心的是碰撞对筛选。详见 碰撞检测系统。

PBRT 的视角：离线光线追踪器里的 BVH（PBRT 4e 第 7 章）

RTR4 和 GEA 从实时渲染与碰撞的角度讲 BVH；PBRT 给出一个完整的 CPU 离线实现 BVHAggregate，重点在构建算法的选择（中点 / 等数量 / SAH / HLBVH）、扁平化内存布局和无递归遍历。GPU 路径不用这些类，直接交给硬件光追 API（见 硬件光线追踪管线）。

Primitive 与聚合体：元层次结构（7.1–7.2）

• Shape 只管几何；Primitive 接口只有三个方法 Bounds()、Intersect()、IntersectP()，在此之上绑定材质、面光源、两侧介质和 alpha 纹理（GeometricPrimitive）。不需要这些属性的物体用 SimplePrimitive，每个省 32 字节。
• 聚合体 (aggregate) 本身也实现 Primitive 接口，所以 BVH 里可以装 BVH、装实例。这就是 Kirk 与 Arvo（1988）提出的元层次结构 (meta-hierarchy)：加速结构和图元共用一个接口，可以随意混搭。聚合体的求交方法不设置材质等信息，留给真正被击中的图元。
• 两大类方法：空间细分（网格、kd 树：把空间划成区域，图元可能出现在多个区域、被重复测试）与物体细分（BVH：每个图元在层次中只出现一次）。PBRT 认为二者没有根本优劣；BVHAggregate 是默认，KdTreeAggregate 只放在网络版里。
• 实例化：TransformedPrimitive 存一个 Primitive 加一个变换，把射线变到实例空间再求交，交点变回渲染空间；$t$ 值不需修正（变换不归一化方向）。书中的生态场景：31 种植物模型、23,241 株，总计 31 亿三角形，内存中只有 2400 万，渲染约 4 GB（BVH 1.7 GB + Primitive 707 MB + 网格 877 MB + 纹理 846 MB，合计 4.13 GB），不用实例化需 516 GB 以上。（脚注：上一版 pbrt 渲染同一场景要 7 GB，差别主要来自更省内存的 Primitive 表示、去掉每个 Shape/Primitive 的虚函数指针，以及 8 位纹理不再一律存成 32 位浮点。）AnimatedPrimitive 用 AnimatedTransform（696 字节，对比 Transform 的 128 字节）实现刚体运动模糊，所以只给真正运动的物体用。

BVH 的基本性质（7.3）

• 每个叶存 1 个图元的二叉 BVH 共 $2n-1$ 个节点（$n$ 个叶 + $n-1$ 个内部节点），内存有上界；kd 树没有这个保证。
• PBRT 认为 BVH 比 kd 树构建更快，而且数值上更鲁棒，不容易因舍入误差漏掉交点，因此作为默认。

构建：三个阶段（7.3.1）

1. 为每个图元算 AABB 和质心，存成 BVHPrimitive 数组；
2. 按 splitMethod 递归建一棵带指针的二叉树（BVHBuildNode），叶节点引用重排后 orderedPrims 数组中一段连续区间，因此叶节点只要存"起始偏移 + 数量"；
3. 扁平化为紧凑的 LinearBVHNode 数组。

划分轴的选择：只取质心包围盒最长的轴（不三轴都试）。若所有质心重合（质心包围盒体积为 0），直接建叶。两棵子树互不依赖，图元足够多时用 ParallelFor 并行构建；叶节点向 orderedPrims 申请空间用原子 fetch_add（见 多线程渲染与任务系统）。节点内存用 pmr::monotonic_buffer_resource，每线程一个；作者实测改用默认分配器会多约 10% 内存、慢约 10%。

表面积启发式 SAH（7.3.2）

直接建叶的代价是 $\sum_{i=1}^{n} t_{\text{isect}}(i)$；划分成 $A$、$B$ 两个子节点的代价是 $c(A,B)=t_{\text{trav}}+p_A\sum_{i=1}^{n_A}t_{\text{isect}}(a_i)+p_B\sum_{i=1}^{n_B}t_{\text{isect}}(b_i)$ 其中 $p_A,p_B$ 用几何概率估计：凸体 $A\subset B$ 时，穿过 $B$ 的均匀随机射线也穿过 $A$ 的条件概率为 $p(A\mid B)=s_A/s_B$（表面积之比，与 相交测试基础与分离轴 中"击中概率正比于表面积"是同一结论）。

PBRT 的实现细节：

• 假设所有图元求交代价相同，取 $t_{\text{isect}}=1$、$t_{\text{trav}}=1/2$。作者说明这个 2:1 是故意低估两者的真实差距：图元求交除了计算外还有两次以上动态分派、填 SurfaceInteraction、可能的变换插值；而遍历代价设得更低会让树更深、节点更多、缓存未命中更多。
• 只有 12 个桶，桶边界给出 11 个候选；前向扫描、后向扫描各一次，线性时间算出所有候选代价。（脚注：旧版 pbrt 对每个候选从头计算，是 $O(n^2)$；即便桶数很小，改成两次扫描后 BVH 构建也快了约 2 倍。）比较时省略 $t_{\text{trav}}$ 和除以 $s$（不影响选哪个），最后才换算成真实代价与叶代价 $n$ 比较。
• 剩下两个图元时直接对半分；若最优划分的代价不低于建叶代价，且图元数不超过 maxPrimsInNode，就建叶。

数值例（自行计算验证公式）：一个节点有 8 个图元，某划分得到两个各含 4 个图元、表面积均为父节点 60% 的子盒，代价 $0.5+0.6\times4+0.6\times4=5.3<8$，应划分；若子盒都占 95%，代价 $0.5+3.8+3.8=8.1>8$，应建叶。

HLBVH（7.3.3）

SAH 的两个缺点：要多遍扫描图元；自顶向下构建在顶层几层几乎没有可并行的工作（对 GPU 尤其糟）。LBVH 把构建变成排序问题：

• 质心在场景质心包围盒内归一化到 $[0,1]$，每轴乘 $2^{10}$ 量化为 10 位整数，交错成 30 位莫顿码（见 莫顿码与空间填充曲线），塞进 32 位整数；
• 基数排序：每遍 6 位，5 遍排完 30 位（作者实测比标准库 std::sort 快）；
• 莫顿码高 12 位相同的图元归为一簇，相当于 $2^{12}=4096$ 个网格单元、每轴 $2^4=16$ 格；每簇并行建一个"小树 (treelet)"，自高位向低位逐位按中点划分（等价于 Middle），用二分查找找到该位从 0 变 1 的位置；若首尾图元该位相同则跳过这一位。数组无需复制或重排；
• 起始位是 $29-12$：第 30 位的零基下标是 29，高 12 位已用于聚类；
• 各小树的节点计数先累加到局部变量，每个小树结束时才更新一次原子 totalNodes，避免多核缓存一致性开销；
• 最后对所有小树根（通常几十到几百个，最多 4096 个）用 SAH 建顶层，耗时很少。

扁平化与遍历（7.3.4–7.3.5）

• 深度优先布局：第一个子节点紧跟父节点，只需存第二个子节点的偏移。LinearBVHNode 是 Bounds3f（24 字节）+ 偏移（4 字节）+ 图元数 uint16_t + 划分轴 uint8_t，补齐到 32 字节并按 32 字节对齐，保证一个节点不跨两条缓存行（另见 C++ 内存布局与对齐）。每图元最多 2 个节点，即每图元至多 64 字节开销。
• 遍历不用递归：显式栈 nodesToVisit[64]。叶节点逐个测图元，命中就缩短 tMax，后面更远的节点会被射线-盒测试直接剔除。
• 近子节点优先而不必两个子盒都求交：看射线方向在该节点划分轴上的分量符号，为负则先访问第二个子节点（它的图元在划分点上侧）。
• IntersectP() 找到任意交点即返回。

与 RTR4/GEA 的分歧与对照

原书问题

• 7.3.1 划分方案数：书中写"$n$ 个图元划分成两个非空组，一般有 $2^{n-1}-2$ 种方式"（已解码网页 SVG 字形确认是 $2^{n-1}-2$，非 MathJax 语音文本的误读）。正确数目是 $2^{n-1}-1$（有序划分为 $2^n-2$，无序再除以 2）。$n=2$ 时显然只有 1 种，而原式给出 0；对 $n=2..6$ 穷举得 1, 3, 7, 15, 31，与 $2^{n-1}-1$ 一致。在 pbr-book-website 与 pbrt-v4 的 issue 中未找到此条。
• 7.3.2 "所有 $2n$ 种可能的划分"：沿一条轴按质心排序后只有 $n-1$ 个划分位置（三轴约 $3n$，与 7.3.1 自己的说法一致），这里的 $2n$ 不精确（SVG 解码确认原文为 $2n$）。
• 7.3.3 莫顿码区间：书中说图 7.9(a) 对应索引区间 $[8,15]$、图 7.9(c) 对应 $[8,11]$。对 8 位莫顿码穷举，$y\ge8$ 的码在 $[128,255]$，$y\ge8$ 且 $x<8$ 的码在 $[128,191]$；只有取高 4 位（$y_3x_3y_2x_2$）当索引时才是 $[8,15]$ 和 $[8,11]$。属于表述歧义。
• 延伸阅读的参考文献：正文"Cline 等（2006）提出更紧凑的 BVH 节点表示（量化包围盒、隐式索引 $2i$/$2i+1$）"，文献表对应条目却是同年同作者的另一篇《Two stage importance sampling for direct lighting》。应为 Cline, Steele, Egbert,《Lightweight Bounding Volumes for Ray Tracing》, Journal of Graphics Tools 11(4):61–71, 2006（https://doi.org/10.1080/2151237X.2006.10129226）。顺带一提，该文也把自己的结构叫 LBVH，与 Lauterbach 等（2009）的 Linear BVH 同名但不同物。
• 文献表 "Walter, B., K. Bala, M. Kilkarni, and K. Pingali. 2008" 的第三作者应为 Milind Kulkarni（见论文首页 https://www.cs.cornell.edu/~kb/publications/IRT08.pdf）。
• 文献表 "Hunt, W., and B. Mark. 2008b. Adaptive acceleration structures in perspective space ... 111–17" 页码有误，应为 11–17（Crossref，https://doi.org/10.1109/RT.2008.4634614；第 3 版写作 "117–17"，也是错的）。
• 网络版 7.1.2 节出现未解析的交叉引用 "Figure fig:spinning-spheres"（排版残留）。