我研究了碰撞识别过程，这使我想到了Gilbert-Johnson-Keerthi（GJK）算法。

帖子中的所有代码示例均使用TypeScript编写。 这些示例使用我创建的结构，本文中没有详细讨论。 它们很简单，可以在GitHub存储库中查看：

• Vector
• IShape
• Collision

帖子中的所有代码都存储在GitHub存储库中：

https://github.com/jthomperoo/gjk-ts-implementation

该帖子是根据本文以及其中推荐的视频撰写的：

• http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
• http://mollyrocket.com/849

引言

GJK是一种算法，用于确定两个凸形的交集。 它很简单，并使用通用的“辅助功能”实现，该功能使您可以使用更通用的方法-以相同的方式，您可以处理由曲线组成的多边形和形状，例如椭圆。

必填信息

明可夫斯基总和

GJK使用称为Minkowski和的概念。 SM是通过将两个数字的所有点相加得出的。 例如，请看下面两个图：


图A（绿色）：


图B（紫色）：


取图A和图B的值，我们可以计算出Minkowski和：

A + D = (0,1) + (0,-1) = (0,0)

A + E = (0,1) + (1,1) = (1,2)

A + F = (0,1) + (-1,1) = (-1,2)

B + D = (1,-1) + (0,-1) = (1,-2)

B + E = (1,-1) + (1,1) = (2,0)

B + F = (1,-1) + (-1,1) = (0,0)

C + D = (-1,-1) + (0,-1) = (-1,-2)

C + E = (-1,-1) + (1,1) = (0,0)

C + F = (-1,-1) + (-1,1) = (-2,0)

如果我们采用这些值并根据它们绘制图表，我们将看到结果是哪个数字。

图A和B的Minkowski总和：

请注意，表和图中的AD对应于A + D



为了更好地理解Minkowski和，我们可以想象得到一个数字A，并绕过它的轮廓B。结果得到的数字就是Minkowski和。

Minkowski差异

GJK使用Minkowski总和的一种变体，其中不采用A + B，而是采用A-B。在我阅读的资料中，这称为“ Minkowski差”。 Minkowski差具有一个有趣的属性：如果两个图形重叠/相交，则所得的Minkowski差将包含原点。 这是GJK算法的基础。

取图A和B的值，我们可以计算出Minkowski差：

A - D = (0,1) - (0,-1) = (0,2)

A - E = (0,1) - (1,1) = (-1,0)

A - F = (0,1) - (-1,1) = (1,0)

B - D = (1,-1) - (0,-1) = (-1,0)

B - E = (1,-1) - (1,1) = (0,-2)

B - F = (1,-1) - (-1,1) = (2,-2)

C - D = (-1,-1) - (0,-1) = (-1,0)

C - E = (-1,-1) - (1,1) = (-2,-2)

C - F = (-1,-1) - (-1,1) = (0,-2)

如果我们将这些值放在图表上，我们将看到结果图。

图A和B的Minkowski差：

请注意，表和图中的AD指的是A-D

演算法

基于这些概念，GJK算法对其进行了优化。 计算Minkowski和可能要花费很多时间，尤其是如果您检查由许多点组成的两个图形的交集。 为了避免这种情况，GJK使用了两个关键概念：辅助函数和单纯形。

辅助功能

辅助功能是一种在不构造整个图形的情况下对Minkowski差的边缘上的点进行采样的方法。 辅助函数获得两个比较的数字，以及需要检查的方向。 然后，辅助功能从每个图形中接收一个距离两个相反方向最远的点。 使用这两个最远的点，您可以在Minkowski差的图形上计算辅助点。 我们从相反的方向获取点，因为我们在Minkowski差上得到了一个点，这将为我们提供最大的面积，也就是说，将原点封闭在图中的可能性更高。 由于Minkowski差是 a - b从相反方向采样的图形b的点的存在将为我们提供一个在该方向上尽可能远的辅助点。

helper函数的实现非常简单：

 function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

