Welcome(〃'▽'〃)!

这里可能没有什么厉害的技术帖,但是会有一些实用的小教程

碰撞检测之GJK算法(一)

最近在为学校的一个工程软件做优化,需要用到碰撞检测算法,从网上找了一篇英语的文章,里面比较详细地介绍了GJK算法,翻了一下中文网站,发现也有对这篇文章的中文翻译,不过排版和翻译不是很好,所以想着自己翻译一下,这样也能对算法理解得更深一点。最近比较忙,所以可能分成好几次更新。

碰撞检测之GJK算法

1.概述

GJK算法全称为Gilbert–Johnson–Keerthi距离算法,最初是用来计算两个凸体之间的距离,也可以用来计算碰撞。GJK算法和SAT算法一样,只对凸形有效。GJK算法的最吸引人的一点是通过实现一个support函数,能够支持任何形状的凸形碰撞检测(这个我们之后再说)。因此,你没必要像SAT算法那样用特殊的代码或算法处理曲面。

GJK算法主要用了一种迭代求解的方法,但收敛速度非常快,如果事先给出穿透或是分离向量,那么这个算法可以在常量时间内完成。由于SAT算法必须测试的轴数过多,所以在3D环境中,GJK算法是SAT算法的更好替代品。

GJK算法发明的初衷是为了确定两个凸形之间的距离。它也可以返回比较浅层的穿透的碰撞信息,也可以和其他算法相结合,实现更深入的穿透碰撞检测。

2.凸形

GJK算法只能用在凸形上,凸形的解释请自行搜索。

3.明可夫斯基和

GJK算法在依赖于一个名为明可夫斯基和的概念。明可夫斯基和很容易理解:假设你有两个图形,这两个图形的明可夫斯基和是第一个图形中的所有点加到第二个图形中的所有点上,即:

A + B = {a + b|a∈A, b∈B}

如果两个图形都是凸形,那么结果也会是一个凸形。

你可能会想,“没错,但这和算法有什么关系?”其实这个概念的重要性不在于明可夫斯基和,而是做差,我们类比一下,可以叫它明可夫斯基差:

A – B = {a – b|a∈A, b∈B}

这里做差的重要性在于下面这个定理:

如果两个图形重叠或者相交,那么它们的明可夫斯基差将包围原点。

下一篇:碰撞检测之GJK算法(二)

点赞

发表评论

电子邮件地址不会被公开。