22 Intersection Test Methods

相交测试方法

章节引言：相交测试的核心地位

相交测试是实时渲染乃至整个计算机图形学领域的基石。它不仅仅是用来判断“两个物体是否碰上了”，其应用贯穿于渲染管线的多个阶段。

• 核心观点: 相交测试用于判断两个或多个几何实体（物体、射线、平面等）是否存在重叠区域。这是实现高级渲染特性和场景交互的基础。

• 关键应用场景:

  • 碰撞检测 (Collision Detection): 判断游戏世界中的物体是否发生物理接触。
  • 视锥体剔除 (Frustum Culling): 快速判断物体是否在摄像机可见范围内，避免对不可见物体进行渲染，是性能优化的关键一环。
  • 拾取 (Picking): 判断用户通过鼠标等设备点击的屏幕位置对应场景中的哪个物体。
  • 光线追踪 (Ray Tracing): 计算光线与场景中物体的交点，是实现照片级真实感渲染的核心算法。
  • 环境查询: 例如，计算角色脚下到地面的距离以实现贴地行走。

• 关键术语:

  • 包围体 (Bounding Volume, BV): 用于近似表示复杂几何体的简单形状，如球体 (Sphere)、轴对齐包围盒 (AABB)、定向包围盒 (OBB) 和 k-DOPs。对BV进行相交测试通常比对原始几何体快得多。

---

22.1 GPU加速的拾取 (GPU-Accelerated Picking)

传统的拾取操作（如光线投射）在CPU端执行，但这在现代渲染管线中面临诸多挑战。GPU加速拾取利用渲染硬件本身，提供了一种更高效、更精确的解决方案。

CPU拾取的局限性

• 核心观点: 在CPU端通过投射射线并遍历场景数据来进行拾取，虽然可行，但难以处理由GPU动态生成的几何体，且在复杂场景下效率低下。

• 主要缺点:

  • 性能瓶颈: 对包含大量三角形的模型进行逐一测试非常耗时，即使使用了加速结构（如BVH）。
  • 几何信息不匹配: 无法处理位移贴图 (Displacement Mapping) 或 GPU曲面细分 (Tessellation) 生成的动态几何体，因为这些细节只存在于GPU上。
  • 无法处理着色器效果: 无法精确处理由 Alpha贴图 产生的透明区域（例如树叶的镂空部分），用户可能会点到“看不见”的区域。

GPU拾取的核心思想

• 核心观点: 将场景中的物体信息（如唯一ID）渲染到一张屏幕外的图像（渲染目标）中。通过读取用户点击位置的像素值，直接获取该物体的信息。这个过程也被称为 ID缓冲 (ID Buffering)。

• 实现流程:

  1. 分配唯一标识符: 为场景中每个可被拾取的物体分配一个独一无二的 ID。这个ID可以被编码成一种颜色值（例如，物体1的ID是1，就渲染成颜色 (1,0,0,0)）。
  2. 离屏渲染: 在一个单独的渲染通道(pass)中，使用一个极简的着色器将整个场景渲染到一个离屏渲染目标 (Off-screen Render Target)。此着色器的唯一任务就是输出其正在渲染的物体的 ID颜色。
  3. 读取像素: 当用户点击屏幕时，程序会读取离屏渲染目标中对应像素的颜色值。
  4. 识别物体: 将读取到的颜色值解码，即可得到被点击物体的ID。

• 性能开销: 主要开销在于 将像素数据从GPU回读到CPU (GPU-to-CPU Readback)，这可能会导致管线同步停顿。

GPU拾取的高级应用与优化

• 获取重心坐标 (Barycentric Coordinates):

  • 技巧: 可以在另一个渲染通道中，将正在渲染的三角形的三个顶点颜色分别设为纯红(1,0,0)、纯绿(0,1,0)和纯蓝(0,0,1)。
  • 原理: GPU的硬件插值器会自动计算像素点在三角形内部的颜色。读取这个插值后的颜色值（例如 (r, g, b)），其 r, g, b 分量就直接对应于该点相对于三个顶点的重心坐标。这对于获取精确的碰撞点、纹理坐标等信息非常有用。

• 针对动态场景的优化：“小窗口”渲染法

  • 问题: 如果相机或物体在持续移动，每一帧都为拾取重绘整个场景的代价太高。
  • 解决方案:
    1. 不必渲染全屏，而是创建一个极小的渲染目标（例如 3x3 或 5x5 像素）。
    2. 使用一个 离轴相机 (Off-axis Camera) 或修改过的投影矩阵，使这个小窗口精确地聚焦于鼠标光标周围的区域。
    3. 执行ID缓冲渲染。由于视锥体极小，CPU端的视锥体剔除会过滤掉绝大部分物体，使得这个渲染通道非常快。

• 处理遮挡物 (Picking Occluded Objects):

  • 如果需要选择被遮挡的物体，可以使用 深度剥离 (Depth Peeling) 技术，逐层渲染并拾取，或者在每次拾取后将已拾取的物体排除掉，然后再次执行“小窗口”渲染。

22.2 定义和工具 (Definitions and Tools)

本节为你提供了后续学习相交测试算法所必需的“词汇表”和“工具箱”。理解这些基础定义至关重要，它们是构建所有复杂算法的基石。

核心几何实体与表面表示法

1. 射线 (Ray)

• 核心观点: 射线是相交测试中最基本的“探针”，它由一个起点和一个方向定义。
• 标准公式: $$\mathbf{r}(t)=\mathbf{o}+t\mathbf{d}$$
• 关键术语:
  • o: 射线的原点 (origin)。
  • d: 射线的方向向量 (direction)，通常预先归一化 (normalized)，即 ||d|| = 1。
  • t: 标量参数，代表沿射线方向的距离。
    • t > 0: 位于射线方向上的点。
    • t = 0: 射线的原点。
    • t < 0: 位于射线反方向的点（技术上不属于射线）。
• 实践技巧: 在代码实现中，通常会维护一个最大相交距离 l (初始为无穷大)。任何计算出的相交距离 t 如果大于 l，就会被忽略。这使得射线实际上变成了一个有向线段，用于寻找最近的交点。

2. 表面表示法 (Surface Representations)

• 核心观点: 物体的表面可以用两种主要方式进行数学描述：隐式和显式。这两种方式对应着不同的相交测试求解思路。
• 隐式表面 (Implicit Surface):
  • 定义: 由一个方程 f(p) = 0 定义。所有满足该方程的点 p 构成了表面。
  • 直观理解: 它描述了一种“属于/不属于”的关系。点 p 代入函数，结果为0则在表面上，非0则不在。
  • 例子 (单位球): $$f(p_x,p_y,p_z)=p_x^2+p_y^2+p_z^2-1=0$$
