我正在关注我的 2d 游戏碰撞处理教程，本教程解释了我最喜欢的游戏“N”中使用的碰撞。他们如何更有效地使用分离轴定理来解决 AABB 与 AABB 以及 AABB 与圆之间的碰撞。 http://www.metanetsoftware.com/technique/tutorialA.html 。我了解 AABB 与 AABB 碰撞处理的实现，但我无法理解 AABB 与圆碰撞检测，尤其是 voronoi 区域。完全困惑如何/从哪里开始。
AABB 与 AABB 碰撞检测
- 通过查找每条边的法线来查找沿所有边的轴。
- 将所有顶点投影到 合成轴，最终结果应该 是一个标量值。
- 依次得到的标量值 用于查找是否发生碰撞 存在或不存在。
有人可以解释一下如何处理 AABB vc Circle 的碰撞 - 反之亦然吗？
最佳答案
由于与圆的碰撞总是归结为与半径的比较(在您的情况下，通过投影)，因此具有最近的线段(多边形的边缘)和法线向量是您需要的唯一构建 block 。法向量很容易从线段的点计算出来(类似于unit(y2-y1, x1-x2) ...斜率的负倒数)。找出最接近的边缘是剩下的构建 block 。沃罗诺伊区域为我们提供了最后一个构建 block 。
您了解轴对齐边界框之间的碰撞。我想你也了解两个圆之间的碰撞。我假设你不了解 voronoi 区域。那么，从哪里开始呢？沃罗诺伊图。我强烈建议您找到一个图解说明。 This link is quite good 。然而，根据你迷失的程度，也许还有一点额外的背景(但说真的，没有任何解释可以打败视觉效果):
泰森图是计算几何中普遍存在的数据结构之一。任何计算几何书籍都会讨论 Voronoi 图。它回答了一个简单的问题:最近的邮局在哪里？给定平面上的一组点(邮局)，泰森图将平面分为不同的区域，每个区域包含一个点。如果您位于某个特定地区，您知道哪个点(邮局)距离您最近。如果你是一个圆圈，这对于碰撞检测来说是很好的，原因很简单:最近的点是测试碰撞的最重要的点。
请注意，如果您想以数学方式导出 voronoi 图，您只需考虑所有点对并计算所有平分线即可。然后，您将所有平分线相交，并丢弃不重要的线段，因为其他一些点更接近感兴趣的点(这发生在每个相交处)。但这会导致算法效率极低。高效的实现涉及计算几何中另一个普遍存在的东西:线扫描算法。其详细信息可以在其他地方找到；重要的是它提供了一种在算法的任何阶段只考虑重要点的方法。
教程中的 voronoi 区域稍微复杂一些。我们不仅有点，还有线段。幸运的是，线扫描算法可以很好地处理这个问题。您主要需要担心线段的起点或终点。从概念上讲，一旦掌握了基本算法，就不会发生太大变化。同样，这对于圆的碰撞检测非常有帮助:给定 voronoi 区域，您就知道要测试碰撞的线段。
这还有帮助吗？感谢反馈。我很乐意澄清任何事情。在没有视觉效果的情况下解释 voronoi 图可能是一个坏主意。
关于math - AABB 与圆 - 反之亦然，使用分离轴定理，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6154120/