企业官网建设流程全解析

一句话：两个形状相撞 ⇔ 它们的"差集"包含原点。GJK 不去算完整的差集，而是在差集里挑几个点围成三角形（3D 是四面体），看能不能把原点围住。

还是按直觉 → 原理 → 代码 → 坑的顺序讲。

一、它解决什么问题？

物理引擎检测碰撞分两步：

GJK 的特点：

• 只要是凸形状都能用：多边形、圆、胶囊、凸多面体……
• 不关心形状具体是什么，只需要形状能回答一个问题：“往某个方向，你最远的点在哪？”

凸形状：任意两点连线都在形状内部，没有凹进去的地方。
圆、正方形、胶囊是凸的；L 形、五角星不是。

二、核心思想一：把"两个形状相交"变成"原点在不在一个形状里"

1. 推理只有三步

A 和 B 相交 ⇔ 存在一个点，既属于 A 又属于 B，即 a = b ⇔ a − b = 0 ⇔ 原点 (0,0) 属于集合 { a − b }

集合{ a − b }（A 里每个点减去 B 里每个点）叫闵可夫斯基差（Minkowski Difference），记作A − B。

所以：A、B 相撞 ⇔ 原点在 A − B 里面。
两个形状的问题，变成了一个形状 + 一个点的问题。

2. 用数字看一下

两个边长为 2 的正方形，A 中心在 (0, 0)，B 中心在 (1.5, 0)：

A 的 x 范围：[-1, 1] B 的 x 范围：[0.5, 2.5] A − B 的 x 范围：[-1 − 2.5, 1 − 0.5] = [-3.5, 0.5] ← 包含 0 → 相撞 ✅

把 B 移到 (3, 0)：

B 的 x 范围：[2, 4] A − B 的 x 范围：[-1 − 4, 1 − 2] = [-5, -1] ← 不包含 0 → 没撞 ❌

相撞时： 不撞时： ┌──────────┐ ┌──────────┐ │ A − B │●原点 │ A − B │ ● 原点 │ ● │ │ │ └──────────┘ └──────────┘ 原点在里面 原点在外面

3. 但差集点太多了，怎么办？

两个 100 个顶点的多边形，差集有 1 万个点组合，全部算出来太慢。GJK 的聪明之处：一个都不提前算，需要哪个点再临时算哪个。这就要靠"支撑函数"。

三、核心思想二：支撑函数（Support）——“往这个方向，最远的点”

1. 单个形状的支撑函数

给一个方向 d，返回形状上沿 d 方向最远的点。

d → ┌──────────● ← 往右最远的点 │ │ │ A │ └──────────┘

2. 差集的支撑函数

想让a − b沿 d 方向尽可能远：

• a 要沿 d尽量远→Support(A, d)
• b 要沿 d尽量近，也就是沿 −d 尽量远 →Support(B, −d)

Support(A − B, d) = Support(A, d) − Support(B, −d)

不用构造差集，只需要分别问 A 和 B 各一次。这是 GJK 高效的关键。

四、核心思想三：用"单纯形"去围住原点

2D 里能围住一块区域的最简单图形是三角形（3D 是四面体）。这些"点、线段、三角形、四面体"统称为单纯形（Simplex）。

GJK 的过程就像在黑暗中用三根绳子去套一个点：

① 随便选个方向，取一个支撑点 A （一个点） ② 朝着原点的方向，再取一个支撑点 B （一条线段） ③ 朝着"线段指向原点那一侧"，再取一个支撑点 C （一个三角形） ④ 原点在三角形里？ 是 → 相撞！ 否 → 扔掉离原点最远的那个点，朝原点方向再取一个新点，回到 ④

什么时候判定"不相撞"？

每次朝方向 d 取新点 p 时检查：

如果 dot(p, d) < 0 → 往原点方向找到的"最远点"都没越过原点 → 整个差集都在原点的另一边，原点不可能在里面 → 不相撞，直接结束

d ──────→ p ● | ● 原点 最远只到这里 | 没越过原点 → 不可能包住它

图解一次完整过程

第 1 步：取点 A 第 2 步：朝原点取点 B ● A ● A ╲ ○ 原点 ╲ ○ ● B 第 3 步：朝"线段 AB 靠原点的一侧"取点 C 第 4 步：原点在三角形内 → 相撞 ● A ● A ╲ │╲ ╲ ○ │ ╲ C ●──● B │○ ╲ C ●────● B

通常几次迭代就能出结果，非常快。

五、代码（Unity 2D 版本）

1. 形状接口：只需要支撑函数

