GJK 算法

判断两个凸形状是否相交、并算出它们最近距离的经典迭代算法。

由 Elmer Gilbert、Daniel Johnson 和 S. Sathiya Keerthi 于 1988 年发表。它只需要每个凸形状的「支撑函数」：给定一个方向，返回形状上沿该方向最远的点，所以球、盒子、胶囊、凸网格都能统一处理。核心事实是：两个凸体相交，当且仅当它们的闵可夫斯基差（A 中每点减 B 中每点得到的集合）包含原点。算法在差集里迭代构造点、线段、三角形、四面体等单纯形，逐步逼近离原点最近的点，从而得到最近距离或判定相交。它快且省内存，是物理引擎窄相碰撞检测的常用核心，MuJoCo 的默认碰撞管线就基于 GJK 加 EPA（扩展多面体算法，用来算穿透深度）。非凸物体要先做凸分解。

例子运动规划时检查机械臂某根连杆（用凸包表示）与桌上盒子的最近距离，GJK 迭代几步就给出距离值，规划器据此判断这段路径是否留有足够余量。

也叫

GJK 距离算法、Gilbert–Johnson–Keerthi distance algorithm

相关

碰撞检测（物理引擎）、碰撞检查、凸分解、宽相 / 窄相碰撞检测、碰撞体、FCL

来源

Wikipedia: Gilbert–Johnson–Keerthi distance algorithm
MuJoCo documentation: Computation (collision detection pipelines)