• 显式表面 (Explicit Surface):
  • 定义: 由一个参数化函数 p = f(u, v, ...) 定义。通过改变参数，可以“生成”表面上的所有点。
  • 直观理解: 它提供了一个“配方”，告诉你如何根据一组参数来构造表面上的点。
  • 例子 (三角形): $$\mathbf{t}(u,v)=(1-u-v){\mathbf{v}}_0+u{\mathbf{v}}_1+v{\mathbf{v}}_2$$ 其中 u ≥ 0, v ≥ 0, u+v ≤ 1。这里的 (u, v) 就是参数，而 (1-u-v, u, v) 是重心坐标 (Barycentric Coordinates)。

常用包围体 (Bounding Volumes)

• 核心观点: 使用简单的几何体（包围体）来包裹复杂的模型，可以极大地加速相交测试。先测试包围体，只有当包围体相交时，才需要进行更昂贵的精确测试。

• 关键术语:

  • AABB (Axis-Aligned Bounding Box): 轴对齐包围盒。
    • 定义: 所有面都与世界坐标系的坐标轴（X, Y, Z）平行的盒子。
    • 表示: 通常用两个点 min 和 max 来定义。
    • 特点: 存储和相交测试都极其简单快速，但贴合度可能较差，特别是对于旋转后的物体。
  • OBB (Oriented Bounding Box): 定向包围盒。
    • 定义: 可以任意旋转的盒子，能够更紧密地包裹物体。
    • 表示: 通常用一个中心点 c、三个互相正交的归一化方向向量 u, v, w 和沿这些方向的半长（extents）h_u, h_v, h_w 来定义。
    • 特点: 贴合度比AABB好，但测试更复杂。
  • k-DOP (Discrete Oriented Polytopes): 离散定向多面体。
    • 定义: 由 k/2 对平行平面（称为平板 - Slab）所围成的凸体。
    • 理解: AABB 和 OBB 都是 6-DOP 的特例（由3对平行平面定义）。增加 k 的值（例如使用18-DOP或26-DOP）可以得到更紧密的包围体，代价是测试成本更高。
  • 凸多面体 (Convex Polyhedron):
    • 定义: 由多个平面定义的半空间 (half-space) 的交集构成的有限体积。AABB、OBB、k-DOP和视锥体都是它的特例。
  • 胶囊体 (Capsule) / 含片体 (Lozenge):
    • 定义: 分别由一个球体沿一条线段或一个矩形扫掠而成。常用于角色等细长物体的碰撞检测。

分离轴测试 (Separating Axis Test - SAT)

• 核心观点: 这是用于判断两个凸多面体是否相交的强大工具。其基本思想是：如果能找到一个轴，使得两个物体在该轴上的投影（区间）不重叠，那么这两个物体就不相交。这个轴就叫做分离轴。

• 重要定理 (分离超平面定理的推论): 对于两个不相交的凸物体 A 和 B，分离轴必然存在，且只需要在以下有限的方向中寻找：

  1. 物体 A 的每个面的法线。
  2. 物体 B 的每个面的法线。
  3. 物体 A 的每条边与物体 B 的每条边的叉积 (Cross Product)。

• 注意: 该方法仅适用于凸物体。对于凹物体，即使它们不相交，也可能找不到分离轴。

• 优化技巧 - 时间一致性 (Temporal Coherence): 在连续的帧之间，物体的位置变化很小。因此，当前帧找到的分离轴很可能在下一帧仍然是分离轴。可以在下一帧的测试中，优先测试上一帧找到的分离轴，从而实现快速拒绝。

通用测试策略与注意事项

• 拒绝测试 (Rejection Test):

  • 核心思想: 在执行昂贵的精确相交测试之前，先进行一系列简单、快速的测试来证明“不相交”。只要有一个拒绝测试通过，就可以提前终止整个相交判断，节省大量计算。这是性能优化的黄金法则。

• 降维处理 (Dimensionality Reduction):

  • 核心思想: 许多复杂的三维问题，可以通过将其投影到某个“最佳”的二维平面（如XY, XZ, YZ平面）上，从而简化为更容易解决的二维问题。

• 数值精度 (Numerical Precision):

  • 核心问题: 计算机使用浮点数进行计算，存在舍入误差。直接用 a == b 来判断两个浮点数相等是危险的。
  • 解决方案: 在相交测试中，通常会引入一个极小的正数 epsilon (ε)。例如，判断一个点是否在平面上时，会检查点到平面的距离的绝对值是否小于 ε。
  • 警告: 选择一个合适的 ε 值非常重要但也很棘手。一个在某个场景中运行良好的 ε 值，在另一个尺度完全不同的场景中可能会失效。这是一个需要持续关注的工程问题。

22.3 创建包围体 (Creating Bounding Volumes)

• 核心观点: 创建一个紧密贴合 (tight-fitting) 的包围体是性能优化的关键。一个松散的包围体 V 会导致大量的“误报”（射线或视锥体与 V 相交，但与内部的实际物体不相交），从而浪费了大量本可避免的、昂贵的精确相交测试。

• 优化目标:

  • 对于光线追踪/拾取: 目标是最小化包围体的表面积，因为这与射线击中概率成正比。
  • 对于碰撞检测: 目标是最小化包围体的体积，因为这与点或物体侵入概率成正比。

22.3.1 创建AABB和k-DOP

• 核心思想: 这是最简单的包围体创建方法，通过将所有顶点投影到一组预定义的轴上并找到极值来完成。
• AABB创建:
  1. 遍历模型的所有顶点。
  2. 分别记录下 X、Y、Z 坐标的最小值和最大值。
  3. 由这组 (minX, minY, minZ) 和 (maxX, maxY, maxZ) 即可构成 AABB。
• k-DOP创建:
  1. 与AABB类似，但不是投影到X/Y/Z轴，而是投影到 k/2 个预定义的法线向量上。
  2. 对于每个法线 n_i，记录下所有顶点投影到该方向上的最小和最大距离 (d_min, d_max)。
  3. 这一组 (n_i, d_min, d_max) 就定义了包围模型的 k/2 个平板 (Slabs)，它们的交集就是 k-DOP。

22.3.2 创建球体 (Sphere)

创建最优（最小）包围球比创建AABB复杂。算法的选择是在速度和贴合紧密度之间做权衡。

• 方法1: 基于AABB的快速法 (Fast, but Loose)

  1. 计算模型的 AABB。
  2. 取 AABB 的中心点作为球心。
  3. 取 AABB 中心到任意一个顶点的距离（即对角线长度的一半）作为半径。
  4. 改进: 仍然使用 AABB 中心作为初始球心，但随后遍历所有模型顶点，找到距离球心最远的那个点，用这个最远距离作为最终半径。这通常能得到更紧密的球体。

• 方法2: Ritter 算法 (Fast and Good Approximation)

  • 核心思想: 一种单次遍历的近似最优算法，效果通常很好。
  1. 找出模型在 X, Y, Z 轴上分别相距最远的两个顶点，得到三对点。
  2. 选择这三对点中，距离最远的那一对，用它们的中点和距离的一半创建初始球体。
  3. 遍历所有其他顶点。如果发现某个顶点在球体外，则扩展球体，使其刚好同时包含旧球体和这个新的界外点。
  4. 一次遍历后即可得到一个质量不错的包围球。

