与矩形以外的形状碰撞出现了问题..?

Question

我习惯于使用矩形进行碰撞检测，现在遇到了一些棘手的问题。我正在处理类似菱形的形状，并且在过去几个小时里一直在尝试如何检查碰撞。

我尝试检查第一个对象的四个点是否在第二个对象的点内，但这只会生成一个框（我想）

我感觉自己遇到困难的原因是角度问题。

- user513638

---

你可以检查一个形状中两个点之间的线是否与另一个形状中的两个点之间的线相交。你可以遍历形状中所有相邻节点。这将提供最准确的碰撞检测，除非形状相互围绕。 - bhavinp

@bhavinp 我明白了，我需要找出检查线碰撞的最佳方法。我猜我得使用某种斜率？ - user513638

@Robert Fratto 注意：我能想到的一种方法是使用两个点创建一条线，然后使用矩阵求解。如果您可以找到一个矩阵计算的API，那将会很有帮助。然后，如果矩阵有解（即存在交点），只需检查该交点是否在框内即可。 - bhavinp

对于所有线段对进行线-线交点测试既低效又不通用：如果一个多边形完全包含在另一个多边形中，则多边形相交而它们的任何线段都没有相交。 - Gareth Rees

在检查游戏中的某些事物时，我只需要检查对象的一侧碰撞。为了检查这个，我使用了第二条线上两点之间的斜率，并查看它是否与斜率相匹配。（我还使斜率仅在第二条线上的两个点之间） - user513638

Answer 1

您想要将一个移动的凸多边形（即您的“菱形”）与另一个移动的凸多边形进行碰撞，对吗？就像这样：

你的第一步应该是将问题转化为一个等价问题，其中一个多边形是静止的:

然后，您可以将移动的多边形转化为一个“轴”，覆盖移动多边形扫过的区域。这很容易做到：如果原始多边形有n个边，则轴有n+2个边，额外的两个边与移动向量具有相同的长度和方向。通过根据它们在运动向量正交的分量对顶点进行排序，并在极值处插入新边来找到插入这些新边的位置。

现在你已经将问题简化为静态多边形相对于静态多边形。查看realtimerendering.com提供的方便的碰撞算法表，并跟随参考文献，我们可以看到需要使用分离轴测试，例如David Eberly在这篇论文第3节中所描述的方法。

在二维空间中，如果我们能找到一条分离轴，即一条线使得一个多边形位于该线的一侧，而另一个多边形位于该线的另一侧，则两个凸多边形不相交：

如果我们有一个方向，就可以轻松地发现是否存在一个分离轴沿着该方向运行，通过将两个多边形投影到垂直于该方向的线上，并查看投影是否不相交：

我们如何知道分离轴的方向？如果存在任何分离轴，则其中一个与凸多边形的一侧平行（参见Eberly第3页）。因此只需要检查少量方向，如果您在没有找到分离轴的情况下检查了所有方向，则两个多边形相交（因此原始运动物体发生碰撞）。

有许多改进和优化可以进行，当然不限于以下内容：

1. 在执行完整的移动多边形/多边形测试之前，进行简单的测试，例如圆/圆，以便快速拒绝易处理的情况。
2. 使用某种空间分区方案，例如四叉树，以便仅测试足够接近可能发生碰撞的对象。
3. “缓存见证人”-如果一条线在时间t上将两个对象分开，则它很可能在时间t+δ继续将它们分开，因此记住您找到的分离轴并尝试下次首先使用它（请参阅Rabbitz，“Fast Collision Detection of Moving Convex Polyhedra”在图形宝石IV中）。

但不要过于担心优化：首先正确地完成，在信心中相信您将能够加速它。

- Gareth Rees