自动驾驶小白说 🏎️1.3 碰撞检测算法:AABB, SAT
type
status
slug
date
summary
tags
category
password
icon
彪子,你太爱学习了! —漫长的季节 丽茹
🏰代码及环境配置：请参考0.2 环境配置和代码运行 | 动手学运动规划!
在规划算法中，碰撞检测是确保轨迹安全性的关键环节。通过实时检测物体之间的相对位置和状态，碰撞检测算法能够预测并避免潜在的碰撞事件，从而保障系统的稳定运行和安全性。
1.3.1 碰撞检测的方法分类
碰撞检测方法主要分为两大类：基于几何空间的碰撞检测算法和基于图像空间的碰撞检测算法。
1.3.1.1 基于几何空间的碰撞检测算法
- 空间剖分算法：如均匀网格、八叉树、k-d树等，通过将空间划分成不同的区域来减少碰撞检测的计算量。这类算法适用于多模型场景的粗检测阶段。
- 基于层次包围盒的算法：包括轴向包围盒（AABB）、球包围盒（Sphere）、方向包围盒（OBB）和离散方向多面体（k-DOP）等。这些算法通过构建物体的包围盒来快速剔除不相交的情况，提高碰撞检测的效率。
- 裁剪扫掠法：通过计算每个模型的包围盒，并在坐标轴上进行投影和排序，来检测模型之间的相交情况。这种方法适用于精检测阶段的碰撞检测。
1.3.1.2 基于图像空间的碰撞检测算法
这类算法利用图形硬件将模型投影到二维平面空间，再根据投影的相交情况和模型的各类缓存信息来判断模型之间是否碰撞。优点是碰撞检测过程不需要进行任何预处理，且能够利用GPU加速图形的渲染，降低CPU的计算负荷。但缺点是图像的分辨率会影响算法的精确度，且需要解决图形硬件和CPU的负载均衡问题。
1.3.2 碰撞检测的粗糙检测算法
为了提高碰撞检测效率,在规划中的碰撞检测一般会先执行计算成本较低的粗糙检测算法,当粗检测判定可能碰撞后,再进行精细检测算法.
粗糙检测的目的是快速过滤掉一些显然不会碰撞的情况,这里我们介绍一些常见的粗检测算法:
1.3.2.1 基于层次包围盒
- 轴向包围盒(AAB Box)
“Axis-Aligned Bounding Box”（轴对齐边界框）。这种边界框是一个包围着目标多边形的最小的矩形，且这个矩形的每一边都与坐标轴（通常是X轴、Y轴）平行。
给定 AABB 的中心点 c 和两条边的半径𝑟𝑥 ，𝑟𝑦 ，𝑟𝑧，AABB 所包含的区域可以用 以下公式定义：
对于两个AABB BOX,只需要在X,Y坐标上分别进行两次相交测试即可判断是否相交
- 球包围盒（Sphere）
球包围盒（Sphere）是一类紧密性相对较差的包围盒，其优点是可以 实现快速相交测试，以及在对模型的球包围盒重构时不用考虑模型的旋转变换。
需要给定球的球心 c 以及半径 r：
对于两个球包围盒,只需要计算 两个球心的距离与两个包围盒的半径和的大小即可判定是否相交
- 其他包围盒
还有其他形式的包围盒,如方向包围盒,离散方向多面体等. 不再赘述
1.3.3 碰撞检测的精细检测算法
精细检测算法用来判定两个几何体是否真正发生碰撞,在轨迹规划中常见的碰撞检测算法有分离轴算法(SAT),GJK算法等
1.3.3.1 分离轴算法(SAT)
分离轴算法（Separating Axis Theorem，简称SAT）,只能用于判断两个凸集是否相交.
SAT算法的主要思路是寻找分离轴。对于任意两个凸集，如果存在一个分离轴，使得两个凸集在该轴上的投影没有重叠，则可以确定这两个凸集不相交。反之，如果对于所有可能的分离轴，两个凸集的投影都重叠，则可以确定它们相交。
对于凸多边形,可以使用边的垂线作为分离轴。如果存在一个投影不重叠,则可判定不相交;反之,如果所有边的垂线的投影都重叠,则判定相交.
如下图,存在不重叠的边的垂线e3。
SAT不适用于非凸多边形的相交检测,如下图:
优点:
- SAT十分快,并且精准
缺点
- SAT的计算量随着边数增加,会快速增长.
- 不能用于非凸多边形
由于SAT对边数多的凸多边形检测效率较低,下一节我们将介绍另一种碰撞检测算法:GJK
下一节, 我们会解析和运行代码.
Loading...
