A fast 3D collision detection algorithm
10 months ago
- #collision detection
- #computational geometry
- #optimization
- 文章讨论了针对凸多面体碰撞检测的分离轴测试(SAT)算法的改进方法。
- 提出通过叠加高斯图来寻找闵可夫斯基差的面，从而减少对完整支撑函数计算的依赖。
- 作者将寻找分离重叠凸集的最小平移量问题构建为一个非凸二次约束二次规划(QCQP)优化问题。
- 对于凸多面体，支撑函数的特性允许高效遍历顶点区域来找到全局最小值，而无需重新计算支撑点。
- 优化后的SAT测试涉及在球面上遍历弧线、跟踪支撑点，并在区域变化时更新它们，显著加快了碰撞检测速度。
- 提供的演示表明，对于多面体模型，该方法比传统SAT快5-10倍，但在三角形处理方面仍存在一些数值问题。
- 该方法被表述为球面上的优化问题，利用图遍历和支撑函数特性来提高计算效率。