大家好，我是橙子，套用某位老总的话“安全是最大的豪华”，在智能驾驶的算法的一个细分领域—路径规划算法，同样离不开安全，如何确保路径安全，那就需要准确的碰撞检测算法。

算法很多种，各有优劣势，今天给大家用大白话讲清楚两个常用的，也是我实践中用到的算法，AABB碰撞检测算法和SAT碰撞检测算法。

Part 1. AABB碰撞检测算法

AABB是Axis-Aligned Bounding Box的缩写，中文名：轴对齐包围盒，因为它的计算速度快、实现结构也简单、同时不依赖复杂数学运算，所以在游戏、物理引擎、图形学里广泛使用，我们智驾领域也不例外。

其流程如下：

分别计算物体A与物体B在X,Y轴方向的投影，一般由感知给出障碍物的矩形框信息，包含4个角点信息

物体A的Y轴方向最大点坐标为Y1，最小点坐标Y2，X轴方向最小点坐标X1，最大点坐标X2

物体B的Y轴方向最大点坐标为Y３，最小点坐标Y４，X轴方向最小点坐标X３，最大点坐标X４

一般需要将物体A与物体B分别沿两个坐标轴做投影，当投影在两个坐标轴都发有重叠的情况下，认为两个物体发生了碰撞

未碰撞条件：

步骤一：物体A的Y轴方向最小值大于物体B的Y轴方向最大值；

步骤二：物体A的X轴方向最小值大于物体B的X轴方向最大值；

步骤三：物体B的Y轴方向最小值大于物体A的Y轴方向最大值；

步骤四：物体B的X轴方向最小值大于物体A的X轴方向最大值；

C++伪代码：

结论：若满足上述任意一个条件，则证明物体A与物体B并未发生重合，反之，若上述条件全部都不满足，则证明物体A与物体B重合。

Part 2. SAT碰撞检测算法

SAT,（Separating Axis Theorem, SAT）中文是分离轴碰撞检测算法，顾名思义，其目标是找出一条能够将物体分开的轴线，是2D/3D 凸多边形碰撞检测最通用、最高效的算法，AABB 只是 SAT 的一种特例。

其流程如下：

步骤一：从需要检测的多边形中取出一条边，并找出它的法向量（虚线，垂直于它的向量），这个向量将会是我们的一个“投影轴”;

步骤二：循环获取第一个多边形的每个点，并将它们投影到这个轴上;

步骤三：对第二个多边形投影到该轴上;

步骤四：分别得到这两个多边形的投影，并检测这两段投影是否重叠;

步骤五：重复上面1到4步;

结论：如果这两个投影到轴上的“阴影”有间隙，那么这两个图形一定没有相交。但如果没有间隙，那么它们则可能接触，你需要继续检测直到把两个多边形的每条边都检测完。如果你检测完每条边后，都没有发现任何间隙，那么它们是相互碰撞的，即有一个轴上的两个物体的投影存在间隙（蓝色线段），即没有碰撞，如果没有找到，就要遍历完所有轴都没有间隙才认为有碰撞。

Part 3. 总结

AABB算法，满足一个未碰撞条件即可结束，结果是未碰撞，所有未碰撞条件不满足即为碰撞。

SAT算法，存在一条未重叠的投影轴即为未碰撞，所有投影轴都没有间隙即为碰撞。

文章转载自公众号：智驾前沿社

作者：小橙子的青葱岁月
原文链接：https://mp.weixin.qq.com/s/QQyVyVj0KFiGivKmuOyqYw

简单、易懂！聊聊智能驾驶中常用的碰撞检测算法

Part 1. AABB碰撞检测算法

Part 2. SAT碰撞检测算法

Part 3. 总结