PCL：基于PCL绘制包围盒基础介绍（1）
包圍盒顧名思義就是類似一個盒子把物體包圍起來。
以下內(nèi)容來自百科：
包圍盒是一種求解離散點集最優(yōu)包圍空間的算法，基本思想是用體積稍大且特性簡單的幾何體（稱為包圍盒）來近似地代替復(fù)雜的幾何對象。
常見的包圍盒算法有AABB包圍盒、包圍球、方向包圍盒OBB以及固定方向凸包FDH。碰撞檢測問題在虛擬現(xiàn)實、計算機(jī)輔助設(shè)計與制造、游戲及機(jī)器人等領(lǐng)域有著廣泛的應(yīng)用，甚至成為關(guān)鍵技術(shù)。而包圍盒算法是進(jìn)行碰撞干涉初步檢測的重要方法之一。
分類：
最常見的包圍盒算法有AABB包圍盒（Axis-aligned bounding box軸對齊包圍盒），包圍球（Sphere）， 方向包圍盒OBB（Oriented bounding box）以及固定方向凸包FDH（Fixed directions hulls或k-DOP）。
AABB是應(yīng)用最早的包圍盒。它被定義為包含該對象，且邊平行于坐標(biāo)軸的最小六面體（坐標(biāo)軸平行不僅指盒體與世界坐標(biāo)軸平行，同時也指盒體的每個面都和一條坐標(biāo)軸垂直。同一物體的不同方向，AABB也可能不同。如果物體在場景中移動變換，它的AABB也需要隨之移動，當(dāng)物體發(fā)生旋轉(zhuǎn)時，有兩種選擇，用變換后的物體來重新計算AABB，或者對AABB做和物體同樣的變換）。故描述一個AABB，僅需六個標(biāo)量。AABB構(gòu)造比較簡單，存儲空間小，但緊密性差，尤其對不規(guī)則幾何形體，冗余空間很大，當(dāng)對象旋轉(zhuǎn)時，無法對其進(jìn)行相應(yīng)的旋轉(zhuǎn)。處理對象是剛性并且是凸的，不適合包含軟體變形的復(fù)雜的虛擬環(huán)境情況。
AABB內(nèi)的點需要滿足xyz分別滿足分別大于最小的小于最大的。因此需要知道兩個頂點最小點，最大點；中心點是兩個頂點的中點代表了包圍盒的質(zhì)心。
對象的包圍球被定義為包含該對象的最小的球體。確定包圍球，首先需分別計算組成對象的基本幾何元素集合中所有元素的頂點的x，y，z坐標(biāo)的均值以確定包圍球的球心，再由球心與三個最大值坐標(biāo)所確定的點間的距離確定半徑r。包圍球的碰撞檢測主要是比較兩球間半徑和與球心距離的大小。（由于球體只有一個自由度，所以檢測球?qū)ξ矬w方向不敏感。）
OBB是較為常用的包圍盒類型。它是包含該對象且相對于坐標(biāo)軸方向任意的最小的長方體（OBB是根據(jù)物體本身的幾何形狀來決定盒子的大小和方向，盒子不需要和坐標(biāo)軸垂直）。OBB最大特點是它的方向的任意性，這使得它可以根據(jù)被包圍對象的形狀特點盡可能緊密的包圍對象，但同時也使得它的相交測試變得復(fù)雜。OBB包圍盒比AABB包圍盒和包圍球更加緊密地逼近物體，能比較顯著地減少包圍體的個數(shù)，從而避免了大量包圍體之間的相交檢測。但OBB之間的相交檢測比AABB或包圍球體之間的相交檢測更費時。
FDH（k-DOP）是一種特殊的凸包，繼承了AABB簡單性的特點，但其要具備良好的空間緊密度，必須使用足夠多的固定方向。被定義為包含該對象且它的所有面的法向量都取自一個固定的方向(k個向量)集合的凸包。FDH比其他包圍體更緊密地包圍原物體，創(chuàng)建的層次樹也就有更少的節(jié)點，求交檢測時就會減少更多的冗余計算，但相互間的求交運算較為復(fù)雜。
優(yōu)缺點：
AABB也是比較簡單的一類包圍盒。但對于沿斜對角方向放置的瘦長形對象，其緊密性較差。由于AABB相交測試的簡單性及較好的緊密性，因此得到了廣泛的應(yīng)用，還可以用于軟體對象的碰撞檢測。
包圍球是比較簡單的包圍盒，而且當(dāng)對象發(fā)生旋轉(zhuǎn)運動時，包圍球不需做任何更新，當(dāng)幾何對象進(jìn)行頻繁的旋轉(zhuǎn)運動時，使用包圍球可能會得到很好的結(jié)果；當(dāng)對象變形時，需要重新計算其包圍球。但它的緊密性是比較差的，因此較少使用。
OBB的簡單性要比上面兩種包圍盒差，但它的緊密性是比較好的，可以大大減少參與相交測試的包圍盒的數(shù)目，因此總體性能要優(yōu)于AABB和包圍球。當(dāng)幾何對象發(fā)生旋轉(zhuǎn)運動后，只要對OBB進(jìn)行同樣的旋轉(zhuǎn)即可。因此，對于剛體間的碰撞檢測，OBB不失為一種較好的選擇，但迄今為止，還沒有一種有效的方法能夠較好地解決對象變形后OBB樹的更新問題，而重新計算每個結(jié)點的OBB的代價又太大，所以O(shè)BB不適用于包含軟體對象的復(fù)雜環(huán)境中。
FDH相對于上面三種包圍盒其緊密性是最好的，同時其相交測試算法比OBB要簡單的多。可以用于軟體對象的碰撞檢測。
基于PCA的包圍盒實現(xiàn)：原理如下：
OBB的生成思路簡單來說就是根據(jù)物體表面的頂點，通過PCA（主成分分析）獲得特征向量，即OBB的主軸。
最小包圍盒的計算過程大致如下:
1.利用PCA主元分析法獲得點云的三個主方向，獲取質(zhì)心，計算協(xié)方差，獲得協(xié)方差矩陣，求取協(xié)方差矩陣的特征值和特長向量，特征向量即為主方向。
2.利用1中獲得的主方向和質(zhì)心，將輸入點云轉(zhuǎn)換至原點，且主方向與坐標(biāo)系方向重回，建立變換到原點的點云的包圍盒。
3.給輸入點云設(shè)置主方向和包圍盒，通過輸入點云到原點點云變換的逆變換實現(xiàn)。
1.1、計算出來的協(xié)方差
主對角線的元素表示變量的方差。主對角線的元素較大則表示強(qiáng)信號。非主對角線的元素表示變量之間的協(xié)方差。較大的非對角線元素表示數(shù)據(jù)的畸變。
為了減小畸變，可以重新定義變量間的線性組合，將協(xié)方差矩陣對角化。協(xié)方差矩陣的的元素是實數(shù)并且對稱。
協(xié)方差矩陣的特征向量表示OBB包圍盒的方向。大的特征值對應(yīng)大的方差，所以應(yīng)該讓OBB包圍盒沿著最大特征值對應(yīng)的特征向量的方向。
求均值
協(xié)方差矩陣
協(xié)方差矩陣
對協(xié)方差矩陣特征分解
單位向量是指模等于1的向量。由于是非零向量，單位向量具有確定的方向。單位向量有無數(shù)個。
一個非零向量除以它的模，可得所需單位向量。一個單位向量的平面直角坐標(biāo)系上的坐標(biāo)表示可以是：(n,k) ，則有n2+k2=1。
計算出來的特征向量進(jìn)行正交標(biāo)準(zhǔn)化。（單位向量）
2.1、將各點的（x,y,z）坐標(biāo)投影到計算出的坐標(biāo)軸上，求出中心和半長度。小（x,y,z表示點）大（XYZ表示標(biāo)準(zhǔn)化后找到的主方向）
做投影要用到與單位向量的內(nèi)積（點乘），b向量在a向量方向上的投影：內(nèi)積的幾何意義：做投影和兩向量之間的夾角。
為了確定最大和最小的范圍，可以通過計算每個頂點位置坐標(biāo)與單位向量（XYZ）的內(nèi)積來完成。（可以分別求出XYZ的最大最小值）
邊界盒的尺寸就是X,Y,Z三個方向上(XYZ表示找到的三個主方向即單位向量)相應(yīng)內(nèi)積的最大值與最小值之差，邊界盒的中心O就是三對反向平面中三個平面的交點。令a,b,c分別為X,Y,Z上最大值與最小值的平均值：
那么中心點坐標(biāo)就是O=aX+bY+cZ(兩向量做投影/點乘/內(nèi)積)。
最小包圍盒頂點計算的過程大致如下:
1.輸入點云轉(zhuǎn)換至遠(yuǎn)點后,求得變換后點云的最大最小x,y,z軸的坐標(biāo),此時(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)
即為變換后點云的包圍盒,也是原始輸入點云包圍盒頂點坐標(biāo)經(jīng)過變化后的坐標(biāo).
2.將上述求得的6個包圍盒坐標(biāo)逆變換回輸入點云的坐標(biāo)系,即得到原始輸入點云的包圍盒頂點坐標(biāo).
PS：說明一下
PCA在很多地方還可以用到，筆者覺得了協(xié)方差矩陣、特征值、特征向量的幾何意義是理解PCA的關(guān)鍵。上述代碼中還用到四元數(shù)，四元數(shù)主要用于旋轉(zhuǎn)變化
參照博客：https://blog.csdn.net/qq_16775293/article/details/82801240
?
?
總結(jié)
以上是生活随笔為你收集整理的PCL：基于PCL绘制包围盒基础介绍（1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： PCA（3）：PCA实现C++代码
- 下一篇： PCL：基于PCL绘制包围盒代码实现（2