Welcome(〃'▽'〃)!

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

碰撞检测之GJK算法(四)

上篇讲到如何创建单纯形去判断碰撞,接下来讲如何通过迭代一步步找到包围原点的单纯形(当然也有可能无法包围)

8.迭代

上一章中,即使我们更改了方向向量,也仍然可能无法获得包含原点的单纯形。所以我们必须迭代地创建单纯形,使得单纯形越来越接近原点最终包含它。

在迭代过程中我们需要检查两个条件:1)当前的单纯形是否包含原点 2)我们能否包含原点?

下面是迭代算法的架构:

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的中心的向量:

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);

接下来进入循环:

第一次迭代:

注意: (A x B) x C = B(C.dot(A)) – A(C.dot(B)) 

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显示了第一次迭代后得到的单纯形。我们得到了一个线段(棕色)单纯形,下一个方向向量(蓝色)垂直于线段并指向原点。需要注意的是,方向向量不需要标准化,这里这么做,是为了让我们可以验证给定比例的方向。

《碰撞检测之GJK算法(四)》
图5

第二次迭代:

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)

在第二次迭代之后,得到的单纯形还没有包含原点,但我们仍然不能断定图形不相交。在第二次迭代中,我们删除了(-6,9)点,因为任何时候我们只需要3个点来构成单纯形。

《碰撞检测之GJK算法(四)》
图6a
《碰撞检测之GJK算法(四)》
图6b

第三次迭代:

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)!

未完待续

点赞

发表评论

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