想象一座完全漆黑的圆形舞池。两位舞者正在里面高速旋转，主办方站在场边，手里只有一支探照灯，必须判断他们是否撞在了一起。这支灯往任意方向一扫，就能找到某人身上最靠近光柱的那个亮点；再把两个人的“影子”在脑中重叠，便得到了一张能回答“是否相撞”的神秘图像。这就是 GJK 与 EPA 的故事——游戏物理引擎每帧都在执行的“黑暗验身术”。本文会带你从零搭建这套直觉：先用探照灯认识支撑函数，再学会把两个形状折叠成一张影子图，然后看 GJK 如何用三五个探针就断定碰撞，最后用 EPA 量出把两人分开所需的最小一步。全程只用一个比喻，不堆砌公式。

岗位关联

对于 AI 工程师而言，碰撞检测是物理模拟、机器人操作与空间智能的“底层触觉”。读懂 GJK/EPA，你才能为智能体训练、数字孪生与具身交互写出真正可信的物理反馈——这是从“会调接口”走向“懂引擎”的必修课。

目录
  1. 可视化演示
  2. 碰撞检测基础
  3. 支撑函数
  4. 闵可夫斯基差
  5. GJK核心迭代
  6. EPA穿透深度
  7. 工程优化实践
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示GJK单纯形迭代逼近原点判定碰撞、支撑函数沿方向取凸体最远点、Minkowski差集包含原点判定相交及EPA扩展多面体计算穿透深度方向，含六边网格背景动画。

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

碰撞检测基础

想象一座完全漆黑的圆形舞池，上百位舞者同时旋转。主办方不可能让每对人都停下互相“验身”——那会让整场舞会瘫痪。聪明的做法是先看座位表：只有座位相邻的几对才可能撞上，其余的连看都不用看。这套“先分区域、再细查”的思路，正是物理引擎碰撞检测的灵魂。

游戏物理引擎面对同样的窘境：一帧只有约 16 毫秒，却要处理上百个刚体。若对每一对都做精确求交，帧率会立刻崩溃。于是检测被拆成两个阶段——宽相位先用球或 AABB 包围盒快速排除明显不相邻的对象，窄相位再对留下的少数候选对做精确判定。我们今天的主角 GJK 与 EPA，就属于窄相位。

这里有一个重要前提：GJK 只对凸体严格有效。凸体就像饱满的糖球，任意两点连线都留在内部；而凹体（如马蹄形）会让“最远点探测”产生歧义。游戏中的凹地形通常先做凸分解，拆成若干凸块再逐对测试。每秒要检查的候选对数量可以直接估算：

回到舞池：宽相位像翻座位表，窄相位才是两位舞者真正面对面“验身”的那一刻。GJK 正是那位一丝不苟、又极其节俭的验身官——他不碰任何一盏灯之外的东西，却总能在最短时间内给出答案。

Nframe=f×n(n−1)2\displaystyle N_{\text{frame}} = f \times \frac{n(n-1)}{2}
通俗解释：帧率乘以刚体两两组合数，就是物理系统每秒要做多少次碰撞查询——这也是为什么必须先用宽相位砍掉大部分组合。
  1. 帧率 f每秒渲染的画面帧数，游戏通常为 60，代表一秒钟内要检查 60 轮碰撞。
    f\displaystyle f
  2. 配对总数n 个刚体两两组合成候选对，数量是组合数公式。
    n(n−1)2\displaystyle \frac{n(n-1)}{2}
  3. 每秒成本两者相乘即每秒碰撞查询总量，由此看到暴力检测的爆炸式增长。
    Nframe=f×n(n−1)2\displaystyle N_{\text{frame}} = f \times \frac{n(n-1)}{2}

支撑函数