• 方法3: Welzl 算法 (Optimal, but Slower)

  • 核心思想: 能保证找到数学上体积最小的包围球。
  • 原理: 一个三维球体最多由其表面上的4个点唯一确定。算法通过迭代，寻找并维护这个“支撑点”集合，直到找到的球体能包围所有顶点。
  • 应用场景: 由于计算成本较高（虽然是线性时间复杂度，但常数因子大），通常用于离线预处理，而不是在运行时动态生成。

22.3.3 创建凸包 (Convex Hull)

• 核心思想: 凸包是能够包裹一个物体集合的最小凸多面体，提供了最紧密的凸包围。
• 创建算法:
  • Quickhull 算法: 是生成凸包的标准算法。
  • 特点: 结果非常精确（紧密），但计算成本高，几乎总是作为离线步骤来执行。
• 实践技巧:
  • 为了平衡性能和精度，可以先对原始高精度网格进行简化，再为简化后的网格计算凸包。
  • 当 k-DOP 的 k 值取得很大时，其形状会逐渐逼近物体的凸包。

22.3.4 创建OBB (Oriented Bounding Box)

寻找最优（最小体积）的OBB是一个难题。现有方法大多是近似算法。

• 方法1: 主成分分析 (PCA - Principal Component Analysis)

  • 核心思想: 通过 PCA 分析模型顶点（通常是凸包上的顶点）的分布，找出数据方差最大的三个主方向，并将这些方向作为 OBB 的三个轴。
  • 评价: 速度快，实现相对简单，但生成的 OBB 贴合度不一定最优，有时会比较松散。

• 方法2: Larsson & Kallberg 近似最优算法

  • 核心思想: 一种更现代、速度快、质量高且无需计算凸包的线性时间算法，非常适合现代硬件（SIMD友好）。
  • 流程简介:
    1. 先创建一个 k-DOP (如26-DOP)，快速找到模型表面的一小组极值点 (extremal points)。后续计算只基于这少量点，而非全部顶点。
    2. 在极值点中找到相距最远的一对点构成一条边，再找到距离此边最远的极值点构成一个基础三角形。
    3. 基于这个三角形的边和法线，构建并评估几个候选 OBB。
    4. 通过一系列迭代和优化步骤，从少量候选者中选出体积（或表面积）最小的那个。
  • 评价: 性能和质量的绝佳平衡点，是现代引擎中创建高质量OBB的推荐方法。

---

22.4 几何概率 (Geometric Probability)

• 核心观点: 一个物体的几何属性（体积、表面积、宽度）直接关系到它与随机点、射线、平面相交的概率。理解这一点有助于我们选择和设计最高效的包围体及加速结构。

• 关键关系:

  • 点 vs 物体: 相交概率正比于物体的 体积 (Volume)。
    • 应用: 在碰撞检测中，应优先选择体积最小的包围体。
  • 射线 vs 物体: 相交概率正比于物体的 表面积 (Surface Area)。
    • 重要结论: 一个凸体在所有方向上的平均投影面积是其表面积的 1/4。
    • 应用: 这是光追中著名的 表面积启发式 (Surface Area Heuristic, SAH) 的理论基础。在构建 BVH 等加速结构时，SAH 用于评估在哪分割节点能获得最大收益。对于光线拾取，应选择表面积最小的包围体。
  • 平面 vs 物体: 相交概率正比于物体的 平均宽度 (Mean Width)。（对于Box，可以近似为其三边长度之和）。
    • 应用: 在视锥体剔除中，由于视锥体由6个平面定义，平均宽度更小的包围体被剔除的概率更高。

---

22.5 经验法则 (Rules of Thumb)

这是一份你在设计和实现任何相交测试算法时都应该牢记在心的“最佳实践”清单。

1. 尽早退出 (Early Out): 将最廉价的拒绝测试放在最前面。只要能提前证明“不相交”，就能避免后续所有昂贵的计算。
2. 利用时间一致性 (Temporal Coherence): 如果上一帧找到了一个分离轴，那么这一帧可以优先测试这个轴。物体在帧间的运动通常很小，所以上一帧的结果很有可能依然有效。
3. 延迟昂贵计算: 除法、平方根、三角函数 等操作非常耗时。尽可能推迟它们，直到确认必须进行计算时再执行。多用平方距离比较来避免开方。
4. 降维打击: 尽可能将3D问题投影到2D或1D来解决，这通常能极大地简化问题。
5. 预计算: 如果要用一个物体（如一条射线）去测试大量其他物体，那么先为这条射线预计算一些值（如方向向量的倒数），可以避免在循环中重复计算。
6. 使用层次化测试: 先用一个计算开销极小但可能较松散的包围体（如包围球）做第一轮快速拒绝，只有通过了测试，再用更紧密但更昂贵的包围体（如OBB）进行第二轮测试。
7. 实际测量，拒绝臆断: 算法的性能高度依赖于数据、场景和硬件架构。不要想当然，一定要用真实数据和场景去剖析 (Profile) 你的代码。
8. 追求健壮性 (Robustness): 充分考虑浮点数的精度问题和所有可能的边界情况 (edge cases)。健壮的代码比微秒级的性能提升更重要。

22.6 射线/球体相交 (Ray/Sphere Intersection)

射线与球体的相交测试是学习所有相交算法的绝佳起点。它有两种经典的解法：纯粹的代数解法和利用几何直觉的优化解法。理解这两种方法的思路，能帮你更好地掌握更复杂的测试。

22.6.1 代数解法 (Mathematical Solution)

• 核心观点: 将射线的参数方程代入球体的隐式方程，会得到一个关于射线参数 t 的一元二次方程。通过解这个方程，可以直接求出交点。

• 推导过程:

  1. 球体隐式方程: 对于一个中心为 c、半径为 r 的球体，其表面上的任意一点 p 满足： $$|\mathbf{p}-\mathbf{c}{|}^2=r^2$$
  2. 射线参数方程: $$\mathbf{r}(t)=\mathbf{o}+t\mathbf{d}$$
  3. 联立求解: 将射线方程中的 r(t) 替换球体方程中的 p： $$|(\mathbf{o}+t\mathbf{d})-\mathbf{c}{|}^2=r^2$$
  4. 展开与整理: 经过一系列向量点乘运算和化简（假设射线方向 d 已归一化，即 d · d = 1），我们可以得到一个标准的一元二次方程 At² + Bt + C = 0 的形式。书中为了简化，给出了如下形式： $$t^2+2t(\mathbf{d}\cdot (\mathbf{o}-\mathbf{c}))+(\mathbf{o}-\mathbf{c})\cdot (\mathbf{o}-\mathbf{c})-r^2=0$$

• 求解与判断:

  • 该方程可以写成更简洁的 t² + 2bt + c = 0 形式，其中：
    • b = d ⋅ (o - c)
    • c = (o - c) ⋅ (o - c) - r²
  • 判别式 (Discriminant): 方程的解取决于判别式 Δ = b² - c 的值。
    • b² - c < 0 (Δ < 0): 方程无实数解。射线与球体不相交。
    • b² - c = 0 (Δ = 0): 方程有一个实数解。射线与球体相切（1个交点）。
    • b² - c > 0 (Δ > 0): 方程有两个不同的实数解。射线穿过球体（2个交点）。
  • 交点距离: 当存在实数解时，交点对应的 t 值为： $$t=-b\pm \sqrt{b^2-c}$$ 我们通常关心的是最小的那个正数解 t，因为它代表了离射线原点最近的交点。

