5

OBB 具有位置（x，y）、速度（x，y）和方向（矩阵）。鉴于定期更新，OBB 必须相互碰撞，返回被认为成功的移动部分。

我查看了 GPWiki 上的多边形测试 - http://gpwiki.org/index.php/Polygon_Collision - 但它没有考虑移动对象或完全在 OBB 内的对象。

Real Time Collision Detection 一书在第 4 章：包围体中介绍了 3D OBB，但在 3 维中进行测试的方法明显比在 2D 中更复杂。

4

5 回答 5

4

为了测试 2 个定向边界框之间的碰撞检测，我将使用分离轴定理 ( SAT )。事实上，SAT 可用于任意 2 个凸形之间的碰撞检测。这种技术理解起来并不太复杂，并且具有合理的性能。该定理可以很容易地扩展到 3D。

编辑：

该算法试图确定是否可以在两个对象之间拟合一个平面。如果存在这样的平面，则对象是分离的，并且不能相交。

要确定对象是否分离，只需将对象投影到平面的法线上，然后比较间隔并查看它们是否重叠。

因此，显然有无数个平面可以容纳在两个分离的物体之间。但事实证明，您只需测试少数几架飞机。

可以看出，对于盒子来说，要测试的分离平面是法线等于两个盒子轴线的平面。所以对于 2 个盒子，你总共只需要测试 4 个分离平面。在这 4 个平面中，一旦你找到了一个分隔盒子的分离平面，那么你就知道盒子不能相交，并且你返回一个无碰撞标志。

如果这4个平面不能分开盒子，那么盒子一定是相交的，你就会发生碰撞。

于 2009-04-19T03:27:22.927 回答
2

另一个建议（包括遏制，我认为更便宜）：

检查 #1 的 4 个顶点是否在 #2 内，然后检查 #2 的 4 个顶点是否在 #1 内。我建议这样做：

假设您要检查的#1 的顶点是 v，而#2 的 4 个顶点是 v1 ... v4。按 #2 的方向反向旋转所有 5 个顶点。（要通过方向矩阵 M 对向量 u 进行反向旋转，将 u 乘以 M 转置：M^T u ，假设在您的约定中，方向通过左乘法起作用。）生成的第二个框，称为 #2'，现在是轴对齐的 - 您可以立即检查 v' 是否包含在其中。

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

一些优化立即浮现在脑海中（也许您可以在每个框中存储未旋转的顶点副本？如果大小是固定的，也许您可​​以比较它们以立即消除其中一个可能的包含，并保存 3 个潜在的测试？）但除非你将它应用在数以万计的盒子对上，这个测试应该足够便宜。

关于运动，您可以随心所欲地深入 - 查找“连续碰撞”，然后自己看看。（我特别记得 Stephane Redon 的一些好作品）。我全心全意地相信，没有任何游戏能做到这些花哨的东西：如果你确实移动得非常快，你可以细分你的时间步，并对每个位置/方向子迭代执行碰撞检查。

（编辑：）这里有另一个讨论，有很好的参考资料。

于 2009-04-19T03:46:31.693 回答
1

如果您有两个具有任意方向的边界框（即矩形）（我认为这意味着一些“旋转”），那么我将执行以下操作：

  • 从初始位置开始（我假设边界框不相交），根据每个框的速度向前平移每个框（但是随着时间的推移您正在应用运动）。
  • 找到每个平移边界框的角坐标。这 4 个坐标定义了构成边界框边缘的 4 条线段的端点。
  • 对于边界框 #1，测试其每个线段与边界框 #2 的 4 个线段之间的交点。例如，您可以使用标准方程来计算两条线的交点，如此处所述。
  • 如果存在交叉点，请使用交叉点的坐标和您应用的已知平移来计算成功移动的分数。
  • 对每个更新重复上述步骤。

编辑：粗略的伪代码（包含评论中讨论的内容）如下所示：

...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...
    }
}
于 2009-04-19T02:47:33.147 回答
0

您可能应该实现四叉树（参见wikipedia）来跟踪平面上的所有对象。不幸的是，我从未实现过碰撞检测，但似乎其他人已经能够使用四叉树创建与您类似的场景。

于 2009-04-19T08:00:26.763 回答
-1

你说 2d，但也提到 3d 更复杂。对于碰撞检测，您基本上想测试两个形状是否相互交叉。在 2D 中，带有边界框，这些是矩形。您需要使用一种算法来查看矩形是否相交，并检查一个矩形是否完全包含在另一个矩形中（简单算法的 3 次测试）。对于 3d，这些是立方体。一样。查看这个对象-对象交叉矩阵并找到你想要的。检查对象本身的交集，并且枯萎的一个完全包含在另一个中。

此过程不仅可以扩展到边界框，还可以扩展到边界球体或凸边界壳、多边形或完整 3d 对象中的实际对象本身。最终结果是，随着物体在空间和时间中前进，它们的表面是否发生碰撞或它们是否在彼此内部。如果您的粒度太粗，并且在您建模的情况下，它们应该发生碰撞，但它们最终会相互移动，您应该进行额外的光线边界相交测试，以查看是否有某个中心加权点在对象与另一个对象的边界相交。

于 2009-04-19T02:01:21.870 回答