裁判站在舞池中央，手里唯一的工具是一支探照灯。他朝任意方向照去，光柱最先照亮舞者身上的那个亮点，就是“该方向上的支撑点”。奇妙的是，只要不断变换光照方向，把这些亮点连起来，就能完整描出这位舞者的轮廓——在黑暗中，探照灯就是裁判认识世界的全部方式。

数学上，支撑函数就是上面这个动作的精确化：给定方向向量，返回形状上在该方向投影最大的顶点。对一个凸多边形或凸多面体而言，任意方向的支撑点就能唯一确定它的形状，因此凸体可以完全用支撑函数来描述，无需保存全部顶点信息。

支撑函数还有一个极其优雅的组合性质：如果形状由多个子体组成，整体在某方向的支撑点可以通过子体的支撑点快速合并得到；而两个形状的闵可夫斯基和的支撑点，等于各自支撑点之和。这个性质让 GJK 每次查询只需要计算两次支撑函数，成本极低。它的定义如下：

裁判只要会“打光”，就能在黑暗中摸清任何一位舞者的身形。支撑函数是整个 GJK/EPA 大厦的地基——没有它，后面所有精妙算法都无从谈起。

SA(d^)=arg⁡max⁡p∈A(p⋅d^)\displaystyle S_A(\hat{\mathbf{d}}) = \arg\max_{\mathbf{p} \in A} \left( \mathbf{p} \cdot \hat{\mathbf{d}} \right)
通俗解释：把形状的所有顶点朝方向 d 上投影，投影最远的那个顶点就是答案——就像探照灯下最先被照亮的地方。
  1. 单位方向向量探照灯照射的方向，长度为 1，保证投影结果不受光强影响。
    d^,∥d^∥=1\displaystyle \hat{\mathbf{d}}, \quad \lVert \hat{\mathbf{d}} \rVert = 1
  2. 点积投影顶点 p 在方向 d 上的投影长度，衡量“这个点有多靠前”。
    p⋅d^\displaystyle \mathbf{p} \cdot \hat{\mathbf{d}}
  3. argmax 选取遍历形状 A 的所有顶点，取投影最大者作为支撑点。
    arg⁡max⁡p∈A(p⋅d^)\displaystyle \arg\max_{\mathbf{p} \in A} \left( \mathbf{p} \cdot \hat{\mathbf{d}} \right)

闵可夫斯基差

光知道两个人的身形还不够，裁判还需要一个统一标尺来回答“是否相撞”。他想出一个妙招：在脑海中把两张剪影叠印——甲方身上的每个点，减去乙方身上的每个点，得到一张全新的“双人影子图”。这张影子图浓缩了两人的全部相对位置关系。

这张影子图就是闵可夫斯基差。它的惊人之处在于：只要这张影子图覆盖了舞台中央的原点，就意味着两人能恰好占据同一个位置——也就是相撞了。反之，如果原点在影子图之外，两人即使贴身也还差着一点距离。

于是，一个复杂的“两个形状是否相交”问题，被转化为一个简单得多的问题：“原点是否落在一个区域内”。GJK 不需要真的找出交点坐标，它只需要判断包含关系，这就大大降低了对几何细节的要求。形式化表述如下：

有了这张影子图，裁判不再需要同时盯着两个人——他只要盯住一个点。空间相交这一难题被浓缩成“点在区域内吗”的简单提问，一切豁然开朗。

A∩B≠∅  ⟺  0∈{a−b∣a∈A, b∈B}\displaystyle A \cap B \neq \varnothing \iff \mathbf{0} \in \{ \mathbf{a} - \mathbf{b} \mid \mathbf{a} \in A,\ \mathbf{b} \in B \}
通俗解释：A 的每个点减去 B 的每个点拼成影子图，影子盖住原点，两人就撞上了。
  1. 差集构造对 A 中每个点 a 与 B 中每个点 b 做减法，得到影子图上的一个点。
    a−b,a∈A, b∈B\displaystyle \mathbf{a} - \mathbf{b}, \quad \mathbf{a} \in A,\ \mathbf{b} \in B
  2. 原点含义坐标原点代表“两人位置完全相同”这一碰撞状态。
    0\displaystyle \mathbf{0}
  3. 等价判定差集是否包含原点，与两形状是否相交完全等价。
    A∩B≠∅  ⟺  0∈A⊖B\displaystyle A \cap B \neq \varnothing \iff \mathbf{0} \in A \ominus B

