碰撞检测原理：AABB、OBB、GJK 算法简介，如何选择检测精度与速度

碰撞检测，说白了就是回答一个问题：我的机械臂跟障碍物碰上了没有？

这个问题听起来简单，但在实际项目中，它往往是整个运动规划的性能瓶颈。我见过不少团队，算法选型时没想清楚，结果机械臂一跑起来，碰撞检测占了 80% 的计算时间，路径规划根本没法实时。

这一章，我就带你把这几种主流碰撞检测算法吃透。咱们不搞数学推导，重点讲清楚它们各自适合什么场景，以及怎么在精度和速度之间做取舍。

为什么碰撞检测需要分层？

你想想看，机械臂的连杆是三维几何体，障碍物也是。如果每帧都拿两个复杂的三角网格去做精确求交，计算量会爆炸。

所以工业界的做法是分层检测：先用粗筛快速排除明显不相交的物体，再用细筛处理那些可能碰撞的候选对。粗筛阶段用的就是包围盒算法。

AABB：最简单，也最常用

AABB 的全称是 Axis-Aligned Bounding Box，轴对齐包围盒。它的特点是：盒子的每条边都平行于世界坐标系的轴。

为什么它快？因为判断两个 AABB 是否相交，只需要做 6 次比较——分别检查三个轴上的投影区间是否重叠。没有任何三角函数，没有矩阵运算。

// 两个 AABB 的碰撞检测
bool AABBOverlap(const AABB& a, const AABB& b) {
    // 检查 X 轴
    if (a.max.x < b.min.x || a.min.x > b.max.x) return false;
    // 检查 Y 轴
    if (a.max.y < b.min.y || a.min.y > b.max.y) return false;
    // 检查 Z 轴
    if (a.max.z < b.min.z || a.min.z > b.max.z) return false;
    return true;
}

我在项目中遇到过一个问题：机械臂的末端执行器旋转时，AABB 会变得特别大。因为盒子不能跟着物体旋转，只能把整个旋转范围包进去。结果就是，明明没碰到，AABB 却说碰到了——这就是虚警。

OBB：更紧致，但更贵

OBB 是 Oriented Bounding Box，有向包围盒。它的盒子可以跟着物体一起旋转，所以包裹得更紧。

判断两个 OBB 是否相交，用的是分离轴定理（SAT）。简单说，就是找一条轴，让两个盒子在这条轴上的投影不重叠。如果能找到，它们就不相交。

但问题是，两个 OBB 最多需要检查 15 条轴（每个盒子的 3 个面法向量 + 9 条边叉积）。每条轴都要做投影计算，涉及点积和比较。所以 OBB 的计算量是 AABB 的几十倍。

什么时候用 OBB？当物体长宽比很大，而且经常旋转时。比如机械臂的细长连杆，用 AABB 会包出很大一片虚警区域，用 OBB 就能紧贴连杆表面。

GJK：精确碰撞检测的利器

AABB 和 OBB 都是保守检测——它们说没碰到，那肯定没碰到；但说碰到了，不一定真碰到（虚警）。

GJK（Gilbert-Johnson-Keerthi）算法则不同。它直接对两个凸多面体做精确求交，能告诉你到底碰没碰到，以及最近距离是多少。

GJK 的核心思想是：如果两个凸体相交，它们的明可夫斯基差一定包含原点。算法通过迭代搜索，不断缩小包含原点的单纯形，直到收敛。

// GJK 伪代码（简化版）
bool GJK(ConvexShape shapeA, ConvexShape shapeB) {
    // 初始化：取一个支撑点作为起始单纯形
    Simplex simplex;
    simplex.add(support(shapeA, shapeB, Vec3(1,0,0)));
    
    // 迭代搜索
    Vec3 direction = -simplex.getLast();
    while (true) {
        Vec3 p = support(shapeA, shapeB, direction);
        if (p.dot(direction) < 0) return false; // 没碰到
        simplex.add(p);
        if (simplex.containsOrigin()) return true; // 碰到了
        // 更新搜索方向
        direction = simplex.getNewDirection();
    }
}

GJK 的优点是精度高，缺点是计算不稳定。当两个物体几乎相切时，迭代次数会暴增。我一般只在最终验证阶段用 GJK，或者在需要计算穿透深度时用。

如何选择检测精度与速度？

这个问题没有标准答案，但有一个经验法则：

场景	推荐算法	原因
静态环境碰撞检测	AABB	障碍物不移动，AABB 紧致且极快
机械臂自碰撞检测	OBB + 空间哈希	连杆旋转频繁，OBB 减少虚警
动态障碍物避障	AABB + 时间戳缓存	需要高频更新，AABB 计算量最低
最终路径验证	GJK	需要精确结果，避免误报导致路径无效
高精度抓取规划	OBB + GJK 混合	先用 OBB 粗筛，再用 GJK 精确验证

知识体系总览

下面这张图总结了三种算法的定位和关系：

实际项目中的调参经验

光知道算法原理还不够，调参才是真功夫。我分享几个实战中总结出来的经验：

• 包围盒的膨胀系数：别把包围盒做得跟物体一模一样。留 2-5mm 的余量，可以避免因为传感器误差或控制抖动导致的误报。我一般设 3mm，效果不错。
• 更新频率：AABB 可以每控制周期（1ms）更新一次。OBB 建议每 5-10 个周期更新一次，因为它的计算量更大。GJK 只在路径规划完成后调用一次。
• 空间分区：当障碍物数量超过 20 个时，别做两两检测。用八叉树或网格把空间分成小块，只检测同一块或相邻块里的物体对。
• 缓存机制：如果障碍物上一帧没动，这一帧就别重新算它的包围盒。我见过有人每帧都重建 OBB，白白浪费 CPU。