usingUnityEngine;usingSystem.Collections.Generic;publicinterfaceIConvexShape{Vector2Support(Vector2dir);// 沿 dir 方向最远的点}publicclassPolygonShape:IConvexShape{publicVector2[]vertices;// 世界坐标下的顶点publicVector2Support(Vector2dir){Vector2best=vertices[0];floatmaxDot=Vector2.Dot(best,dir);for(inti=1;i<vertices.Length;i++){floatd=Vector2.Dot(vertices[i],dir);if(d>maxDot){maxDot=d;best=vertices[i];}}returnbest;}}publicclassCircleShape:IConvexShape{publicVector2center;publicfloatradius;publicVector2Support(Vector2dir){returncenter+dir.normalized*radius;}}

2. GJK 主体

publicstaticclassGJK2D{// 差集的支撑点staticVector2Support(IConvexShapea,IConvexShapeb,Vector2d){returna.Support(d)-b.Support(-d);}publicstaticboolIntersect(IConvexShapea,IConvexShapeb){varsimplex=newList<Vector2>(3);// ① 随便选一个初始方向Vector2d=Vector2.right;Vector2p=Support(a,b,d);if(p.sqrMagnitude<1e-12f)returntrue;// 恰好就是原点：贴在一起simplex.Add(p);d=-p;// 朝原点方向for(intiter=0;iter<32;iter++)// 迭代上限，防止精度问题死循环{p=Support(a,b,d);// 往原点方向最远的点都没越过原点 → 不相撞if(Vector2.Dot(p,d)<0)returnfalse;simplex.Add(p);if(UpdateSimplex(simplex,refd))returntrue;}returnfalse;}// 处理单纯形：原点被包住返回 true；否则精简单纯形并更新搜索方向// 约定：simplex 最后一个元素是最新加入的点staticboolUpdateSimplex(List<Vector2>s,refVector2d){if(s.Count==2){// —— 线段情况 ——Vector2a=s[1],b=s[0];Vector2ab=b-a,ao=-a;// 取垂直于 ab、并指向原点一侧的方向Vector2perp=newVector2(-ab.y,ab.x);if(Vector2.Dot(perp,ao)<0)perp=-perp;if(perp.sqrMagnitude<1e-12f||Vector2.Dot(perp,ao)==0)returntrue;// 原点刚好在线段上：接触d=perp;returnfalse;}else{// —— 三角形情况 ——Vector2a=s[2],b=s[1],c=s[0];Vector2ab=b-a,ac=c-a,ao=-a;// AB 边的外法线（背离 C）Vector2abPerp=newVector2(-ab.y,ab.x);if(Vector2.Dot(abPerp,ac)>0)abPerp=-abPerp;// AC 边的外法线（背离 B）Vector2acPerp=newVector2(-ac.y,ac.x);if(Vector2.Dot(acPerp,ab)>0)acPerp=-acPerp;if(Vector2.Dot(abPerp,ao)>0){s.RemoveAt(0);// 原点在 AB 外侧 → 扔掉 Cd=abPerp;returnfalse;}if(Vector2.Dot(acPerp,ao)>0){s.RemoveAt(1);// 原点在 AC 外侧 → 扔掉 Bd=acPerp;returnfalse;}returntrue;// 两条边内侧都是 → 原点在三角形内}}}

3. 为什么三角形只检查 AB、AC 两条边，不检查 BC？

● A（最新加入的点） ╱ ╲ ╱ ╲ B ●───────● C ↑ 上一轮就是从 BC 这条边朝原点方向找到了 A， 说明原点一定在 BC 的 A 这一侧，不用再查

A 是刚刚"越过原点"找到的点，所以原点也不会在 A 的背后。只剩 AB、AC 外侧两种可能，判断一下即可。这也是 GJK 快的原因之一。

4. 使用

varbox=newPolygonShape{vertices=new[]{newVector2(-1,-1),newVector2(1,-1),newVector2(1,1),newVector2(-1,1)}};varcircle=newCircleShape{center=newVector2(1.5f,0),radius=1f};boolhit=GJK2D.Intersect(box,circle);// true：圆的左边缘到了 x=0.5，与方块重叠

注意：方块和圆的碰撞用同一套代码，GJK 完全不关心形状类型，这就是支撑函数带来的通用性。

六、3D 版本有什么不同？

思路完全一样，只是单纯形多了一级：

3D 中求"垂直方向"常用叉乘：cross(cross(ab, ao), ab)，得到垂直于 ab、指向原点的方向。

七、GJK 的扩展

物理引擎里常见组合：GJK 判断相交 → EPA 求穿透深度和法线 → 物理求解器把两个物体推开。

八、GJK 与 SAT 对比

九、常见的坑

一句话总结

GJK = 把"两个形状相撞"转化为"原点在不在它们的差集 A − B 里"。

它不计算完整的差集，而是用支撑函数（往某方向最远的点）临时取点，构造三角形（3D 是四面体）去围住原点：每次朝原点方向取新点，若新点没越过原点就说明不相撞；若围住了原点就说明相撞；否则丢掉无用的点继续迭代。只需几次迭代，就能处理任意凸形状的碰撞。