基于包围球的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越来越大。