粗略的物体碰撞预测及检测

二手车知识大讲堂

2018-01-27

该博客实时更新于我的Github。
在机器人局部路径规划中，需要实时躲避运动或者静态的障碍物，这个过程涉及到碰撞检测这个问题，本文主要讨论这个问题。
碰撞检测问题也是游戏开发中经常遇到的问题，一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者相对无关的状态，那么一个物体的碰撞运算没必要遍历这些物体，我们可以使用一个包围一个或多个物体的多边形来讨论碰撞问题，这样子可以节省重要的计算量和时间。
在真实的物理系统中，一般需要在运算速度和精确性上做取舍。尽管非常精确的碰撞检测算法可以精确地表示和解决碰撞问题，但是在路径规划初期对碰撞只需要有一个初步的估计，比如是否会发生碰撞，碰撞的大概程度如何，以免把大量的精力浪费在碰撞检测问题上，从而降低了在其他方面的注意力。本文主要利用游戏中用到的碰撞检测方法，来解决碰撞检测的初步估计，或者对碰撞精确度要求不高的场合，将不规则的物体投影成较规则的物体进行碰撞预测及检测。

AABB介绍

目前，成功的3D游戏普遍采用的碰撞检测是BSP树以及AABB(Axially Aligned Bounding Box)包装盒方式。BSP树是用来控制检测顺序和方向的数据描述。这里不再详细讨论。AABB检测方法采用一个描述用的立方体或者球形体包裹住3D物体对象的整体（或者主要部分），我们可以根据包装盒的距离、位置等信息来计算是否发生碰撞。注意：出于计算量和方便性考虑，AABB中常用的包装盒形状是球体和长方体，但是在其它特殊场合，其他形状也可以作为包装盒。
坐标轴平行（Axially-aligned）不仅指盒体与世界坐标轴平行，同时也指盒体的每个面都和一条坐标轴垂直，这样一个基本信息就能减少转换盒体时操作的次数。AABB技术在当今的许多游戏中都得到了应用，开发者经常用它们作为模型的检测模型。
二维场景中的AABB包围盒具备特点(下图中的所有坐标系均采用右手直角坐标系):

表现形式为四边形，即用四边形包围物体。
四边形的每一条边，都会与坐标系的轴垂直。

三维场景中的AABB包围盒特点：

表现形式为六面体。
六面体中的每条边都平行于一个坐标平。

其中，为了更明显的展示AABB包围盒的特点，在最右侧展示了一个OBB（Oriented Bounding Box）包围盒，也称作有向包围盒。AABB包围盒与OBB包围盒的最直接的区别就是，AABB包围盒是不可以旋转的，而OBB包围盒是可以旋转的，也就是有向的。

三维场景中物体的AABB包围盒是一个六面体，虽然有8个顶点，但是对于规则的AABB立方体，我们仅需要知道两个顶点(x_min,y_min,z_min)和(x_max,y_max,z_max)就可以得到AABB的中心点、边长等属性,具体不再详述。三维物体的AABB包围盒的八个顶点依旧可以用两个顶点来标识，如下图所示。

球体碰撞预测及检测

球体是碰撞检测中最简单的数学模型，我们只需要直到两个球体的球心和半径就可以进行检测。
球体碰撞的优点是非常适用于需要快速检测的游戏，因为它不需要精确的碰撞检测算法,执行速度相对较快，不会给CPU带来过大的计算负担。球体碰撞的另一个劣势是只适用于近似球形物体，如果物体非常窄或者非常宽，该碰撞检测算法将会失效，因为会在物体实际发生碰撞之前，碰撞检测系统就发出碰撞信号。

球体树

为了解决包容球精确度不高的问题，人们又提出了球体树的方法。如下图所示，球体树实际上是一种表达3D物体的层次结构。对一个形状复杂的3D物体，先用一个大球体包容整个物体，然后对物体的各个主要部分用小一点的球体来表示，然后对更小的细节用更小的包容球体，这些球体和它们之间的层次关系就形成了一个球体树。

举例来说，对一个游戏中的人物角色，可以用一个大球来表示整个人，然后用中等大小的球体来表示四肢和躯干，然后用更小的球体来表示手脚等。这样在对两个物体进行碰撞检测时，先比较两个最大的球体。如果有重叠，则沿树结构向下遍历，对小一点的球体进行比较，直到没有任何球体重叠，或者到了最小的球体，这个最小的球体所包含的部分就是碰撞的部分。

速度锥

在实际碰撞检测中，我们需要提前预估碰撞的危险程度，通过将运动物体碰撞处理为两个球体，在已知球体的球心、半径、运动矢量后，就可以预估出沿着当前运动趋势的最近距离和对应时间。为方便理解，如下图所示，以二维平面上的两个圆形为例建立相对运动坐标系，讨论碰撞检测问题，可以扩展到3维空间的球体中。

在二维平面内，障碍物的碰撞预测如下，其中DCPA表示最近距离的值，TCPA表示在最近时刻的时间。

碰撞预测C#源代码:

