与矩形以外的形状发生碰撞。 [英] Collision with shapes other than rectangles..?

问题描述

我已经习惯于仅使用矩形进行碰撞检测，所以我现在有些困惑。我正在处理类似钻石的形状，在过去的几个小时中，我一直在努力寻找如何检查碰撞的方法。

我尝试检查第一个对象的四个点是否在第二个对象的点之内，但这只是一个盒子（我认为）

之所以感到困难，是因为角度。

解决方案

您正试图将一个移动的凸多边形（您的钻石）与另一个移动的凸多边形碰撞，对吗？ ？像这样的东西：

p>

您的第一步应该是将问题转换为其中一个多边形固定的等价问题：

然后，您可以将移动的多边形转换为一个轴，该轴覆盖移动的多边形所扫过的区域。这很容易做到：如果原始多边形具有 n 个边，则轴具有 n + 2个边，另外两个边的长度和方向与运动矢量。通过根据与运动矢量正交的分量对顶点进行排序，然后在最大值处插入新边，可以找到在哪里插入这些新边。

现在，您已经减少了静态多边形对静态多边形的问题。看一下方便的，第3页）。因此，只有一小部分方向需要检查，如果您在未找到分隔轴的情况下检查了所有方向，则两个多边形相交（因此原始移动对象发生碰撞）。

您可以进行很多改进和优化，当然不限于这些：

1. 在进行完整移动的多边形之前/ polygon测试，进行诸如circle / circle之类的更简单的测试，以便您可以快速拒绝简单的情况。


2. 使用诸如四叉树之类的空间分区方案，以便仅测试附近的对象


3. 缓存见证 –如果一行在时间 t 处将两个对象分开，则很可能在时间 t +δ，因此记住您找到的分离轴并在下次再次尝试时可以花点时间（请参见Rabbitz， 快速碰撞 Graphics Gems IV 中检测运动凸多面体。

但不要过度担心优化：首先将其正确设置，以确保以后可以加快它的速度。

I'm so used to working just with rectangles for collision detection that I'm a bit stumped right now. I'm working with diamond-like shapes, and for the past few hours, have been trying to figure out how to check for collision.

I tried checking to see if the first objects four points are inside the points of the second object, but that just makes a box (I think)

The reason why I feel like I'm having difficulty with this is because of the angles.

解决方案

You're trying to collide a moving convex polygon (your "diamond") with another moving convex polygon, is that right? Something like this:

Your first step should be to transform the problem to an equivalent one in which one of the polygons is stationary:

Then you can transform the moving polygon into a "shaft" that covers the area swept by the moving polygon. This is straightforward to do: if the original polygon has n sides, then the shaft has n + 2 sides, with the extra two sides being the same length and direction as the movement vector. You find where to insert these new sides by sorting the vertices according to their component that's orthogonal to the movement vector, and inserting new sides at the maxima.

Now you've reduced the problem to static polygon against static polygon. Taking a look at the handy table of collision algorithms courtesy of realtimerendering.com, and following the references, we can see that we need to use the separating axis test, for example as described in section 3 of this paper by David Eberly.

In two dimensions, two convex polygons fail to intersect if we can find a separating axis, a line such that one polygon falls on one side of the line, and the other polygon on the other:

If we are given a direction, we can easily discover if there exists a separating axis that runs in that direction, by projecting the two polygons onto a line running perpendicular to that direction, and looking to see whether the projections are disjoint:

How do we know which direction the separating axis will run in? Well, if any separating axis exists, then there's one that runs parallel to one of the sides of one of the convex polygons (see Eberly, page 3). So there's only a small set of directions to check, and if you've checked them all without finding a separating axis, then the two polygons intersect (and hence the original moving objects collide).

There are lots of refinements and optimizations you can make, certainly not limited to these:

1. Before doing the full moving polygon/polygon test, do a simpler test like circle/circle so that you can reject easy cases quickly.
2. Use some kind of spatial partitioning scheme like quadtrees so that you only test objects that are close enough that they might collide.
3. "Caching witnesses" — if a line separates two objects at time t, it's likely that it continues to separate them at time t + δ, so it can pay to remember the separating axis you found and try it first next time (see Rabbitz, "Fast Collision Detection of Moving Convex Polyhedra" in Graphics Gems IV).

But don't worry too much about optimizing: get it right first in the confidence that you'll be able to speed it up later.

这篇关于与矩形以外的形状发生碰撞。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！