《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

时间:2022-06-15 15:17:20

基于包围球的AABB

    通过在任意方向上全包围物体对象,从而实现重构造AABB。且物体可以围绕球心P旋转:半径r为球心距离物体最远顶点的距离。若P与物体中心位置重合,则可保证当前球体半径为最小半径。

《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

    该表达方式优点之一是:在更新AABB过程中只需考虑平移变换,且可忽略旋转变换。然而包围球自身也具备上诉特征(优于AABB),因此在此例中包围球是更好的选择。

基于原点的AABB重构

    此更新策略在AABB与各坐标轴重对齐时,将动态地调整其尺寸。对于一个紧密拟合的包围体,将检测其底层几何数据,同时沿坐标轴的6个方向搜索端点从而构造AABB的包围数据。一种比较直接的方法是遍历全部顶点,并记录各方向向量上的最大距离顶点。

    该距离可以通过顶点向量在方向向量上的投影得到。由于需要进行比较,这里不比规范化方向向量。该计算过程如下列代码所示,其中记录了沿方向向量上的最近顶点和最远顶点:

//Returns indices imin and imax into pt[] array of the least and
//most, respectively, distant point along the direction dir
void ExtremePointAlongDirection(Vector dir, Point pt[], int n, int *imin, int *imax) {
  float minproj = FLT_MAX, maxproj = -FLT_MAX;
  for(int i = 0; i < n; i++) {
      //Project vector from origin to point onto direction vector
      float proj = Dot(pt[i], dir);
      //Keep track of least distant point along direction vector
        if(proj < minproj) {
            minproj = proj;
           *imin = i;
        }
      //Keep track of most distant point along direction vector
        if(proj > maxproj) {
            maxproj = proj;
          *imax = i;
      }
    }
}

    该算法复杂度为O(n),预处理顶点数据可以在一定程度上加速计算过程,如提前存储凸顶上的顶点,只检查这几个顶点(只有凸顶上的顶点才影响包围体形状)。

    通过额外的特定预处理搜索结构,确定端点的时间消耗可以降低到O(log n)。例如,Dobkin-Kirpatrick层次结构便用于此目的。但该结构将占用内存空间且存在遍历时间消耗,导致性能下降。若紧凑包围体在计算中确实十分重要,可以考虑它而不考虑AABB

爬山法构造AABB

    快速计算物体顶点的邻接顶点。通过简单的爬山法确定新AABB各端点。如下图:

《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

   这里不采用记录各轴向上最小、最大值的方法,而是维护6个顶点指针(这里不理解6怎么来的),并指向各轴向的物体端点。爬山法将一个参考点与其邻接点进行比较,并查看参考点是否仍在之前同一个方向上的端点,若不是,则端点替换为新的邻接顶点,重复直至获得该方向上最终端点。注意,爬山法要求物体为凸体。

旋转AABB后的重计算

    最简单的方法是利用一个新的AABB包围旋转后的AABB,但这只是形成了逼近AABB而非紧凑AABB。 

    考查一个轴对齐包围盒A,且旋转矩阵M作用于A之上,结果是具有某一方向的旋转包围盒AM3个列(或行)给出A中世界坐标轴(若向量为列向量且右乘矩阵,则M列为坐标轴;若向量为行且左乘矩阵则M的行为坐标轴)。

    令包围盒采用最小值-最大值形式,且M为列矩阵。由于平移操作不影响包围盒尺寸,可以加入平移变换。

x轴上最大范围值计算如下:

B.max[0] = max(m[0][0] * A.min[0], m[0][0] * A.max[0])

          + max(m[0][1] * A.min[1], m[0][1] * A.max[1])

          + max(m[0][2] * A.min[2], m[0][2] * A.max[2]) + t[0];

因此,对于采用最小-最大值形式的AABB,其旋转后的包围盒可以参考下列代码:

//Transform AABB a by the matrix m and translation t,
//find maximum extents, and store result into AABB b.
void UpdateAABB(AABB a, float m[3][3], float t[3], AABB &b) {
   //For all three axes
   for(int i = 0; i < 3; i++) {
        //Start by adding in translation
        b.min[i] = b.max[i] = t[i];
        //Form extent by summing smaller and larger terms respectively
        for(int j = 0; j < 3; j++) {
            float e = m[i][j] * a.min[j];
            float f = m[i][j] * a.max[j];
            if(e < f) {
                b.min[i] += e;
                b.max[i] +=f;
            } esle {
                b.min[i] += f;
                b.max[i] +=e;
            }
        }
    }
}

    而采用中心-半径形式的AABB,其旋转后的包围盒可参考下列代码:

//Transform AABB a by the matrix m and translation t,
//find maximum extents, and store result into AABB b.
void UpdateAABB(AABB a, float m[3][3], float t[3], AABB &b) {
    for(int i = 0; i < 3; i++) {
        b.c[i] = t[i];
        b.r[i] = 0.0f;
        for(int j = 0; j < 3; j++) {
            b.c[i] += m[i][j] * a.c[j];
            b.r[i] += Abs(m[i][j]) * a.r[j];
        }
    }
}
 

关于旋转矩阵

旋转矩阵M实际上代表仍以原点为原点设置新的坐标系

若M中x,y轴向量不是单位向量则会放大相应倍数

M = 

《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

旧坐标系上的点(以列表示)右乘矩阵,形成新坐标系上的点

new_A.x = M[0][0]*old_A.x + M[0][1]*old_A.y

new_A.y = M[1][0]*old_A.x + M[1][1]*old_A.y

《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

如下旋转矩阵

M =  {{ -1, 0}

           { 0 , 1}}

则新坐标系为x(-1,0)y(0,1)

点A(1,1)变成A(-1,1)

《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

2D图形进行测试,平移一定距离观察(否则跑到黑框外面啦,因为原点为左上角)。

左边为原物体以及AABB,右边为旋转后物体及新AABB

《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

其他测试

《实时碰撞检测算法技术》读书笔记(二):轴对齐包围盒(AABB)的计算与更新

可见由于新的AABB是基于旧的AABB得来,故不是十分紧密,而且多次旋转重构时,若不每次都使用最原始的AABB进行重构,而是使用新的AABB重构的话,将使AABB越来越大。