Welcome(〃'▽'〃)!

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

碰撞检测之GJK算法(二)

接上一篇文章

接下来对明可夫斯基差举个例子,对图1中的两个图形做明可夫斯基差,将会得到图2中的图形,你会发现这个图形包围着原点,这是因为两个图形相交。

《碰撞检测之GJK算法(二)》
图1

执行明可夫斯基差的操作总共需要shape1.vertices.size * shape2.vertices.size * 2次的减法操作。这点很重要,虽然图形是由无数个点组成的,但两个图形都是凸的并且由最外面的顶点定义,所以我们只需要在顶点上执行此操作。而GJK算法的好处在于你实际上并不需要计算明可夫斯基差。

《碰撞检测之GJK算法(二)》
图2

4.单纯形Simplex

在GJK算法中的实现中我们不必计算全部的明可夫斯基差。相反,我们只想知道明可夫斯基差是否包含原点。包含的话说明两个图形相交,反之亦反。

所以我们可以在得到的明可夫斯基差中迭代地构建一个多边形(也就是说从中取几个点),去试图包围原点。如果我们构建的多边形包含原点,那么我们可以说明可夫斯基差包含原点。

我们所要构建的这个多边形称为单纯形(Simplex)。关于单纯形的定义自行搜索。

5.Support函数

接下来的问题是我们如何去构建需要的单纯形?我们可以用一个support函数去辅助构造这个单纯形。给定两个图形,Support函数可以返回这两个图形的明可夫斯基差中的一个点。我们可以从图形1和图形2中各取一个点并相减来获得明可夫斯基差中的一个点,但我们不希望每次都获得相同的点。

所以说如果我们让support函数依赖于某个方向,那么我们可以确保每次调用support函数时都不会得到相同的点。换句话说,我们开始的时候可以让support函数在某个方向上返回最远的点,之后我们可以选择其他方向,这样就不会得到重复的点了。

选择某个方向上的最远点很有用,因为它可以创建包含最大区域的单纯形,可以加快算法的快速结束。此外,我们知道用这种方式返回的所有点都位于明可夫斯基差的边上,因此如果我们不能沿着某个方向跨越原点后再添加一个点,那么明可夫斯基差就不可能包含原点。这可以让算法在两个图形不相交的情况下快速结束。以下是support函数的实现。

 
public Point support(Shape shape1, Shape shape2, Vector d) {
  // d is a vector direction (doesn't have to be normalized)
  // get points on the edge of the shapes in opposite directions

  Point p1 = shape1.getFarthestPointInDirection(d);
  Point p2 = shape2.getFarthestPointInDirection(d.negative());
  // perform the Minkowski Difference
  Point p3 = p1.subtract(p2);
  // p3 is now a point in Minkowski space on the edge of the Minkowski Difference
  return p3;
}

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

点赞

发表评论

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