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

Question

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

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

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

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

Answer 1

由分离轴定理求解:

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

与原方案相比:

• 理论复杂度从 O(N log N) 降至 O(N)，其中 N = |C| = |一个| * |B|
• 就地工作——没有内存分配