如何测试两个移动的2D定向边界框之间的碰撞？

Question

如何测试两个移动的2D定向边界框之间的碰撞？

5

OBBs具有位置(x,y)、速度(x,y)和方向(矩阵)。给定周期性更新，OBBs必须相互碰撞，并返回被视为成功的移动部分的比例。我查看了GPWiki上的多边形测试-http://gpwiki.org/index.php/Polygon_Collision-但它没有考虑到移动物体或完全在OBB内的物体。书籍《实时碰撞检测》第4章涵盖了3D OBBs:包围体积，但在3维中进行测试的方法明显比2D更复杂。

- Michael Labbé

你可以尝试这个：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.9172 源代码可根据请求提供。 - Daniel Rikowski

5个回答

2

另一个建议（涵盖包含，我认为更便宜）：

检查#1的4个顶点是否在#2中，然后检查#2的4个顶点是否在#1中。以下是我的建议：

假设您正在检查的#1顶点是v，#2的4个顶点是v1 ... v4。通过#2的方向逆旋转五个顶点（称为#2'），使第二个盒子轴对齐 - 您可以立即检查v'是否包含在其中。

如果您发现任何#1顶点在#2内 - 停止，您有交集。否则继续。

有一些优化立即浮现在脑海中（也许您可以在每个盒子中存储未旋转的顶点副本？如果大小固定，也许您可以将它们与立即消除其中一种可能的容纳，从而节省3个潜在测试？），但是除非您将其应用于数以亿计的箱对，否则此测试应该足够便宜。

关于运动，您可以深入探讨 - 查找“连续碰撞”，并自行查看。（我特别记得Stephane Redon的一些不错的作品）。我由衷地相信，没有任何游戏做出这些花哨的东西：如果您确实移动得非常快，可以将时间步长细分，并在每个位置/方向子迭代上执行碰撞检查。

（编辑：）这里还有另一个讨论链接，提供了很好的参考。

- Ofek Shilon

+1 为这次编辑加分。我一开始想给你的回答打-1，但我觉得你的编辑挽救了情况 :）。我猜应该有人会把这个问题关闭为重复。 - Erich Mirabal

我仍然支持我的建议。为什么是-1？ - Ofek Shilon

只是为了明确，我没有给你的回答投反对票。虽然我理解你的意思，但是那个答案很难理解（即使我读了几遍之后有点明白了），它没有解释或链接如何反转旋转顶点。另外，你是不是指“如果任何4个顶点”而不是3个？ - Erich Mirabal

1

如果您有两个带有任意方向（即某种“旋转”）的边界框（即矩形），那么我会执行以下操作：

从初始位置开始（在这里我假设边界框不相交），根据其速度将每个框向前移动（无论您如何应用随时间变化的运动）。
找到每个已翻译边界框的角落坐标。这4个坐标定义了组成边界框边缘的4条线段的端点。
对于边界框＃1，请测试其每个线段与边界框＃2的4个线段之间的交点。例如，您可以使用计算两条线的交点的标准方程，如here所讨论的那样。
如果存在交点，请使用交点的坐标和已知的平移量来确定成功移动的分数。
重复上述步骤以进行每次更新。

编辑：一个粗略的伪代码（结合了评论中讨论的内容）如下：

...test for intersections between the OBB edges...
if any intersections are found{
    ...run code for when OBBs are partially overlapping...
}else{
    P = line segment whose endpoints are the OBB centers;
    ...test for intersections between P and OBB edges...
    if P intersects edges of both OBBs{
        ...run code for when OBBs are not touching...
    }else{
        ...run code for when one OBB is completely inside the other...
    }
}

- gnovice

我认为这并不能涵盖一个OBB完全在另一个OBB内部的情况，因为线段不会相交，但是OBB会相交。 - Erich Mirabal

是的，这将是一个特殊情况，您需要进行额外的测试。但是，如果OBB以足够小的增量移动，交集很可能会先发生，而不是一个OBB进入另一个OBB。 - gnovice

1

我知道这可能不适用于他的用例，但如果初始条件是一个已经在另一个里面呢？我认为他可以从中心点到中心点画一条直线。如果该线只与一个OBB的线相交，则一个OBB在另一个OBB内部。这将在运行测试以排除部分重叠之后完成。有没有比那更简单的检查方法？ - Erich Mirabal

（顺便说一句，我忽略了其中一个OBB比增量移动小的情况，因为您已经提到了“足够小的增量”，这应该考虑到OBB的大小。） - Erich Mirabal

我需要再仔细检查一下，但我相信测试一个OBB是否在另一个OBB内的一种方法是创建一个从中心点到中心点的向量，并测试它是否a) 与仅一个OBB的边线相交或b) 不与任何OBB的边线相交并且总长度小于OBB对角线长度的一半。 - gnovice

0

你可能需要实现一个四叉树（参见wikipedia），以跟踪平面上的所有对象。不幸的是，我从未为碰撞检测实现过四叉树，但似乎其他人们已经能够使用四叉树创建类似于你的场景。

- Darwyn

-1

你说2D，但也提到3D更复杂。对于碰撞检测，你基本上想要测试两个形状是否相交。在2D中，使用边界框，这些是矩形。您需要使用算法查看矩形是否相交，并检查一个是否完全包含在另一个内（简单算法需要3个测试）。对于3D，这些是立方体。同样的事情。查看此矩阵对象-对象相交并找到您想要的相交点。检查对象本身的相交以及其中一个是否完全包含在另一个内。

这个过程不仅可以应用于边界框，还可以应用于边界球或凸包、多边形或完整的3D对象。最终结果是，随着物体在空间和时间中的运动，它们的表面是否碰撞或者它们是否相互包含。如果你的粒度太粗，在你模拟的情况下它们应该碰撞，但它们最终却擦肩而过，那么你应该进行额外的射线边界相交测试，以查看一个物体中心加权点是否与其他物体的边界相交。

- John Ellinwood

1

问题特别涉及可以旋转的定向边界框，而不是轴对齐框。 - Michael Labbé

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mez · Accepted Answer

为了测试两个有向边界框之间的碰撞检测，我会使用分离轴定理(SAT)。实际上，SAT可用于任何两个凸形状之间的碰撞检测。这种技术并不过于复杂，性能也相当不错。该定理可以轻松扩展到3D。

编辑：该算法试图确定是否可能在两个对象之间适合一个平面。如果存在这样的平面，那么物体是分离的，不能相交。确定物体是否分离只是简单地将物体投影到平面的normal上，并比较区间以查看它们是否重叠。因此，显然可以适合两个分离对象之间的无限平面。但是已经证明只需要测试少数平面即可。

对于盒子，可以证明需要测试的分离平面是法线等于两个盒子轴的平面。因此对于2个盒子，您只需要总共测试4个分离平面。在这4个平面中，一旦找到一个分离平面将盒子分开，那么您就知道盒子不会相交，并返回无碰撞标志。

如果这4个平面无法分离盒子，则盒子必须相交，这时您就有了一个碰撞。