GJK 算法：用闵可夫斯基差做凸体相交检测

StonyBear2026/7/29大约 17 分钟

GJK（Gilbert–Johnson–Keerthi）是一种用于计算二维或三维空间中凸体之间距离与碰撞检测的算法，广泛应用于计算机图形学、机器人学，以及 Box2D、Bullet 等物理引擎。

与逐边、逐顶点做相交测试的传统方法不同，GJK 把「两个形状是否相交」化成一个更干净的问题：原点是否落在它们的闵可夫斯基差里。它不构造完整差集，只靠支撑映射在边界上采样，并用单纯形迭代逼近原点。

核心前提：凸性

GJK 只对凸形状正确。凸集内任意两点的连线段仍落在集内。游戏里若出现凹网格，物理引擎通常先做凸分解（Convex Decomposition），再对凸片分别跑 GJK。

闵可夫斯基差

设 $A,B \subset \mathbb{R}^2$ （三维同理）为非空凸集。它们的闵可夫斯基差常写成

A \ominus B = A \oplus (-B) = \{ a - b \mid a \in A,\ b \in B \}.

核心属性：

A \cap B \neq \emptyset \quad\Longleftrightarrow\quad \mathbf{0} \in A \ominus B.

证明很短：若存在 $x \in A \cap B$ ，则 $x-x=\mathbf{0}$ ；反之若 $\mathbf{0}=a-b$ ，则 $a=b\in A\cap B$ 。

不相交时，原点到差集的最短距离，就是两形状之间的最短距离。

GJK 的关键一步：不必显式构造整个差集（那通常很贵），只需在边界上按需「采样」。

下面的交互演示按 Reducible GJK 视频里的 CompactGJK 流程：在差集（可开关显示）上取支撑点、更新单纯形、用「是否越过原点」判定相交。拖动 A/B 顶点会即时重算；点「查看步骤」逐步回放。

提示：默认种子是略微分开的六边形与五边形（分离）。把 B 往 A 拖近，直到判定变成「相交」，再点「查看步骤」看单纯形如何包住原点。橙色虚线是完整闵可夫斯基差（教学用，GJK 本身不会建它）。

差集本身的几何含义也可以在下面这张图里单独摸：切到「差 ⊖」，拖动 A、B，看橙色结果是否包住原点 $(0,0)$ 。

提示：先把模式切到「差 ⊖」。橙色包住原点 ⟹ 碰撞。更完整的和/差讲解见闵可夫斯基和与差。

支撑函数

为了不建完整差集就能取到边界点，GJK 使用支撑函数（支撑映射）。

给定方向 $d \neq \mathbf{0}$ ，凸集 $C$ 在该方向上的支撑点为

s_C(d) = \arg\max_{x\in C}\, x\cdot d.

差集上的支撑点可以分解到原形状：

s_{A\oplus(-B)}(d) = s_A(d) - s_B(-d).

也就是：取 A 在方向 $d$ 上的最远点，减去 B 在 $-d$ 上的最远点。

优势：算法不关心形状是多边形、圆还是胶囊——只要每个形状能提供 support(direction)，GJK 就能处理。多边形取点积最大的顶点；圆盘取圆心 $+\ r\hat{d}$ 。全程复杂度与「显式闵可夫斯基和」无关。

单纯形

GJK 的目标是判断差集是否包含原点。它在差集内部（准确说：用差集上的支撑点）不断构造单纯形，试图包围原点。

单纯形是给定维度下最简单的「体」：

维数	单纯形
0	点
1	线段
2	三角形
3	四面体

二维里最多用到三角形；三维最多用到四面体。

重心坐标

重心坐标（Barycentric Coordinates）是 GJK 里求投影点、以及把差集结果映回原物体表面的核心工具：用单纯形顶点的加权和描述空间中的点，且所有权重之和为 1。

Q = \sum_i \lambda_i\, V_i,\qquad \sum_i \lambda_i = 1.

几何意义：特征上的比例

权重在不同维度下对应直观的比例关系：

单纯形	权重含义
线段（1-单纯形）	长度比： $P = u A + v B$ （ $u+v=1$ ）， $u,v$ 越大表示越靠近对应端点
三角形（2-单纯形）	面积比：各顶点权重等于对面小三角形与大三角形的面积比
四面体（3-单纯形）	体积比：各顶点权重等于对面小四面体与大四面体的体积比

它还直接给出最近点坐标（边内部 $P=uA+vB$ ；顶点区域则退化为该顶点），并把同一组 $\lambda_i$ 映回 $A$ 、 $B$ 表面（见距离计算）。单纯形约化时「原点落在哪个 Voronoi 区域」则有两套常用判法——相交判定多用方法一，距离计算多用方法二。