GJK的优点之一是FarthestPointInDirection可以抽象并应用于多边形和曲线。 这是多边形的FarthestPointInDirection的实现。

 class Polygon implements IShape { public points: Vector[]; ... public FarthestPointInDirection(direction: Vector): Vector { let farthestDistance = -Infinity; // If there are no points, just return point 0,0 let farthestPoint: Vector = new Vector(0,0); for (const point of this.points) { const distanceInDirection = point.Dot(direction); if (distanceInDirection > farthestDistance) { farthestPoint = point; farthestDistance = distanceInDirection; } } return farthestPoint; } } 

如果您想了解如何实现其他形状， 请查看本文的Git存储库 ，其中介绍了Circle的实现。

这是如何为图A和B计算（1,0）方向上的辅助点的方法：

1. 从图A取最远的点； 原来是点B（1，-1） 。 （您可以按照上面显示的算法进行计算，也可以通过查看图表来查看它）。
2. 从图B取最远的点； 原来是点F（-1，1） 。
3. 计算B-F ; 事实证明它是点BF（2，-2） -将是辅助点 。

单纯形

单形是沿Minkowski差图的点的样本。 单纯形最多可以包含三个点。 GJK使用它们，试图围绕原点构造一个三角形以确定碰撞的发生。

单面构造

通过在不同方向上添加辅助点来迭代构造单纯形。 每个辅助点都应指向一个新方向，以便我们可以尽快构建包含原点的单纯形。 困难在于选择获得下一个辅助点的方向。

碰撞检测和方向选择

基本算法只是在辅助功能的帮助下构建一个单纯形，试图将图中的原点封闭起来。 通过检查计算出的辅助点是否到达原点，我们可以理解没有碰撞/相交，如果没有到达，则原点必须在Minkowski差之外； 因此，可以说没有碰撞/交叉。

 function Calculate(a: IShape, b: IShape): Collision | undefined { // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); } 

该算法的所有复杂性和内部运算都在simplex.CalculateDirection 。 该函数确定原点是否在当前的单纯形中-如果是这样，它将返回undefined ； 否则，它将返回新方向以获得辅助点，该辅助点必须添加到单纯形中。

 class Simplex { private points: Vector[]; ... CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } return undefined; } // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; } } 

您可能想知道：为什么我们不检查BC段？ 因为我们可以无条件排除原点沿其垂直方向。 由于点B和C已经在单纯形中，并且不仅已经添加了它们，所以我们知道在上一次迭代中已对其进行了检查。 可以将它们检查为三角形的一部分，也可以将其作为单纯形的前两个点的一部分进行检查-没关系。 因此，我们可以安全地跳过BC段检查。

详细说明

我们有很多代码，看起来很混乱。 下面，我将分析上述图A和B的算法步骤。

图A和B的要点：

1. 编写算法； 我们将(0,1)作为初始方向。
   
   

    // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); 

   
   
2. 我们得到第一个辅助点。
   
   

     // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); 

   
   我们从点A沿方向(0,1)获得最远的点，从点B沿方向(0,-1)获得最远的点。
   
   aFar： (0,1)和bFar： (0,-1)
   
   使用这些值获得辅助点。
   
   支持度： aFar-bFar = (0,2)
   
   

     function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

   
   
3. 我们翻转下一个辅助点的方向并开始迭代，计算出一个新的辅助点。
   
   支持： (0,-3)
   
   

     // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); 

4. 检查辅助点是否到达原点； 如果没有，则不应有交叉点。 如果她到达原点，则将点添加到单纯形。
   
   在这种情况下，辅助点已到达原点。
   
   方向： (0,-1)
   
   支持： (0,-3)
   
   supportPoint.Dot（方向）： 3
   
   

     // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); 

   
   
5. 在此阶段，单纯形是一个线段，因此它不能在其中包含起点。 定义寻找辅助点的新方向。
   
   

     direction = simplex.CalculateDirection(); 

   
   
   1. 我们采用添加到单纯形的最后一点，并确定到原点的方向，这将是该点的倒数。
      
      a： (0,-3) ao： (0,3)
      
      

        CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { 

   2. 由于单纯形是一个线段，而不是三角形，因此我们取该线段的第二个点，然后计算单形的线段。
      
      b： (0,2) ab： (0,5)
      
      

        // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); 

   3. 我们计算与该线段的垂直线，并验证其是否指向原点。 这将是下一个辅助点的新方向。
      
      abPerp： (5, 0) 5，0 (5, 0)
      
      abPerp.Dot（ao） 0
      
      abPerp： (-5, 0) 5，0 (-5, 0)
      
      
      
      
      

        // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; 

6. 现在我们有一个方向来搜索下一个辅助点。 我们返回到循环的起点，但不退出循环，因为虽然我们有方向，但尚未找到交点。
   
   方向： (-5, 0)
   
   支持： (-2,-2)
   
   supportPoint.Dot（方向）： 10
   
   辅助点已到达原点，因此我们不能说没有交点。
   
   

     while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } 

7. 在单纯形上添加一个新的辅助点，从而创建一个三角形。 这个三角形可能包含原点，如果是这样，则单纯形将返回undefined ，而不是搜索的新方向。
   
   

     // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); 

   
   
   1. 取三角形的单纯形的点。
      a： (-2,-2) b： (0,-3) c： (0,2) ao： (2,2)
      
      

        // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; 

   2. 取段ab和ac。
      
      ab： (2,-1) ac： (2,4)
      
      

        // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); 

   3. 我们计算从单纯形指向段ab的垂直线。
      
      abperp： (-1,-2)
      
      

        // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } 

   4. 我们确定原点是否在ab以外的单纯形之外。
      
      abPerp.Dot（ao）：- -6
      
      原点不在ab之外的单纯形之外。
      
      
      
      
      

        if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } 

   5. 我们计算与单纯形指向的ac的垂直线。
      
      acPerp： (-4,2) 4.2 (-4,2)
      
      

        // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } 

   6. 确定原点是否在交流以外的单纯形之外。
      
      ac.Dot（ao）：-4
      
      原点不在ab之外的单纯形之外。
      
      
      
      
      

        // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } 

   7. 由于在此迭代中检查了AB和AC，并且我们知道在先前的迭代中检查了BC，因此原点必须位于单纯形内，因此检测到碰撞/相交-对此进行通知，该函数将返回undefined 。
      
      
      
8. 由于已检测到碰撞，因此退出循环并返回有关两个图形之间Collision信息。
   
   

     direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); 

结论

希望本文能帮助您了解GJK算法。 该算法对两个图形之间是否存在冲突给出了是/否的答案。 可以在此帖子的存储库中查看带有多边形和圆形的工作示例。 通过尝试获取两个图形之间的穿透距离，碰撞法线和接触点，可以使用其他算法和技术来扩展此代码。 dyn4j帖子提供了有关各种冲突/响应识别算法的良好资源的链接； 如果要扩展GJK，则应该研究它们。