使用多边形碰撞检测

Question

我想知道是否有人可以给我一个关于如何首先实现一个类来定义多边形的想法，以及如何检测使用这个类的两个多边形之间的碰撞。我在Android上的Java工作是更具体的，但我也可以使用NDK的C/C++。我想要定义我的多边形，我只需要一个顶点数组吧？

当我做碰撞检测时，我已经阅读了有关分离轴定理和GJK算法的内容。这是正确的路要走，还是我让这个过于复杂？只是试图开始正确的方向。谢谢！

Answer 1

你听起来像是你对这种事情相当陌生，这也许是你意识到的一个更大的问题。

我认为你最好先定义你想要解决的问题，然后找到一个解决方案来解决这个问题。

让我问你一些问题预选赛：

你说的是2D还是3D？

这是用于物理系统吗？

你需要知道它们相交的地方吗？或者只是它们相交？

你需要做的形状布尔操作（如获得交集或联合或东西）？

Answer 2

这取决于多边形的类型。

如果你的多边形是凸的，那么一个有序的顶点列表将描述一个，而分离轴和GJK都将是可应用的算法。

如果你的多边形是凹的但是简单的（即，边从不相交），那么有序的顶点列表仍然足够，但是分离轴或GJK都不适合。

如果你的多边形是复杂的（即边可能相交），那么你需要顶点列表和填充规则。该规则确定哪些部分的飞机被认为是在多边形内部，哪些在外部。

例如，假设像五角星的多边形：

在填充规则的区别在于在中间的五边孔是多边形的部分或简单的孔的差。

所有更复杂的多边形类型都可以分解为多种简单多边形的多个实例，因此只需在地面放置一面旗帜并声明您只对凸多边形感兴趣就可以了 - 这就是例如，GPU正是如此。

假设您将碰撞定义为两个多边形是否重叠，分离轴定理非常简单，而且绝对是一种可行的方法。如果你打算制作一个包含很多多边形的场景，那么你可能还需要一个宽泛的阶段，这是一个快速的方法来标记一堆多边形，因为在做昂贵的测试之前，它们绝对不会重叠，以找出哪个多边形其余的仍然是。

一个明显的例子是bin排序 - 假设你将屏幕划分为16个像素的垂直条，然后对每个多边形进行分类（i）确定它接触的是哪个bin; （ii）针对已经在这些箱中的所有多边形进行测试; （iii）将其添加到垃圾箱。这可能意味着你甚至从来没有考虑过很多时候应用这个测试。这个具体的方案有一些明显的问题，取决于你的场景，但存在更智能的算法。