collision-detection - 与矩形以外的形状碰撞..？

Question

我已经习惯于使用矩形进行碰撞检测，现在我有点难住了。我正在处理类似菱形的形状，在过去的几个小时里，我一直在试图找出如何检查碰撞。

我尝试检查第一个对象的四个点是否在第二个对象的点内，但这只是一个框(我认为)

我觉得我有困难的原因是因为角度。

Answer 1

您正试图将一个移动的凸多边形(您的“菱形”)与另一个移动的凸多边形碰撞，对吗？像这样的东西:



您的第一步应该是将问题转换为其中一个多边形静止的等效问题:



然后，您可以将移动多边形转换为覆盖移动多边形扫过的区域的“轴”。这很简单:如果原始多边形有 n 条边，那么轴有 n + 2 条边，额外的两条边与运动向量的长度和方向相同。通过根据顶点与运动向量正交的分量对顶点进行排序，并在最大值处插入新边，您可以找到插入这些新边的位置。



现在您已将问题简化为静态多边形对静态多边形。看看方便的table of collision algorithms由 realtimerendering.com 提供，按照引用资料，我们可以看到我们需要使用 分离轴测试 ，例如如 this paper 的第 3 节所述大卫·埃伯利。

在二维中，如果我们能找到，两个凸多边形就不能相交。分离轴 , 一条线，使得一个多边形落在线的一侧，另一个多边形落在另一侧:



如果给定一个方向，我们可以通过将两个多边形投影到垂直于该方向的线上，并查看投影是否不相交，很容易发现是否存在沿该方向运行的分离轴:



我们如何知道分离轴将在哪个方向运行？好吧，如果存在任何分离轴，那么就会有一个与凸多边形之一的边之一平行的轴(参见 Eberly，第 3 页)。所以只有一小部分方向需要检查，如果你在没有找到分离轴的情况下检查了所有方向，那么两个多边形相交(因此原始移动物体发生碰撞)。

您可以进行许多改进和优化，当然不仅限于这些:

在进行完整的移动多边形/多边形测试之前，先做一个更简单的测试，如圆/圆，以便您可以快速拒绝简单的案例。

使用某种空间分区方案，如四叉树，以便您仅测试足够接近它们可能会发生碰撞的对象。

“缓存见证”——如果一条线在时间 t 将两个对象分开，它很可能会在时间 t + δ 继续将它们分开，所以记住你找到的分离轴并下次先尝试是值得的(参见 Rabbitz， “Fast Collision Detection of Moving Convex Polyhedra ”在图形 gem IV 中)。

但是不要太担心优化:首先做对，相信以后可以加快速度。