Voronoi 区域判定：两种方法

Voronoi 区域回答：原点离单纯形的哪个特征（顶点 / 边 / 内部）最近。约化时丢掉无贡献顶点，并把垂直于最近特征、指向原点的方向设为下一步的 $d$ 。

方法一：法向量与点积（区域排除）

这是布尔碰撞检测里最常用的高效写法（与上文交互演示 / CompactGJK 一致）。算法总是朝原点方向取新支撑点；对三角形单纯形 $ABC$ ，令 $A$ 为最新点，利用这一历史信息可以直接排除大量不可能区域。

排除阶段： $A$ 是沿指向原点的方向搜到的最远点， $B$ 、 $C$ 更早。因此原点不可能落在：

顶点 $C$ 、顶点 $B$ ，或边 $BC$ 的外侧区域；
顶点 $A$ 的外侧——若连最新点 $A$ 都未越过原点（ $A\cdot d\le 0$ ），外层循环早已终止。

剩下只需区分：边 $AB$ 外侧 / 边 $AC$ 外侧 / 三角形内部。

判定边 $AB$ ： 用三重积算出垂直于 $AB$ 、朝向三角形外部的法向

n_{AB} = (\overrightarrow{AC}\times\overrightarrow{AB})\times\overrightarrow{AB}.

若 $n_{AB}\cdot\overrightarrow{AO} > 0$ （ $\overrightarrow{AO}=-\mathbf{A}$ ，从 $A$ 指向原点），原点落在边 $AB$ 的 Voronoi 区 → 丢掉 $C$ ，单纯形降为线段 $AB$ ，下一步搜索方向取 $n_{AB}$ 。

判定边 $AC$ ： 同理

n_{AC} = (\overrightarrow{AB}\times\overrightarrow{AC})\times\overrightarrow{AC}.

若 $n_{AC}\cdot\overrightarrow{AO} > 0$ → 丢掉 $B$ ，降为 $AC$ ，方向取 $n_{AC}$ 。

判定内部： 若两个点积都 $\le 0$ ，原点既不在 $AB$ 外侧也不在 $AC$ 外侧 → 只能在三角形 $ABC$ 内部 → 相交。

二维线段情形同样用 $n=(\overrightarrow{AB}\times\overrightarrow{AO})\times\overrightarrow{AB}$ 作为下一方向（方法一只测「朝原点的那一侧」，不再枚举全部顶点区——因为最新点语义已经排除了）。

方法二：重心坐标（完整 Voronoi 测试）

算确切距离时，引擎通常用重心坐标做更严谨的区域判定：先算原点在各特征上的加权投影，再按权重正负分流，并严格遵循从低维到高维——先顶点，再边，最后内部。

线段 $AB$ （1-单纯形）： 用点积求线段重心坐标 $(u,v)$ ，满足 $u+v=1$ ，且 $P=uA+vB$ 。

条件	区域
$v\le 0$	顶点 $A$
$u\le 0$	顶点 $B$
$u>0$ 且 $v>0$	边 $AB$ 内部

三角形 $ABC$ （2-单纯形）： 需要一组边坐标与一组面坐标，例如三条边的线段重心 $(u_{AB},v_{AB})$ 、 $(u_{BC},v_{BC})$ 、 $(u_{CA},v_{CA})$ ，以及三角形面积重心 $(u_{ABC},v_{ABC},w_{ABC})$ （对应顶点 $A,B,C$ ，三者之和为 1）。

测顶点： 例如原点在边 $AB$ 与边 $CA$ 上的投影都落在 $A$ 一端（ $v_{AB}\le 0$ 且 $u_{CA}\le 0$ ）→ 顶点 $A$ 区域。对 $B$ 、 $C$ 对称处理。
测边： 若线段坐标显示投影落在边 $AB$ 两端之间（ $u_{AB}>0$ 且 $v_{AB}>0$ ），但三角形坐标显示原点在该边外侧（例如对边顶点权重 $w_{ABC}\le 0$ ）→ 边 $AB$ 区域。对 $BC$ 、 $CA$ 同理。
测内部： 顶点和边都不命中 → 原点在三角形内部；此时必有 $u_{ABC}>0,\ v_{ABC}>0,\ w_{ABC}>0$ 。

方法二不依赖「 $A$ 是最新支撑点」这类历史假设，因此适合距离模式里对任意单纯形求最近点；代价是要算齐各边 / 面的权重。方法一用历史信息砍掉大半区域，布尔检测里通常更短、更快。