// C# 代码
public static ARPA CPACalculation(double USVGeo_x, double USVGeo_y, double OBSGeo_x, double OBSGeo_y, double USV_Speed, double USV_Azimuth, double OBS_Speed, double OBS_Azimuth)
{
    // 计算距离
    double distance = GeographyBase.GeographyTransfer.CalLength(USVGeo_x,USVGeo_y,OBSGeo_x,OBSGeo_y);
    // 计算方位
    double UAV2OBSAzimuth = GeographyBase.GeographyTransfer.CalAzimuth(USVGeo_x, USVGeo_y, OBSGeo_x, OBSGeo_y);
    double interAngle = USV_Azimuth - OBS_Azimuth; //取值范围在[-180, 180]之间
    if (interAngle > 180)
        interAngle -= 360;
    if (interAngle < -180)
        interAngle += 360;
    // 相对速度
    double RelativSpeed = Math.Sqrt(Math.Pow(USV_Speed, 2) + Math.Pow(OBS_Speed, 2) - 2 * USV_Speed * OBS_Speed * Math.Cos(interAngle / 180.0 * Math.PI));
    // 相对航向
    double angleQ = Math.Acos((Math.Pow(RelativSpeed, 2) + Math.Pow(USV_Speed, 2) - Math.Pow(OBS_Speed, 2)) / (2 * RelativSpeed * USV_Speed)) * 180.0 / Math.PI;
    double RelativeAzimuth = 0;
    if (interAngle > 0)
        RelativeAzimuth = USV_Azimuth + angleQ;
    else
        RelativeAzimuth = USV_Azimuth - angleQ;
    // 相对舷角的计算 
    double bearing = UAV2OBSAzimuth - RelativeAzimuth;
    double DCPA = distance * Math.Sin(bearing * Math.PI / 180.0);
    double TCPA = distance * Math.Cos(bearing * Math.PI / 180.0) / RelativSpeed;
    ARPA arpa = new ARPA();
    arpa.DCPA = DCPA;
    arpa.TCPA = TCPA;
    arpa.SailSpeed = OBS_Speed;
    arpa.SailAngle = OBS_Azimuth;
    arpa.TargetDistance = distance;
    arpa.TargetAzimuth = UAV2OBSAzimuth;
    return arpa;
}

立方体碰撞检测--AABB

AABB对物体的方向很敏感，同一物体的不同方向，AABB也可能不同（由于球体只有一个自由度，所以检测球对物体方向不敏感）。
当物体在场景中移动时，它的AABB也需要随之移动，当物体发生旋转时，有两种选择：用变换后的物体来重新计算AABB，或者对AABB做和物体同样的变换。如果物体没有发生扭曲，可以通过“变换后AABB”重新计算，因为该方法要比通过“变换后的物体”计算快得多。可以利用矩阵变化加快新的AABB的计算速度，具体可以参考适合新手的3d碰撞检测

AABB静态检测

AABB的静态检测比较简单，检测两个静止包装盒是否相交，它是一种布尔测试，测试结果只有相交或者不相交。这里我们还提供了获取相交范围信息的方法，一般来说，这种测试的目的是为了返回一个布尔值。
在一维坐标轴中，两线段A和B相交的条件是:

线段A在坐标轴上的最大值A_max不小于线段B在坐标轴上的最小值B_min;
线段B坐标轴上的最大值B_max不小于线段A在坐标轴上的最小值A_min;
即 (A_max-B_min)*(B_max-A_min)>0

基于上述事实，二维场景中AABB碰撞检测原理:

在上图中，分别做物体A与物体B在X,Y轴方向的投影，物体A的Y轴方向最大点坐标为Y1，最小点坐标Y2，X轴方向最小点坐标X1，最大点坐标X2，物体B同理。图中红色区域为物体A与物体B投影的重叠部分。
二维场景中AABB碰撞检测具有如下规则：物体A与物体B分别沿两个坐标轴做投影，只有在两个坐标轴都发生重叠的情况下，两个物体才意味着发生了碰撞。
即，若Y轴方向上(Y1-Y4)*(Y3-Y2)>0，X轴方向上(X4-X1)*(X2-X3)>0,那么证明物体A与物体B发生重合，否则证明物体A和B并未发生重合。
三维场景中AABB碰撞检测原理:
三维场景中物体的AABB包围盒是一个六面体，其坐标系对于二维坐标系来讲只是多了一个Z轴，所以实际上在三维场景中物体的AABB碰撞检测依然可以采用四个点信息的判定来实现，即从物体A的八个顶点与物体B的八个顶点分别选出两个最大与最小的顶点进行对比。碰撞的示意如下图：

三维场景中AABB碰撞检测具有如下规则：物体A与物体B分别沿三个坐标轴做投影，只有在三个坐标轴都发生重叠的情况下，两个物体才意味着发生了碰撞。
实现代码如下，其中min和max数组是另一个AABB的最小点和最大点，最后返回碰撞检测结果和碰撞部分的AABB。

运动多面体

在使用单步碰撞检测时，存在时间步长较大时会发生两个物体完全穿透而算法却未检测出来的问题，如下图所示。通常的解决方法是产生一个4D空间，在单位时间步长内，在物体运动的开始和结束时间之间产生一个4D超多面体，又称运动多面体，用于穿透测试。

对一个三维物体网格化处理后，需要对三维物体内的子网格做碰撞监测，子网格是规则的立方体。在单位时长内，连接开始和结束时刻物体的最大包络线得到的就是运动多面体。其中，通过求取垂直物体运动方向上的宽度就可以得到包络线的宽度，可以应用旋转的方法。
AABB碰撞检测算法虽然计算方法简单，速度快，但是仅适用于精度要求不高的场合中。相对于AABB碰撞检测，还有一种更逼近物体并更为精确的一种算法--OBB碰撞检测。

OBB

未完待续

参考文献和资源(不分先后)

[1] Gottschalk, Stefan, Ming C. Lin, and Dinesh Manocha. "OBBTree: A hierarchical structure for rapid interference detection." Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, 1996.
三维物体AABB碰撞检测算法
适合新手的3d碰撞检测
船舶碰撞危险度的计算方法比较(非匿名)

包围盒