想象你是一个仓库管理员，负责管理一个堆满杂物的巨型仓库。每天都有无数货物被搬进搬出，而你最核心的任务只有一个：判断两个箱子有没有碰到一起。如果你每来一个新箱子，就要和仓库里所有箱子逐一比对位置，那么当仓库里有 10000 个箱子时，光是检查一个新箱子就要比对 10000 次——游戏里每秒钟要搬运 60 次，你的仓库就会彻底瘫痪。 这就是碰撞检测要解决的核心难题。在本篇文章中，我们将化身“空间管理者”，学习两件神兵利器：BVH（层次包围体树），它像一套智能的仓库分区索引系统，让你瞬间锁定“可能相撞的候选区域”；GJK（吉尔伯特-约翰逊-基尔思算法），它则像一把神奇的“距离刻度尺”，能精确告诉你两个物体之间的最短距离，甚至直接判断它们是否相交。掌握了这两样工具，你就能在游戏物理、机器人运动规划、动画仿真等领域游刃有余。

岗位关联

对于 AI 从业者而言，碰撞检测是游戏 AI、具身智能与物理仿真的底层基础设施。理解 BVH 与 GJK，不仅能帮你读懂主流物理引擎（如 PhysX、Bullet）的核心逻辑，更能让你在设计智能体导航、抓取规划时，对“空间感知”的代价与优化有直觉判断。

目录
  1. 可视化演示
  2. 碰撞检测概述
  3. 朴素方法局限
  4. BVH树构建
  5. BVH遍历更新
  6. GJK原理基础
  7. GJK迭代实现
  8. 算法选型策略
  9. 工程实践优化
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示碰撞检测三大核心：BVH层次包围盒树查询、GJK单纯形迭代演化、宽相/窄相性能对比，切换查看算法运行机制。

本节配有交互动效（进入视口后自动加载，约 3KB）。

BVH层次包围盒树 根节点AABB包含全部对象，逐层二分至叶节点 查询点仅需遍历相交叶节点，裁剪无关分支 Query = O(log N) vs Brute = O(N) 层次结构将碰撞查询从O(N)降至O(log N)

碰撞检测概述

想象你是一位仓库管理员，每天的任务是确保货物之间没有“亲密接触”。当你从传送带上接下新箱子时，第一件事就是判断它是否顶到了旁边的箱子。这个“是否重叠”的判断，就是碰撞检测的本质。在物理模拟的世界里，每一个 3D 模型都是“货物”，而碰撞检测系统就是那个不知疲倦的管理员——它每时每刻都在回答一个问题：“这两个物体碰上了吗？”

在游戏物理引擎中，碰撞检测通常被拆分为两个阶段：广阶段和窄阶段。广阶段就像管理员先用眼睛扫一遍仓库，快速排除掉那些明显离得很远的货物；窄阶段则像走近后用卷尺精确测量，确认是否真的发生了接触。这种分层策略的智慧在于：用廉价的计算过滤掉大量的“不可能”，把昂贵的精确计算留给少数的“可能”。

从更宏观的角度看，碰撞检测是物理模拟的基石。没有它，子弹会穿过墙壁，汽车会陷入地面，角色会踩空楼梯。它是连接“逻辑世界”与“物理世界”的桥梁，也是游戏 AI 感知环境的重要手段——智能体知道“前方有障碍”这件事本身，就依赖着一套高效的碰撞查询系统。

朴素方法局限

让我们回到仓库场景：如果你是一个新手管理员，最简单的做法是什么？——把新来的箱子和仓库里每一个已有的箱子都比一遍。这就是朴素方法：对所有物体对进行两两检测。听起来很直接，但设想一下：仓库里有 100 个箱子，你需要比对 $100 \times 99 / 2 = 4950$ 对；有 1000 个箱子，就是约 50 万对；有 10000 个箱子，则是约 5000 万对。

这种方法的计算量随物体数量呈平方级增长，用数学语言描述就是 $O(n^2)$ 复杂度。在游戏场景中，一个中等规模的关卡可能有数万个独立物体（石块、碎片、子弹、角色），如果每帧都进行一次 5000 万次级别的两两比对，再强大的 CPU 也会不堪重负。

因此，我们迫切需要一种“空间剔除”策略——不去检测所有物体对，而是先通过某种廉价手段，把明显不相交的物体对直接丢弃。BVH 和 GJK 正是解决这个问题的两把钥匙，但它们解决的问题层次不同：BVH 解决的是“哪些物体对可能靠近”，GJK 解决的是“两个物体到底有没有相交”。后者通常是前者筛选出的少数候选对之间的距离判定工具。

BVH树构建

既然不能逐一比对，那就得像图书馆给书籍编目一样，给空间建立索引。BVH（Bounding Volume Hierarchy，层次包围体树） 就是这样一个空间索引结构。它的核心思想是：用简单的几何体（通常是轴对齐包围盒 AABB）把物体包裹起来，然后把这些包围盒组织成一棵二叉树，父节点的包围盒完整地包住所有子节点的包围盒。

