附录 A 几何测试 (Geometric Tests)

核心结论

几何测试 = 多图元之间的最近点 / 相交判定：每个测试有明确输入、输出、几何意义；本章是工程参考手册。
最近点计算：点 → 线 / 射线 / 平面 / 圆 / 球 / AABB 的最近点；用于碰撞响应、布料锚定、AI 路径。
相交测试：线 / 射线 / 平面 / 球 / AABB / 三角形之间的相交；用于碰撞检测、可见性、拾取。
算法选择依赖图元类型与查询频率：高频查询用 AABB / 球（O(1)），精确查询用三角形（O(n)）；粗筛 + 细判是常用模式。
数值精度：除零保护（点积接近 0 时退化为其他情况）、浮点 epsilon 比较、min / max 钳制。

本章主旨

附录 A 是"几何 cookbook"——18 个常用的最近点与相交测试。每个测试给出几何意义、关键公式、C 代码骨架。读者应能"按图索骥"：遇到具体需求时（如"射线 vs AABB"）直接找到对应小节。完整代码与更多测试见 http://www.realtimerendering.com/intersections.html。

一、核心概念

本章围绕 4 个核心概念展开：最近点计算、相交测试、算法选择、数值精度。

概念定义 + 重要性实现提示

概念	定义 + 重要性	实现提示
最近点计算 (closest point)	给定点到某图元的最近点；用于碰撞响应（最小位移）、布料锚定、AI 路径追踪。	A.1-A.5；公式简洁，是相交测试的前置步骤。
相交测试 (intersection)	两图元是否相交 / 相交点位置；用于碰撞检测、可见性、拾取、阴影。	A.6-A.18；分线 / 射线 / 平面 / 球 / AABB / 三角形几大类。
算法选择	高频查询用 AABB / 球（O(1)），精确查询用三角形（O(n)）；粗筛 + 细判是常用模式。	选择图元影响性能；BVH / 八叉树用 AABB 粗筛。
数值精度	除零保护、浮点 epsilon 比较、min / max 钳制；bug 来源多在边界条件。	物理引擎常设 epsilon = 10⁻⁶；AABB 比较用 `<` 而非 `≤` 避免边界重叠。

最近点计算 (closest point)

给定点到某图元的最近点；用于碰撞响应（最小位移）、布料锚定、AI 路径追踪。

A.1-A.5；公式简洁，是相交测试的前置步骤。

相交测试 (intersection)

两图元是否相交 / 相交点位置；用于碰撞检测、可见性、拾取、阴影。

A.6-A.18；分线 / 射线 / 平面 / 球 / AABB / 三角形几大类。

算法选择

高频查询用 AABB / 球（O(1)），精确查询用三角形（O(n)）；粗筛 + 细判是常用模式。

选择图元影响性能；BVH / 八叉树用 AABB 粗筛。

数值精度

除零保护、浮点 epsilon 比较、min / max 钳制；bug 来源多在边界条件。

物理引擎常设 epsilon = 10⁻⁶；AABB 比较用 < 而非 ≤ 避免边界重叠。

二、详细笔记

2.1 最近点计算 (Closest Point Computations)

What：给定点 q 到某图元 L 的最近点 q'；用于碰撞响应（最小位移推开）、AI 路径（沿曲面滑动）。

Why：几乎所有碰撞响应都基于"最小位移"——把物体沿最小向量推到不重叠位置；布料 / IK 把顶点"贴"到约束面。

How：

最近点计算总览（表 A.1）：

图元关键公式

图元	关键公式
2D 隐式线	`q' = q + (d - q·n̂)n̂`
2D / 3D 射线	`t = d̂·(q - porg); q' = clamp(t, 0, l)`
平面	`q' = q - (q·n̂ - d)n̂`
圆 / 球	`q' = c + r(q - c)/
q -	`
AABB	`q'[i] = clamp(q[i], pmin[i], pmax[i])`

2D 隐式线

q' = q + (d - q·n̂)n̂

2D / 3D 射线

t = d̂·(q - porg); q' = clamp(t, 0, l)

平面

q' = q - (q·n̂ - d)n̂

圆 / 球