GJK核心迭代

影子图虽然清晰，但覆盖范围可能极其巨大且形状复杂，直接判断原点是否在内部仍然昂贵。裁判改用“收网”策略：先朝一个方向打光取一个支撑点，再朝能逼近原点的方向打光取下一个点，把取到的点连成一个不断收紧的绳圈——这个绳圈在数学上叫单纯形。

每一次迭代，裁判都做三件事：从当前单纯形上找到离原点最近的点，把探照方向设为这个最近点的反方向，然后沿新方向取一个支撑点加入单纯形。若新支撑点出现在原点更远的一侧（满足终止条件），说明影子图根本够不到原点，两人不可能相撞；若单纯形成功把原点包围在内部，则判定碰撞成立。

这个迭代过程保证收敛：每一轮单纯形到原点的距离都在单调减小，而单纯形的顶点组合是有限的，因此必然终止。实际工程中，得益于初始方向选得好，平均只需要 2 到 4 次迭代就能出结果。核心更新式如下：

渔夫收网——每一次只问一个问题，用极少的探针就能断定相撞与否。这就是 GJK 优雅与高效并存的秘密：不问“你们怎么撞的”，只问“你们撞没撞”。

dk+1=− arg⁡min⁡x∈conv⁡(Sk)∥x∥\displaystyle \mathbf{d}_{k+1} = -\, \arg\min_{\mathbf{x} \in \operatorname{conv}(S_k)} \lVert \mathbf{x} \rVert
通俗解释：每次找到绳圈上离原点最近的那个点，朝它的反方向继续撒网，绳圈就会不断向原点合拢。
  1. 单纯形凸包当前所有支撑点围成的凸包，在 2D 中是三角形，3D 中是四面体。
    conv⁡(Sk)\displaystyle \operatorname{conv}(S_k)
  2. 最近点凸包上距离原点最近的点，代表当前绳圈与碰撞状态的最小距离。
    arg⁡min⁡x∈conv⁡(Sk)∥x∥\displaystyle \arg\min_{\mathbf{x} \in \operatorname{conv}(S_k)} \lVert \mathbf{x} \rVert
  3. 取反方向新探照方向指向最近点的反方向，推动绳圈朝原点收拢。
    dk+1=− vk\displaystyle \mathbf{d}_{k+1} = -\, \mathbf{v}_k

EPA穿透深度

确认相撞之后，裁判的任务还没结束：他必须把两位舞者分开，而且要知道往哪个方向推、推多远，两人才能刚好脱开。GJK 只回答“撞没撞”，而“撞得多深、怎么推开”是 EPA 的职责——它是 GJK 的续集。

EPA 从 GJK 留下的那个包含原点的三角形出发，不断扩展影子图的边界。具体做法是：找出当前多边形上距离原点最近的边，沿这条边的外法线方向打光取一个新支撑点，把它插入多边形，如此循环。每扩展一次，多边形就离“理想影子图”更近一分，直到深度变化小于容差，迭代收敛。

最终输出的是一个向量：最小穿透向量（MTV）。它的方向就是分离方向，长度就是穿透深度。物理引擎拿到 MTV 后，可以立刻修正刚体位置并生成碰撞响应。用公式表达，穿透深度就是影子图边界到原点的最短距离：

就像在黑暗中为缠绕的舞伴找准那个“最小的分开动作”——方向错一点会推倒别人，深度少一分两人还贴着彼此。EPA 让这一推恰到好处。

