包围体构建

AABB 与 k-DOP（22.3.1 节）

• AABB：沿每条轴取顶点的最小与最大值。
• k-DOP：把顶点投影到每条法线 $\mathbf{n}_i$，最小、最大投影值即 $d_i^{min}$、$d_i^{max}$，定义该方向最紧的平板；全部平板即最小 k-DOP。k 增大时 k-DOP 越来越接近凸包。

包围球（22.3.2 节）

嵌套子球时：子球半径相同则把球心当顶点处理，最后加上子半径；半径不同时在计算 AABB 和距离时把各自半径算进去。简化版 Ritter 只比基础版贵约 20%，但有时结果更差，两者都跑一遍取更好者是值得的。

凸多面体（22.3.3 节）

凸物体可用于分离轴测试。用任意平面集"收缩包裹"物体得到凸包，可削去更多体积，从而避免对内部网格做更昂贵的测试。Quickhull 等算法虽名为 quick，实际慢于线性时间，复杂模型通常离线预处理。凸包可能平面很多，可先生成简化（并可能向外扩张以完全包住原物体）的网格，得到精度较低但更简单的凸包。

OBB（22.3.4 节）

物体可能有"天然" OBB（AABB 经旋转得到），但未必最优：例如斜伸出建筑的旗杆，沿杆方向的 OBB 比 AABB 紧得多。没有明显最佳轴的模型，构建 OBB 比构建好的包围球更难。

• O'Rourke（1985）精确解：$O(n^3)$。
• Gottschalk：先求凸包（避免内部顶点影响结果），再用线性时间的主成分分析 (PCA) 求轴；缺点是有时较松。
• Eberly：采样若干方向作为起点，用 Powell 方向集法数值最小化体积。还有用遗传算法搜索的方法。
• Larsson 与 Källberg 近优法：不需要凸包、线性时间，质量通常优于 PCA、更快、适合 SIMD。

flowchart TD
  A["构建 k-DOP, 每个平板取一对触边顶点作为极值点"] --> B["最佳 OBB 初始化为 AABB"]
  B --> C["距离最远的一对极值点构成基三角形一边, 离该边最远的极值点为第三点"]
  C --> D["对三角形每条边: 边与面内法线定二轴, 投影极值点得二维矩形, 取最小者"]
  D --> E["沿三角形法线投影得高度, 生成完整 OBB 与 AABB 比较"]
  E --> F["高度最高与最低的两个极值点各与基三角形构成四面体, 新增 6 个三角形重复评估"]
  F --> G["共 7 个三角形中最佳 OBB, 用所有顶点扩展并再与 AABB 比较"]

如上图，26-DOP 会产生 13 对极值点（可能重复）。由于同一三角形的三个候选 OBB 高度相同，只需比较二维包围矩形即可选出最好的一个。作者倾向于按表面积而非体积优化，原因见几何概率（相交测试基础与分离轴）。

PBRT 的视角：AABB 的实现细节（PBRT 4e 3.7）

• 表示：pbrt 的 Bounds2/Bounds3 存最小角 pMin 和最大角 pMax 两个点（另一种是"一个角 + 三个边长"）；图像分块并行用 2D 整数包围盒，BVH 用 3D 浮点包围盒。
• 空盒：默认构造把 pMin 设为最大可表示数、pMax 设为最小可表示数，故意违反 pMin <= pMax，这样与空盒做 Union() 自然得到正确结果。
• 坑：Union() 要直接给结果的 pMin/pMax 赋值，不能把 Min()/Max() 的结果传给"两个角点"构造函数：构造函数会对坐标排序，把两个空盒的并集变成近乎无穷大的盒。
• 常用操作：交集取两盒 pMin 的最大值和 pMax 的最小值；重叠测试即三条轴上的区间都重叠；Inside() 与不含上边界的 InsideExclusive()（适合整数盒）；点到盒的平方距离逐轴取 $\max(0,\,pMin-p,\,p-pMax)$ 再平方求和；Corner(i) 用 $i$ 的低三位选角；Offset() 是 Lerp() 的逆；MaxDimension() 给出最长轴，供加速结构选分割轴。
• 包围球：BoundingSphere() 给出包住盒子的球，比直接包住原几何的球（上文 Ritter/Welzl 方法）松得多，但某些运算用球更方便，例如 球面几何与方向参数化 中的方向锥。
• "空"指体积为零，不一定表面积为零。