`q' = c + r(q - c)/

q -

AABB

q'[i] = clamp(q[i], pmin[i], pmax[i])

最近点的"投影"几何意义

最近点 = q 在图元上的投影。
投影方向：对于线 / 平面 / 球 = 法线方向；对于射线 = 方向向量。
"最近点"既给位置也给距离：dist = |q - q'|，用于穿透深度。

When：碰撞响应（推开物体）；布料约束；IK 解算；AI 路径约束（沿曲面滑动）。

Example：物体 q = (1, 0, 5) 在 xz 平面（n̂ = (0, 1, 0), d = 0）的最近点 = (1, 0, 5) - (0 - 0)(0, 1, 0) = (1, 0, 5)（已在平面上）。

2.2 相交测试 (Intersection Tests)

What：两图元是否相交 / 相交点位置；用于碰撞检测、可见性、拾取、阴影。

Why：物理引擎每帧做上千次相交测试；游戏拾取（鼠标点 → 物体）依赖射线 vs 三角形。

How：

相交测试总览（表 A.2）：

测试关键思路

测试	关键思路
两 2D 隐式线	联立线性方程组
两射线（3D）	最短距离（§2.11）
射线 vs 平面	代入参数 t 解 `n·P(t) = d`
AABB vs 平面	平面法向量最大 box corner
三平面	联立线性方程组 / Cramer 法则
射线 vs 球	二次方程 `
P(t) -	² = r²`
两球	中心距 vs 半径和 / 差
球 vs AABB	AABB 上最近点 vs 球心
球 vs 平面	球心到平面距离 vs 半径
射线 vs 三角形	Möller-Trumbore 算法
两 AABB	三轴独立比较
射线 vs AABB	slab method

两 2D 隐式线

联立线性方程组

两射线（3D）

最短距离（§2.11）

射线 vs 平面

代入参数 t 解 n·P(t) = d

AABB vs 平面

平面法向量最大 box corner

三平面

联立线性方程组 / Cramer 法则

射线 vs 球

二次方程 `

P(t) -

