01 概述
包圍盒是一種求解離散點集最優包圍空間的算法，基本思想是用體積稍大且特性簡單的幾何體（稱為包圍盒）來近似地代替復雜的幾何對象。常見的包圍盒算法有AABB包圍盒、包圍球、有向包圍盒OBB以及固定方向凸包FDH。
圖1. 3D包圍盒
圖2. 2D包圍盒
OBB這種方法是根據物體本身的幾何形狀來決定盒子的大小和方向，盒子無需和坐標軸垂直。這樣就可以選擇最合適、最緊湊的包容盒子。OBB盒子的生成比較復雜。一般是考慮物體所有的頂點在空間的分布，通過一定的算法找到最好的方向(OBB盒子的幾個軸)。
包圍球是用球體包圍整個幾何體, 無論是幾何體還是相交測試都很簡單，但是它的緊密性太差。因為除了在3 個坐標軸上分布得比較均勻的幾何體外, 幾乎都會留下較大的空隙，需要花費大量的預處理時間，以構造一個好的層次結構逼近對象。當物體變形之后，包圍球不需要重新計算。因此，它是使用得比較少的一種包圍盒。當對象發生旋轉運動時，包圍球不需作任何更新，這是包圍球的較優秀特性；當幾何對象進行頻繁的旋轉運動時，采用包圍球可能得到較好結果。
AABB就是3D一個簡單的六面體，每一邊都平行于一個坐標平面，矩形邊界框不一定都是立方體，它的長、寬、高可以彼此不同。
02 包圍盒在3D點云分割中的應用
-
三維點云分割是將同屬性的點云物體分割出來，以便于單獨對該點云物體處理，以下是借助PCL點云庫尋找點云的最小包圍盒的實現原理。
-
最小包圍盒的計算過程大致如下：
-
利用PCA主元分析法獲得點云的三個主方向，獲取質心，計算協方差，獲得協方差矩陣，求取協方差矩陣的特征值和特長向量，特征向量即為主方向。
-
利用獲得的主方向和質心，將輸入點云轉換至原點，且主方向與坐標系方向重合，建立變換到原點的點云的包圍盒。
-
給輸入點云設置主方向和包圍盒，通過輸入點云到原點點云變換的逆變換實現。
-
輸入點云轉換至遠點后，求得變換后點云的最大最小x,y,z軸的坐標,如 (max.x,max.y,max.z),(max.x,min.y,max.z),(max.x,max.y,min.z),(min.x,max.y,max.z),(min.x,max.y,min.z),(min.x,min.y,max.z),(min.x,min.y,max.z),(min.x,min.y,min.z)，即為變換后點云的包圍盒，也是原始輸入點云包圍盒頂點坐標經過變化后的坐標。將上述求得的８個包圍盒坐標逆變換回輸入點云的坐標系，即得到原始輸入點云的包圍盒頂點坐標。
實現效果如下圖：
圖3. 點云分割前
圖4. 點云分割后
03 包圍盒在碰撞檢測中的應用
在碰撞檢測中，為減少計算消耗，在進行相交測試前，可以先進行粗略的包圍體（BV）測試。對于某些應用程序，包圍體測試足以提供碰撞檢測依據。一般情況下，包圍體計算須采用預處理而非實時計算。當包圍體所包含的對象移動時，一些包圍體需要實現空間重對齊。
包圍體的期望特征：
-
低消耗的相交測試
-
實現緊密擬合
-
計算耗費較少
-
易于旋轉和變換
-
內存占用較少
包圍體主要包含球體、軸對齊包圍盒（AABB）、有向包圍盒（OBB）、8-DOP以及凸殼，以下僅對軸對齊包圍盒（AABB）在碰撞檢測的實現原理。
軸對齊包圍盒（AABB）是應用最廣泛的包圍體之一。其最大特點是能實現快速的相交測試，即僅執行相應的坐標值之間的比較。
軸對齊包圍盒（AABB）有3種常規表達方式：
1.采用各坐標軸上的最小值和最大值
//region R = (x,y,z) | min.x <= x <= max.x, min.y <= y <= max.y, min.z <= z <= max.z
struct AABB {
Point min;
Point max;
};
AABB間的相交測試
bool Collision(AABB a, AABB b) {
//Exit with no intersection if separated along an axis
if(a.max[0] < b.min[0] || a.min[0] > b.max[0]) return false;
if(a.max[1] < b.min[1] || a.min[1] > b.max[1]) return false;
if(a.max[2] < b.min[2] || a.min[2] > b.max[2]) return false;
//Overlapping on all axes means AABs are intersecting
return true;
}
2.采用一個最小頂點值和直徑范圍dx,dy,dz
//region R = (x,y,z) | min.x <= x <= min.x + dx, min.y <= y <= min.y + dy, min.z <= z <= min.z + z
struct AABB {
Point min;
float d[3];
};
AABB間的相交測試
bool Collision(AABB a, AABB b) {
float t;
if((t = a.min[0] - b.min[0]) > b.d[0] || -t > a.d[0]) return false;
if((t = a.min[1] - b.min[1]) > b.d[1] || -t > a.d[0]) return false;
if((t = a.min[2] - b.min[2]) > b.d[2] || -t > a.d[0]) return false;
return true;
}
3.給定AABB的中心點C，以及各軸向半徑rx,ry,rz
//region R = (x, y, z) | |c.x - x| <= rx, |c.y - y| <= ry, |c.z - z| <= rz
struct AABB {
Point c;
float r[3];
};
AABB間的相交測試
bool Collision(AABB a, AABB b) {
if(Abs(a.c[0] - b.c[0]) > (a.r[0] + b.r[0])) return false;
if(Abs(a.c[1] - b.c[1]) > (a.r[1] + b.r[1])) return false;
if(Abs(a.c[2] - b.c[2]) > (a.r[2] + b.r[2])) return false;
return true;
}
對于需要執行大量相交測試的碰撞檢測系統，可根據狀態的相似性對測試進行排序。例如：如果相應操作基本出現在xz平面，則y坐標測試應最后執行，從而使狀態的變化降低到最小程度。
若物體只是以平移方式運動，與“最大-最小值”方式相比，另外兩種更加方便——只需要更新6個參數中的3個（即Point中的x,y,z）。
對于AABB的計算與更新，在此僅列出以下4種基本方法：
-
使用固定尺寸且較為松散的AABB包圍物體對象
-
基于原點確定動態且緊湊的重構方式
-
利用爬山法確定動態且緊湊的重構方式
-
基于旋轉后的AABB，確定近似且動態的重構方式