δ=min⁡e∈E(M)dist⁡(0,e)\displaystyle \delta = \min_{\mathbf{e} \in E(M)} \operatorname{dist}(\mathbf{0}, \mathbf{e})
通俗解释：影子图的边就像墙壁，原点被围在墙里；找到离原点最近的那面墙，墙到原点的距离就是要把两人推开的最小步长。
  1. 边集闵可夫斯基多边形上已经扩展出的所有边，代表影子图的候选边界。
    E(M)\displaystyle E(M)
  2. 点到边距离原点到每条边所在直线的垂直距离，衡量这条边离碰撞状态多重有多近。
    dist⁡(0,e)\displaystyle \operatorname{dist}(\mathbf{0}, \mathbf{e})
  3. 取最小值最短距离即穿透深度，对应的法线方向即分离方向。
    δ=min⁡e∈E(M)dist⁡(0,e)\displaystyle \delta = \min_{\mathbf{e} \in E(M)} \operatorname{dist}(\mathbf{0}, \mathbf{e})

工程优化实践

再聪明的裁判也架不住舞池里同时涌进上万对舞者。真正的舞会调度是分层艺术：先用宽相位把明显隔开的人流筛掉，再对余下的小批量候选对请出 GJK 与 EPA。这也是物理引擎的标准流程——GJK 从不孤军奋战。

第二个优化诀窍是“热启动”：相邻两帧之间，刚体的运动通常很小，上一帧的单纯形和探照方向几乎仍然有效。直接复用这些中间结果，GJK 平均能省掉一半的迭代次数；EPA 也可以从上一帧的 MTV 方向起步，快速收敛到新的穿透状态。

第三个关键是数值稳定性与预算控制。浮点误差会让支撑点计算产生微小偏差，工程上普遍使用容差 epsilon 和最大迭代次数双重保护；对凹地形预先做凸分解，对静态场景预计算 BVH 层级结构。整体成本可以这样估算：

金牌裁判的秘诀从来不是力气大，而是“该查的才查、能省的全省”。宽窄结合、增量复用、容差保护——这三招足以让舞池在万千舞者中依然行云流水。

C=N×I×(TA+TB)\displaystyle C = N \times I \times \left( T_A + T_B \right)
通俗解释：总成本等于候选对数乘以迭代次数再乘以单次支撑查询代价，三个乘数每一项都能靠工程手段压到最小。
  1. 候选对数 N宽相位筛选后进入窄相位的刚体对数量，是最大的成本杠杆。
    N\displaystyle N
  2. 迭代次数 IGJK 平均迭代次数，靠 warm start 可压到 2 至 4 次。
    I\displaystyle I
  3. 支撑代价单次支撑函数查询的花费，与两形状的顶点数及组合方式相关。
    TA+TB\displaystyle T_A + T_B

AI 应用场景

游戏物理引擎的刚体接触响应

阶段：窄相位碰撞检测与物理求解

解决的问题：传统做法用包围盒近似碰撞，物体贴身时会出现“假碰”或“穿模”；AI 驱动的物理模拟需要可靠接触信息来训练策略。

具体案例：Box2D、Bullet 等引擎中，坦克碾过箱子、角色踩上台阶这类场景，引擎用 GJK 判定凸多边形是否相交，再用 EPA 求出最小穿透向量，交给求解器生成冲量与摩擦，保证物体既不穿模也不弹飞。

机器人运动规划与避障

阶段：运动规划与阻抗控制

解决的问题：机械臂在狭小空间作业时，必须实时知道各连杆与障碍物的最短分离距离；传统网格求交慢且不稳定。

具体案例：六自由度机械臂把每段连杆近似为凸包，用 GJK/EPA 每毫秒查询一次与工作台、墙壁的穿透深度和方向，规划器据此调整路径，实现安全避障与柔顺力控。

VR 手势交互与抓取判定

阶段：交互层的碰撞判定与反馈

