相交测试基础与分离轴

GPU 加速拾取（22.1 节）

• 需要某点或区域内所有物体（不论是否可见）：在 CPU 上从像素生成穿过近远平面的光线（矩形区域则生成视锥），用 BVH 测试。缺点：千级三角形网格逐三角形测试昂贵；位移贴图或 GPU 细分生成的几何需要在 CPU 上匹配；alpha 贴图（如树叶）的全透明纹素不应被选中，CPU 模拟纹理访问工作量大。
• 只需可见物体：用 GPU 管线本身。每个三角形、多边形或网格以唯一 ID（可视为颜色）渲染到离屏目标，点击时直接查表，思路与可见性缓冲相近；可在常规渲染时用简单着色器顺便写入单独渲染目标，主要开销是从 GPU 读回像素。还可存法线、纹理坐标；把三角形三个顶点分别着色为纯红、纯绿、纯蓝，插值后的颜色除以 255 就是重心坐标。
• 相机静止时（如三维绘画系统）拾取缓冲可复用；相机运动时可用离轴相机把屏幕极小区域渲染到如 3×3 的小目标，CPU 视锥剔除几乎去掉全部几何，代价很小；要拾取所有物体可配合深度剥离或不再渲染已选物体重复几次。

基本定义（22.2 节）

• 光线：$\mathbf{r}(t)=\mathbf{o}+t\mathbf{d}$，$\mathbf{d}$ 通常归一化，$t<0$ 在原点之后。实践中常保存当前最大搜索距离 $l$（初值 $\infty$），找到交点后更新，光线就变成线段。
• 隐式曲面 $f(\mathbf{p})=0$（如球 $p_x^2+p_y^2+p_z^2-r^2=0$）；显式曲面由参数生成点，如三角形 $\mathbf{t}(u,v)=(1-u-v)\mathbf{v}_0+u\mathbf{v}_1+v\mathbf{v}_2$，$u,v\ge0$，$u+v\le1$。

更复杂的 k-DOP 和凸多面体主要用于碰撞检测，额外的平面能削掉更多空体积，从而避免昂贵的网格精确求交。

分离轴测试 SAT

分离轴：两个不重叠物体在其上的投影区间也不重叠的直线；两物体之间能插入的平面，其法线就是分离轴。（常被称为"分离轴定理"，书中指出这是误称，它是分离超平面定理的特例。）

对任意两个凸且分离的多面体 A、B，至少存在一条分离轴；并且分离轴一定可以取为垂直于（即分隔平面平行于）以下之一：

1. A 的某个面；
2. B 的某个面；
3. 来自两者各一条边的叉积。

凹物体不成立：井壁与井中的桶不接触，但没有平面能分开它们。前两类说明一个物体完全位于另一个物体某个面的外侧；第三类是因为分隔平面贴近两物体时最多只能贴到边上。线段和三角形是退化的凸多面体（线段没有面，第一类测试消失）。时间相干优化：本帧找到的分离轴存下来，下一帧对同一对物体先测它。

flowchart LR
  A["候选轴: A 的面法线"] --> D{"投影区间分离?"}
  B["候选轴: B 的面法线"] --> D
  C["候选轴: 边 x 边"] --> D
  D -- "任一轴分离" --> E["不相交, 立即返回"]
  D -- "所有轴都重叠" --> F["相交"]

其他通用技巧

• 拒绝测试：先做能尽早判定"不相交"的简单计算。
• 降维：把三维问题投影到"最佳"坐标平面（xy、xz 或 yz）在二维中求解。
• epsilon：数值误差需要极小数 $\epsilon$，取值因测试而异；常见做法是选一个对自己问题有效的值（"方便的虚构"），换个场景可能失效。书中给出的 epsilon 仅作为"正常"数据（规模约 0.1～100、靠近原点）的起点。

几何概率（22.4 节）

