GJK碰撞检测算法

田有朋

2020-05-03

关注关注

https://blog.lufei.so/#/collisionDetection/GJK/1

https://blog.lufei.so/#/collisionDetection/GJK/2

现实世界里我们对于是否碰撞的判断可以说极其容易而且准确，比如下图。在二进制的世界里，一切就没这么直观了。

GJK碰撞检测算法

GJK(Gilbert-Johnson-Keerthi Distance Algorithm)

GJK 就是此次要实现的碰撞检测算法。如果对碰撞算法有过了解的话，大概率听过另一个碰撞检测算法 SAT(Separating Axis Theorem)。

GJK 相较于 SAT 有什么优点吗？

快
简单

实际上就我目前了解的碰撞检测算法，应用对象都是凸多边形(Convex polygon)。如果不是凸多边形，问题也不大，可以事先分割。

游戏里对于不规则物体，我们通常都是借助工具生成顶点数据。此时生成的数据通常都是处理过的(凹多边形被分解)，如果你想了解更多关于凹多边形分解的知识，可以参考这两个库：poly-decomp.js，earcut。

GJK碰撞检测算法

Minkowski Difference

由于不知道 Min 到底是“明”还是“闵”，所以下面都用 MD 表示了。

MD 是 GJK 算法的理论基础。那么到底什么是 MD ？

假设有两个凸多边形：

s1 =[{x:1, y:10},{x:3, y:10},{x:3, y:8},{x:1, y:8}]
s2 =[{x:2, y:9},{x:4, y:7},{x:2, y:7}]

那么它们的位置看起应该像下图这样。

GJK碰撞检测算法

MD 就是 s1 与 s2 所有点的差形成的集合。

MD(s1, s2):
  s3 =[]for p1 in s1:for p2 in s2:
      s3.push(p1 - p2)return s3

MD(s1, s2)=>[{x:-1, y:1},{x:-3, y:3},{x:-1, y:3},{x:1, y:1},{x:-1, y:3},{x:1, y:3},{x:1, y:-1},{x:-1, y:1},{x:1, y:1},{x:-1, y:-1},{x:-3, y:1},{x:-1, y:1}]

这些点的布局如下图所示：

GJK碰撞检测算法

关键的地方来了。首先要介绍一个新的概念叫 Convex Hull。

Convex Hull 是包含点集的最小凸多边形。拿上面的例子来说：

GJK碰撞检测算法

铺垫了这么久，现在可以说结论了。

我们把 s1 - s2 点集形成的 Convex Hull 命名为 s3。如果 s3 包含点 (0, 0)，那么 s1 和 s2 发生碰撞。

有没有觉得很简单？对，原理就是这么简单。

至于怎么算出点集的 Convex Hull，翻译自维基百科的 Gift wrapping algorithm 。

functionwrap(points){const hull =[]let current ={x:Infinity}for(const p of points){if(p.x < current.x) current = p
  }let i =0, end

  while(true){
    hull[i]= current
    end = points[0]for(let j =1; j < points.length; j++){if((end.x === current.x && end.y === current.y)||inline(points[j], hull[i], end)>0){
        end = points[j]}}
    i +=1
    current = end

    if(end.x === hull[0].x && end.y === hull[0].y)break}return hull
}

Gift wrapping algorithm 是获取 Convex Hull 的一种算法，不是效率最高的但应该是最易懂的。

最后就是判断点是否在多边形内的算法了，可以看我之前的文章。

交互示例

思考

有小伙伴不禁要问：这样的嵌套循环真的比 SAT 快？确实，上面的实现并不是真正意义上的 GJK 算法。但是核心思想是一样的：

如果两个凸多边形的 Minkowski Difference 所形成的 Convex Hull 包含点 (0, 0)，那么这两个凸多边形相交。

怎么优化这个实现呢？

我们并不需要计算两个凸多边形所有点的 Minkowski Difference。还是文章开始的例子：

GJK碰撞检测算法

我们只需要尽早的从已知的条件里判断出是否包含原点即可。

比如：如果获取到的第一个点刚好是原点，说明相交停止循环，否则继续获取下一个点，如果原点在两点的连线上，说明相交停止循环，否则继续获取下一个点。

真正的 GJK 算法用了一个很取巧的方式来减少循环次数，而且效果很理想。当然这也是下篇文章里的内容了。

感兴趣的小伙伴也可以从下面的参考资料里先尝试一波。

参考资料

国际惯例先放图。

GJK碰撞检测算法

GJK 是怎么快速判断出这两个图形是否碰撞的呢？

GJK碰撞检测算法

Support Function

Support Function 用来计算凸体在给定方向上的最远点。什么意思呢？

GJK碰撞检测算法代码片段

图示中的例子带入，可以得到 (9, 6) = (0, 4) - (-9, -2)，正是图二三角形的一个顶点。

将方向取反再调用 getSupport，我们可以得到 (-1, -2) = (-6, 0) - (-5, 2)，也是图二三角形的一个顶点。

这样做的意义是什么呢？因为可以确保我们所取的两个点跨度足够大，有更大的概率包含原点，减少循环次数。

GJK碰撞检测算法

那么问题来了：

初始给定的方向是怎么来的？
随机。更推荐的是凸体中心的差：direction = shapeA.center - shapeB.center。
已经获取了两个点，那么第三个点如何确定呢？
通过 a(9, 6)，b(-1, -2)，可以计算出垂直于向量 ab(-10, -8) 且指向原点方向的向量，这个向量将会作为 direction 来获取第三个点。
这里要用到向量积来计算出 direction。
代码片段