collision-detection - 三角形到三角形的 3D 碰撞检测

Question

我了解 2 个三角形之间的三角形到三角形碰撞检测。
有人可以解释我如何将它与由 1000 个顶点组成的 3D 对象一起使用吗？
如何为每个网格创建三角形列表？
我是否必须采用顶点的每个排列？
这将导致 O(n^3)，我觉得这很糟糕。

我该如何概括这一点？

我将需要从格式中读取数据。如果所有其他方法都失败了，有人可以建议一种从三角形制作网格的格式吗？我还需要一个格式的网格目录，至少对于初学者来说。

非常感谢。

Answer 1

您可以应用许多优化来检测网格之间的碰撞:

空间分区，如 James 所述。

使用 bounding volumes 提前拒绝.例如，球体碰撞很便宜，所以在测试网格 A 和 B 是否碰撞之前，您可能会看到围绕 A 的球体是否与围绕 B 的球体发生碰撞。如果球体未命中，显然网格无法碰撞，所以没有需要测试它们。不同类型的对象可能需要不同类型的边界体积:轴对齐的长方体和圆柱体很常见。

缓存证人。在某些碰撞测试中，您最终会计算碰撞的“见证人”，例如当您应用 separating axis test 时你计算一个分离轴。如果一个轴在时间 t 将两个对象分开，它很可能会在时间 t + δ 继续将它们分开，因此可以缓存您找到的轴并在下次第一次尝试(参见 Rabbitz，“快速碰撞检测移动凸多面体”在图形 gem IV)。