22.6.2 优化解法 (Optimized Geometric Solution)

• 核心观点: 纯代数解法虽然直接，但包含了许多可以被提前避免的计算。通过分析射线和球体的几何关系，我们可以设计出包含多个廉价的早期拒绝测试的算法，从而在平均情况下获得更高的性能。

• 算法步骤 (基于几何直觉):

  1. 定义向量 l: 计算从射线原点 o 指向球心 c 的向量： l = c - o。

  2. 提前接受测试: 如果射线原点在球体内部，则必然相交。

     • 判断: l ⋅ l < r² ?
     • 操作: 如果成立且我们只关心“是否相交”，可以直接返回 true。

  3. 计算投影长度 s: 计算 l 在射线方向 d 上的投影长度：s = l ⋅ d。

  4. 第一次拒绝测试 (球体在后方): 如果球心在射线原点的“后面”，并且射线原点在球体外部，那么射线不可能与球体相交。

     • 判断: s < 0 并且 l ⋅ l > r² ?
     • 操作: 如果成立，可以直接返回 false。

  5. 计算最近距离的平方 m²: 利用勾股定理，计算球心 c 到射线的垂直距离的平方：m² = l ⋅ l - s²。

  6. 第二次拒绝测试 (射线偏离): 如果球心到射线的最近距离大于球体半径，那么射线不可能与球体相交。

     • 判断: m² > r² ?
     • 操作: 如果成立，可以直接返回 false。

  7. 计算交点: 如果通过了所有测试，说明射线必然与球体相交。

     • 计算从最近点到交点的距离 q: q = sqrt(r² - m²)。
     • 两个交点对应的距离 t 分别是：t₁ = s - q 和 t₂ = s + q。
     • 如果射线原点在球外，第一个交点是 t₁；如果在球内，第一个正向交点是 t₂。

• 伪代码逻辑:

  function RaySphereIntersect(ray, sphere):
      l = sphere.center - ray.origin
      s = dot(l, ray.direction)
      l2 = dot(l, l)
      r2 = sphere.radius * sphere.radius
   
      if s < 0 and l2 > r2:
          return NO_INTERSECTION // 球在后方且o在球外
   
      m2 = l2 - s * s
      if m2 > r2:
          return NO_INTERSECTION // 射线偏离
   
      // 此时已确定相交
      q = sqrt(r2 - m2)
      if l2 > r2:
          t = s - q // 原点在球外，取近点
      else:
          t = s + q // 原点在球内，取远点（正向）
   
      intersection_point = ray.origin + t * ray.direction
      return INTERSECTION, t, intersection_point

对比与总结

特性	代数解法	优化几何解法
核心思路	联立方程，求解一元二次方程	利用几何关系，进行一系列逐步筛选的测试
性能	无论是否相交，大部分计算都要执行	平均性能更高，因为有多个廉价的早期拒绝
可读性	推导直接，但最终代码可能不直观	每一步都有明确的几何意义，代码更易理解
适用场景	教学或简单实现	性能敏感的应用，如游戏引擎、实时渲染

22.7 射线/Box相交 (Ray/Box Intersection)

射线与Box（AABB或OBB）的相交测试是剔除和拾取操作中的常客。本节介绍的核心方法——平板法，非常巧妙且高效。

22.7.1 平板法 (The Slab Method)

• 核心观点: 任何一个Box都可以看作是三对无限大的平行平面（称为平板 - Slabs）的交集。一条射线要穿过Box，就必须同时穿过这三个Slab的重叠区域。

• 算法原理:

  1. 分解为Slab: 将Box（无论是AABB还是OBB）看作由X、Y、Z三个方向上的Slab组成。
  2. 计算各Slab的穿越区间: 对每个Slab，计算射线进入（t_near）和穿出（t_far）该Slab的距离t值。这会得到三组区间：[t_near_x, t_far_x], [t_near_y, t_far_y], [t_near_z, t_far_z]。
  3. 寻找总相交区间: 射线与Box的实际相交区间，是这三个独立区间的交集。
     • 总的进入时间 t_min 是所有 t_near 中最大的那个。
     • 总的穿出时间 t_max 是所有 t_far 中最小的那个。
     t_{min} = \max(t_{near\_x}, t_{near\_y}, t_{near\_z}) $$ $$ t_{max} = \min(t_{far\_x}, t_{far\_y}, t_{far\_z})

• 相交判断:

  • 核心测试: 如果 t_min ≤ t_max，那么这条射线所定义的直线与Box相交。
  • 方向判断: 还需要一个额外的检查来确保交点在射线前方，例如 t_max > 0。如果 t_max < 0，则整个相交区间都在射线原点之后，应视为不相交。

• 实现要点与优化:

  • 处理平行情况: 当射线方向与某个Slab的法线垂直时（即点积为0），射线平行于该Slab。此时需要判断射线原点是否位于Slab内部，如果不在，则不可能相交。
  • 除法优化: 可以预先计算射线方向各分量的倒数 1/d.x, 1/d.y, 1/d.z，将后续的除法全部转换成乘法，以提升性能。
  • AABB特例: 对于AABB，其Slab法线就是坐标轴，计算过程可以大幅简化，无需处理复杂的坐标变换。

22.7.2 射线斜率法 (Ray Slope Method)

• 核心观点: 一种将3D问题降维到2D解决的快速布尔测试方法。
• 基本思想:
  1. 将射线和Box分别投影到XY、YZ、XZ三个平面上。
  2. 在每个2D平面上，检查投影后的射线是否穿过了投影后的矩形。这可以通过比较射线的斜率与射线原点到矩形两个“轮廓”顶点连线的斜率来完成。
  3. 只有当射线通过了所有三个平面的2D测试时，才判定它与3D Box相交。
• 优势: 速度极快，尤其适合一条射线 vs 大量Box的场景，因为部分计算只依赖于射线本身，可以被预计算和复用。

---

22.8 射线/三角形相交 (Ray/Triangle Intersection)

这是实时渲染中最重要、最基础的相交测试之一。书中介绍的 Möller-Trumbore 算法 无需预计算三角形法线，在内存和效率上取得了很好的平衡。

22.8.1 核心思想与推导 (Möller-Trumbore 算法)

• 核心观点: 不通过“求平面交点再判断点是否在三角形内”的两步法，而是直接利用重心坐标 (Barycentric Coordinates) 将射线方程和三角形参数方程联立，构建一个线性方程组，一次性解出所有未知数 (t, u, v)。

