Welcome(〃'▽'〃)!

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

碰撞检测之GJK算法(三)

上次讲到support函数的实现,接下来用一个例子来讲一下如何创建单纯形。

6.创建单纯形

用图二中的形状执行support函数三次:

首先使用方向向量d=(1,0)

p1 = (9, 9);
p2 = (5, 7);
p3 = p1 - p2 = (4, 2);

接下来使用d=(-1,0)

p1 = (4, 5);
p2 = (12, 7);
p3 = p1 - p2 = (-8, -2);

可以注意到,p1可能是(4,5)或(4,11)。两者都将在明可夫斯基差的边缘产生一个点。接下来使用d=(0,1)

p1 = (4, 11);
p2 = (10, 2);
p3 = p1 - p2 = (-6, 9);

我们可以得到图三中的单纯形。

《碰撞检测之GJK算法(三)》
图3

7.确定碰撞

我们知道如果明可夫斯基差中的单纯形包含原点,那么这两个图形是相交的。在图3中,我们构造的单纯形不包含原点,但这两个图形其实是相交的。问题就在于我们第一次选择方向向量时没有产生包含原点的单纯形。如果我们选择d=(0,-1)作为第三次执行support函数的方向向量:

p1 = (4, 5);
p2 = (5, 7);
p3 = p1 - p2 = (-1, -2);

这将产生图4中所示的单纯形,它包含原点,所以我们可以确定两个图形存在碰撞。

《碰撞检测之GJK算法(三)》
图4

因此,我们可以发现,方向向量的选择会影响结果。如果我们得到了不包含原点的单纯形,我们可以计算其他的点加入单纯形中。

这就是为什么GJK算法要用迭代。因为我们不能确保我们选择的前3个点包含原点,也不能保证明可夫斯基差包含原点。所以我们可以通过仅选择原点方向上的点来修改我们选择的点。

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:

d = …
a = support(…, d)
b = support(…, -d)
AB = b - a
AO = ORIGIN - a
d = (AB x AO) x AB
c = support(…, d)

所以现在我们只需要为第一个明可夫斯基差选择方向向量d。可以选择任意方向或者由图形中心的差指向的方向等。

注意:AB代表“A点到B点”,是通过B-A得到的而不是A-B。

未完待续

点赞

发表评论

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