• 随机点落在物体内的概率与体积成正比（1×2×3 的盒是 1×1×1 的 6 倍）。
• 任意方向光线击中凸物体的概率与表面积成正比：凸体的平均正交投影面积是其表面积的四分之一（球：投影 $\pi r^2$、表面积 $4\pi r^2$）；双面多边形的平均投影面积是面积的一半。这就是光线追踪中构建加速结构所用的表面积启发式 (SAH)。例：球被光线击中的相对概率是其内接立方体的 $\pi/2\approx1.57$ 倍；立方体是其内切球的 $6/\pi\approx1.91$ 倍。可用于 LOD：包围球相同但细长的物体覆盖像素更少，视觉重要性较低。
• 平面与盒相交的概率与盒三个维度之和（平均宽度）成正比：1×2×3 的盒（6）比单位立方体（3）被任意平面切到的概率高一倍。乘以 0.5 得到可与球直径比较的几何平均宽度：单位立方体为 1.5，其外接球直径 $\sqrt3\approx1.732$，因此外接球被平面切到的概率是立方体的 1.155 倍。视锥剔除和 BSP 分割位置选择都可参考这些关系。

由于光线命中概率与表面积相关，求交加速应最小化 BV 表面积；碰撞检测则通常更适合最小化体积（见 包围体构建）。

经验法则（22.5 节）

1. 尽早做可能平凡拒绝或接受的计算。
2. 复用之前测试的结果。
3. 多个拒绝/接受测试时尝试调整顺序，看似小的改动也可能有影响。
4. 推迟昂贵运算（三角函数、开方、除法）直到真正需要。
5. 尽量降维（三维到二维甚至一维）。
6. 一条光线或一个物体与许多对象比较时，寻找可预先计算一次的量。
7. 测试昂贵时先用球或其他简单 BV 做第一级快速拒绝。
8. 养成在自己机器上、用真实数据和场景计时比较的习惯。
9. 利用上一帧结果（如上一帧的分离轴）。
10. 让代码健壮：处理所有特殊情况，尽量不受浮点误差影响，并清楚它的局限。

没有某个测试的"最佳"算法：随机数据加预设命中率只能说明部分事实，应在真实场景（如游戏中）用尽量多的测试场景评估；GPU 和宽 SIMD 实现可能因多个拒绝分支都要执行而变慢。

GEA 的视角：碰撞引擎中的分离轴与 GJK（卷 II 14.3.5）

• SAT 的定位：GEA 把分离轴定理当作碰撞引擎中大多数相交测试的基础。凸形状在某条轴上的投影区间不重叠，它们就不相交；找不到这样的轴就一定相交。凹形状不满足这一点，这是碰撞引擎偏好凸形状的原因之一。两球即将接触时，唯一的分离轴平行于球心连线；分得越开，可选的轴越多（卷 II 14.3.5.3）。
• GJK：适用于任意凸多面体。两个凸形状的闵可夫斯基差包含原点，当且仅当两者相交。算法朝原点方向反复取差的凸包上的支撑顶点，把单纯形（点 → 线段 → 三角形 → 四面体）扩充到包住原点（相交），或者找不到更靠近原点的支撑点为止（不相交）。GJK 受欢迎还因为它用一个算法覆盖所有凸形状，只有支撑函数因形状而异，可以缓解 N 种形状需要 $O(N^2)$ 种两两测试的问题（卷 II 14.3.5.5–14.3.5.6）。
• 本页（RTR4）侧重 SAT 的数学和具体候选轴，GEA 侧重它在碰撞引擎中的角色，两者互补。详见 碰撞检测系统。

PBRT 的视角：SAH 在 BVH 构建中的用法（PBRT 4e 7.3.2）

上文的几何概率结论在 PBRT 中写成条件概率形式：凸体 $A$ 包含于凸体 $B$ 时，穿过 $B$ 的均匀随机射线也穿过 $A$ 的概率 $p(A\mid B)=s_A/s_B$。这和"平均投影面积 = 表面积/4"是同一回事：两者的投影面积之比等于表面积之比。PBRT 用它估计子节点被访问的概率，代价模型为 $c(A,B)=t_{\text{trav}}+p_A n_A t_{\text{isect}}+p_B n_B t_{\text{isect}}$（假设图元求交代价相同），取 $t_{\text{isect}}=1$、$t_{\text{trav}}=1/2$，并用 12 个桶近似搜索最优划分。完整实现与数值例见 空间数据结构 的 PBRT 小节。

延伸阅读里的提醒：SAH 假设射线在空间中均匀分布，而实际射线大多从表面或相机、光源出发；Aila 等（2013）指出 SAH 代价更高的树有时反而更快，并为此提出了补充指标。