两个凸多面体的 3D 连续碰撞检测

Question

对于碰撞检查，如果其中一个沿直线移动，我需要计算两个凸多面体相交的时间。目前，我有：

1. 输入：凸多面体定义为一个对象的一组点A及其运动方向。
2. 输入：定义为第二个对象的一组点的凸多面体B
3. 计算两组点的Minkowski和C,|C| = |A| * |B|
4. 计算 C 的三角凸包（使用 QuickHull）
5. 与凸包的三角形相交并存储沿线的最小和最大距离。

这一切都有效，但速度很慢。特别是计算三角凸包的步骤。

我想知道是否有更快的方法来计算点集的射线-凸多面体交点而不计算三角凸包。如果有帮助，我可以将输入作为平面（平面方程）得到。

Answer 1

分离轴定理求解：

1. 输入：作为点和平面方程的凸碰撞体积
2. 对于两个碰撞体中的每个平面，计算shift当每个平面成为分离平面时的运动方向（另一个碰撞体的顶点都在该平面的前面）。
3. 在没有分离面的情况下计算shift的间隔。这可以通过跟踪遇到的最小值和最大值来就地完成。

与原方案相比：

• 理论复杂度从 O(N log N) 下降到 O(N)，其中 N = |C| = |A| * |B|
• 就地工作 - 没有内存分配