构建 BVH 的过程非常像管理员给仓库分区：先把所有货物分成左右两堆，分别放进两个大箱子；然后每个大箱子内部再分成两小堆，放进更小的箱子；如此递归下去，直到每个箱子里只剩一个货物。这个“递归二分”的策略，可以用中位切分（median split）或表面积启发式（SAH）来指导分割位置。

在数学上，BVH 的构建可以看作是一个递归的空间划分过程。假设我们有一组物体 $S$，我们选择一个分割轴（如 x 轴），按中心坐标排序后取中位数 $m$，将 $S$ 分为 $S_L$ 和 $S_R$，然后递归构建左右子树，直到 $|S| = 1$。每个节点存储其包围盒 $B = \bigcup_{o \in S} \text{AABB}(o)$。

当 BVH 构建完成后，查询两个物体是否碰撞就变成了一次“从上到下”的搜索：先检测两个根节点包围盒是否重叠，如果不重叠，整棵子树直接剪枝；如果重叠，则递归进入子节点检测。这个过程像极了管理员先在仓库平面图上圈出两个区域，只有区域之间有交集时，才去区域内部逐一检查货物。

BVH(S)={Leaf(S)if ∣S∣≤1Node(B,BVH(SL),BVH(SR))otherwise\text{BVH}(S) =\begin{cases}\text{Leaf}(S) & \text{if } |S| \leq 1 \\\text{Node}(B, \text{BVH}(S_L), \text{BVH}(S_R)) & \text{otherwise}\end{cases}
BVH 的本质是用“大箱子套小箱子”的收纳智慧，把空间关系组织成树形索引，让碰撞查询从全局搜索变成局部递归。
  1. 叶子节点判定如果当前集合 $S$ 中只有一个物体，就创建一个叶子节点，存储该物体的包围盒。
    Leaf(S)if ∣S∣≤1\text{Leaf}(S) \quad \text{if } |S| \leq 1
  2. 内部节点分割否则，选择一个分割轴，将物体集合分成左右两部分，递归构建子树。
    Node(B,BVH(SL),BVH(SR))\text{Node}(B, \text{BVH}(S_L), \text{BVH}(S_R))
  3. 包围盒合并父节点的包围盒 $B$ 是所有子物体包围盒的并集——它必须完整覆盖其所有后代。
    B=⋃o∈SAABB(o)B = \bigcup_{o \in S} \text{AABB}(o)

BVH遍历更新

BVH 建好之后，真正考验功力的是如何高效地使用它。想象你每天都要接收新货物，仓库的布局随时在变——有些箱子被移走了，有些新箱子加了进来。如果每次都要重新构建整棵树，那成本太高了。聪明的做法是：能局部调整的就不要全局重建。

BVH 的遍历过程遵循“自顶向下、重叠剪枝”的法则。假设我们要检测物体 $X$ 与场景中所有物体的碰撞：从根节点出发，检测 $X$ 的包围盒与当前节点的包围盒是否重叠。如果不重叠，这棵子树里所有物体都不可能和 $X$ 碰撞，直接剪枝跳过；如果重叠，就继续向下检测两个子节点。这样，我们常常只需要访问树的一小部分，就能确定碰撞关系。

对于动态物体，我们有两种更新策略：重构（rebuild） 和 更新（refit）。重构是重新构建整棵树，代价高但质量好；更新是自底向上重新计算包围盒，代价低但可能让树的质量退化。实践中常用“惰性更新”策略——只有当物体的移动距离超过某个阈值时，才触发局部重构。

在游戏物理引擎中，静态场景（墙壁、地面）的 BVH 通常只构建一次；动态物体（角色、子弹）则每帧更新它们在树中的位置。通过合理的更新策略，BVH 能在保持查询效率的同时，避免每帧全量重建的开销——这就像管理员只需要微调局部货架的位置，而不必把整个仓库重新装修一遍。

Traversal(X,N)={∅if AABB(X)∩BN=∅LeafCheck(X,N)if N is leafTraversal(X,NL)∪Traversal(X,NR)otherwise\text{Traversal}(X, N) =\begin{cases}\varnothing & \text{if } \text{AABB}(X) \cap B_N = \varnothing \\\text{LeafCheck}(X, N) & \text{if } N \text{ is leaf} \\\text{Traversal}(X, N_L) \cup \text{Traversal}(X, N_R) & \text{otherwise}\end{cases}
BVH 遍历与更新，是一门关于“怎样用最小的努力维持大仓库秩序”的学问。真正优秀的物理引擎，总是静悄悄地把树的维护成本藏在了每一帧的低延迟背后。
  1. 包围盒重叠测试检测物体 $X$ 的包围盒与当前节点 $N$ 的包围盒 $B_N$ 是否相交。如果不相交，返回空集——整棵子树被剪枝。
    if AABB(X)∩BN=∅⇒∅\text{if } \text{AABB}(X) \cap B_N = \varnothing \Rightarrow \varnothing
  2. 叶子节点检测如果当前节点是叶子，直接对 $X$ 与该叶子中的物体做精确碰撞检测。
    LeafCheck(X,N)\text{LeafCheck}(X, N)
  3. 递归深入如果包围盒重叠且不是叶子，就同时向下遍历左右子树，合并结果。
    Traversal(X,NL)∪Traversal(X,NR)\text{Traversal}(X, N_L) \cup \text{Traversal}(X, N_R)

GJK原理基础

如果说 BVH 回答的是“哪些物体可能碰在一起”，那么 GJK 算法回答的就是“这两个物体到底有没有碰在一起”。GJK 的绝妙之处在于，它不直接比较两个物体的形状，而是通过明可夫斯基差（Minkowski Difference）把问题转化为“一个点是否在一个凸集内”。

让我用一个更生活化的比喻来解释：你有两个形状奇怪的积木，想知道它们是否重叠。最笨的方法是直接拿积木去比对——如果积木形状复杂，这就是一场噩梦。GJK 的做法是：把积木 A 的每个点减去积木 B 的每个点，得到一大堆新点，构成一个“差集”形状。如果差集包含原点，说明两个积木必然重叠——因为存在至少一对点 $a$ 和 $b$ 使得 $a - b = 0$，即 $a = b$。

支撑函数（Support Function）是 GJK 的灵魂。给定一个方向 $d$，支撑函数返回凸体上沿该方向最远的点：

对两个凸体做差，我们可以在差集上定义支撑函数——只需分别计算两个物体的支撑点再做减法：

GJK 的输入是两个凸体的顶点集合（或多面体描述），输出是一个布尔值：是否碰撞。它通过迭代构建一个单纯形（simplex）——在 2D 中是三角形，在 3D 中是四面体——逐步逼近原点，判断原点能否被单纯形包含。这个过程就像用三根手指逐渐捏住一个小球，通过不断调整手的姿态，最终判断小球是否在手心内。

SA(d)=arg⁡max⁡p∈A(p⋅d)S_A(d) = \arg\max_{p \in A} (p \cdot d)
SA−B(d)=SA(d)−SB(−d)S_{A-B}(d) = S_A(d) - S_B(-d)
GJK 的核心思想可以浓缩为一句话：与其直接问“两个积木是否重叠”，不如换个视角问“差集是否包含了原点”。这个视角的转换，让碰撞检测从几何难题变成了简单的包含判定。
  1. 明可夫斯基差定义差集 $A - B$ 包含所有形如 $a - b$ 的点，其中 $a \in A$，$b \in B$。原点属于差集当且仅当 A 与 B 重叠。
    A−B={a−b∣a∈A,b∈B}A - B = \{a - b \mid a \in A, b \in B\}
  2. 支撑点求解在方向 $d$ 上，$A$ 的支撑点是使投影 $p \cdot d$ 最大的点。
    SA(d)=arg⁡max⁡p∈A(p⋅d)S_A(d) = \arg\max_{p \in A} (p \cdot d)
  3. 差集支撑函数利用 $S_A$ 和 $S_B$，可以直接计算差集的支撑点，无需显式构造差集。
    SA−B(d)=SA(d)−SB(−d)S_{A-B}(d) = S_A(d) - S_B(-d)

GJK迭代实现

现在让我们深入 GJK 的迭代实现，看看它是如何一步步逼近真相的。想象你要判断原点是否在一个未知形状（差集）内，但你无法直接看到这个形状的全貌——你只有一个“探针”（支撑函数），可以向任意方向发射，返回那个方向上的最远点。

GJK 的迭代过程可以用“猜方向、找支撑、验包含”九字诀概括。首先选择一个初始方向 $d$（比如 $d = (1, 0)$），计算支撑点 $S_{A-B}(d)$；然后将支撑点加入单纯形，检查当前单纯形能否包含原点。如果不能，就根据单纯形中离原点最近的面/边，更新搜索方向 $d$，继续迭代。当支撑点无法让单纯形更靠近原点时，算法终止并判定“不碰撞”；当单纯形包含原点时，判定“碰撞”。

在实际的物理引擎中，GJK 通常配合 EPA（Expanding Polytope Algorithm） 一起使用——GJK 判断是否碰撞，EPA 计算碰撞的深度和法向量。而这个迭代过程之所以高效，是因为它通常在 3-4 次迭代内就能收敛——就像一个有经验的管理员，只需要瞥几眼就能判断两个货物是否贴在一起，而不是翻来覆去地测量。

GJK(A,B):{d←任意初始方向s←SA−B(d)V←{s}loop:if containsOrigin(V) then return Trued←closestDirection(V)s′←SA−B(d)if s′⋅d<0 then return FalseV←reduceSimplex(V∪{s′})\text{GJK}(A, B):\begin{cases}d \leftarrow \text{任意初始方向} \\s \leftarrow S_{A-B}(d) \\V \leftarrow \{s\} \\\text{loop:} \\\quad \text{if } \text{containsOrigin}(V) \text{ then return True} \\\quad d \leftarrow \text{closestDirection}(V) \\\quad s' \leftarrow S_{A-B}(d) \\\quad \text{if } s' \cdot d < 0 \text{ then return False} \\\quad V \leftarrow \text{reduceSimplex}(V \cup \{s'\})\end{cases}
GJK 的迭代智慧在于“每次只问对一个问题”：方向选对了，答案自然浮现。它不追求一步到位，而是用快速的局部反馈不断逼近全局真相。
  1. 初始化方向与单纯形选定初始搜索方向 $d$，计算第一个支撑点并放入单纯形 $V$。
    d←InitialDirection,V←{SA−B(d)}d \leftarrow \text{InitialDirection}, \quad V \leftarrow \{S_{A-B}(d)\}
  2. 原点包含检查如果当前单纯形（线段、三角形或四面体）包含原点，立即判定碰撞。
    containsOrigin(V)=True⇒Collision\text{containsOrigin}(V) = \text{True} \Rightarrow \text{Collision}
  3. 更新搜索方向计算单纯形中距离原点最近的特征（2D 中是边，3D 中是面），以其法向量作为新的搜索方向。
    d←closestDirection(V)d \leftarrow \text{closestDirection}(V)
  4. 终止条件判断如果新支撑点在方向 $d$ 上的投影为负，说明无论如何也无法跨越原点，判定不碰撞。
    s′⋅d<0⇒No Collisions' \cdot d < 0 \Rightarrow \text{No Collision}

算法选型策略

仓库管理员的工具箱里不止一种工具。当你面对不同的货物和场景时，需要懂得选择最合适的检测策略——这就是算法选型的艺术。

首先，GJK 是一种“窄阶段”精确检测算法，适用于凸体与凸体之间的碰撞判定。它的优点是快速、优雅、支持任意凸形状（包括由三角形网格构成的凸多面体）；缺点是它只适用于凸体，对于凹形状需要先做凸分解。在物理引擎中，Box、Sphere、Capsule、ConvexHull 这些基础碰撞体都由 GJK（或其变体）处理。

其次，BVH 更多用于“广阶段”的候选筛选，以及静态网格（如地形、建筑物）与动态物体之间的碰撞查询。一个典型的混合架构是：场景中所有动态物体维护一棵 BVH，每帧先通过 BVH 遍历找出“可能碰撞的候选对”，然后对每一对候选调用 GJK 做精确判定。这就是 Bullet、PhysX 等主流物理引擎的标准做法。

最后，特殊形状有特殊处理。球与球之间只需比较距离与半径之和；球与平面只需计算点到平面距离；而两个由三角形网格构成的大型复杂模型，则通常用 BVH 做三角形的层次裁剪。选型的核心原则是：用最快的算法解决最简单的情况，把复杂情况留给更精确但更昂贵的算法。

在实践中，游戏开发者还会根据物体的物理材质与运动状态做进一步的优化：例如，静态物体使用预计算的 BVH，动态物体使用较浅的 BVH 或直接两两检测；高速物体开启连续碰撞检测（CCD），防止“隧道效应”（物体一帧内穿过薄墙）。这些策略的本质，都是对“空间查询的成本”与“物理模拟的精度”之间的权衡取舍。

Cost=Nbroad×Cbroad+Nnarrow×Cnarrow\text{Cost} = N_{\text{broad}} \times C_{\text{broad}} + N_{\text{narrow}} \times C_{\text{narrow}}
算法选型就像管理员的直觉：面对一堆棉花，你只需要远远看一眼就知道不会撞坏；面对一箱瓷器，你才会走近用卷尺仔细测量。聪明的工程师总是让简单的检测处理大多数情况，把精确的计算留给少数关键碰撞。
  1. 广阶段代价$N_{\text{broad}}$ 是广阶段需要检测的物体对数量，$C_{\text{broad}}$ 是每次检测的代价——通常是一次包围盒重叠测试，非常廉价。
    Nbroad×CbroadN_{\text{broad}} \times C_{\text{broad}}
  2. 窄阶段代价$N_{\text{narrow}}$ 是通过广阶段筛选后需要精确检测的物体对数，$C_{\text{narrow}}$ 是每次精确检测的代价（如 GJK 的迭代）。
    Nnarrow×CnarrowN_{\text{narrow}} \times C_{\text{narrow}}
  3. 成本权衡总代价是两者之和。BVH 的作用是降低 $N_{\text{narrow}}$，GJK 的作用是控制 $C_{\text{narrow}}$。
    Total=Nbroad×Cbroad+Nnarrow×Cnarrow\text{Total} = N_{\text{broad}} \times C_{\text{broad}} + N_{\text{narrow}} \times C_{\text{narrow}}

工程实践优化

即使选对了算法，真正的考验还在工程优化——就像仓库管理员不仅要有好工具，还要有好习惯。碰撞检测性能优化的核心思路是：让 CPU 别做无用功。

第一板斧是时空分治。时间上，我们可以把场景中的物体按运动状态分类：静态物体（墙壁）、动态物体（角色）、高速物体（子弹）。空间上，我们可以用 BVH 或者网格（Grid）把场景分区。分治的核心目标是“每次查询只触及局部”。例如，玩家角色周围的物理查询，只需要访问角色附近的几个空间格子，而不是整个 BVH。

第二板斧是并行化与 SIMD。现代 CPU 拥有多个核心和宽向量指令（SIMD），我们可以让多个碰撞检测任务并行执行。例如，一个 BVH 节点有多个子节点需要检测时，可以并行处理；GJK 中的支撑点计算也可以写成 SIMD 友好的向量运算。在物理引擎中，通常使用任务图（Task Graph） 来管理并行物理模拟的依赖关系。

第三板斧是缓存与增量更新。BVH 的 refit 操作可以复用旧的树结构，只更新移动物体的包围盒；碰撞检测的结果可以被缓存，用于下一帧的初始猜测（temporal coherence，时间连贯性）；内存布局上，尽量让 BVH 节点的数据连续存储，提高 CPU 缓存命中率。

另一个重要的优化手段是查询缓存与批量化。在游戏 AI 中，同一个智能体可能在一帧内发起多次形状查询（如“前方是否有障碍”、“左右是否有掩体”）。将这些查询合并成一批，统一走一遍 BVH 遍历，可以显著减少遍历次数。此外，物理引擎还可以利用 GPU 进行批量碰撞检测——让 GPU 并行处理数千个窄阶段检测任务，从而释放 CPU。

T(n)=Tcull(n)+Texact(m)+Tupdate(n)T(n) = T_{\text{cull}}(n) + T_{\text{exact}}(m) + T_{\text{update}}(n)
工程优化的本质，是让物理模拟的每一毫秒都花在刀刃上。正如优秀的管理员不会在夕阳西下时还在数箱子——他们早已用索引、分区和智能的更新策略，把每天的工作浓缩成了一杯茶的功夫。
  1. 剔除时间$T_{\text{cull}}(n)$ 是广阶段的时间，与物体总数 $n$ 相关，但希望是近线性的。
    Tcull(n)=O(nlog⁡n)T_{\text{cull}}(n) = O(n \log n)
  2. 精确检测时间$T_{\text{exact}}(m)$ 是窄阶段的时间，与候选对数量 $m$ 相关——我们的目标是通过剔除让 $m \ll n$。
    Texact(m)=O(m)T_{\text{exact}}(m) = O(m)
  3. 更新时间$T_{\text{update}}(n)$ 是每帧维护 BVH 结构的时间，可以通过增量更新和惰性策略来控制。
    Tupdate(n)=O(nlog⁡n)T_{\text{update}}(n) = O(n \log n)

AI 应用场景

机器人运动规划中的碰撞检测

阶段：数据生成与仿真验证

解决的问题：在机器人抓取和路径规划中，机器人必须知道“这个姿态下，机械臂会不会撞到障碍物”。传统方法需要机器人工程师手动编写碰撞规避规则，耗时且难以覆盖复杂场景。AI 方法（如强化学习）在训练过程中需要海量的碰撞查询——每一次动作尝试都要判断是否与环境碰撞，BVH+GJK 提供了亚毫秒级的碰撞查询，使训练成为可能。

具体案例：在 Isaac Sim 或 MuJoCo 等仿真环境中，机械臂模型由多个凸碰撞体（capsule、box）构成，环境物体则组织成 BVH。每次强化学习智能体选择一个动作，物理引擎通过 GJK 检查机械臂末端与周围物体的碰撞，返回布尔值或穿透深度，作为奖励信号的一部分。没有 GJK 的毫秒级检测，数百万步的训练根本无法在合理时间内完成。

游戏 AI 的感知系统

阶段：推理与决策

解决的问题：游戏中的 NPC 需要感知周围环境——“我能不能看到玩家？”、“掩体后面安全吗？”、“这条路可以通行吗？”。这些感知查询本质上都是碰撞检测或射线检测。AI 系统每帧可能发起上千次查询，必须依赖高效的 BVH 加速结构。

具体案例：在开放世界游戏《赛博朋克 2077》中，NPC 的 AI 使用“环境查询系统”：当 NPC 要寻找掩体时，系统向场景 BVH 发起球形查询（“半径 5 米内有哪些可站立表面？”），然后对候选项逐一做视线检测（射线 vs BVH）。整个查询链路的耗时必须控制在 0.1 毫秒以内，才能保证上百个 NPC 的 AI 同时运转。

数字孪生中的物理交互仿真

阶段：模型部署与在线推理

解决的问题：在工业数字孪生系统中，需要模拟传送带上的零件、机械臂、AGV 小车之间的物理交互。每一次“零件滑落”、“AGV 碰撞”事件，都需要物理引擎实时计算。BVH+GJK 组合能够处理数百个动态物体在复杂静态环境中（管道、支架）的实时碰撞。

具体案例：某汽车工厂的数字孪生系统，将产线上的 200 个 AGV 小车和 500 个静态障碍物（机器、货架）导入物理引擎。每帧先通过 BVH 找出 AGV 与静态障碍的候选碰撞对（约 200×log500 ≈ 1800 次查询），再用 GJK 精确判定，整体耗时稳定在 2 毫秒以内，支撑了工厂物流调度的实时仿真与预测。

Python 演示

python145 行
import mathimport random class Vec2:    def __init__(self, x, y):        self.x = x        self.y = y     def __sub__(self, other):        return Vec2(self.x - other.x, self.y - other.y)     def __add__(self, other):        return Vec2(self.x + other.x, self.y + other.y)     def __neg__(self):        return Vec2(-self.x, -self.y)     def dot(self, other):        return self.x * other.x + self.y * other.y     def perp(self):        return Vec2(-self.y, self.x) def support(poly, d):    """支撑函数：返回多边形在方向 d 上最远的点"""    best = None    best_dist = -float("inf")    for p in poly:        dist = p.dot(d)        if dist > best_dist:            best_dist = dist            best = p    return best def support_diff(A, B, d):    """差集 A-B 的支撑点 = support(A,d) - support(B,-d)"""    return support(A, d) - support(B, -d) def contains_origin_simplex(simplex):    """检查单纯形（线段或三角形）是否包含原点"""    if len(simplex) == 2:        a, b = simplex        ab = b - a        ao = Vec2(0, 0) - a        if ab.dot(ao) > 0:            return False        return True    else:        a, b, c = simplex        ab = b - a        ac = c - a        ao = Vec2(0, 0) - a        # 使用叉积符号判断原点是否在三角形内        ab_perp = ab.perp()        ac_perp = ac.perp()        if ab_perp.dot(ac) * ab_perp.dot(ao) < 0:            return False        if ac_perp.dot(ab) * ac_perp.dot(ao) < 0:            return False        return True def gjk_2d(A, B, max_iter=32):    """GJK 算法：判断两个凸多边形是否碰撞"""    d = Vec2(1, 0)    s = support_diff(A, B, d)    simplex = [s]    d = Vec2(0, 0) - s    for _ in range(max_iter):        s = support_diff(A, B, d)        if s.dot(d) < 0:            return False        simplex.append(s)        if contains_origin_simplex(simplex):            return True        # 根据单纯形更新搜索方向（简化版）        if len(simplex) == 2:            a, b = simplex            ab = b - a            ao = Vec2(0, 0) - a            d = ab.perp() if ab.perp().dot(ao) > 0 else (Vec2(0, 0) - ab.perp())        else:            # 3 个点：需要去掉离原点最远的点（简化处理）            a, b, c = simplex            distances = [a.x * a.x + a.y * a.y, b.x * b.x + b.y * b.y, c.x * c.x + c.y * c.y]            idx = distances.index(max(distances))            simplex.pop(idx)            a, b = simplex[0], simplex[1]            ab = b - a            ao = Vec2(0, 0) - a            d = ab.perp() if ab.perp().dot(ao) < 0 else (Vec2(0, 0) - ab.perp())    return False class AABB:    def __init__(self, x, y, w, h):        self.x = x        self.y = y        self.w = w        self.h = h     def overlaps(self, other):        return (self.x < other.x + other.w and self.x + self.w > other.x and                self.y < other.y + other.h and self.y + self.h > other.y) def build_bvh(objects):    """递归构建极简 BVH：返回 (包围盒, 左子树, 右子树, 物体列表)"""    if len(objects) <= 1:        return (objects[0], None, None, objects)    mid = len(objects) // 2    left = build_bvh(objects[:mid])    right = build_bvh(objects[mid:])    # 合并包围盒    l_box, r_box = left[0], right[0]    merged = AABB(min(l_box.x, r_box.x),                  min(l_box.y, r_box.y),                  max(l_box.x + l_box.w, r_box.x + r_box.w) - min(l_box.x, r_box.x),                  max(l_box.y + l_box.h, r_box.y + r_box.h) - min(l_box.y, r_box.y))    return (merged, left, right, objects) def query_bvh(node, box, results):    """查询 BVH：返回所有与 box 重叠的物体"""    if node is None:        return    if not node[0].overlaps(box):        return    if node[2] is None:        results.extend(node[3])        return    query_bvh(node[1], box, results)    query_bvh(node[2], box, results) if __name__ == "__main__":    # GJK 测试    random.seed(42)    poly_a = [Vec2(0, 0), Vec2(4, 0), Vec2(4, 4), Vec2(0, 4)]    poly_b = [Vec2(2, 2), Vec2(6, 2), Vec2(6, 6), Vec2(2, 6)]    print("GJK overlap:", gjk_2d(poly_a, poly_b))    poly_c = [Vec2(10, 10), Vec2(14, 10), Vec2(14, 14), Vec2(10, 14)]    print("GJK separated:", gjk_2d(poly_a, poly_c))     # BVH 测试    objects = [AABB(1, 1, 2, 2), AABB(3, 3, 1, 1), AABB(10, 10, 3, 3)]    tree = build_bvh(objects)    results = []    query_bvh(tree, AABB(0, 0, 5, 5), results)    print("BVH candidates:", len(results))
目的：用约 140 行 Python 实现了正文中讲解的两个核心算法——GJK 用于凸多边形碰撞判定，BVH 用于空间候选筛选，并包含可运行的测试入口，帮助读者直观理解算法行为。
  1. def support(poly, d):支撑函数是 GJK 的“探针”，在给定方向上找到多边形最远的顶点，是整个算法的基础操作。
  2. s = support_diff(A, B, d)利用明可夫斯基差的性质，直接通过两个物体的支撑点做差得到差集的支撑点，避免了显式构造差集的开销。
  3. if s.dot(d) < 0: return False这是 GJK 的终止条件：如果新的支撑点在当前搜索方向上投影为负，说明差集上的点无法跨越原点，因此不碰撞。
  4. def build_bvh(objects):递归构建 BVH 树的入口，采用中位切分策略，每次将物体列表分成两半并递归建树。简化版没有按坐标排序，但思想一致。
  5. merged = AABB(min(...), ...)合并左右子树的包围盒，父节点的包围盒必须覆盖所有子节点，这是 BVH 正确性的关键。
  6. if not node[0].overlaps(box): returnBVH 查询的剪枝操作：如果当前节点的包围盒与查询盒不相交，整个子树直接跳过，节省了大量无效计算。

常见误区

误区“BVH 是一种碰撞检测算法，我可以用它直接判断两个物体有没有碰在一起。”

正解BVH 本质上是一种空间索引结构，它的作用是快速筛选出“可能相交的物体对”，而不是精确地判断两个物体是否相交。想象 BVH 是仓库的货架分区系统——它告诉你“这两堆货可能在相邻区域”，但真正确认两个箱子是否紧贴，你还需要走近测量。在物理引擎中，BVH 通常作为广阶段，筛选出候选对后交给 GJK 等窄阶段算法做精确判定。

为何常见：因为 BVH 的查询过程中确实包含了“包围盒重叠”测试，而两个包围盒重叠在很多简单场景下等价于物体相交，容易让人误以为 BVH 完成了碰撞判定。

误区“游戏里的角色、怪物都是复杂形状（凹的），GJK 只能处理凸体，所以 GJK 在真实游戏中没什么用。”

正解这是一个常见的误解。GJK 确实只适用于凸体，但物理引擎的解决方案是凸分解——把复杂的凹形状拆分成多个凸体的组合。例如，一个 L 形的墙壁可以拆成两个矩形；一个角色的胶囊体碰撞体本身就是凸的。此外，GJK 还被广泛用于处理凸多面体之间的碰撞（如盒子、胶囊、凸包网格），配合 EPA 算法还能计算碰撞深度和法向量。GJK 不仅有用，而且是现代物理引擎的基石之一。

为何常见：初学碰撞检测时接触的多是复杂的凹网格，看到“GJK 仅支持凸体”的限制，很容易误判它缺乏实用价值，而忽略了“凸分解”这一关键配套技术。

误区“BVH 建树之后，场景里的物体随便怎么动都没关系，树会自动保持正确。”

正解BVH 是一棵数据结构树，它的正确性依赖于每个节点的包围盒真实覆盖其子物体。当物体移动时，如果不更新 BVH，包围盒就会“过期”——明明物体已经移走了，包围盒还留在原地，导致查询结果错误。正确的做法是每帧检测物体位移，必要时refit（自底向上重新计算包围盒）或rebuild（重构整棵树）。物理引擎通常采用“惰性更新”策略：物体移动超过阈值才触发更新，以平衡开销与正确性。

为何常见：静态场景的 BVH 只需要构建一次，很多教程强调“BVH 构建的高效”，容易让人忽略动态物体的更新需求。

误区“GJK 能精确判断任意两个凸体是否碰撞，而 BVH 只是粗略的包围盒筛选，所以直接用 GJK 检测所有物体对不是更好吗？”

正解GJK 确实精确，但它的计算成本远高于一次包围盒重叠测试。如果有 n 个物体，两两做 GJK 需要 O(n²) 次调用，每次 GJK 都要经历多轮迭代（即使通常 3-5 轮就能收敛）。相比之下，BVH 的包围盒重叠测试只需要几次比较运算。正确的架构是：BVH 做广阶段快速剔除，GJK 做窄阶段精确判定。两者是配合关系，不是替代关系。

为何常见：初学者容易把“精确”和“高级”画等号，忽视了工程中最核心的成本意识——在空间计算中，最快的算法永远是“不计算”。

误区“BVH 和 GJK 是游戏引擎里的东西，我做 AI 或者是机器人研究用不到。”

正解碰撞检测是空间智能的基础设施，应用远不止游戏。机器人运动规划（RRT、PRM）需要碰撞查询来判断路径是否安全；自动驾驶中的障碍物检测与路径规划需要将激光雷达点云与车辆模型做碰撞检测；数字孪生系统需要模拟产线上物体的物理交互。在 AI 领域，强化学习训练智能体时，碰撞反馈是重要的奖励信号来源——没有高效的碰撞检测，训练根本无法在合理时间内完成。

为何常见：BVH 和 GJK 这个术语组合在游戏开发教程中出现频率最高，容易让人形成“游戏专属”的刻板印象，而忽视了其作为通用空间算法的本质。

面试题

Q1. BVH 中“包围盒”（Bounding Volume）的主要作用是什么？

单选题 · easy

  • A.精确描述物体的几何形状
  • B.用简单几何体近似包裹物体，用于快速剔除← 正确答案
  • C.替代碰撞网格，直接参与渲染
  • D.存储物体的材质信息

答案：B。包围盒用简单的几何体（如 AABB、球体）近似包裹复杂物体，目的是用廉价的测试代替昂贵的精确检测。它不描述精确形状（A 错）、不参与渲染（C 错）、不存储材质（D 错）。就像是给积木套上一个快递纸箱——纸箱不是为了展示积木，而是为了方便快速搬运。

Q2. 朴素碰撞检测（两两比对）的时间复杂度是？

单选题 · easy

  • A.O(n)
  • B.O(n log n)
  • C.O(n²)← 正确答案
  • D.O(1)

答案：C。n 个物体两两配对需要比较 n(n-1)/2 对，即 O(n²)。当物体数量从 100 增加到 1000 时，计算量增加约 100 倍——这就是为什么大场景必须使用 BVH 等空间索引结构来降低无效比对次数。

Q3. GJK 算法用于判断两个凸体是否相交时，将问题转化为了？

单选题 · mid

  • A.计算两个凸体的质心距离
  • B.判断明可夫斯基差是否包含原点← 正确答案
  • C.求两个凸体的交集体积
  • D.比较两个凸体的表面积大小

答案：B。GJK 的核心思想是通过明可夫斯基差 A-B，把碰撞检测转化为判断原点是否属于差集——差集包含原点当且仅当两凸体重叠。就像把“两个影子是否重叠”转化为“一个影子是否盖住了某个固定点”。

Q4. 在 BVH 遍历过程中，如果当前节点的包围盒与查询包围盒不相交，正确的做法是？

单选题 · mid

  • A.继续检测该节点的所有子节点
  • B.将该节点加入结果集
  • C.直接剪枝，跳过该节点整棵子树← 正确答案
  • D.重新构建整棵 BVH 树

答案：C。BVH 的核心优化就是剪枝：如果父节点包围盒与查询盒不相交，那么所有子节点中的物体也不可能相交，直接跳过整棵子树可以节省大量计算。这是空间管理员的智慧——某个货架区域完全不在查询范围内，就没必要走进去逐个检查。

Q5. GJK 迭代中，终止条件“新支撑点与搜索方向的点积小于零”意味着什么？

单选题 · mid

  • A.两个物体一定碰撞
  • B.两个物体一定不碰撞← 正确答案
  • C.需要增加迭代次数
  • D.需要更换初始方向

答案：B。支撑点到当前方向投影为负，说明在当前搜索方向上，差集无法越过原点——即无法用新的支撑点逼近原点。这是 GJK 判定“不碰撞”的数学依据。就像探针向某个方向探测后确认那里是真空，永远不会碰到物体。

Q6. 关于 BVH 和 GJK 在物理引擎中的配合方式，下列说法正确的是？

单选题 · hard

  • A.BVH 负责精确判定，GJK 负责候选筛选
  • B.BVH 作为广阶段筛选候选对，GJK 作为窄阶段精确检测← 正确答案
  • C.两者功能重复，只需选择其一
  • D.GJK 的结果需要 BVH 做二次验证

答案：B。标准物理引擎架构中，BVH 以极低的代价快速剔除“不可能碰撞”的物体对（广阶段），GJK 只对少数候选对做精确检测（窄阶段）。如同管理员先用分区图锁定几个“可能出问题”的货架区域，再走到近处逐一检查。

Q7. 下列哪些方法可以优化 BVH 在动态场景中的更新代价？

多选题 · mid

  • A.每帧从零开始重建整棵树
  • B.自底向上重新计算包围盒（refit）← 正确答案
  • C.物体移动超过阈值才触发局部更新← 正确答案
  • D.禁用所有包围盒重叠测试

答案：BC。refit 和阈值触发局部更新是标准的增量更新策略——只更新移动物体的祖先节点包围盒，避免全量重建。每帧重建代价太高（A 错），禁用重叠测试会让 BVH 失效（D 错）。就像仓库管理员只需微调几个货架的隔板位置，而不是把整个仓库重新装修一遍。

Q8. GJK 算法的输入和输出分别是什么？

多选题 · mid

  • A.输入是两个凸体的顶点集合← 正确答案
  • B.输入是两个凹多面体的三角网格
  • C.输出是布尔值：是否碰撞← 正确答案
  • D.输出是碰撞点的具体坐标

答案：AC。GJK 的输入是两个凸体的描述（通常是顶点集合或凸包），输出是布尔值（是否碰撞）。它不直接输出碰撞点——碰撞深度和法向量通常由 EPA 算法在 GJK 之后计算。GJK 只回答“碰没碰”这个问题，不回答“怎么碰”。

Q9. 以下哪些场景适合使用 GJK 算法？

多选题 · hard

  • A.两个凸多边形之间的碰撞检测← 正确答案
  • B.高速子弹穿过薄墙的连续碰撞检测
  • C.凸分解后的凹角色模型与环境的碰撞检测← 正确答案
  • D.两个大地形网格之间的碰撞检测

答案：AC。GJK 天然支持凸体，凹体需要先做凸分解，因此 A、C 都适用。对于 B，GJK 是窄阶段算法，高速穿墙问题需要 CCD 的额外处理（如 swept 检测），不能只靠 GJK。D 中的大网格通常采用 BVH 分块处理，不会直接对两个完整网格跑 GJK。

Q10. 关于碰撞检测中“时空分治”的核心理念，描述最准确的是？

单选题 · hard

  • A.用更多的时间换取更高的精度
  • B.将物体按运动状态分类，在空间上分区，让每次查询只触及局部← 正确答案
  • C.用空间换时间，把每个物体复制多份
  • D.把所有物体放在一张大表中统一管理

答案：B。时空分治强调“分类+分区”：静态物体预计算树、动态物体增量更新、高速物体特殊处理（CCD），同时在空间上让查询只触及相邻区域。目标是大幅减少每次碰撞查询涉及的物体数量，而不是简单的空间换时间或精度换时间。