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