两种方法判定到同一特征后，下一步相同：丢掉无关顶点，用该特征上的最近点（或外法向）更新 $d$ ，继续支撑迭代。

相交判定的迭代

只回答「是否碰撞」时，算法通过不断取新支撑点、更新单纯形，向原点方向「进化」：

初始化： 任选初始搜索方向 $d$ （例如两物体中心连线），用支撑函数取差集上第一个点，作为单纯形 $W$ 的第一个顶点。
反向搜索： 将下一个搜索方向设为指向原点（取反），再取第二个支撑点。
原点跨越测试： 检查新点 $v$ 是否在搜索方向上越过了原点——算 $v\cdot d$ ，若 $\le 0$ 则未越过。若连该方向上最远的点都到不了原点另一侧，差集不可能包含原点 → 不相交，直接返回。
更新单纯形与方向： 若已越过原点，把 $v$ $v$ 加入 $W$ $W$ ，再按当前形态做 Voronoi 区域判定（布尔检测常用上文方法一：法向 + 点积排除）：
- 若单纯形（三角形 / 四面体）已包围原点 → 相交，结束。
- 否则找出离原点最近的特征（边 / 面），丢掉对靠近原点无贡献的顶点（降维单纯形）。
- 再取垂直于该最近特征、指向原点的新方向作为 $d$ 。二维线段情形常用三重积形式 $(\overrightarrow{AB}\times\overrightarrow{AO})\times\overrightarrow{AB}$ 。
重复步骤 3、4，直到包围原点（相交）或无法越过原点（不相交）。

二维直觉：

单纯形	含义
1 个点	还在摸方向
线段	看原点落在线段哪一侧，丢掉远端点
三角形	若原点在三角形内则碰撞；否则丢掉无用顶点，缩回线段并换方向

这就是名字背后的几何：用支撑点逐步逼近差集上离原点最近的点；最近距离是否为零，即是否相交。若还要数值距离与表面上的最近点，走下面的距离模式——同一套支撑与单纯形，结束条件不同。

距离计算

距离等价

形状 $A$ 与 $B$ 之间的最短距离，等价于闵可夫斯基差 $A \ominus B$ 到原点的最短距离。算法目标仍是：不显式构建整个差集，找到其边界上离原点最近的点 $P$ ； $\lVert P \rVert$ 就是两形状间距（ $P=\mathbf{0}$ 时距离为 0，即碰撞）。

距离模式的迭代

距离模式下同样用单纯形在差集上迭代，但每步显式维护「当前对最近点的近似」，并用收敛判定结束：

初始化： 在差集上任取一点 $v$ （某个初始方向的支撑点）作为最短距离的初始近似，放入单纯形点集 $W$ 。
单纯形上的最近点： 用重心坐标做完整 Voronoi 测试（上文方法二），找出当前单纯形上距原点最近的点 $P$ 。
设定搜索方向： 理想情况令 $d=-P$ （指向原点）；鲁棒实现见下文「搜索方向」——边上时应强制取垂直于边、再朝向原点的法向，避免浮点偏角。
取新支撑点： 在方向 $d$ 上对差集取支撑点 $w = s_A(d)-s_B(-d)$ 。
收敛判定： 比较 $w$ 与当前近似 $P$ 。若 $w$ 在方向 $d$ 上的投影并未比 $P$ 更靠近原点（例如 $\lVert w \rVert$ 相对 $\lVert P \rVert$ 无明显改进，或落入容差），说明无法再向原点逼近——算法收敛， $\lVert P \rVert$ 即为两物体的最短距离。
更新单纯形： 若还能继续逼近，把 $w$ 加入 $W$ 。若更新后的单纯形包围了原点，距离为 0（碰撞）。否则再求新单纯形上的最近点，丢掉对构成该最近点无贡献的顶点（降维），把近似值更新为这个新最近点，回到步骤 2。

与相交判定的差别：相交模式可在「支撑点未越过原点」时早停返回 false；距离模式则继续把单纯形收成差集上真正的最近点，直到支撑方向上再也挤不出更短的近似。

还原原始形状上的最近点

GJK 距离算法还能给出 $A$ 、 $B$ 表面上相距最近的那一对点（witness points）——正是上文重心坐标的「映回」用法。

收敛时差集上的最近点 $P$ 是单纯形顶点的线性组合：

P = \sum_i \lambda_i\, w_i,\qquad \sum_i \lambda_i = 1,\ \lambda_i \ge 0,

