GJK算法

Gilbert-Johnson-Keerthi Algorithm GJK

Gilbert-Johnson-Keerthi Algorithm

GJK 算法是一种用于凸体之间距离查询和碰撞查询的计算几何算法。它常作为距离检测和碰撞检测的核心组件，用于机器人、图形学和物理仿真中的凸网格、凸包或其他凸几何体。

Convex Distance

给定两个凸体 $A$ 与 $B$ ，它们之间的距离为

d (A, B) = min_{a \in A, b \in B} ∥ a - b ∥ .

GJK 把这个问题转化为 Minkowski 差

A ⊖ B = A + (- B) = {a - b ∣ a \in A, b \in B}

到原点的距离：

d (A, B) = min_{x \in A ⊖ B} ∥ x ∥ .

若原点落在 $A ⊖ B$ 内，则两个凸体相交；若原点在外，原点到 $A ⊖ B$ 的最近距离就是两凸体清距。

GJK 不需要显式构造完整的 Minkowski 差，而是反复调用支持点函数。对方向 $v$ ，

s_{A} (v) = \arg max_{a \in A} v^{T} a .

Minkowski 差的支持点可由两个原始支持点组合得到：

s_{A ⊖ B} (v) = s_{A} (v) - s_{B} (- v) .

算法维护一个由支持点组成的 simplex，并迭代更新最接近原点的 simplex。二维中 simplex 是点、线段或三角形；三维中是点、线段、三角形或四面体。

对凸机器人部件和凸障碍，GJK 可直接返回距离或相交判断。复杂形状通常先分解成凸体并取所有凸体对的最小距离：

d (A, B) = min_{u, v} d (A_{u}, B_{v}),

其中

A = ⋃_{u} A_{u}, B = ⋃_{v} B_{v} .

这样非凸机械臂、环境网格和工具模型可以通过凸分解接入同一个距离查询框架。

GJK 的基本对象是凸体；非凸形状若不做分解，支持映射不能表达真实最近距离。数值实现还需要容差来区分微小正距离、接触和穿透。若需要穿透深度或接触法向，工程系统常在 GJK 相交后接入额外的接触求解步骤。