解决的问题：VR 中手部模型需要高帧率判定与物体是否接触，并实时给出“推离量”防止手指陷入物体。

具体案例：Quest 手柄的指尖模型用凸体 GJK 判定与桌面、水杯的碰撞，EPA 输出 MTV 后驱动震动反馈和抓取判定，让用户感觉“物有所触”。

Python 演示

python117 行
import math  class Vec2:    def __init__(self, x=0.0, y=0.0):        self.x = x        self.y = y     def __add__(self, o): return Vec2(self.x + o.x, self.y + o.y)    def __sub__(self, o): return Vec2(self.x - o.x, self.y - o.y)    def __mul__(self, k): return Vec2(self.x * k, self.y * k)    __rmul__ = __mul__    def dot(self, o): return self.x * o.x + self.y * o.y    def cross(self, o): return self.x * o.y - self.y * o.x    def norm(self):        d = math.hypot(self.x, self.y)        return Vec2(self.x / d, self.y / d) if d > 1e-12 else Vec2()  def support(shape, d):    best = shape[0]    score = best.dot(d)    for p in shape[1:]:        s = p.dot(d)        if s > score:            score, best = s, p    return best  def minkowski_support(a, b, d):    return support(a, d) - support(b, Vec2(-d.x, -d.y))  def perp_toward(edge, target):    pl = Vec2(-edge.y, edge.x)    pr = Vec2(edge.y, -edge.x)    return pl if pl.dot(target) > 0 else pr  def outward(edge, interior):    pl = Vec2(-edge.y, edge.x)    pr = Vec2(edge.y, -edge.x)    return pl if pl.dot(interior) < 0 else pr  def gjk(a, b):    d = Vec2(1.0, 0.0)    simplex = [minkowski_support(a, b, d)]    d = simplex[0] * -1.0    for _ in range(32):        p = minkowski_support(a, b, d)        if p.dot(d) < 0.0:            return False, simplex        simplex.insert(0, p)        if len(simplex) == 2:            edge = simplex[1] - simplex[0]            ao = simplex[0] * -1.0            d = perp_toward(edge, ao)            if abs(d.dot(ao)) < 1e-12:                return False, simplex        else:            a0, b0, c0 = simplex            ab, ac = b0 - a0, c0 - a0            ao = a0 * -1.0            nab = outward(ab, ac)            if nab.dot(ao) > 0.0:                simplex.pop(2)                d = nab            else:                nac = outward(ac, ab)                if nac.dot(ao) > 0.0:                    simplex.pop(1)                    d = nac                else:                    return True, simplex    return False, simplex  def epa(a, b, simplex):    poly = list(simplex)    while len(poly) < 3:        poly.append(minkowski_support(a, b, Vec2(1.0, 0.0)))    for _ in range(32):        n = len(poly)        min_d = float('inf')        min_n = Vec2()        min_i = 0        for i in range(n):            j = (i + 1) % n            e = poly[j] - poly[i]            nrm = Vec2(e.y, -e.x)            if nrm.dot(poly[i]) < 0.0:                nrm = nrm * -1.0            nd = nrm.dot(poly[i]) / math.hypot(nrm.x, nrm.y)            if nd < min_d:                min_d, min_n, min_i = nd, nrm.norm(), i        p = minkowski_support(a, b, min_n)        if p.dot(min_n) - min_d < 1e-5:            return min_n * min_d        poly.insert(min_i + 1, p)    return min_n * min_d  def main():    tri = [Vec2(-1.2, -0.8), Vec2(1.4, -0.6), Vec2(-0.2, 1.5)]    sq = [Vec2(-0.8, -0.9), Vec2(1.0, -0.9), Vec2(1.0, 0.7), Vec2(-0.8, 0.7)]    hit, simplex = gjk(tri, sq)    print('gjk hit:', hit, 'simplex size:', len(simplex))    if hit:        mtv = epa(tri, sq, simplex)        print('mtv:', round(mtv.x, 4), round(mtv.y, 4))        moved = [p + mtv for p in sq]        print('collision after separation:', gjk(tri, moved)[0])  if __name__ == '__main__':    main()
目的：用 2D 凸多边形实现完整的 GJK 碰撞判定与 EPA 穿透深度求解，并验证“用 MTV 平移后两形状确实分离”。
  1. def support(shape, d)支撑函数：遍历顶点，返回方向 d 上投影最大的点，对应文中的探照灯。
  2. def minkowski_support(a, b, d)在闵可夫斯基差空间中取支撑点，一次调用产生一个影子图顶点。
  3. def outward(edge, interior)计算边的外法线方向，用于判断原点在单纯形的哪一侧。
  4. if p.dot(d) < 0.0终止条件：新支撑点无法越过原点，直接判定不相交。
  5. simplex.insert(0, p)新支撑点插入最前，单纯形逐步收网逼近原点。
  6. if nab.dot(ao) > 0.0原点在边 AB 外侧，剔除最旧顶点 C 并切换方向。
  7. else: return True, simplex原点被三角形包围，碰撞成立。
  8. epa(a, b, simplex)从 GJK 的三角形出发，循环找最近边、取新支撑点、扩展多边形。
  9. if p.dot(min_n) - min_d < 1e-5深度收敛，返回最小穿透向量。