• 推导步骤:

  1. 联立方程: 射线上的点 r(t) 必须等于三角形上的点 f(u,v)。 $$\underset{\text{Ray}}{\underbrace{\mathbf{o}+t\mathbf{d}}}=\underset{\text{Triangle}}{\underbrace{(1-u-v){\mathbf{p}}_0+u{\mathbf{p}}_1+v{\mathbf{p}}_2}}$$
  2. 构建线性系统: 将上式整理，可以得到一个关于未知数 (t, u, v) 的3x3线性方程组： $$\left(\begin{array}{ccc}-\mathbf{d}& {\mathbf{p}}_1-{\mathbf{p}}_0& {\mathbf{p}}_2-{\mathbf{p}}_0\end{array}\right)\left(\begin{array}{c}t\\ u\\ v\end{array}\right)=\mathbf{o}-{\mathbf{p}}_0$$
  3. 求解: 使用 克莱姆法则 (Cramer's Rule) 求解该方程组。求解过程会涉及到一系列行列式计算，而三阶行列式可以巧妙地用向量的标量三重积 (Scalar Triple Product) 来高效计算，即 det(a,b,c) = (a x b) ⋅ c。最终可以推导出 t, u, v 的表达式： $$\left(\begin{array}{c}t\\ u\\ v\end{array}\right)=\frac{1}{(\mathbf{d}\times {\mathbf{e}}_2)\cdot {\mathbf{e}}_1}\left(\begin{array}{c}(\mathbf{s}\times {\mathbf{e}}_1)\cdot {\mathbf{e}}_2\\ (\mathbf{d}\times {\mathbf{e}}_2)\cdot \mathbf{s}\\ (\mathbf{s}\times {\mathbf{e}}_1)\cdot \mathbf{d}\end{array}\right)$$ 其中 e₁ = p₁ - p₀, e₂ = p₂ - p₀, s = o - p₀。

• 相交条件: 解出的 (t, u, v) 必须同时满足以下所有条件，才算有效相交：

  1. t > 0: 交点在射线前方。
  2. u ≥ 0
  3. v ≥ 0
  4. u + v ≤ 1: 这三条保证了交点位于三角形内部（包括边界）。

22.8.2 实现要点与优化

• 第一步：计算行列式: 首先计算分母中的行列式 det = (d x e₂) ⋅ e₁。

  • 如果 det 接近于0，说明射线几乎平行于三角形平面，应判为不相交以避免数值问题。
  • det 的符号可以用于背面剔除 (Back-face Culling)。如果 det 为负（取决于坐标系和法线定义），说明射线从三角形背面射入，可以提前拒绝。

• 第二步：延迟除法: 算法最精妙的优化在于将唯一的、昂贵的除法运算延迟到最后。

  1. 先计算出 u 的分子部分，然后与 det 比较，检查 u 是否在 [0, det] 区间内（这等价于检查 u 是否在 [0, 1] 区间内，但避免了除法）。如果不在，立即拒绝。
  2. 同理，计算 v 的分子部分，并检查 u+v 是否在 [0, det] 区间内。如果不在，立即拒绝。
  3. 只有通过了所有测试，确认了交点一定在三角形内，才执行一次除法来计算最终的 t, u, v 值。

这个延迟除法的技巧是 Möller-Trumbore 算法高性能的关键，体现了“尽早退出”的优化思想。

22.9 射线/多边形相交 (Ray/Polygon Intersection)

• 核心观点: 这是一个经典的两步问题：首先，计算射线与多边形所在无限大平面的3D交点；然后，通过降维 (Dimensionality Reduction)，判断这个3D交点是否落在2D多边形的边界之内。

步骤 1: 射线与平面相交

1. 联立求解: 将射线方程 p = o + td 代入平面方程 n⋅x + d = 0。
2. 解出距离 t: $$t=\frac{-d_p-{\mathbf{n}}_p\cdot \mathbf{o}}{{\mathbf{n}}_p\cdot \mathbf{d}}$$
3. 平行判断: 如果分母 n_p ⋅ d 的绝对值非常接近0，说明射线与平面平行，视为不相交。
4. 计算交点 p: 如果不平行，将求出的 t 值代回射线方程 p = o + td 即可得到3D交点。

步骤 2: 判断点是否在多边形内 (Point in Polygon)

• 核心思想: 将3D问题简化为2D问题。我们把多边形的所有顶点和上一步求出的交点 p 一起投影到一个2D坐标平面（XY, YZ, 或 XZ）。
• 选择最佳投影平面: 为了避免投影后的多边形退化成一条线，我们选择面积最大的投影方向。
  • 技巧: 检查多边形法线 n 的哪个分量（x, y, z）的绝对值最大，然后在投影时就丢弃那个坐标轴。例如，如果 |n_y| 最大，我们就将所有点投影到 XZ 平面。

22.9.1 交叉点测试 (The Crossings Test)

这是最常用、最稳健的2D“点在多边形内”测试方法。

• 理论基础: 乔丹曲线定理 (Jordan Curve Theorem)。
• 核心规则: 从待测点 p 出发，向任意固定方向（例如 +X 轴）画一条射线。计算这条射线与多边形边界的交点数量。
  • 如果交点数量为 奇数，则点 p 在多边形 内部。
  • 如果交点数量为 偶数，则点 p 在多边形 外部。
• 算法实现要点:
  • 坐标系变换: 为了简化计算，可以将多边形整体平移，使得待测点 p 恰好位于原点。这样，我们只需要统计多边形的边与 +X 轴的交叉次数。
  • 处理边界情况: 当测试射线恰好穿过多边形顶点时，为了避免重复计数，需要一个统一的规则。一个简单有效的方法是：将 y 坐标大于等于0的顶点视为在射线“上方”，这样顶点本身就不会被算作与射线相交。
  • 优点: 算法快速、稳健，且无需对多边形进行预处理，能很好地处理凹多边形。
• 缠绕数 (Winding Number): 交叉点测试的一个变种可以计算缠绕数，它能正确处理自相交多边形，判断一个区域是否真的属于多边形的“内部”。

---

22.10 平面/Box相交 (Plane/Box Intersection)

这是视锥体剔除 (Frustum Culling) 的核心操作之一，因为视锥体就是由6个平面定义的。这里的算法极其高效。

• 核心观点: 无需测试Box的8个顶点。我们只需要计算Box中心点到平面的距离，并将其与Box在平面法线方向上的投影半径 (projected radius) 进行比较。

22.10.1 AABB 与平面相交

1. 表示AABB: 使用中心点 c 和 半对角向量 h (extents) 来表示AABB。
   • c = (b_max + b_min) / 2
   • h = (b_max - b_min) / 2
2. 计算中心点到平面的有符号距离 s:
   • s = c ⋅ n + d
3. 计算AABB在平面法线 n 上的投影半径 e:
   • 这是一个非常巧妙的快速计算：
   $$e=h_x|n_x|+h_y|n_y|+h_z|n_z|$$
4. 相交判断:
   • 如果 s > e (即 s - e > 0)，Box完全在平面的正侧（外部）。
   • 如果 s < -e (即 s + e < 0)，Box完全在平面的负侧（内部）。
   • 否则 (|s| ≤ e)，Box与平面相交。

22.10.2 OBB 与平面相交

• 核心观点: 算法逻辑与AABB完全相同，唯一的区别在于投影半径 e 的计算方式，因为它需要考虑OBB自身的坐标轴。
• OBB的投影半径 e: $$e=h_u^B|\mathbf{n}\cdot {\mathbf{b}}^u|+h_v^B|\mathbf{n}\cdot {\mathbf{b}}^v|+h_w^B|\mathbf{n}\cdot {\mathbf{b}}^w|$$ 其中 b^u, b^v, b^w 是OBB的三个正交轴，h_u, h_v, h_w 是沿这些轴的半长。

---

22.11 三角形/三角形相交 (Triangle/Triangle Intersection)

这是底层碰撞检测中的一个复杂但重要的问题。书中所述的Guigue和Devillers方法是一种基于几何谓词（Geometric Predicates）的高效算法。

• 核心思想 (非共面情况):

  1. 跨越测试: 首先检查 T1 的所有顶点是否在 T2 所在平面的同一侧。如果是，则不相交。反之，对 T2 和 T1 所在平面也做此检查。
  2. 区间重叠测试: 如果两个三角形都“跨越”了对方所在的平面，那么这两个平面必然相交于一条直线 L。此时，两个三角形也都会与这条直线 L 相交，形成两个线段。问题就转化为判断这两个在直线 L 上的一维线段是否重叠。

• 核心数学工具: 4x4 行列式

  • 算法的核心是大量使用一个 4x4 的行列式 [a, b, c, d]，它在几何上代表了由四个点构成的四面体的有符号体积。 $$[\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}]=(\mathbf{d}-\mathbf{a})\cdot ((\mathbf{b}-\mathbf{a})\times (\mathbf{c}-\mathbf{a}))$$
  • 几何意义: 这个行列式的符号可以告诉我们点 d 是在由 a,b,c 定义的平面的正侧还是负侧。这是执行上述“跨越测试”的数学基础。

