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

基于包围球的AABB

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

    该表达方式优点之一是：在更新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各端点。如下图：

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

旋转AABB后的重计算

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

    考查一个轴对齐包围盒A，且旋转矩阵M作用于A之上，结果是具有某一方向的旋转包围盒A。M的3个列（或行）给出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 = 

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

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

如下旋转矩阵

M =  {{ -1, 0}

           { 0 , 1}}

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

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

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

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

其他测试

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