常见误区

误区我跑完 GJK 拿到返回结果，以为它就是碰撞点，直接拿去做特效、音效与伤害判定。

正解GJK 只回答“是/否相交”，不产生任何碰撞点。真正的接触信息需要 EPA 求出穿透深度与方向后，再由接触裁剪（contact clipping）算法在边界上生成接触流形。GJK 是“验身官”，不是“法医”。

为何常见：许多教程只讲 GJK 的判定过程，却很少交代工程中接触点由另一套流程产出，两者经常被混为一谈。

误区游戏里很多地形是凹的，我把所有顶点丢给 GJK，以为它一定能判断正确。

正解GJK 依赖凸体的支撑性质与闵可夫斯基差；凹体的“某方向最远点”无法唯一确定形状，判定结果会出错。必须先把凹体分解成若干凸体（凸分解），再对每个凸对分别测试。

为何常见：支撑函数对凹体也能算出“最远点”，让人误以为算法依然成立，但闵可夫斯基差的等价性在凹体上不成立。

误区我把 EPA 的迭代上限设得很大，容差设得极小，以为穿透深度越精确越好，结果帧率暴跌。

正解物理引擎只需要近似 MTV 就足以把物体分开，容差在 1e-3 量级已能肉眼无感，配合最大迭代次数保护实时性。过高的“精确”换来的只是小数点后五六位的差异，却会拖垮整个模拟。

为何常见：误把“数值精确”当“系统正确”，忽略了实时物理系统每一毫秒都极其宝贵的算力预算。

误区多边形有几百个顶点，每次支撑查询都要遍历所有顶点，GJK 应该很慢。

正解支撑查询是 O(n)，但 GJK 平均只有 2 到 4 次迭代；对球体、盒子等基础体还有解析公式，对组合体可按子体支撑合并。再叠加宽相位过滤，实际开销远小于暴力检测。

为何常见：只盯着单次查询的复杂度，忽略了迭代次数极少与宽相位大幅削减候选对这两个决定性事实。

面试题

Q1. GJK 算法主要服务于碰撞检测的哪个阶段？

单选题 · easy

  • A.宽相位粗筛阶段
  • B.窄相位精确判断← 正确答案
  • C.渲染裁剪阶段
  • D.光照烘焙阶段

答案：B。宽相位用包围盒或空间哈希快速排除明显不相邻的对象，GJK 处理的是筛选后剩余的少数候选对，属于窄相位精确判定。

Q2. 支撑函数 S_A(d) 返回的是形状 A 的哪个顶点？