² = r²`

两球

中心距 vs 半径和 / 差

球 vs AABB

AABB 上最近点 vs 球心

球 vs 平面

球心到平面距离 vs 半径

射线 vs 三角形

Möller-Trumbore 算法

两 AABB

三轴独立比较

射线 vs AABB

slab method

"粗筛 + 细判"的性能模式

粗筛：AABB / 球 vs AABB / 球（O(1) 或 O(log n)）。
细判：三角形 vs 三角形（O(n²) 或 BVH）。
现代物理引擎（PhysX / Bullet）：两层 BVH（粗筛 + 细判），每帧 ~10⁵-10⁶ 次测试。

When：碰撞检测；拾取（射线 vs 三角形网格）；shadow ray；可见性判定。

Example：Möller-Trumbore 算法（射线 vs 三角形）：用重心坐标 α + β + γ = 1 一次性算出交点 + UV + 法向。

2.3 算法选择 (Algorithm Selection)

What：根据图元类型与查询频率选择测试算法。

Why：选错算法性能差 10-100 倍；高频查询必须用 O(1) 或 O(log n) 算法。

How：

查询频率 × 图元类型决策表：

查询频率	推荐图元 + 测试
高频（每帧 > 1000 次）	AABB / 球 + O(1) 测试
中频（每帧 100-1000 次）	OBB / 凸多面体 + SAT / GJK
低频（每帧 < 100 次）	三角形 / 多边形 + 精确算法（重心坐标等）

查询频率

推荐图元 + 测试

高频（每帧 > 1000 次）

AABB / 球 + O(1) 测试

中频（每帧 100-1000 次）

OBB / 凸多面体 + SAT / GJK

低频（每帧 < 100 次）

三角形 / 多边形 + 精确算法（重心坐标等）

BVH / 八叉树加速

BVH（Bounding Volume Hierarchy）：层级 AABB；粗筛用根节点 AABB，细判逐步深入。
八叉树（Octree）：3D 空间均匀划分；适合稀疏场景。
k-d tree：按某轴交替划分；适合最近点查询。

When：物理引擎选型；自研引擎的碰撞结构选型；debug 性能瓶颈时识别"是否图元选错"。

Example：Unreal Chaos 用 BVH + 凸碰撞器；Unity PhysX 默认 BVH。

2.4 数值精度 (Numerical Precision)

What：浮点运算的精度问题——除零、epsilon、边界条件。

Why：90% 的物理引擎 bug 出在数值边界——AABB 重叠误判、射线平行误判、NaN 传播。

How：

常见边界问题与对策：

点积接近 0：射线 / 平面平行时 NaN；用 epsilon 比较。
AABB 比较：用 < 而非 ≤（避免边界 box 互相判定重叠）。
三角形退化：面积为 0（3 点共线）；退化检查后再算重心。
浮点累加：长链条物理模拟误差累积；用 Kahan 求和或 double precision。
sqrt 接近 0：向量归一化时除零；保护 |v| > epsilon。

物理引擎的 epsilon 经验值

AABB 比较：1e-6
三角形面积：1e-8
三角形退化检测：1e-10
浮点相等：1e-5

不同引擎略有差异；调参时根据物理步长与典型位移调整。

When：写测试函数时显式处理边界；物理引擎调参（步长 + epsilon）。

Example：射线方向向量 d = (0, 0, 1e-10) 与 z 轴平行；若直接 t = q.z / d.z 得 NaN；应先 if (fabs(d.z) < epsilon) 退化为其他测试。

三、关键图表

视觉图表

Figure 1. 图 A-1：点到隐式线最近点

Figure 2. 图 A-2：点到射线最近点

Figure 3. 图 A-3：射线与平面相交

Figure 4. 图 A-4：射线与球相交（二次方程 0/1/2 解）

Figure 5. 图 A-5：射线与三角形相交（Möller-Trumbore）

Figure 6. 图 A-6：AABB 与平面相交

Figure 7. 图 A-7：AABB-AABB 相交（slab method）

非可视化条目

非可视化条目（表 / 算法）

编号

内容摘要

表 A.1

18 个测试的输入 / 输出 / 关键公式总览。

式 A-1 至 A-18

每个测试的核心公式。

列表 A.1-A.x

C 代码骨架：最近点 5 个、相交 13 个。

表 A.2

"粗筛 + 细判"的查询频率 × 图元类型决策表。

表 A.3

浮点 epsilon 经验值（物理引擎常用）。

核心公式对照表

测试

公式

点 → 隐式线

\(\mathbf{q}' = \mathbf{q} + (d - \mathbf{q} \cdot \hat{\mathbf{n}}) \hat{\mathbf{n}}\)

点 → 射线

\(t = \hat{\mathbf{d}} \cdot (\mathbf{q} - \mathbf{p}_{\text{org}}),\quad \mathbf{q}' = \mathbf{p}_{\text{org}} + t \hat{\mathbf{d}}\)

点 → 平面

\(\mathbf{q}' = \mathbf{q} - (\mathbf{q} \cdot \hat{\mathbf{n}} - d) \hat{\mathbf{n}}\)

点 → 球

\(\mathbf{q}' = \mathbf{c} + r \frac{\mathbf{q} - \mathbf{c}}{|\mathbf{q} - \mathbf{c}|}\)

点 → AABB

\(\mathbf{q}'[i\) = \text{clamp}(\mathbf{q}[i],\ p_{\min}[i],\ p_{\max}[i])]

射线 vs 球（二次）

latexmath:[

\mathbf{P}(t) - \mathbf{c}

^2 = r^2 \Rightarrow a t^2 + bt + c = 0]

AABB-AABB

\(\forall i: p_{\max}^{A,i} \ge p_{\min}^{B,i} \land p_{\max}^{B,i} \ge p_{\min}^{A,i}\)

射线 vs AABB（slab）

\(\forall i: t_{\min} \le t_{\max} \Rightarrow \text{相交}\)

四、思维导图

mindmap
  root((附录 A 几何测试))
    最近点
      点到线
      点到射线
      点到平面
      点到球
      点到AABB
    相交测试
      线vs线
      射线vs平面
      射线vs球
      射线vs三角形
      AABB相交
      球vs球
    算法选择
      高频用AABB
      粗筛加细判
      BVH八叉树
    数值精度
      epsilon边界
      除零保护
      退化检查

五、重点与易错点

粗筛 + 细判是物理引擎的核心模式：BVH 用 AABB 粗筛，逐步深入到 OBB / 凸 / 三角形细判。
*Möller-Trumbore 算法*是射线 vs 三角形的事实标准：一次性算出交点 + UV + 重心坐标；现代 GPU 拾取常用。
AABB 比较用 < 而非 ≤：避免边界 box 互相重叠造成无限循环；这是经典 bug。
退化三角形检测：3 点共线时面积为 0，叉积方向无定义；先检查再算重心坐标。
浮点 epsilon 选错会"假阳性碰撞"：AABB 边界重叠、球-球近距离接触、射线平行都易误判。
射线 vs AABB 用 slab method：三轴独立求 t 范围（tmin, tmax），三者有交集则相交。
最近点 = 投影 = 法线方向位移：对于线 / 平面 / 球都是这样；公式简洁。
球 vs 球用中心距 vs 半径和 / 差：0/1/2 三个解；详细见 §9.3 + 本章 A.13。
三角形 vs 三角形复杂度高：一般用 BVH 加速；精确算法有 Möller SAT。
射线方向必须单位化：否则 t 物理意义错位；长距离射线精度下降。
NaN 是物理引擎的"杀手"：除零后传播到所有后续计算；务必显式保护。
几何测试是 3D 引擎的核心：渲染、物理、拾取、AI、可见性都依赖这些测试。
跨章衔接：§9 章几何图元提供本章测试的输入；§10 章 GPU 拾取用射线 vs AABB / 三角形；§12 章物理碰撞用球 / AABB / 三角形测试。