1.3 碰撞检测算法:AABB, SAT | 自动驾驶小白说

1.3.1 碰撞检测的方法分类

碰撞检测方法主要分为两大类：基于几何空间的碰撞检测算法和基于图像空间的碰撞检测算法。

基于层次包围盒的算法：包括轴向包围盒（AABB）、球包围盒（Sphere）、方向包围盒（OBB）和离散方向多面体（k-DOP）等。这些算法通过构建物体的包围盒来快速剔除不相交的情况，提高碰撞检测的效率。

这类算法利用图形硬件将模型投影到二维平面空间，再根据投影的相交情况和模型的各类缓存信息来判断模型之间是否碰撞。优点是碰撞检测过程不需要进行任何预处理，且能够利用GPU加速图形的渲染，降低CPU的计算负荷。但缺点是图像的分辨率会影响算法的精确度，且需要解决图形硬件和CPU的负载均衡问题。

为了提高碰撞检测效率,在规划中的碰撞检测一般会先执行计算成本较低的粗糙检测算法,当粗检测判定可能碰撞后,再进行精细检测算法.

粗糙检测的目的是快速过滤掉一些显然不会碰撞的情况,这里我们介绍一些常见的粗检测算法:

“Axis-Aligned Bounding Box”（轴对齐边界框）。这种边界框是一个包围着目标多边形的最小的矩形，且这个矩形的每一边都与坐标轴（通常是X轴、Y轴）平行。

给定 AABB 的中心点 c 和两条边的半径𝑟𝑥 ，𝑟𝑦 ，𝑟𝑧，AABB 所包含的区域可以用以下公式定义：

对于两个AABB BOX,只需要在X,Y坐标上分别进行两次相交测试即可判断是否相交

球包围盒（Sphere）是一类紧密性相对较差的包围盒，其优点是可以实现快速相交测试，以及在对模型的球包围盒重构时不用考虑模型的旋转变换。

需要给定球的球心 c 以及半径 r：

对于两个球包围盒,只需要计算两个球心的距离与两个包围盒的半径和的大小即可判定是否相交

还有其他形式的包围盒,如方向包围盒,离散方向多面体等. 不再赘述

精细检测算法用来判定两个几何体是否真正发生碰撞,在轨迹规划中常见的碰撞检测算法有分离轴算法(SAT),GJK算法等

分离轴算法（Separating Axis Theorem，简称SAT）,只能用于判断两个凸集是否相交.

SAT算法的主要思路是寻找分离轴。对于任意两个凸集，如果存在一个分离轴，使得两个凸集在该轴上的投影没有重叠，则可以确定这两个凸集不相交。反之，如果对于所有可能的分离轴，两个凸集的投影都重叠，则可以确定它们相交。

对于凸多边形,可以使用边的垂线作为分离轴。如果存在一个投影不重叠,则可判定不相交;反之,如果所有边的垂线的投影都重叠,则判定相交. 如下图,存在不重叠的边的垂线e3。

SAT不适用于非凸多边形的相交检测,如下图:

优点:

缺点

由于SAT对边数多的凸多边形检测效率较低,下一节我们将介绍另一种碰撞检测算法:GJK

下一节, 我们会解析和运行代码.