GJK 算法(Gilbert–Johnson–Keerthi)
翻译自：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 = support(..., d) d = ... b = support(..., d) AB = b - a AO = ORIGIN - a d = (AB x AO) x AB c = support(..., d) |
因为c将要使用的d取决于a和b形成一条线，所以我们可以选择b使之与a尽可能远离，方法是使用相反的方向：
| 1 2 3 4 5 6 7 | d = ... a = support(..., d) b = support(..., -d) AB = b - a AO = ORIGIN - a d = (AB x AO) x AB c = support(..., d) |
因此，现在我们只需要为第一个Minkowksi差点选择d。这里有很多选择，一个任意方向，由形状中心的差异创建的方向，等等。任何方法都可以，但是有些更优化。
注意：AB代表“ A点到B点”，可以通过B – A 而不是 A – B 来找到。这适用于其余职位。AO，AC等均遵循此格式。
迭代
即使我们更改了上面的内容来确定碰撞，我们仍然可能无法在这三个步骤中获得包含原点的单纯形。我们必须迭代创建Simplex，以使Simplex更加接近于包含原点。我们还需要检查两个条件：1）当前的单纯形是否包含原点？和2）我们能够附上原点吗？
让我们看一下迭代算法的框架：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | Vector d = // choose a search direction // get the first Minkowski Difference point Simplex.add(support(A, B, d)); // negate d for the next point d.negate(); // start looping while (true) { // add a new point to the simplex because we haven't terminated yet Simplex.add(support(A, B, d)); // make sure that the last point we added actually passed the origin if (Simplex.getLast().dot(d) <= 0) { // if the point added last was not past the origin in the direction of d // then the Minkowski Sum cannot possibly contain the origin since // the last point added is on the edge of the Minkowski Difference return false; } else { // otherwise we need to determine if the origin is in // the current simplex if (Simplex.contains(ORIGIN)) { // if it does then we know there is a collision return true; } else { // otherwise we cannot be certain so find the edge who is // closest to the origin and use its normal (in the direction // of the origin) as the new d and continue the loop d = getDirection(Simplex); } } } |
接下来，在图1的示例中使用骨骼。让我们将初始方向设置为从shape1的中心到shape2的中心的向量：
| 1 2 3 4 | d = c2 - c1 = (9, 5) - (5.5, 8.5) = (3.5, -3.5) = (1, -1); p1 = support(A, B, d) = (9, 9) - (5, 7) = (4, 2); Simplex.add(p1); d.negate() = (-1, 1); |
然后我们开始循环：
迭代1
请注意，使用了以下三乘积展开：
（A x B）x C = B（C.dot（A））– A（C.dot（B））来评估三乘积。
| 1 2 3 4 5 6 7 8 9 10 11 | last = support(A, B, d) = (4, 11) - (10, 2) = (-6, 9); proj = (-6, 9).dot(-1, 1) = 6 + 9 = 15 // we past the origin so check if we contain the origin // we dont because we are line // get the new direction by (AB x AO) x AB AB = (-6, 9) - (4, 2) = (-10, 7); AO = (0, 0) - (-6, 9) = (6, -9); (AB x AO) x AB = AO(149) - AB(-123) = (894, -1341) - (1230, -861) = (-336, -480) = (-0.573, -0.819) |
图5：第一次迭代
图5显示了迭代1之后的结果单纯形。我们有一个线段（棕色）单纯形，下一方向（蓝色）指向与原点垂直的线。需要注意的是，不需要对方向进行规范化（请参见迭代2），但是我在这里这样做，因此我们可以根据给定的比例来验证方向。
迭代2
| 1 2 3 4 5 6 7 8 9 10 11 12 | last = support(A, B, d) = (4, 5) - (12, 7) = (-8, -2) proj = (-8, -2).dot(-336, -480) = 2688 + 960 = 3648 // we past the origin so check if we contain the origin // we dont (see Figure 6a) // the new direction will be the perp of (4, 2) and (-8, -2) // and the point (-6, 9) can be removed AB = (-8, -2) - (4, 2) = (-12, -4); AO = (0, 0) - (-8, -2) = (8, 2); (AB x AO) x AB = AO(160) - AB(-104) = (1280, 320) - (1248, 416) = (32, -96) = (0.316, -0.948) |
图6a：第二个迭代：新的单纯形
图6b：第二个迭代：新的单纯形和方向
在第二次迭代后，我们尚未封闭原点，但仍不能得出形状未相交的结论。在第二次迭代中，我们删除了（-6，9）点，因为我们随时需要3个点，并且在每次迭代的开始处添加一个新点。
迭代3
| 1 2 3 4 | last = support(A, B, d) = (4, 5) - (5, 7) = (-1, -2) proj = (-1, -2).dot(32, -96) = -32 + 192 = 160 // we past the origin so check if we contain the origin // we do (Figure 7)! |
图7：第三个迭代：检测到碰撞
检查单纯形
我们仅使用图片和检查就算法中的两个操作进行了介绍。一种是，我们如何知道当前的单纯形包含原点？另一个是，我们如何选择下一个方向？在上面的伪代码中，为清楚起见，我将这些操作分开，但实际上，它们实际上应该在一起，因为它们需要了解很多相同的信息。
我们可以通过执行一系列平面测试（二维线测试）来确定原点相对于单纯形的位置，其中每个测试都由简单的点积组成。必须处理的第一种情况是线段情况。因此，让我们看一下上面示例中的第一次迭代。在线9上添加第二个点之后，单纯形现在是线段。我们可以通过检查Voronoi区域来确定单纯形是否包含原点（参见图8）。
图8：Voronoi地区
线段定义为A到B，其中A是添加到单纯形的最后一点。我们知道A和B都在Minkowski差的边缘，因此原点不能位于R1或R4中。我们可以做这个假设，因为第11行的支票返回false，表示当我们获得下一个点时，我们通过了原点。原点只能位于R2或R3中，并且由于线段不能包含原点，因此所有要做的就是选择一个新方向。如前所述，这可以通过使用AB在原点方向上的角度来完成：
| 1 2 3 4 | // the perp of AB in the direction of O can be found by AB = B - A; AO = O - A; perp = (AB x AO) x AB; |
当O躺在线上时会发生什么呢？如果发生这种情况，perp将为零向量，并且将导致第11行的检查失败。这可能在两个地方发生：1）Minkowski Sum内部和2）Minkowski Sum的边缘。后一种情况表示接触是接触而不是穿透，因此您需要确定是否将其视为碰撞。无论哪种情况，都可以使用AB的左或右法线作为新方向。
现在让我们检查第二个迭代。第二次迭代将我们的单纯形变成一个三角形（图9）。
图9：Voronoi地区
白色区域不必进行测试，因为原点不能超过任何这些点，因为添加了每个点是因为它们通过了第11行的检查。R2不能包含原点，因为我们选择的最后一个方向是相反的方向。因此，仅要测试的区域是R3，R4和R5。我们可以执行（AC x AB）x AB来产生与AB垂直的向量。然后我们执行：ABPerp.dot（AO）以确定原点是否在区域R4中。
| 1 2 3 4 5 6 7 8 9 10 11 | AB = (-6, 9) - (-8, -2) = (2, 11) AC = (4, 2) - (-8, -2) = (12, 4) // (AC x AB) x AB = AB(AB.dot(AC)) - AC(AB.dot(AB)) ABPerp = AB(68) - AC(125) = (136, 748) - (1500, 500) = (-1364, 248) = (-11, 2) // compute AO AO = (0, 0) - (-8, -2) = (8, 2) ABPerp.dot(AO) = -11 * 8 + 2 * 2 = -84 // its negative so the origin does not lie in R4 |
因此，通过另一项测试，我们可以确定原点在哪里：
| 1 2 3 4 5 6 7 8 9 10 11 | AB = (-6, 9) - (-8, -2) = (2, 11) AC = (4, 2) - (-8, -2) = (12, 4) // (AB x AC) x AC = AC(AC.dot(AB)) - AB(AC.dot(AC)) ACPerp = AC(68) - AB(160) = (816, 272) - (320, 1760) = (496, -1488) = (1, -3) // compute AO AO = (0, 0) - (-8, -2) = (8, 2) ACPerp.dot(AO) = 1 * 8 + -3 * 2 = 2 // its positive so that means the origin lies in R3 |
因此，我们发现原点位于R3中，因此现在我们需要选择一个方向，以便获得该方向上的下一个Minkowski差点。这很容易，因为我们知道AC是其Voronoi区域的原点包含在以下线段中：
| 1 | (AC x AO) x AC |
由于我们使用的是A点和C点，因此我们可以不用B点就可以摆脱它。新代码变为：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | Vector d = // choose a search direction // get the first Minkowski Difference point Simplex.add(support(A, B, d)); // negate d for the next point d.negate(); // start looping while (true) { // add a new point to the simplex because we haven't terminated yet Simplex.add(support(A, B, d)); // make sure that the last point we added actually passed the origin if (Simplex.getLast().dot(d) <= 0) { // if the point added last was not past the origin in the direction of d // then the Minkowski Sum cannot possibly contain the origin since // the last point added is on the edge of the Minkowski Difference return false; } else { // otherwise we need to determine if the origin is in // the current simplex if (containsOrigin(Simplex, d) { // if it does then we know there is a collision return true; } } }
public boolean containsOrigin(Simplex s, Vector d) { // get the last point added to the simplex a = Simplex.getLast(); // compute AO (same thing as -A) ao = a.negate(); if (Simplex.points.size() == 3) { // then its the triangle case // get b and c b = Simplex.getB(); c = Simplex.getC(); // compute the edges ab = b - a; ac = c - a; // compute the normals abPerp = tripleProduct(ac, ab, ab); acPerp = tripleProduct(ab, ac, ac); // is the origin in R4 if (abPerp.dot(ao) > 0) { // remove point c Simplex.remove(c); // set the new direction to abPerp d.set(abPerp); } else { // is the origin in R3 if (acPerp.dot(ao) > 0) { // remove point b Simplex.remove(b); // set the new direction to acPerp d.set(acPerp); } else{ // otherwise we know its in R5 so we can return true return true; } } } else { // then its the line segment case b = Simplex.getB(); // compute AB ab = b - a; // get the perp to AB in the direction of the origin abPerp = tripleProduct(ab, ao, ab); // set the direction to abPerp d.set(abPerp); } return false; } |
这样就完成了GJK碰撞检测算法的教程。原始的GJK算法计算了两个凸形之间的距离。我计划在另一篇文章中介绍算法的这一部分，因为这篇文章已经太长了。另外，正如我之前所说，如果您需要碰撞信息（法线和深度），则需要修改GJK算法或用其他算法进行补充。EPA是一种补充算法，我打算在另一篇文章中介绍。直到下一次…
