从SAT到GJK：3D物理引擎碰撞检测算法演进与选型指南
在机器人仿真、3D游戏和VR应用中，物理引擎的碰撞检测模块往往决定着整个系统的真实感和性能表现。当两个虚拟物体在三维空间中交错时，如何快速准确地判断它们是否发生碰撞？这个问题看似简单，却困扰着无数开发者。从早期的分离轴定理(SAT)到如今主流的Gilbert-Johnson-Keerthi(GJK)算法，碰撞检测技术已经走过了一段令人惊叹的演进历程。
1. 碰撞检测算法的历史转折点
1.1 SAT算法的黄金时代
分离轴定理(SAT)曾长期统治着碰撞检测领域，其核心思想简单而优雅：如果存在一条直线（在3D中是平面），能够将两个凸体投影到该直线上时投影不重叠，则两个物体必定不相交。这种基于投影的检测方式特别适合处理轴对齐包围盒(AABB)和定向包围盒(OBB)这类规则几何体。
SAT在简单形状上的性能表现令人印象深刻：
- 对AABB的检测仅需6次投影测试
- 对OBB的检测需要15次投影测试
- 计算复杂度为O(n)，n为可能的分离轴数量
然而，随着3D场景复杂度的提升，SAT开始暴露出明显局限。当处理非规则凸体或需要精确碰撞响应时，SAT需要为每种特殊形状定制分离轴检测逻辑，导致代码维护成本剧增。更关键的是，SAT难以优雅地处理曲面物体，这成为推动算法革新的重要动因。
1.2 GJK算法的范式革命
1988年，Gilbert、Johnson和Keerthi提出的GJK算法带来了全新思路。它通过明可夫斯基差(Minkowski Difference)将碰撞检测转化为原点包含问题，配合support函数和单纯形(Simplex)迭代，实现了对任意凸体的统一处理。
GJK的革命性突破体现在三个层面：
- 形状无关性：只需实现support函数，即可支持所有凸体形状
- 迭代高效性：通常4-8次迭代即可得出结论
- 扩展灵活性：与EPA算法配合可获得穿透深度信息
# GJK算法核心伪代码示例 def GJK_collision(shapeA, shapeB): d = initial_direction() # 初始搜索方向 simplex = [support(shapeA, shapeB, d)] # 初始单纯形 d = -d # 反向搜索 while True: new_point = support(shapeA, shapeB, d) if dot(new_point, d) <= 0: return False # 无碰撞 simplex.append(new_point) if contains_origin(simplex, d): return True # 检测到碰撞 d = update_direction(simplex)2. 现代物理引擎中的算法实现
2.1 Bullet Physics的混合策略
Bullet作为开源物理引擎的代表，采用了分层次的碰撞检测架构：
| 检测阶段 | 使用算法 | 优化目标 |
|---|---|---|
| 宽相位(Broadphase) | AABB树/动态AABB树 | 快速剔除不相交物体 |
| 窄相位(Narrowphase) | GJK+EPA/SAT混合 | 精确碰撞判断 |
| 持续碰撞检测(CCD) | 保守前进(Conservative Advancement) | 防止高速物体穿透 |
在窄相位处理中，Bullet会根据物体形状智能选择算法：
- 简单凸体：优先使用SAT（如Box-Box检测）
- 复杂凸体：切换至GJK+EPA组合
- 凹体分解：将凹体分解为凸体后再应用上述算法
2.2 NVIDIA PhysX的硬件优化
PhysX充分利用GPU并行计算优势，对GJK进行了多项创新优化：
- 批处理执行：将多个GJK检测任务打包提交GPU
- Warm Start：利用上一帧的simplex作为初始猜测
- SIMD加速：使用SSE/AVX指令并行计算support函数
这些优化使得PhysX在复杂场景下仍能保持实时性能。测试数据显示，在RTX 3080上，PhysX可同时处理超过10万个GJK检测请求，帧率维持在120FPS以上。
3. 工程选型的关键考量
3.1 形状复杂度与算法选择
不同形状组合下的算法效率对比：
| 形状A | 形状B | 推荐算法 | 平均迭代次数 |
|---|---|---|---|
| AABB | AABB | SAT | 6 |
| OBB | OBB | SAT | 15 |
| 球体 | 球体 | 直接距离 | 1 |
| 凸包 | 凸包 | GJK | 4-8 |
| 凹体 | 凹体 | 凸分解+GJK | 可变 |
3.2 实时性要求与精度权衡
在VR等对延迟敏感的场景中，可采用两阶段检测策略：
- 快速预判：使用简化碰撞体+GJK初步检测
- 精确验证：仅在预判阳性时触发完整检测
// 两阶段检测示例代码 bool TwoPhaseCollisionCheck(Object* objA, Object* objB) { // 阶段一：简化碰撞体检测 if (!GJK_Check(objA->simpleCollider, objB->simpleCollider)) return false; // 阶段二：完整碰撞体检测 return GJK_EPA_Check(objA->detailedCollider, objB->detailedCollider); }3.3 移动端特殊优化
移动平台受限于计算资源，需要特别考虑：
- 算法简化：限制GJK最大迭代次数（通常≤10）
- 内存优化：预计算凸包并量化顶点数据
- 能耗控制：在低电量时自动降低检测精度
4. 性能调优与陷阱规避
4.1 常见性能瓶颈分析
通过Profiling工具可识别典型瓶颈点：
- Support函数开销：占GJK总时间的60-70%
- 优化：空间划分/顶点缓存
- EPA收敛慢：深穿透时迭代次数激增
- 优化：设置最大迭代阈值
- 缓存不友好：随机内存访问模式
- 优化：数据预取/紧凑内存布局
4.2 数值稳定性问题
GJK对浮点误差敏感，常见问题包括：
- 误判碰撞：由于浮点精度导致原点误包含
- 无限循环：方向向量退化未处理
解决方案对比：
| 问题类型 | 解决方案 | 副作用 |
|---|---|---|
| 浮点误差 | 增加容差ε | 可能漏检 |
| 向量退化 | 随机扰动 | 影响确定性 |
| 数值溢出 | 坐标归一化 | 额外计算开销 |
4.3 多线程实现要点
安全并行化GJK需要注意：
- 无状态设计：避免修改共享数据
- 确定性保证：相同输入必定相同输出
- 任务划分：按物体对而非算法阶段划分
提示：在Bullet 3.x中，可通过开启BT_USE_SSE_IN_API标志获得自动向量化优化，这对移动端ARM NEON架构同样有效。
5. 前沿发展与未来展望
虽然GJK仍是当前主流，但新技术正在涌现：
- 深度学习辅助：使用神经网络预测碰撞概率
- 连续碰撞检测优化：结合时空约束的改进GJK
- 异构计算：利用Tensor Core加速矩阵运算
在实际机器人仿真项目中，混合使用传统算法与机器学习方法正在成为趋势。例如先通过轻量级神经网络快速筛选潜在碰撞对，再使用精确的GJK进行验证，这种组合策略可将复杂场景的检测效率提升3-5倍。
