Open phenomLi opened 5 years ago
想要高效地进行碰撞检测,不是一件简单的事情。物理引擎通常面对的是多个物体同时出现在同一场景,比如说现在我们的场景中有 5 个物体:
我们当然可以用碰撞检测算法进行两两碰撞检测,如 SAT ,GJK 等。然而当场景中有 100 个物体时,即使使用优化手段跳过已经检测的物体对,至少也要执行 (100 * (100 - 1)) / 2 次 SAT 或 GJK 。这显然是不能接受的。
即使我们不能快速判断两个物体真的发生了碰撞,但是我们肯定是有办法快速判断两个物体肯定没有发生碰撞。场景中的物体形状都是随机的,这造成了碰撞检测的困难,因此我们可以使用一种简化的易于检测的图形去暂时代替物体,当两个简化的图形没发生相交,那么我们可以马上推断其相应的物体没有发生碰撞。
AABB 名叫轴对齐包围盒(Axis align bounding box),轴对齐意思即是与 x,y 轴对其,包围盒顾名思义是一个矩形,因此不难想到 AABB 是一个包裹物体的最小外接矩形。除 AABB 外,还有 OBB 方向包围盒(Oriented bounding Box)等。
一个物体与其 AABB 如下图所示:
可以有很多方式定义 AABB,我个人比较常用第一种,但是这都不重要,主要看你喜欢。
我们给场景中 5 个物体都加上 AABB:
现在,我们把 5 个物体简化为 5 个矩形了,之后我们就可以使用这 5 个 AABB 矩形来快速筛选掉不可能发生碰撞的物体。
为什么使用矩形?使用矩形的好处是判断矩形的相交十分容易。检测AABB包围盒相交的本质是判断两个矩形是否相交,问题可以再一步转化为与两对与x,y轴平行的线段的在x,y轴的投影的重叠检测。
而检测两条共线线段是否重叠,基本思想是比较两条线段的开始端点和结束端点的大小。但是由于两条线段的位置是任意的,所以在进行比较时,要分线段的先后情况讨论。我们假设两条投影线段分别为L1, L2。
因此可以看到,两 AABB 相交检测的复杂度为 O(1),比执行一次完整的 SAT 或 GJK 要快的多。由于其简单高效的特性,除物理引擎外,AABB 还被应用在许多需要进行“快速筛选”的场景。比如说某些图形库可以利用 AABB 快速判断鼠标指针是否落在某个图形内,有些可视化工具利用 AABB 来计算视图占据的位置,或者快速检测两个图形有没有发生重叠遮挡等。
想要高效地进行碰撞检测,不是一件简单的事情。物理引擎通常面对的是多个物体同时出现在同一场景,比如说现在我们的场景中有 5 个物体:![](https://github.com/phenomLi/Blog/raw/master/photos/2020-4-16/微信截图_20200416171057.png)
我们当然可以用碰撞检测算法进行两两碰撞检测,如 SAT ,GJK 等。然而当场景中有 100 个物体时,即使使用优化手段跳过已经检测的物体对,至少也要执行 (100 * (100 - 1)) / 2 次 SAT 或 GJK 。这显然是不能接受的。
即使我们不能快速判断两个物体真的发生了碰撞,但是我们肯定是有办法快速判断两个物体肯定没有发生碰撞。场景中的物体形状都是随机的,这造成了碰撞检测的困难,因此我们可以使用一种简化的易于检测的图形去暂时代替物体,当两个简化的图形没发生相交,那么我们可以马上推断其相应的物体没有发生碰撞。
AABB 包围盒
AABB 名叫轴对齐包围盒(Axis align bounding box),轴对齐意思即是与 x,y 轴对其,包围盒顾名思义是一个矩形,因此不难想到 AABB 是一个包裹物体的最小外接矩形。除 AABB 外,还有 OBB 方向包围盒(Oriented bounding Box)等。
一个物体与其 AABB 如下图所示:
可以有很多方式定义 AABB,我个人比较常用第一种,但是这都不重要,主要看你喜欢。![](https://github.com/phenomLi/Blog/raw/master/photos/2020-4-16/微信截图_20200416170628.png)
我们给场景中 5 个物体都加上 AABB:![](https://github.com/phenomLi/Blog/raw/master/photos/2020-4-16/微信截图_20200416171025.png)
现在,我们把 5 个物体简化为 5 个矩形了,之后我们就可以使用这 5 个 AABB 矩形来快速筛选掉不可能发生碰撞的物体。
为什么使用矩形?使用矩形的好处是判断矩形的相交十分容易。检测AABB包围盒相交的本质是判断两个矩形是否相交,问题可以再一步转化为与两对与x,y轴平行的线段的在x,y轴的投影的重叠检测。![](https://github.com/phenomLi/Blog/raw/master/photos/2020-4-16/微信截图_20200415234557.png)
而检测两条共线线段是否重叠,基本思想是比较两条线段的开始端点和结束端点的大小。但是由于两条线段的位置是任意的,所以在进行比较时,要分线段的先后情况讨论。我们假设两条投影线段分别为L1, L2。
![](https://github.com/phenomLi/Blog/raw/master/photos/2020-4-16/微信截图_20190522170439.png)
因此可以看到,两 AABB 相交检测的复杂度为 O(1),比执行一次完整的 SAT 或 GJK 要快的多。由于其简单高效的特性,除物理引擎外,AABB 还被应用在许多需要进行“快速筛选”的场景。比如说某些图形库可以利用 AABB 快速判断鼠标指针是否落在某个图形内,有些可视化工具利用 AABB 来计算视图占据的位置,或者快速检测两个图形有没有发生重叠遮挡等。