其中每个差集顶点 $w_i = a_i - b_i$ 来自支撑时成对取出的 $a_i\in A$ 、 $b_i\in B$ 。把同一组 $\lambda_i$ 分别作用到 $\{a_i\}$ 与 $\{b_i\}$ 上：

p_A = \sum_i \lambda_i\, a_i,\qquad p_B = \sum_i \lambda_i\, b_i,

即得表面上的最近点，且 $P = p_A - p_B$ ， $\lVert p_A - p_B \rVert = \lVert P \rVert$ 。无需反向几何推导。

实现分歧与细节

除了 Voronoi 判定（方法一布尔 vs 方法二距离）之外，引擎里的 GJK 还会在目标（碰撞 / 距离）、数值稳定性和维度（2D / 3D）上分叉。下面几处最常踩坑。

终止条件

引擎要「是否碰撞」还是「距离多远」，直接决定何时停：

模式	何时停
布尔相交	① 新支撑点未越过原点（ $w\cdot d\le 0$ ）→ 未碰撞；② 单纯形已包围原点 → 碰撞
精确距离	必须逼近差集上离原点最近的点。常见停法：新支撑点已落在当前单纯形上（重复顶点），说明再也挤不近 → 以当前最近点 $\lVert P \rVert$ 为距离。三维距离实现往往还要检查「距离是否严格递减」，防止浮点噪声导致死循环

搜索方向：理想数学 vs 数值鲁棒

距离模式下，若最近点 $P$ 落在某条边上，需要新方向 $d$ 指向原点 $Q=\mathbf{0}$ ：

朴素： $d = Q - P = -P$ 。数学上应垂直于该边。
鲁棒（如 Box2D 一类实现）： 重心坐标有舍入误差时， $-P$ 往往并不严格垂直于边，微小偏角会选错支撑点，甚至无限循环。更稳的做法是放弃 $-P$ ，用边向量与平面法线做叉乘，强制得到垂直于该边的方向，再选朝向原点的那一侧。二维里可写成对边向量 $(C-E)$ 取 $\mathrm{cross}(C-E,\,\hat{z})=(-(C-E)_y,\ (C-E)_x)$ ，再按与 $-P$ 的点积定号。

布尔路径里用三重积 $(\overrightarrow{AB}\times\overrightarrow{AO})\times\overrightarrow{AB}$ 更新方向，本质上也是在「强制垂直 + 朝向原点」，与鲁棒思路一致。

退化与极端情况

生产实现必须显式兜住几何退化，否则容易崩或挂死：

原点恰在边上： 指向原点的外法向三重积可能得到零向量，无法再取支撑。需检测 $\lVert d \rVert \approx 0$ ，并强制改用边的左法线或右法线。
共线顶点： 三点共线时三角形面积为 0，面积重心公式会除以零。应检测退化，退回「点到线段」逻辑，不要继续当满秩三角形处理。

2D 与 3D

核心思想同维通用，代码差异集中在单纯形与法向：

	2D	3D
最高单纯形	三角形（3 顶点）	四面体（4 顶点）
垂直方向	对向量 $(x,y)$ 取 $(-y,x)$ 即得唯一（差号）法向，极便宜	垂直于线段的方向有无穷多，需三重积 $(\overrightarrow{AB}\times\overrightarrow{AO})\times\overrightarrow{AB}$ 才能既垂直又朝向原点

初始搜索方向

理论上第一步的 $d$ 任意即可。高效实现几乎总是取两物体几何中心（或质心）连线作为初始方向——不改变正确性，但通常能明显减少逼近原点所需的迭代次数。上文演示与三维参考实现都采用这一习惯。

和交互图怎么对照

上面的 GJK 步进演示里，紫色是当前单纯形，红箭头是搜索方向 $d$ ，sA / sB / w 是本步支撑点；判定条显示相交或分离。
闵可夫斯基差演示（差 ⊖）画出完整橙色区域；GJK 不会画整块区域，只在边界上采样。
若橙色区域包含原点，完整差集已相交；GJK 会在有限步内用三角形盖住原点并返回 true。
若区域远离原点，支撑点很快满足 $w\cdot d \le 0$ ，返回 false。

GJK 演示的「查看步骤」是算法迭代本身；闵可夫斯基演示的「查看步骤」是显式边界归并——同一几何对象上的隐式 vs 显式两种看法。

适用与注意

只对凸集正确；凹网格需凸分解或改用其它方法。
支撑映射必须与形状一致；AABB / OBB / 胶囊等解析形状的支撑往往是 $O(1)$ 。
数值上要处理近乎共线、重复支撑点、零法向与距离非递减；细节见上文「实现分歧与细节」。生产实现会加迭代上限与 epsilon。
本文差的语义与交互图一致： $A \ominus B = A \oplus (-B)$ （集合和意义下的差），不是形态学腐蚀里「半径相减」那种运算。