• 算法步骤:

  1. 执行跨越测试: 通过计算6个行列式（例如 [q1,q2,q3, p1] 等）的符号来判断两个三角形是否相互跨越对方的平面。
  2. 执行区间重叠测试: 如果跨越测试通过，再通过计算另外几个特定的行列式，来等价地判断它们在相交直线 L 上的投影区间是否重叠。

• 共面情况 (Coplanar Case):

  • 如果两个三角形共面，则问题退化为2D问题。将它们投影到最佳的2D平面上，然后执行2D三角形重叠测试。这通常包括：
    • 测试 T1 的某条边是否与 T2 的某条边相交。
    • 测试 T1 是否完全包含 T2 (通过测试 T2 的一个顶点是否在 T1 内)。
    • 测试 T2 是否完全包含 T1。

22.12 三角形/Box相交 (Triangle/Box Intersection)

• 核心观点: 判断三角形与AABB是否相交的最高效方法是使用分离轴测试 (Separating Axis Test, SAT)。如果能找到任何一个轴，使得三角形和Box在该轴上的投影不重叠，那么它们就不相交。

• 算法准备:

  1. 坐标系变换: 为了极大简化计算，我们将整个坐标系进行平移，使得AABB的中心位于原点。三角形的三个顶点也进行相应平移。
  2. (OBB情况): 如果待测的是一个OBB，需要先对三角形和OBB进行一次反向旋转变换，将OBB变成一个AABB，然后再应用此算法。

• 需要测试的13个分离轴: 根据SAT理论，对于三角形 vs Box，我们只需要测试以下13个方向就足够了：

  1. 3个轴: AABB的三个面法线（即世界坐标系的X, Y, Z轴）。
     • 直观理解: 这相当于测试“三角形的AABB”是否与“Box的AABB”相交。
  2. 1个轴: 三角形所在平面的法线 n。
     • 直观理解: 这是一个快速的平面/Box相交测试（见22.10.1）。
  3. 9个轴: AABB的三个轴与三角形的三条边的叉积 (e_i × f_j)。
     • 直观理解: 这些轴代表了可能发生“边对边”接触的方向。

• 测试流程:

  1. 遍历这13个轴。
  2. 对于每个轴，计算Box和三角形在该轴上的投影区间。
     • Box的投影区间很简单，对于一个以原点为中心、半长为 h 的Box，其在轴 a 上的投影区间为 [-r, r]，其中投影半径 r 的计算方式为: $$r=h_x|a_x|+h_y|a_y|+h_z|a_z|$$
     • 三角形的投影区间通过将它的三个顶点投影到轴上并取 min 和 max 得到。
  3. 判断分离: 检查两个投影区间是否重叠。如果不重叠（例如 min(p_triangle) > r 或 max(p_triangle) < -r），则说明找到了一个分离轴。
  4. 提前退出: 一旦找到任何一个分离轴，算法立刻终止并返回“不相交”。
  5. 最终结论: 如果遍历完所有13个轴都没有找到分离轴，那么可以确定三角形和Box必然相交。

---

22.13 BV/BV 相交 (Bounding Volume vs Bounding Volume)

包围体（BV）测试的核心目的就是提供比网格测试快得多的快速拒绝 (fast rejection)。只有当包围体相交时，才需要进行更昂贵的底层几何测试。

22.13.1 球体 vs 球体 (Sphere/Sphere)

• 核心思想: 比较两个球心的距离与它们的半径之和。
• 实现: 强烈建议使用距离的平方进行比较，这样可以完全避免昂贵的sqrt()开方运算。
  • distance_squared = (center1 - center2) ⋅ (center1 - center2)
  • radii_sum_squared = (r1 + r2) * (r1 + r2)
  • 相交条件: distance_squared ≤ radii_sum_squared

22.13.2 球体 vs Box (Sphere/Box)

• 核心思想: 找到Box上距离球心最近的点 (closest point)，然后判断该点到球心的距离是否小于球的半径。
• 算法 (Sphere vs AABB):
  1. 将球心的坐标 c 钳制 (clamp) 到AABB的 min 和 max 边界内，得到AABB上的最近点 p。
  2. 计算球心 c 和最近点 p 之间距离的平方 d²。
  3. 如果 d² ≤ r²，则相交。
• 优化:
  • 快速拒绝: 可以设计很多廉价的早期拒绝测试，比如逐轴检查球心到Box边界的距离。
  • 无分支实现: 对于SIMD（如SSE）非常友好，可以通过max操作实现无分支的距离计算，从而获得极高性能。
• Sphere vs OBB:
  1. 将球心变换到OBB的局部坐标系中。
  2. 此时OBB可以被看作一个AABB。
  3. 应用上面的Sphere vs AABB算法。

22.13.3 AABB vs AABB

• 核心思想: 这是最简单和最快的BV测试之一。两个AABB相交，当且仅当它们在X、Y、Z三个轴上的投影区间都重叠。
• 实现: 对X、Y、Z三个轴分别进行一次一维区间重叠测试。只要有一个轴不重叠，就立刻返回“不相交”。

22.13.4 k-DOP vs k-DOP

