1. 为什么GJK值得单独拎出来讲做物理引擎绕不开碰撞检测而GJKGilbert-Johnson-Keerthi算法几乎是所有现代物理引擎的标配。Bullet、PhysX、Box2D的某些版本底层都用到了GJK或者它的变体。我刚开始接触物理引擎的时候看到GJK这三个字母就头疼网上的资料要么是论文式的数学推导要么是几行代码甩你脸上让你自己悟。踩了几次坑之后我决定用自己的方式把这个算法拆开揉碎讲清楚。这篇文章适合谁看如果你已经了解基本的向量运算知道点积和叉积是怎么回事想搞明白物理引擎里碰撞检测到底怎么做的那这篇内容就是写给你的。我会从最核心的思路讲起把GJK为什么这么设计、每一步在干什么、代码怎么写、容易踩什么坑全部串一遍。不堆公式不搞玄学用最直白的方式把这件事说透。GJK的本质是什么一句话概括它是在两个凸体之间找最近距离的算法如果距离为零就说明碰撞了。听起来简单但实现起来有几个关键点需要理解到位否则写出来的代码要么检测不准要么性能拉胯。2. GJK算法的核心思路拆解2.1 从“两个物体碰没碰上”到“两个点集的距离”先想一个最朴素的问题给你两个凸多面体你怎么判断它们是否相交最直接的办法是遍历所有面、所有边做多边形相交测试。但这样做计算量太大尤其是物体顶点多的时候O(n²)的复杂度直接爆炸。GJK换了一个角度。它不去直接判断两个物体是否相交而是把问题转化成这两个物体的闵可夫斯基差Minkowski Difference形成的新的凸体是否包含原点。如果包含原点说明两个物体相交如果不包含原点到这个新凸体的距离就是两个物体的最近距离。这个转化是GJK的灵魂。为什么因为判断“一个凸体是否包含某个点”比判断“两个凸体是否相交”要简单得多。而且闵可夫斯基差有一个很好的性质两个凸体的差仍然是凸体。凸体意味着我们可以用支撑函数Support Function来高效地探索它的形状而不需要显式地计算出它的所有顶点。2.2 闵可夫斯基差到底在干什么用生活化的例子解释一下。假设你在地上画了一个圆A又在旁边画了一个圆B。闵可夫斯基差的操作是把B上的每一个点取反然后加到A上。结果是什么你会得到一个更大的圆这个新圆的半径是A和B半径之和圆心是A圆心减去B圆心。如果这个新圆包含了原点说明什么说明原来的A和B有重叠。你可以这样理解原点代表A和B的“接触点”如果原点在新圆内部就意味着存在一对点一个在A上一个在B上它们恰好重合。对于多边形也是同样的道理。两个凸多边形的闵可夫斯基差是一个新的凸多边形我们不需要真的去计算它的所有顶点只需要通过支撑函数在需要的时候“探测”它的边界上的点。2.3 支撑函数GJK的发动机支撑函数是GJK的核心工具。给定一个方向向量d支撑函数返回凸体在这个方向上最远的点。对于闵可夫斯基差支撑函数有一个非常优雅的性质support(A - B, d) support(A, d) - support(B, -d)这意味着我们不需要显式构造闵可夫斯基差只需要分别在A和B上调用支撑函数然后相减就行了。这个性质让GJK的计算效率极高每次迭代只需要做几次向量运算。支撑函数的实现对于多边形来说很简单遍历所有顶点找点积最大的那个。对于球体、胶囊体这些有解析表达式的形状可以直接用公式算。对于复杂网格可以用凸包预处理来加速。2.4 单纯形GJK的工作台GJK通过迭代构建一个叫做“单纯形”Simplex的几何体来工作。在三维空间中单纯形可以是一个点0阶单纯形一条线段1阶单纯形一个三角形2阶单纯形一个四面体3阶单纯形算法的流程是从一个初始方向开始用支撑函数找到一个点加入单纯形。然后检查当前单纯形是否包含原点。如果不包含就找到单纯形上离原点最近的点用这个方向继续找新的支撑点扩展单纯形。重复这个过程直到找到原点或者确定不可能包含原点。每次迭代单纯形都会“朝着”原点的方向扩展同时我们会剔除掉那些不可能帮助包含原点的顶点。这就是GJK高效的原因它不需要遍历所有顶点只需要沿着最有希望的方向探索。3. GJK算法的完整实现步骤3.1 初始化从任意方向开始第一步是选择一个初始方向。这个方向可以是任意的但通常选择两个物体中心点的连线方向这样收敛更快。用这个方向调用支撑函数得到第一个点加入单纯形。def gjk_init(shape_a, shape_b): # 选择初始方向从A中心指向B中心 direction shape_b.center - shape_a.center if direction.length_squared() 1e-8: direction Vector(1, 0, 0) # 退化情况随便选一个 # 第一个支撑点 point support(shape_a, shape_b, direction) simplex [point] return simplex, -direction # 下一次搜索方向指向原点这里有一个细节初始方向如果选得不好比如两个物体中心重合方向向量长度为零会导致后续计算出现NaN。所以一定要处理这种退化情况。3.2 迭代循环不断逼近原点主循环的逻辑是这样的def gjk(shape_a, shape_b): simplex, direction gjk_init(shape_a, shape_b) while True: # 沿当前方向找新的支撑点 new_point support(shape_a, shape_b, direction) # 如果新点没有越过原点说明不可能相交 if new_point.dot(direction) 0: return False # 不相交 simplex.append(new_point) # 检查单纯形是否包含原点并更新方向和单纯形 contains_origin, direction, simplex handle_simplex(simplex) if contains_origin: return True # 相交这个循环的终止条件有两个要么新找到的支撑点在搜索方向上的投影为负说明原点在闵可夫斯基差的外部两个物体不相交要么单纯形成功包围了原点说明相交。3.3 单纯形处理点、线、面、体的逐级判断这是GJK最复杂的部分需要根据单纯形的维度分别处理。点单纯形只有一个点方向就是原点减去这个点。线段单纯形两个点构成线段需要判断原点在线段的哪个区域。计算原点在线段上的投影如果投影在线段内部方向就是原点到线段的垂线方向如果投影在线段端点外侧就剔除一个点退化成点单纯形。def handle_line(simplex): a, b simplex[0], simplex[1] ab b - a ao -a # 原点减去a if ab.dot(ao) 0: # 原点在AB方向一侧 direction cross(cross(ab, ao), ab) # 垂直于AB指向原点 return False, direction, [a, b] else: # 原点在A的外侧 return False, ao, [a]三角形单纯形三个点构成三角形需要判断原点在三角形的哪个Voronoi区域。这个判断需要计算多个叉积确定原点是在三角形内部、某条边的外侧、还是某个顶点的外侧。def handle_triangle(simplex): a, b, c simplex[0], simplex[1], simplex[2] ab b - a ac c - a ao -a # 计算三角形法线 abc cross(ab, ac) # 检查原点是否在三角形外部 if cross(abc, ac).dot(ao) 0: if ac.dot(ao) 0: return False, cross(cross(ac, ao), ac), [a, c] else: return handle_line([a, b]) if cross(ab, abc).dot(ao) 0: return handle_line([a, b]) # 原点在三角形内部沿法线方向 if abc.dot(ao) 0: return False, abc, [a, b, c] else: return False, -abc, [a, c, b] # 翻转顺序四面体单纯形四个点构成四面体需要判断原点是否在四面体内部。如果在内部直接返回相交如果在某个面的外侧就剔除对面的顶点退化成三角形处理。3.4 终止条件与数值稳定性GJK的终止条件需要仔细设计。理论上当新支撑点在搜索方向上的投影小于零时可以确定原点不在闵可夫斯基差内。但实际中由于浮点误差这个判断可能会出错。我通常的做法是设置一个小的容差值比如1e-6。如果投影小于这个容差就认为不相交。另外迭代次数也要设上限防止死循环。一般设置32次或64次迭代就足够了因为GJK的收敛速度是超线性的。注意容差值的选取很关键。太大容易漏检太小容易误检。建议根据场景尺度来定比如物体尺寸在1左右时用1e-6比较合适。4. 实操中的关键细节与性能优化4.1 支撑函数的实现技巧支撑函数的效率直接决定了GJK的性能。对于凸多边形最直接的方式是遍历所有顶点def support_polygon(vertices, direction): best vertices[0] best_dot best.dot(direction) for v in vertices[1:]: d v.dot(direction) if d best_dot: best_dot d best v return best但如果顶点很多这个遍历会成为瓶颈。优化方法有几种凸包预处理如果原始网格不是凸的先计算凸包减少顶点数量。缓存上一次的支撑点相邻帧的支撑点通常很接近可以从上次的结果开始搜索。使用层次结构比如Doppler BVH可以在O(log n)时间内找到支撑点。对于球体支撑函数有解析解def support_sphere(center, radius, direction): return center direction.normalized() * radius对于胶囊体可以分解成线段和球体的组合。4.2 单纯形缓存与热启动在物理引擎中碰撞检测是每帧都要做的。如果每帧都从零开始跑GJK效率会很低。一个常用的优化是缓存上一帧的单纯形下一帧直接从这个单纯形开始迭代。这样做的好处是如果两个物体持续接触GJK通常只需要几次迭代就能收敛。实测下来热启动可以减少50%以上的迭代次数。class GJKCache: def __init__(self): self.simplex [] self.direction Vector(1, 0, 0) def query(self, shape_a, shape_b): if len(self.simplex) 0: self.simplex, self.direction gjk_init(shape_a, shape_b) # 用缓存的单纯形继续迭代 return gjk_iterate(shape_a, shape_b, self.simplex, self.direction)4.3 距离计算与碰撞法线GJK不仅能判断是否碰撞还能计算最近距离和碰撞法线。当两个物体不相交时最后一次迭代的搜索方向就是最近距离的方向。当两个物体相交时需要配合EPAExpanding Polytope Algorithm来计算穿透深度和法线。EPA的思路是从GJK终止时的单纯形出发不断扩展多面体直到找到闵可夫斯基差边界上离原点最近的面。这个面的法线就是碰撞法线原点到面的距离就是穿透深度。def epa(shape_a, shape_b, simplex): # 构建初始多面体 polytope build_polytope(simplex) while True: # 找到离原点最近的面 face find_closest_face(polytope) # 沿面法线找支撑点 new_point support(shape_a, shape_b, face.normal) # 如果新点没有明显超出当前面收敛 if new_point.dot(face.normal) - face.distance 1e-6: return face.normal, face.distance # 否则扩展多面体 polytope.add_vertex(new_point, face)EPA的收敛速度比GJK慢一些但通常也能在几十次迭代内完成。4.4 数值精度问题的处理GJK对浮点误差比较敏感尤其是在物体几乎接触但还没接触的时候。常见的问题包括抖动物体在接触边缘时碰撞检测结果在“碰撞”和“不碰撞”之间跳变。假阴性明明碰撞了但GJK返回不相交。假阳性明明没碰撞但GJK返回相交。解决这些问题的方法使用双精度在关键计算中使用double而不是float。增加容差在判断投影时加入小的容差。后处理对结果做平滑处理比如连续几帧都检测到碰撞才认为是真碰撞。退化情况处理当单纯形退化比如三点共线时需要特殊处理。实操心得我在项目中遇到过两个盒子平行放置间隙为0.001的情况。GJK在float精度下会随机返回碰撞或不碰撞。后来把支撑函数的计算改成double问题就消失了。所以如果你的场景对精度要求高别省那点内存。5. 常见问题与排查技巧实录5.1 GJK返回不相交但物体明显重叠这是最让人头疼的问题。可能的原因和排查方法可能原因排查方法解决方案支撑函数实现错误用简单形状如两个球测试检查支撑函数是否返回了正确的最远点单纯形处理逻辑错误打印每次迭代的单纯形和方向对照本文的伪代码逐行检查初始方向退化检查两个物体中心是否重合添加退化情况的处理迭代次数不足增加迭代上限看是否解决优化收敛速度或增加上限浮点精度问题改用double精度测试增加容差或使用更稳定的算法我踩过的一个坑是在handle_triangle函数中叉积的顺序写反了导致法线方向朝内。这种情况下GJK会认为原点在三角形外部从而错误地返回不相交。排查的时候把每一步的向量都打印出来和手算结果对比很快就找到了问题。5.2 性能瓶颈定位GJK本身很快但如果用错了地方也会成为瓶颈。常见的性能问题频繁的凸包计算如果每帧都对网格重新计算凸包开销很大。应该在加载时预处理一次。支撑函数遍历所有顶点对于高模网格这是主要开销。可以用BVH加速。没有热启动每帧从零开始迭代浪费计算资源。EPA迭代次数过多EPA比GJK慢如果穿透很深EPA可能需要很多次迭代。用性能分析工具如perf、VTune定位热点函数通常能很快找到问题。5.3 与其他碰撞检测算法的对比GJK不是万能的它有自己的适用场景算法适用场景优势劣势GJK凸体之间的精确碰撞检测高效、精确、支持距离计算只适用于凸体SAT凸体之间的碰撞检测实现简单、支持早期退出对于多面体效率较低BVH复杂场景的粗筛快速排除不相交的物体对需要预处理、内存开销大球体扫描快速移动物体的连续检测简单、快速精度低、只适用于球体实际物理引擎中通常是多种算法组合使用先用BVH做粗筛再用GJK做精确检测最后用EPA计算穿透深度。5.4 调试GJK的实用技巧调试GJK的时候可视化是最好的工具。我通常会写一个简单的渲染器把单纯形、搜索方向、支撑点都画出来。这样一眼就能看出算法在哪一步出了问题。另外单元测试也很重要。用已知结果的简单形状比如两个球、两个盒子做测试确保基本功能正确。然后再逐步增加复杂度。def test_gjk_sphere_sphere(): a Sphere(Vector(0, 0, 0), 1.0) b Sphere(Vector(1.5, 0, 0), 1.0) assert gjk(a, b) True # 相交 b2 Sphere(Vector(3.0, 0, 0), 1.0) assert gjk(a, b2) False # 不相交提示写单元测试的时候边界情况最重要。比如刚好接触、刚好分离、中心重合、一个物体完全包含另一个物体这些情况都要覆盖到。6. 从GJK到完整碰撞检测系统6.1 GJK在物理引擎中的位置在一个完整的物理引擎中碰撞检测通常分为三个阶段粗筛Broad Phase用BVH、网格划分等方法快速排除明显不相交的物体对。中筛Mid Phase对可能相交的物体对用GJK等算法做精确检测。细筛Narrow Phase对确认相交的物体对计算碰撞法线、穿透深度、接触点等信息。GJK属于中筛阶段它的输出是“是否相交”以及“最近距离”。如果需要更详细的碰撞信息还需要EPA等算法配合。6.2 与其他模块的接口设计GJK的输入是两个凸形状和一个可选的缓存输出是布尔值是否相交和可选的最近距离。接口设计要尽量简洁class CollisionDetector: def __init__(self): self.cache {} def detect(self, shape_a, shape_b): key (shape_a.id, shape_b.id) if key not in self.cache: self.cache[key] GJKCache() return gjk(shape_a, shape_b, self.cache[key])缓存的管理很重要。如果物体对不再相邻要及时清理缓存否则内存会无限增长。6.3 扩展到连续碰撞检测GJK也可以用于连续碰撞检测CCD。基本思路是把物体的运动轨迹表示成时间的函数然后在时空空间中做GJK。这需要把支撑函数扩展到四维三维空间时间实现起来更复杂但原理是一样的。另一种更简单的CCD方法是在物体运动的路径上采样多个位置对每个位置做GJK。如果检测到碰撞再用二分法找到精确的碰撞时间。这种方法实现简单但可能漏掉快速移动的小物体。6.4 实际项目中的经验总结我在几个项目中用过GJK总结下来有几个经验不要重复造轮子如果项目允许直接用Bullet或PhysX的碰撞检测模块。自己实现GJK只适合学习或特殊需求。精度和性能要平衡不是所有场景都需要高精度。对于远处的物体可以用简化的碰撞形状。测试要覆盖边界情况GJK在边界情况下的行为最不可预测一定要重点测试。可视化调试工具必不可少没有可视化调试GJK就是盲人摸象。最后分享一个小技巧如果你的GJK实现总是出问题不妨先用二维版本调试。二维的单纯形只有点、线、三角形三种逻辑比三维简单得多。二维调通了三维就是水到渠成的事。
