algorithm - 简单的3d空间碰撞检查算法

Question

我有一个连续的 3d 空间，由 4 个平行线相交的平面(无限长的矩形)的内部空间定义 - 让我们称之为“A”。然后在模型中我还有一堆封闭的凸 3d 形状，它们可能重叠也可能不重叠到空间“A”中 - 让我们称这些中的每一个为“B”。我正在寻找的是一个计算效率尽可能高的算法过程来破译是否有任何“B”形状与“A”重叠。

*每个“B”形状都由其顶点、边和带有平面等的面以及它们之间的链接定义。

*如果其中一些没有意义，我可以做一些涂鸦......

到目前为止，我检查每个“B”形状与“A”形状的过程如下:

1. 检查 b 的任何点是否在 A 的所有 4 个平面内 - 如果是 => 重叠(如果它们都落在同一个外部空间 => 没有重叠)

2. 检查 a 的任何平行线是否与 b 的任何面相交 - 如果相交 => 重叠。

3. 检查 b 的任何边是否与 A 的 4 个面中的任何一个相交 - 如果是 => 重叠。

我还想我可以为每个“B”形状创建一个具有中心点和半径的近似边界圆，以首先检查以快速消除远处的“B”形状...

** 对于第 2 部分和第 3 部分，我使用了一个函数来检查边是否与 3d 对象相交。这是通过将 2 个点与构成对象的每个平面进行比较来查看它们是否是相对的边，然后如果是，则找到平面交点并检查该交点是否在 3d 对象内部。

这似乎可行，但我想看看是否有更好或更快的方法来解决同样的问题？也许我错过了一些明显的东西......

谢谢

Answer 1

请注意，对于无限矩形“管”，您可以将问题简化为二维情况:只需将所有点和边投影到平面上，垂直于管。

现在您必须寻找多段线(多边形)与矩形的交点(如果您使用管母线上的点作为基点和向量，则轴对齐)——这个任务绝对更简单。

如果你的形状是凸的，多边形也是凸的，SAT 方法(分离轴定理)非常好(当然这对于形状之间的链接不是真的，它们应该分开处理)。