三维实现

二维最多用到三角形；三维单纯形升级为四面体（4 个点）。主循环不变——支撑差、跨越测试、约化——多出来的是 evolveSimplex 在 4 点时的三个含最新点的面（ABC / ACD / ADB）：原点若落在某面外侧，就降维成该三角形继续；三面都在「内侧」则四面体包住原点，相交。

形状仍只需提供 support(dir)。下面是可运行的布尔 GJK（只回答是否相交，不含 EPA / 距离），完整文件与自检见同目录 gjk3d.mjs。

支撑与差集采样

function supportDiff(a, b, dir) {
  return sub(a.support(dir), b.support(neg(dir)));
}

function polyhedron(verts) {
  return {
    support(dir) {
      let best = verts[0], bestDot = dot(best, dir);
      for (let i = 1; i < verts.length; i++) {
        const d = dot(verts[i], dir);
        if (d > bestDot) { bestDot = d; best = verts[i]; }
      }
      return best;
    },
  };
}

function sphere(center, radius) {
  return {
    support(dir) {
      return add(center, scale(normalize(dir), radius));
    },
  };
}

主循环

W 中最新支撑点放在末尾。dot(support, dir) <= 0 即未越过原点 → 分离；evolveSimplex 返回 hit → 相交。

function gjkIntersect(a, b, opts = {}) {
  const maxIter = opts.maxIter ?? 32;
  let dir = opts.initialDir ? { ...opts.initialDir } : v3(1, 0, 0);
  const W = [];
  W.push(supportDiff(a, b, dir));
  dir = neg(W[0]);

  for (let i = 0; i < maxIter; i++) {
    if (lenSq(dir) < EPS) return true;
    const support = supportDiff(a, b, dir);
    if (dot(support, dir) <= 0) return false;
    W.push(support);
    const step = evolveSimplex(W, dir);
    if (step.hit) return true;
    dir = step.dir;
  }
  return false;
}

单纯形进化（三维要点）

线段： 原点在 $AB$ 的 Voronoi 边区域内 → 方向取 $AB\times AO\times AB$ ；否则缩成单点 $A$ ，方向 $AO$ 。
三角形： 用面法向 $ABC = AB\times AC$ 与边叉积划区；落到某条边则降为线段；落到面上方 / 下方则 $dir=\pm ABC$ 。
四面体： 只检查含最新点 $A$ 的三个面。某面法向与 $AO$ 同向 ⟹ 原点在该面外侧，丢掉对面顶点，交给三角形情形；否则 hit。

function tetraCase(W) {
  const A = W[3], B = W[2], C = W[1], D = W[0];
  const AO = neg(A);
  const AB = sub(B, A), AC = sub(C, A), AD = sub(D, A);
  const ABC = cross(AB, AC);
  const ACD = cross(AC, AD);
  const ADB = cross(AD, AB);

  if (sameDir(ABC, AO)) {
    W.length = 0; W.push(C, B, A);
    return triangleCase(W);
  }
  if (sameDir(ACD, AO)) {
    W.length = 0; W.push(D, C, A);
    return triangleCase(W);
  }
  if (sameDir(ADB, AO)) {
    W.length = 0; W.push(B, D, A);
    return triangleCase(W);
  }
  return { hit: true, dir: AO };
}

线段 / 三角形分支与自检（分离/重叠的盒子、球、四面体）见 gjk3d.mjs。本地可跑：

node docs/posts/graphics/gjk3d.mjs

若要穿透深度，在 hit === true 时把当前四面体交给 EPA；若要分离距离与 witness，改用上文距离模式（重心坐标 + 收敛判定），单纯形进化逻辑可以共用。

小结与扩展

GJK 通过闵可夫斯基差映射、支撑函数采样和单纯形迭代工作：相交判定看差集是否包住原点；距离模式则逼近差集上离原点最近的点，并用重心坐标还原两侧表面上的最近点。只关心「是否碰撞」时可以早停，通常极快。

若已经相交、还需要穿透深度和接触法向（刚体解算往往要这些），一般在 GJK 返回「包含原点的单纯形」之后，衔接 EPA（Expanding Polytope Algorithm，扩展多胞体算法）继续算——那是穿透情形下的深度，与分离时的 $\lVert P \rVert$ 距离是两条不同的后续路径。

GJK 算法：用闵可夫斯基差做凸体相交检测

详情