单选题 · easy

  • A.在方向 d 上投影最大的点← 正确答案
  • B.在方向 d 上投影最小的点
  • C.距离质心最近的顶点
  • D.随机选取的一个顶点

答案：A。支撑函数沿方向 d 求投影最大者，正如探照灯最先照亮的亮点；投影最小点、质心最近点都与定义无关。

Q3. 两凸体 A、B 相交的充要条件是？

单选题 · mid

  • A.原点位于 A∪B 中
  • B.原点位于 A⊖B 中← 正确答案
  • C.原点位于 A∩B 中
  • D.原点位于 A+B 中

答案：B。A⊖B 是闵可夫斯基差，即影子图；影子图覆盖原点等价于两形状存在同一点，因此相交充要条件是原点落在差集中。

Q4. 二维空间中，GJK 判定碰撞时单纯形需要满足？

单选题 · mid

  • A.三角形包含原点← 正确答案
  • B.线段包住原点
  • C.两点完全重合
  • D.四边形包含原点

答案：A。2D 单纯形最高维是三角形，当三角形包含原点时判定碰撞；线段只能说明原点在一条边上，不构成内部包含。

Q5. EPA 算法最终输出的 MTV 是什么？

单选题 · mid

  • A.两个形状的交点坐标
  • B.物体表面的法线贴图
  • C.最小分离方向与深度← 正确答案
  • D.形状包围盒的对角线

答案：C。MTV 即最小穿透向量，方向表示分离方向、长度表示穿透深度，是物理引擎推离刚体的直接依据。

Q6. GJK 每次迭代的探照方向如何确定？

单选题 · mid

  • A.单纯形上最近点取反方向← 正确答案
  • B.随机生成一个新的方向
  • C.固定沿 x 轴正方向
  • D.与上次方向保持正交

答案：A。方向取当前单纯形上离原点最近点的反方向，能保证收敛并推动单纯形逐步包围原点；随机或固定方向都无法保证逼近。

Q7. 新支撑点 p 满足 p·d<0 意味着什么？

单选题 · hard

  • A.两形状已经发生穿透
  • B.单纯形发生退化异常
  • C.沿 d 无法逼近原点即不相交← 正确答案
  • D.需要立刻切换到 EPA

答案：C。p·d<0 表示沿方向 d 连支撑点都投影在原点之后，说明影子图够不到原点，可直接判定不相交。

Q8. 下列哪些方法适合宽相位粗筛？

多选题 · mid

  • A.包围球快速距离剔除← 正确答案
  • B.AABB 包围盒层级树← 正确答案
  • C.对每对刚体跑 GJK
  • D.空间哈希网格分桶← 正确答案

答案：ABD。宽相位追求“快而糙”，包围球、AABB 层级树、空间哈希都能快速排除远距离对；GJK 是精确窄相位算法，放在宽相位属于杀鸡用牛刀。

Q9. 以下哪些能有效加速 GJK 判定？

多选题 · hard

  • A.复用上一帧单纯形热启动← 正确答案
  • B.凹体先做凸分解预处理← 正确答案
  • C.取消终止条件无限迭代
  • D.先用包围体粗剔除非邻近对← 正确答案

答案：ABD。热启动减少迭代次数，凸分解让 GJK 适用于凹地形，包围体剔除减少候选对；取消终止条件会导致死循环而非加速。

Q10. 关于 EPA 的说法正确的是？

多选题 · hard

  • A.必须以 GJK 确认碰撞为前提← 正确答案
  • B.持续扩展边直到深度收敛← 正确答案
  • C.可以无限迭代保证精确
  • D.输出用于刚体位置修正← 正确答案

答案：ABD。EPA 从 GJK 留下的含原点三角形出发，扩展最近边直至收敛，输出 MTV 用于修正刚体位置；无限迭代违背实时性，必须用容差与上限保护。