AABB 与圆 - 反之亦然，使用分离轴定理
我正在关注我的 2d 游戏碰撞处理教程，本教程解释了我最喜欢的游戏“N”中使用的碰撞。他们如何更有效地使用分离轴定理来解决 AABB 与 AABB 以及 AABB 与圆之间的碰撞。 http://www.metanetsoftware.com/technique/tutorialA.html。我了解 AABB 与 AABB 碰撞处理的实现，但我无法理解 AABB 与圆碰撞检测，尤其是 voronoi 区域。完全困惑如何/从哪里开始。
AABB 与 AABB 碰撞检测
- 通过查找每条边的法线来查找沿所有边的轴。
- 将所有顶点投影到 合成轴，最终结果应该 是一个标量值。
- 依次得到的标量值 用于查找是否发生碰撞 存在或不存在。
有人可以解释一下如何处理 AABB vc 圆的碰撞 - 反之亦然吗？
Am following this tutorial for my 2d game collision handling , this tutorial explains about the collision used in one of my favorite game "N". How they used separate axis theorem more efficiently for collision between AABB vs AABB and AABB vs Circle. http://www.metanetsoftware.com/technique/tutorialA.html. I understand the implementation of AABB vs AABB collision handling but I couldn't understand AABB vs Circle collision detection especially voronoi regions.Totally confused how/where to start.
AABB vs AABB collision detection
- Find the axis along all the edge by finding the normal of each edge.
- Projection all the vertices to the
resultant Axis , final result should
be a scalar value. - The resultant scalar value in turn
is used to find whether collision is
present or not.
Can someone please explain how to handle collision AABB vc Circle - vise versa?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
由于与圆的碰撞总是归结为与半径的比较（在您的情况下，通过投影），因此拥有最近的线段（多边形的边缘）和法线向量是您需要的唯一构建块。法向量很容易从线段的点计算出来（类似于unit(y2-y1, x1-x2) ...斜率的负倒数）。找出最接近的边缘是剩下的构建块。沃罗诺伊区域为我们提供了最后一个构建块。
您了解轴对齐边界框之间的碰撞。我想你也了解两个圆之间的碰撞。我假设你不了解 voronoi 区域。那么，从哪里开始呢？沃罗诺伊图。我强烈建议您找到一个图解说明。 这个链接非常好。然而，根据您迷失的程度，也许需要一些额外的背景知识（但说真的，没有任何解释可以打败视觉效果）：
voronoi 图是计算几何中无处不在的数据结构之一。任何计算几何书籍都会讨论 Voronoi 图。它回答了一个简单的问题：最近的邮局在哪里？给定平面上的一组点（邮局），泰森图将平面分为不同的区域，每个区域包含一个点。如果您位于某个特定地区，您知道哪个点（邮局）距离您最近。如果你是一个圆圈，这对于碰撞检测来说是很好的，原因很简单：最近的点是测试碰撞的最重要的点。
请注意，如果您想以数学方式导出 voronoi 图，您只需考虑所有点对并计算所有平分线即可。然后，您将所有平分线相交，并丢弃不重要的线段，因为其他一些点更接近感兴趣的点（这发生在每个相交处）。但这会导致算法效率极低。高效的实现涉及计算几何中另一个普遍存在的东西：线扫描算法。其详细信息可以在其他地方找到；重要的是它提供了一种在算法的任何阶段只考虑重要点的方法。
教程中的 voronoi 区域稍微复杂一些。我们不仅有点，还有线段。幸运的是，线扫描算法可以很好地处理这个问题。您主要需要担心线段的起点或终点。从概念上讲，一旦掌握了基本算法，就不会发生太大变化。同样，这对于圆的碰撞检测非常有帮助：给定 voronoi 区域，您就知道要测试碰撞的线段。
这还有帮助吗？感谢反馈。我很乐意澄清任何事情。在没有视觉效果的情况下解释 voronoi 图可能是一个坏主意。
Since collisions with a circle always come down to a comparison against the radius (in your case, via projection), having the closest line segment (edge of the polygon) and the normal vector are the only building blocks you need. The normal vector is easily computed from the points of the line segment (something like unit(y2-y1, x1-x2) ... the negative reciprocal of the slope). Figuring out which edge is closest is the building block that remains. Voronoi regions give us the last building block.
You understand collisions between axis-aligned bounding boxes. I assume you also understand collisions between two circles. I'm assuming you don't understand voronoi regions. So, where to start? Voronoi diagrams. I highly suggest that you find a diagrammed explanation. This link is quite good. However, depending on how lost you are, perhaps a little additional background (seriously, though, no explanation can beat the visual):
A voronoi diagram is one of the ubiquitous data structures of computational geometry. Any computational geometry book will discuss the Voronoi diagram. It answers a simple question: where is the closest post office? Given a set of points in a plane (post offices), a voronoi diagram separates the plane into different regions, each containing one of the points. If you are in a particular region, you know which point (post office) is closest to you. If you were a circle, this would be nice for collision detection for a simple reason: the closest point is the most important one to test for collisions.
Note that if you want to mathematically derive a voronoi diagram, you simply consider all point pairs and calculate all bisecting lines. Then you intersect all of the bisecting lines and throw away the segments that are unimportant because some other point is closer to the point of interest (which happens at every intersection). This leads to a terribly inefficient algorithm, though. The efficient implementation involves another ubiquitous thing in computational geometry: the line-sweep algorithm. Its details can be found elsewhere; the important bit is that it provides a method of considering only the important points at any stage of the algorithm.
The voronoi regions in your tutorial are a little more complex. Instead of just points, we have line segments. Fortunately, the line-sweep algorithm handles this nicely. You mostly have to worry about the start or end of the line segments. Conceptually, not much changes once you have the basic algorithm down. Again, this is exceptionally helpful for collision detection with a circle: given the voronoi region, you know which line segment to test collisions against.
Does that even help? Feedback appreciated. I'll be happy to clarify anything. Explaining voronoi diagrams without visuals is probably a bad idea.