翻译自：http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
今天，我将讨论dyn4j项目随附的其他碰撞检测算法。您可以找到很多GJK文档，但是其中很多实际上是技术性的，主要是因为它们是研究论文。我强烈推荐该视频教程，老实说，看完之后，您甚至不需要进一步阅读。但是，如果您在观看视频后觉得需要更多信息，请继续阅读。
- 介绍
- 凸包
- 闵可夫斯基和
- 单纯形
- Support函数
- 创建单纯形
- 确定碰撞
- 迭代
- 检查单纯形
简介
GJK与SAT一样，仅在凸包上运行。GJK更具吸引力的功能之一是，它可以支持实现“support ”函数的任何形状（我们将在后面讨论）。因此，与SAT不同，您不需要增加特殊的代码或算法来处理弯曲的形状。
GJK是一种迭代方法，但是收敛速度非常快，如果使用最终的穿透/分离向量进行约束，则可以在几乎恒定的时间内运行。在3D环境中，它是SAT的更好替代方案，因为SAT必须测试轴数。
GJK的初衷是确定两个凸包之间的距离。GJK还可以用于在小距离穿透情况下获取碰撞信息，并可以通过其他算法进行补充以实现更大距离的穿透。
凸包
正如我之前说的，GJK是只能用于凸包的算法。请参阅我在SAT上的帖子以获取有关凸包的解释。
闵科夫斯基和
GJK算法在很大程度上依赖于称为闵科夫斯基和的概念。闵科夫斯基和在概念上非常容易理解。假设您有两个形状，这些形状的闵科夫斯基和就是shape1中的所有点加到shape2中的所有点上{得到的是另外一个更大更复杂的形状}：
A + B = {a + b |a∈A，b∈B}
如果两个形状均为凸包，则所得形状为凸包{如果需要深入了解，可以参考wiki百科}。
您可能会想，“好，那很好，但是这有什么关系呢？”重要性不在于加法，而是在于减法：
A – B = {a – b |a∈A，b∈B}
作为补充，在继续操作之前，请注意，即使我们使用的是“减法”运算符，然而事实上它不该被称为闵科夫斯基差，因为其仍然是闵科夫斯基和{相当于先将B中的所有点相对于原点进行镜像，使用得到的形状与A计算闵科夫斯基和}。不过，在本文的其余部分中，为清楚起见，我将其称为闵科夫斯基差。
继续，在闵科夫斯基和中执行减法操作的关键是：
如果两个形状重叠/相交，则闵科夫斯基差将包含原点。
图1：两个凸形状相交
让我们看一个例子，取图1中的两个形状并对它们执行闵科夫斯基差，您将得到图2中的结果形状。请注意，结果形状包含原点，因为图1中的两个形状是相交的。
执行此操作需要shape1.vertices.size * shape2.vertices.size * 2个减法。这是很重要的，因为形状是由无穷多个点组成的。由于这两个形状都是凸包，且由最外面的顶点定义，所以我们只需要对这些顶点执行此操作。关于GJK伟大的事情是，你并不真正需要计算闵科夫斯基差。
图2：闵科夫斯基差
单纯形(Simplex)
我们不想计算闵科夫斯基差，而只是想知道闵科夫斯基差是否包含原点。如果包含，那么两个形体就是是相交的；如果不包含，则它们不相交。
我们可以做的是，在闵科夫斯基差形体内迭代构建一个试图包含原点的多边形。如果我们构建的多边形包含原点（也形体包含在闵科夫斯基差形体内），那么我们可以说闵科夫斯基差包含原点。我们要构建的多边形称为“单纯形(Simplex)”。
Support函数
那么下一个问题是我们如何构建单纯形？Simplex是使用所谓的Support函数构建的。给定两个形体，Support函数应在闵科夫斯基差内返回一个点。我们已经知道我们可以从shape1中获取一个点，并从shape2中获取一个点，并将其相减以获得闵科夫斯基差中的一个点，但是我们不希望每次都得到相同的点。
如果使Support函数依赖于方向，我们可以确保每次调用Support函数时都不会得到相同的点。换句话说，如果使Support函数在某个方向上返回最远的点，则可以后续选择其他方向来获取其他点。
选择方向上最远的点很重要，因为它会创建一个最大包含面积的单纯形，因此增加了算法快速退出的机会。另外，我们可以利用这样的事实，即以这种方式返回的所有点都在闵科夫斯基差的边缘，因此，如果我们不能沿某个方向添加一个超出原点的点，我们就知道闵科夫斯基差不包含原点。这增加了算法在非相交情况下快速退出的机会。稍后对此进行更多讨论。
1
2
3
4
5
6
7
8
9
10
public Point support(Shape shape1, Shape shape2, Vector d) {
// d is a vector direction (doesn't have to be normalized)
// get points on the edge of the shapes in opposite directions
Point p1 = shape1.getFarthestPointInDirection(d);
Point p2 = shape2.getFarthestPointInDirection(d.negative());
// perform the Minkowski Difference
Point p3 = p1.subtract(p2);
// p3 is now a point in Minkowski space on the edge of the Minkowski Difference
return p3;
}
创建单纯形
让我们从一个例子开始。使用图2中的形状并执行3次Support函数：
首先让我们开始使用d =（1，0）
1
2
3
p1 = (9, 9);
p2 = (5, 7);
p3 = p1 - p2 = (4, 2);
接下来让我们使用d =（-1，0）
1
2
3
p1 = (4, 5);
p2 = (12, 7);
p3 = p1 - p2 = (-8, -2);
请注意，p1可能是（4，5）或（4，11）。两者都会在闵可夫斯基差的边缘产生一个点。
接下来让我们使用d =（0，1）
1
2
3
p1 = (4, 11);
p2 = (10, 2);
p3 = p1 - p2 = (-6, 9);
我们获得图3中所示的Simplex。
图3：示例单纯形
确定碰撞
前面我们说过，如果闵可夫斯基差中的单纯形包含原点，则我们知道这两个形状是相交的。在图3中，单纯形不包含原点，但是我们知道这两个形状是相交的。这里的问题是，我们的第一个猜测（在选择方向时）没有产生包含原点的单纯形。
如果相反，我为第三个闵科夫斯基差方向选择d =（0，-1）：
1
2
3
p1 = (4, 5);
p2 = (5, 7);
p3 = p1 - p2 = (-1, -2);
这样就产生了图4所示的单纯形，现在我们包含了原点并可以确定存在碰撞。
图4：包含原点的示例单纯形
因此，正如我们所看到的，方向的选择会影响结果。我们还可以看到，如果获得不包含原点的单纯形，则可以计算另一个点，并使用它。
这就是算法的迭代部分出现的地方。我们不能保证我们选择的前3个点将包含原点，也不能保证Minkowski差值包含原点。我们可以通过仅沿原点方向选择点来修改选择点的方式。如果我们将选择第三个Minkowski差异点的方式更改为下方，则可以将原点围起来。
1
2
3
4
5
6
7
8
d = ...
a
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ri-ji/41246.html