• 核心思想: 一个快速但不完全精确的保守测试 (conservative test)。它只会检查k-DOP定义的k/2对平行平板是否重叠。
• 算法:
  1. 遍历k/2个共享的法线方向。
  2. 在每个方向上，进行一次一维区间重叠测试。
  3. 如果任何一个方向上的区间不重叠，则k-DOPs不相交。
  4. 如果所有方向上的区间都重叠，则认为它们相交。
• 重要提示: 这是一个保守测试，意味着它可能会产生误报（False Positives）——报告相交但实际并未相交。这是因为它忽略了SAT中由边-边叉乘产生的测试轴。但好处是速度极快，且绝不会漏报（False Negatives）。

22.13.5 OBB vs OBB

• 核心思想: 这是分离轴测试 (SAT) 的“完全体”应用，是目前最流行和最高效的精确OBB相交测试方法。
• 算法准备:
  1. 将一个OBB(B)变换到另一个OBB(A)的局部坐标系中。这样，A就变成了中心在原点的AABB。
• 需要测试的15个分离轴:
  1. 3个轴: A的面法线 (在A的局部坐标系下就是X, Y, Z轴)。
  2. 3个轴: B的面法线。
  3. 9个轴: A的每条轴与B的每条轴的叉积。
• 流程: 与Triangle/Box测试完全相同：遍历15个轴，只要找到一个分离轴就立即返回“不相交”。如果15个轴都测完仍未找到分离，则返回“相交”。

22.14 视锥体相交测试 (Frustum Intersection Tests)

视锥体剔除 (Frustum Culling) 是实时渲染中最重要的性能优化手段之一。其核心就是高效地判断场景中的包围体（BV）与摄像机视锥体的空间关系。

核心概念：三种状态与保守测试

• 核心观点: 视锥体与BV的相交测试不只是返回“是/否”，而是返回三种精确的状态，每种状态都对应一种特定的优化策略。

  • 1. 完全位于外部 (Outside / Excluded): BV及其包含的所有子物体都完全不可见。整个子树被剔除，不再进行任何处理。这是最大的性能提升点。
  • 2. 完全位于内部 (Inside / Included): BV及其包含的所有子物体都完全可见。整个子树中的所有物体都被发送去渲染，无需再进行后续的视锥体测试。这也是一个重要的性能优化。
  • 3. 部分相交 (Intersection): BV本身与视锥体边界相交。我们无法对整个BV及其子树做出统一判断，必须递归地对其子节点进行进一步的视锥体测试。

• 保守测试 (Conservative Test) 原则:

  • 最关键的原则: 我们可以容忍性能上的小损失，但绝不能容忍渲染错误。
  • 允许的“错误”:
    • 把一个“外部”的物体误判为“相交”（性能损失：多做了一些无用的子节点测试）。
    • 把一个“内部”的物体误判为“相交”（性能损失：多做了一些本可避免的子节点测试）。
  • 绝不允许的错误:
    • 把一个“内部”或“相交”的物体误判为“外部”。这会导致物体突然从画面上消失，是严重的渲染Bug。
  • 因此，我们的剔除算法必须是保守的，宁可多画，也不能漏画。

22.14.1 提取视锥体平面

• 核心观点: 视锥体的6个平面方程可以从组合后的视图-投影矩阵 (View-Projection Matrix) M = P × V 中被极其高效地提取出来。

• 原理简介:

  1. 一个世界坐标点 s 经过矩阵 M 变换到裁剪空间 t = M × s。
  2. 在裁剪空间中，一个点是否在视锥体内，取决于它是否在由 w 定义的6个平面内（例如，对于左平面，需要满足 t.x >= -t.w，即 t.x + t.w >= 0）。
  3. 由于 t.x 和 t.w 分别是矩阵 M 的第一行和第四行与点 s 的点积，因此 (m_row0 + m_row3) ⋅ s >= 0 就直接定义了世界空间中的左裁剪平面。

• 提取公式 (以OpenGL标准为例): 设 m_i 为组合矩阵 M 的第 i 行（从0开始）。

  $$\begin{array}{rl}\text{Left Plane}& ={\mathbf{m}}_3+{\mathbf{m}}_0\\ \text{Right Plane}& ={\mathbf{m}}_3-{\mathbf{m}}_0\\ \text{Bottom Plane}& ={\mathbf{m}}_3+{\mathbf{m}}_1\\ \text{Top Plane}& ={\mathbf{m}}_3-{\mathbf{m}}_1\\ \text{Near Plane}& ={\mathbf{m}}_3+{\mathbf{m}}_2\\ \text{Far Plane}& ={\mathbf{m}}_3-{\mathbf{m}}_2\end{array}$$

  注：得到的平面向量 (a, b, c, d) 可能需要归一化，并且其正方向（指向视锥体外部）可能需要根据矩阵的构建方式进行调整。

22.14.2 视锥体/球体相交 (Frustum/Sphere Intersection)

• 核心思想: 逐一测试球体与视锥体的6个平面。

• 算法流程:

  1. 初始化一个计数器 planes_inside = 0。
  2. 遍历视锥体的6个平面。
  3. 对于每个平面，计算球心 c 到该平面的有符号距离 d。
  4. 外部测试 (Early Exit): 如果 d > r (球心在平面外侧，且距离超过半径)，说明球体完全位于该平面的外部。由于视锥体是凸的，因此球体必然完全位于视锥体外部。立即返回 OUTSIDE 并终止算法。
  5. 内部测试: 如果 d < -r (球心在平面内侧，且距离超过半径)，说明球体完全位于该平面的内部。planes_inside 计数器加一。
  6. 循环结束后判断:
     • 如果 planes_inside == 6，说明球体在所有6个平面的内部，返回 INSIDE。
     • 否则，返回 INTERSECTING。

• 注意: 这个算法是保守的。当球体恰好位于视锥体外侧的“角落”时，它可能不会被任何一个平面完全排除，从而被误判为“相交”。这是一种可接受的性能权衡。

22.14.3 视锥体/Box相交 (Frustum/Box Intersection)

最常用且在CPU上高效的方法也是逐平面测试。

• 核心思想: 逐一使用前面章节介绍的高效平面/Box相交测试算法，来判断Box与视锥体6个平面的关系。

• 算法流程:

  1. 初始化一个计数器 planes_inside = 0。
  2. 遍历视锥体的6个平面。
  3. 对于每个平面，执行平面/Box相交测试 (见22.10)，该测试本身会返回“完全在外”、“完全在内”或“相交”三种状态。
  4. 外部测试 (Early Exit): 如果Box完全位于任何一个平面的外部，立即返回 OUTSIDE 并终止算法。
  5. 内部测试: 如果Box完全位于某个平面的内部，planes_inside 计数器加一。
  6. 循环结束后判断:
     • 如果 planes_inside == 6，说明Box在所有6个平面的内部，返回 INSIDE。
     • 否则，返回 INTERSECTING。

