Speeding up the separating axis test using inscribed spheres
2 days ago
- 分离轴测试（SAT）在计算凸包之间的接触流形时非常稳健，即使形状重叠也能很好地工作，这与GJK不同。
- SAT可能在计算上很昂贵（顶点数为O(N^3)），但通过高斯映射、SIMD、缓存和接触回收等优化措施可以缓解这一问题。
- 使用内切球可以为任何候选轴提供分离的上界，从而允许早期剔除不有前景的面和边。
- 对于面，如果界 n·d - r（d是球心之间的向量，r是半径之和）小于当前最大分离距离，则跳过面测试，用一次点积代替N次点积。
- 对于边，使用高斯映射弧的界确定了边是否能超过最佳面分离，从而剔除许多边-边对测试。
- 基准测试显示速度显著提升：最多98%的边对被剔除，碰撞阶段时间减少62%，在Convex Pile基准测试中总时间减少51%。
- 这种技术使SAT能够与GJK竞争，而不牺牲全局最优性或需要回退，并且实现起来很简单。