• 另一种方法：裁剪空间测试

  • 思想: 将Box的8个顶点全部变换到裁剪空间，然后直接与NDC（Normalized Device Coordinates）立方体进行比较。
  • 优点: 无需提取平面，逻辑简单，在GPU Compute Shader中剔除时非常受欢迎。
  • 缺点: 在CPU上，变换8个顶点的开销通常比6次平面测试要高。

22.15 线/线相交 (Line/Line Intersection)

这一节提供了在2D和3D中寻找两条线交点的精确数学方法。理解这些方法不仅能解决线段相交问题，还能加深对向量代数的理解。

22.15.1 二维 (2D)

方法1: 垂直点积法 (Elegant Vector Solution)

• 核心观点: 利用二维向量的垂直点积 (Perpendicular Dot Product) 属性（a ⋅ a_perp = 0），可以巧妙地解耦线性方程组，直接求出两条线的交点参数 s 和 t。

• 推导: 给定两条线 r₁(s) = o₁ + s⋅d₁ 和 r₂(t) = o₂ + t⋅d₂，令它们相等： o₁ + s⋅d₁ = o₂ + t⋅d₂ 为了求解 s，我们将方程两边同时点乘 d₂_perp。这会使 t 项消失，因为 d₂ ⋅ d₂_perp = 0。

  $$s({\mathbf{d}}_1\cdot {\mathbf{d}}_2^{\perp })=({\mathbf{o}}_2-{\mathbf{o}}_1)\cdot {\mathbf{d}}_2^{\perp }⟹s=\frac{({\mathbf{o}}_2-{\mathbf{o}}_1)\cdot {\mathbf{d}}_2^{\perp }}{{\mathbf{d}}_1\cdot {\mathbf{d}}_2^{\perp }}$$

  同理可求得 t：

  $$t=\frac{({\mathbf{o}}_1-{\mathbf{o}}_2)\cdot {\mathbf{d}}_1^{\perp }}{{\mathbf{d}}_2\cdot {\mathbf{d}}_1^{\perp }}$$

• 判断:

  • 平行: 如果分母 d₁ ⋅ d₂_perp 等于0，则两线平行。
  • 相交类型:
    • 线段 (Segment): 交点有效当且仅当 0 ≤ s ≤ 1 且 0 ≤ t ≤ 1。
    • 射线 (Ray): 交点有效当且仅当 s ≥ 0 且 t ≥ 0。

方法2: 高效比较法 (Fast Comparison Solution)

• 核心观点: 在实践中，除法是非常昂贵的计算。此方法通过将参数 s 和 t 表示为分数形式，并利用比较来代替除法，从而实现提前拒绝，性能更高。

• 原理:

  1. 将 s 和 t 表示为具有公共分母 f 的分数：s = d/f, t = e/f。
  2. 我们不需要计算出 s 的确切浮点值来判断 0 ≤ s ≤ 1。
  3. 取而代之，我们可以直接比较分子和分母：
     • 如果 f > 0，则 0 ≤ s ≤ 1 等价于 0 ≤ d ≤ f。
     • 如果 f < 0，则 0 ≤ s ≤ 1 等价于 f ≤ d ≤ 0。
  4. 通过这种方式，我们将昂贵的除法和浮点数比较替换为廉价的整数或浮点数比较，从而可以更快地判断线段是否相交。

22.15.2 三维 (3D)

• 核心观点: 3D线/线相交的求解过程是2D方法的直接扩展，用叉积 (Cross Product) 代替了2D中的垂直点积。

• 推导: 从 o₁ + s⋅d₁ = o₂ + t⋅d₂ 开始。为了求解 s，我们将方程两边同时叉乘 d₂，这会使 t 项消失 (d₂ × d₂ = 0)。这会得到一个向量方程。为了得到标量，我们再将结果点乘 (d₁ × d₂)，最终解出 s 和 t。

  $$s=\frac{\det ({\mathbf{o}}_2-{\mathbf{o}}_1,{\mathbf{d}}_2,{\mathbf{d}}_1\times {\mathbf{d}}_2)}{\Vert {\mathbf{d}}_1\times {\mathbf{d}}_2{\Vert }^2},t=\frac{\det ({\mathbf{o}}_2-{\mathbf{o}}_1,{\mathbf{d}}_1,{\mathbf{d}}_1\times {\mathbf{d}}_2)}{\Vert {\mathbf{d}}_1\times {\mathbf{d}}_2{\Vert }^2}$$

• 重要特性:

  • 平行: 如果分母 ||d₁ × d₂||² 等于0，则两线平行。
  • 斜线 (Skew Lines): 在3D中，两条不平行的线也可能不相交（即它们是斜线）。在这种情况下，上面公式计算出的 s 和 t 值对应的是这两条线上距离最近的点 (points of closest approach)，这在很多应用中也极其有用。

---

22.16 三平面相交 (Three Plane Intersection)

• 核心观点: 三个互不平行的平面在3D空间中会相交于一个唯一点。这个点的坐标可以用一个直接的公式算出。

• 求解公式: 给定三个平面，每个平面由法线 nᵢ 和平面上一点 pᵢ 定义，其交点 p 为：

  $$\mathbf{p}=\frac{({\mathbf{p}}_1\cdot {\mathbf{n}}_1)({\mathbf{n}}_2\times {\mathbf{n}}_3)+({\mathbf{p}}_2\cdot {\mathbf{n}}_2)({\mathbf{n}}_3\times {\mathbf{n}}_1)+({\mathbf{p}}_3\cdot {\mathbf{n}}_3)({\mathbf{n}}_1\times {\mathbf{n}}_2)}{\det ({\mathbf{n}}_1,{\mathbf{n}}_2,{\mathbf{n}}_3)}$$

• 关键点:

  • 平行/共线检查: 公式的分母是三个法线的标量三重积 (Scalar Triple Product)。如果分母为0，说明三个法线向量共面，这意味着至少有两个平面是平行的，因此不存在唯一的交点。
  • 从 ax+by+cz+d=0 获取 pᵢ: 如果平面由隐式方程 n⋅x + d = 0 给出（其中 n 是单位法线），那么该平面上离原点最近的点 pᵢ 可以很方便地计算出来： pᵢ = -dᵢ ⋅ nᵢ。
  • 应用: 这个公式对于计算由平面定义的BV（如视锥体、k-DOP、凸多面体）的角点非常有用。

---

补充阅读和资源

本章最后提供了一份宝贵的资源列表，对于希望深入研究碰撞检测和相交测试的开发者来说非常有价值。

• 核心推荐书籍:
  • 《Real-Time Collision Detection》 by Christer Ericson: 碰撞检测领域的“圣经”，覆盖面广且深入，包含大量实用代码。
  • 《3D Game Engine Design》 和 《Geometric Tools for Computer Graphics》 by David H. Eberly: 提供了坚实的数学和几何算法基础。
• 其他资源:
  • Journal of Computer Graphics Techniques (JCGT): 开放获取的期刊，经常发表最新的图形学算法和代码。
  • 《Graphics Gems》系列: 经典算法和代码片段的宝库。
  • realtimerendering.com: 本书的官方网站，有专门的页面总结了各种相交测试的资源链接。

---