基于凸包的最小有向包圍盒生成算法

秦啟飛，胡志剛

(中南大學(xué) 軟件學(xué)院，長沙 410075)

1 引 言

物體的包圍盒廣泛應(yīng)用于圖像處理、模式識(shí)別、碰撞檢測(cè)、模具分型設(shè)計(jì)和機(jī)械控制等領(lǐng)域[1,2].目前應(yīng)用最廣泛的OBB(Oriented Bounding Box，有向包圍盒)根據(jù)物體本身的幾何形狀來決定包圍盒的大小和方向，可以對(duì)原模型進(jìn)行緊湊的擬合[3].對(duì)于給定的三維點(diǎn)集，怎樣高效而準(zhǔn)確地得到其最小有向包圍盒一直是國內(nèi)外學(xué)者關(guān)注的問題[4].

一般考慮物體的所有頂點(diǎn)在空間的分布，通過不同的算法找到最佳方向，以確定OBB包圍盒的幾個(gè)軸.主要使用數(shù)值和統(tǒng)計(jì)優(yōu)化方法來找到非最優(yōu)，但在實(shí)際使用中足夠好的近似值.目前的主流方法是使用主成分分析(PCA)[5]，根據(jù)物體表面的頂點(diǎn)，計(jì)算特征向量來估計(jì)點(diǎn)集中最大擴(kuò)展的方向，并作為OBB的主軸.這個(gè)過程必須使用凸包上的連續(xù)集合表示來完成，否則近似值可能是無界差的[5].為了獲得接近最優(yōu)的結(jié)果，Barequet and HarPeled提出一個(gè)(1 +α)逼近方案[6]，而另一方面，Larsson和 Kallberg則提出可以采用預(yù)定義的啟發(fā)式方法來獲得更好的計(jì)算速度[7].國內(nèi)的陳柏松等[4]提出了基于非線性主成分分析的最小包圍盒計(jì)算方法，在計(jì)算時(shí)間和運(yùn)行結(jié)果上都取得了不錯(cuò)的效果，但是該方法利用了頂點(diǎn)之間的連接信息，無法處理無連接關(guān)系的點(diǎn)集數(shù)據(jù).

還有學(xué)者提出使用粒子群優(yōu)化[8]和遺傳算法[9]來計(jì)算最佳結(jié)果，取得了不錯(cuò)的效果.但這些算法中包含隨機(jī)因子，不能保證在所有情況下都找到最佳包圍盒.

法國的Chang等提出混合包圍盒旋轉(zhuǎn)識(shí)別算法HYBBRID，采用遺傳搜索方法對(duì)SO(3，)的所有方向的進(jìn)行暴力搜索[10].對(duì)于給定OBB的候選方向，將模型重復(fù)地投影到與當(dāng)前候選OBB的主軸相對(duì)應(yīng)的平面上，將其轉(zhuǎn)化為2D問題，使用Toussaint的旋轉(zhuǎn)卡尺方法[11]在線性時(shí)間內(nèi)進(jìn)行求解.這減少了暴力搜索的難度，將問題轉(zhuǎn)化為在單位半球中搜索較優(yōu)的起始方向向量.通過不斷重復(fù)計(jì)算得到最佳OBB的取向.然而，在該方法中搜索是在連續(xù)的空間上進(jìn)行的，不能通過對(duì)一組離散的取向進(jìn)行采樣.

綜合上述分析，已知的使用近似值，數(shù)值計(jì)算或啟發(fā)式方法的算法，效果都不夠出色.本文提出一種快速準(zhǔn)確的幾何算法來解決該問題.首先對(duì)三維點(diǎn)集的凸包進(jìn)行分析，總結(jié)了凸包和其最小體積有向包圍盒的4種邊面接觸類型.通過枚舉凸包所有邊可能的組合，選取包圍盒的最優(yōu)方向.實(shí)驗(yàn)證明，該算法可以快速生成符合模型體積特征的最小有向包圍盒，且擬合效果良好.

2 問題定義

2.1 問題描述

由于模型內(nèi)部的點(diǎn)對(duì)問題的解決沒有任何幫助，所以本研究基于凸包的邊上進(jìn)行操作.可以使用Quick Hull算法[12]或其改進(jìn)方法[13，14]在O(n log n)時(shí)間復(fù)雜度內(nèi)計(jì)算點(diǎn)集的凸包.

最小有向包圍盒生成問題定義如下：

輸入：三維點(diǎn)集構(gòu)成的凸包頂點(diǎn)集V

輸出：最小有向包圍盒O

2.2 相關(guān)符號(hào)與概念

為了更好地進(jìn)行后續(xù)討論，首先對(duì)相關(guān)符號(hào)和概念進(jìn)行介紹：

定義1.支持頂點(diǎn) (Supporting Vertices).在凸包中，方向向量n的方向上的一個(gè)或多個(gè)最高頂點(diǎn)，成為支持頂點(diǎn)，表示為Supp(n).

定義2.對(duì)向(Antipodal).對(duì)于兩個(gè)頂點(diǎn)v1和v2，如果存在一個(gè)方向向量n，使得v1∈Supp(n)和v2∈Supp(-n)，則稱v1和v2的位置關(guān)系為對(duì)向.其幾何描述為：如果可以找到封閉OBB的某個(gè)方向，使得凸包上的兩個(gè)頂點(diǎn)位于OBB的相對(duì)面上，則該兩個(gè)頂點(diǎn)是對(duì)向的.

定義3.側(cè)向(Sidepodal).對(duì)于兩個(gè)頂點(diǎn)v1和v2，如果存在兩個(gè)方向向量n1和n2，使得v1∈Supp(n1)，v2∈Supp(n2)，并且n1·n2=0，則稱v1和v2互為側(cè)向.其幾何含義是，對(duì)于一個(gè)閉合的OBB，如果可以找到一個(gè)方向使得頂點(diǎn)v1和v2位于該OBB相鄰的兩個(gè)相鄰面上，則稱v1和v2互為側(cè)向.

支持，對(duì)向和側(cè)向的概念同樣可以用來表示凸包的的邊和面的關(guān)系.如果一條邊e和頂點(diǎn)v分別位于該OBB的兩個(gè)相鄰面，那么也稱邊e和頂點(diǎn)v相互側(cè)向.

如果x是凸包的頂點(diǎn)或邊，則凸包中x的所有對(duì)向頂點(diǎn)的集合將表示為AntiV(x)，凸包中x的所有對(duì)向邊的集合表示為AntiE(x).同樣，SideV(x)和SideE(x)表示x所有側(cè)向的頂點(diǎn)和邊的集合.此外，對(duì)于上述的側(cè)向集合， SideV(e1，e2)表示集合的交集SideV(e1)∩ SideV(e2)的簡寫.顯然，如果一條邊e：v1→v2，是特征x的對(duì)向邊或側(cè)向邊，那么邊e上的頂點(diǎn)v1和v2也具有相同的性質(zhì).即：

如果：e∈AntiE(x)，那么：{v0，v1}∈AntiV(x)，

如果：e∈SideE(x)，那么：{v0，v1}∈SideV(x)，

如果：e∈SideE(x1;x2)，那么：{v0，v1}∈SideV(x1，x2).

因此，遍歷對(duì)向邊集或側(cè)向邊集，等效為遍歷其頂點(diǎn)的集合.值得注意的是，對(duì)于側(cè)向關(guān)系，反過來則不成立.即使兩個(gè)相鄰的頂點(diǎn)對(duì)于特征x是側(cè)向的，連接它們的邊卻不一定也與x側(cè)向.

符號(hào)N(v)表示頂點(diǎn)v的鄰居頂點(diǎn)集合.從凸包內(nèi)部測(cè)量的連接邊e的兩個(gè)相鄰面之間的角度通常稱為邊e的二面角(Dihedral Angle).因?yàn)橥拱峭剐?，所以所有的二面角的范圍都?0，180)內(nèi).最后，在邊e兩側(cè)指向凸包外側(cè)的兩個(gè)相鄰面的法線表示為f<(e)和f>(e).這些法向量具有以下屬性：

引理：如果OBB的面與凸包的邊e齊平，那么OBB的該面的(非歸一化的)法向量n為：

n=f<(e)+(f>(e)-f<(e))*t,t[0,1]

證明：該公式直接來自線性插值.t=0的值對(duì)應(yīng)于OBB與法向量f(e)的面齊平的情況，t=1的值對(duì)應(yīng)于與法向量f>(e)的面齊平的OBB.由于邊的二面角從不為0，所以線性內(nèi)插值不會(huì)產(chǎn)生簡并零向量.

實(shí)際上，我們可以使用幾何的方法將凸包的頂點(diǎn)和邊與支持函數(shù)相關(guān)聯(lián).

引理：給定凸包的一個(gè)頂點(diǎn)v和一條邊e，當(dāng)且僅當(dāng)存在一個(gè)方向向量n使得v∈Supp(n)且(n·f<(e))(n·f>(e))≤0時(shí)，頂點(diǎn)v∈Sidev(e).

證明：根據(jù)引理，與邊e齊平的OBB的面的法向量n2具有性質(zhì)：

n=f<(e)+(f>(e)-f<(e))*t.當(dāng)且僅當(dāng)存在向量n使得v∈Supp(n)和n·n2=0時(shí)，頂點(diǎn)v與邊e側(cè)向.將法向量進(jìn)行替換，給出下列公式：

n·(f<(e)+(f>(e)-f<(e))*t)=0,t[0,1]

(1)

公式左側(cè)是關(guān)于t的線性表達(dá)式，所以當(dāng)t取0和1時(shí)，表達(dá)式取得極限值，分別為：n·f<(e)和n·f<(e).因此，當(dāng)且僅當(dāng)n·f<(e)和n·f<(e)中一個(gè)為正數(shù)，一個(gè)為負(fù)數(shù)時(shí)，該方程有解.即：

n·f<(e)≤0，且n·f<(e)≥0，

或者n·f<(e)≥0，且n·f<(e)≤0.

無論哪種情況，將兩個(gè)表達(dá)式相乘就可以得到引理.

對(duì)于凸包的頂點(diǎn)和邊，不論是對(duì)向還是側(cè)向，都是非傳遞的關(guān)系.本文將通過對(duì)凸包的頂點(diǎn)圖進(jìn)行計(jì)算來得到相關(guān)關(guān)系，具體的實(shí)現(xiàn)算法在2.3節(jié)給出.

2.3 對(duì)向和側(cè)向關(guān)系判斷算法

基于2.2的論述，給出以下判斷頂點(diǎn)與邊和兩條邊是否為對(duì)向關(guān)系的算法：

圖1 算法AreAntipodal(v，e)

圖2 算法AntipodalDir(e1，e2)

圖3 算法AreSidepodal(e1，e2)

圖1中算法輸入為：頂點(diǎn)v，邊e；輸出為：頂點(diǎn)和邊是否是對(duì)向關(guān)系.圖2中算法輸入為：凸包的兩條邊e1，e2，輸出為：使得兩條滿足對(duì)向關(guān)系的單位向量.

同樣，可以使用圖三中算法來判斷兩條邊是否為側(cè)向關(guān)系.圖3中算法輸入為：凸包的邊e1，e2；輸出為：兩條邊是否是側(cè)向關(guān)系.

3 最小有向包圍盒生成算法

3.1 凸包與其OBB的4種接觸類別

該算法總體策略是：通過計(jì)算通過凸包邊的組合唯一確定OBB方向，而不是對(duì)球體中的所有可能定向方向進(jìn)行暴力搜索.

Freeman和Shapira[11]提出并證明了，在二維情況下，圖包的最小面積的包圍矩形的一條邊必定與凸包的一條邊共線，因而考慮凸包的每條邊，以此作為凸包的包圍矩形的一條邊.在三維情況下，通過對(duì)大量實(shí)例的分析，提出以下假設(shè)：

假設(shè)1：凸包至少有三條不同的邊，與其最小體積OBB包圍盒的表面共面，其中至少兩條邊位于OBB的相鄰面上.

該假設(shè)意味著凸包的特定邊e位于OBB的特定表面f上.基于上述假設(shè)，根據(jù)凸包及其封閉OBB的邊緣接觸不同情況，分為以下4個(gè)類別，與OBB接觸的邊以粗線條突出顯示：

圖4 凸包及其OBB的四種不同邊緣接觸示例

1)類別A：凸包三條邊位于OBB的三個(gè)相互相鄰的面.

該類別的實(shí)例如圖2-A所示，其中頂點(diǎn)坐標(biāo)為：

0：(1，0，2);1：(1，4，3);2：(4，0，4);3：(4，2，1);4：(3，2，0)

凸包的邊1→2，1→4和2→3位于OBB的三個(gè)相互相鄰的面，頂點(diǎn)0位于與邊1→2所在平面相對(duì)的面上.

2)類別B：凸包三條邊位于OBB的三個(gè)面，其中兩個(gè)是對(duì)面.

該類別的實(shí)例如圖2-B所示，其中頂點(diǎn)坐標(biāo)為：

0：(0，2，0);1：(0，2，2);2：(0，4，0);3：(2，0，2)

凸包的邊0→1，0→3和2→3位于OBB的三個(gè)面.其中，邊0→1和2→3位于兩個(gè)相對(duì)面.

3)類別C：凸包三條邊位于OBB兩個(gè)相鄰的面.

凸包的三條邊位于OBB的兩個(gè)相鄰面，即凸包的一個(gè)面和一條邊與OBB重合.該類別的實(shí)例如圖2-C所示，其中頂點(diǎn)坐標(biāo)為：

0：(0，0，0);1：(5，2，2);2：(5，5，0);3：(10，0，0)

凸包的三條邊位于頂點(diǎn)0→2→3形成的平面，頂點(diǎn)1位于該面的對(duì)面.需要注意的是，在上述示例中，相鄰面的交邊0→3，剛好位于凸包與OBB重合面，但這種情況不總是發(fā)生.

4)類別D：凸包兩條邊位于OBB三個(gè)面，其中兩個(gè)是對(duì)面.

OBB的三個(gè)不同面上僅與凸包的兩條邊齊平.這是一種特殊情況，其中凸包的邊與OBB的邊重合.此時(shí)，OBB上必須存在兩個(gè)包含凸包邊的對(duì)向面，否則將包圍盒和凸包沿公共共享邊投影到2D平面(將共享邊縮減至一點(diǎn))時(shí)，所得2D矩形沒有與所得2D多邊形的任何邊重合，因此不是最優(yōu)解.該類別的實(shí)例如圖2-D所示，其中頂點(diǎn)坐標(biāo)為：

0：(0，4，2);1：(0，4，4);2：(2，4，2);3：(3，0，1);4：(1，4，0)

在該示例中，最小體積OBB僅與凸包的兩條邊齊平，但是這些邊位于OBB的三個(gè)不同的面.頂點(diǎn)0是不與OBB接觸的內(nèi)部頂點(diǎn).

3.2 搜索最小封閉OBB包圍盒

通過搜索測(cè)試圖2所示的每種類別情況：

1)對(duì)于類別A和類別B：

對(duì)凸包中每條邊e1∈E進(jìn)行遍歷，尋找可能位于OBB的相鄰側(cè)面上的所有邊e2∈SideE(e1).然后，針對(duì)類別A，搜索OBB中與先前兩個(gè)面相互相鄰的第三個(gè)面上的所有邊e3∈SideE(e1,e2).對(duì)于類別B，搜索OBB中與邊e1接觸的面相對(duì)的第三面上的所有邊e3∈AntiE(e1).

2)對(duì)于類別C：

對(duì)凸包中面f∈F進(jìn)行遍歷.確定OBB的一個(gè)面法線n1.對(duì)邊集F中任意一邊e1，遍歷e3∈SideE(e1).

3)類別D：

類別D可以看作類別B中e1=e2時(shí)的特殊情況，因此在搜索類別B時(shí)隱式處理此類別，因此不需要單獨(dú)進(jìn)行測(cè)試.其幾何含義時(shí)，邊可能和自身是側(cè)向的.

執(zhí)行上述迭代的過程如圖5所示.

圖5 算法FindMinOBB(V，F(xiàn) ，E)

算法偽碼包含幾個(gè)中間過程函數(shù).函數(shù)ComputeBasis(e1，e2，e3)和函數(shù)CompleteBasis(n1，e)是兩個(gè)空間幾何計(jì)算函數(shù)，作用是通過3條邊或者1條邊和1個(gè)向量建立包圍盒的基底.函數(shù)ComputeOBB計(jì)算凸包的六個(gè)極端頂點(diǎn)，分別對(duì)應(yīng)OBB的每個(gè)面，為計(jì)算OBB的方向提供基礎(chǔ).使用Dobkin-Kirkpatrick層次數(shù)據(jù)結(jié)構(gòu)，最多需要O(log n)時(shí)間.函數(shù)RecordOBB是常數(shù)時(shí)間的計(jì)算，它計(jì)算新創(chuàng)建OBB的體積，與之前的記錄的OBB進(jìn)行比較，并存儲(chǔ)兩者中較小的一個(gè).

算法中輸入為：凸包頂點(diǎn)集V，表面集F，邊集E；輸出為：最小包圍盒OBB.算法包含兩個(gè)單獨(dú)的頂級(jí)循環(huán).第一個(gè)用(行1-行13)來處理類別A，B和D，第二個(gè)循環(huán)(行14-行21)處理類別C.在第一個(gè)循環(huán)結(jié)構(gòu)中，外層循環(huán)(行1-行13)確定凸包的一條邊，這是一個(gè)O(n)的操作.第二層循環(huán)(行2-行13)遍歷第一條邊的所有側(cè)向邊.時(shí)間復(fù)雜度為O(logn+|SideE(e1)|).

第一個(gè)最內(nèi)圈循環(huán)(3行-7行)針對(duì)類別A的情況進(jìn)行處理，時(shí)間復(fù)雜度為O(logn+|SideE(e1,e2)|).首先建立OBB的方向，對(duì)于給定的三條邊，調(diào)用函數(shù)ComputeBasis計(jì)算基底(n1,n2,n3).然后，調(diào)用函數(shù)ComputeOBB和RecordOBB處理該基底.

第二個(gè)最內(nèi)圈循環(huán)(行8-行13)針對(duì)分類B的情況進(jìn)行處理，時(shí)間復(fù)雜度為：O(logn+|AntiE(e1)|).對(duì)滿足條件的邊進(jìn)行迭代，首先使用算法2計(jì)算OBB一個(gè)面的法向量，通過函數(shù)ComputeBasis計(jì)算基底，然后調(diào)用函數(shù)ComputeOBB和RecordOBB完成計(jì)算.

最后，第二個(gè)頂級(jí)循環(huán)體(行14-行21)針對(duì)類別C進(jìn)行遍歷.凸包中每個(gè)面都可以直接確定一個(gè)法向量.內(nèi)圈循環(huán)(行17-行21)時(shí)間復(fù)雜度為：O(logn+|SideE(e1)|)，對(duì)邊e1的對(duì)向邊集進(jìn)行遍歷，為OBB的第二個(gè)軸的確定一個(gè)候選方向，以完成后續(xù)計(jì)算.

第一循環(huán)結(jié)構(gòu)中的步驟總數(shù)為：

|E|(logn+|SideE(e*)|)(logn+|SideE(e*,e*)|+|AntiE(e*)|)logn

第二個(gè)循環(huán)為|F|(logn+|SideE(e*)|)logn.在標(biāo)準(zhǔn)球型Sphere(n)數(shù)據(jù)集上，算法運(yùn)行時(shí)間是O(n3/2(logn)2).在最壞的情況下2，如在圓柱型Cylinder(n)數(shù)據(jù)集的情況下，算法運(yùn)行在O(n3logn)時(shí)間.

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文進(jìn)行了大量的實(shí)驗(yàn)來測(cè)試算法的擬合效果和執(zhí)行效率.實(shí)驗(yàn)使用C++編程語言和開源軟件包MathGeoLib[15]實(shí)現(xiàn)，所有實(shí)驗(yàn)均運(yùn)行于Dell T700 型號(hào)PC機(jī)器，處理器為Intel Core i7 3.6GHz，內(nèi)存為16GB，操作系統(tǒng)為Windows 10專業(yè)版.測(cè)試程序使用Microsoft Visual Studio 2017編譯器構(gòu)建，采用64位編譯，所有基準(zhǔn)測(cè)試中均為單線程執(zhí)行.

實(shí)驗(yàn)選用兩個(gè)不同的數(shù)據(jù)集進(jìn)行驗(yàn)證，分別為：1.標(biāo)準(zhǔn)球體數(shù)據(jù)Sphere(n)，n表示凸包中頂點(diǎn)數(shù)量，模型通過程序自動(dòng)生成.2.GAMMA Group 3D網(wǎng)格研究數(shù)據(jù)庫[16]，包含5個(gè)不同的類別的數(shù)據(jù)集，共計(jì)2088種不同的3D模型，包括：

·來自數(shù)據(jù)集2001的55個(gè)模型.

·來自數(shù)據(jù)集ANIMALS.的381個(gè)模型.

·來自數(shù)據(jù)集ARCHITEC的530個(gè)模型.

·來自數(shù)據(jù)集GEOMETRY.的437個(gè)模型.

·來自數(shù)據(jù)集MECHANICAL的685個(gè)模型.

4.2 實(shí)驗(yàn)結(jié)果分析

對(duì)于標(biāo)準(zhǔn)球型數(shù)據(jù)集Sphere(n)，首先采用Quick Hull算法計(jì)算凸包頂點(diǎn)，然后使用本文所述算法搜索其最小體積OBB包圍盒，以下所有指標(biāo)均不包括運(yùn)行Quick Hull算法所需的時(shí)間.如圖5所示，對(duì)于相同半徑的球體，當(dāng)凸包頂點(diǎn)數(shù)達(dá)到500時(shí)，已經(jīng)可以較好地還原物體形狀.而本文所述算法搜索到的最小體積封閉OBB包圍盒，可以對(duì)所有的凸包進(jìn)行緊密的包圍，取得了良好的效果.

圖6 Sphere(n)數(shù)據(jù)集OBB示例 圖7 數(shù)據(jù)集Sphere(n) 中計(jì)算最小體積OBB耗時(shí)

算法運(yùn)行時(shí)性能如圖6所示，其中X軸表示數(shù)據(jù)凸包中頂點(diǎn)的數(shù)量，Y軸表示計(jì)算OBB所對(duì)應(yīng)的時(shí)間，實(shí)際數(shù)據(jù)以細(xì)線繪制.結(jié)果表明，當(dāng)凸包頂點(diǎn)數(shù)在10000以下時(shí)，算法表現(xiàn)與預(yù)期的O(n3/2(logn)2)性能回歸曲線有較好的匹配.由于包圍盒僅取決于模型的凸包，因此先將GAMMA Group真實(shí)模型數(shù)據(jù)集中的模型進(jìn)行預(yù)處理.

圖8 GAMMA Group模型OBB示例

算法的擬合效果如圖8所示，可以看出對(duì)復(fù)雜物體模型，算法所計(jì)算出的包圍盒也可以進(jìn)行非常緊密的包圍.圖9中散點(diǎn)圖顯示了算法的性能情況，X軸為該對(duì)象的凸包上的點(diǎn)數(shù)，Y軸表示計(jì)算OBB所需的時(shí)間(秒).這個(gè)基準(zhǔn)測(cè)試的結(jié)果表明，大多數(shù)現(xiàn)實(shí)世界模型對(duì)象的計(jì)算性能與Sphere(n)的情況非常相似.如圖9所示在參與測(cè)試的2088個(gè)模型中，大部分模型表現(xiàn)接近最佳預(yù)期.

圖9 GAMMA Group數(shù)據(jù)集下計(jì)算最小體積OBB耗時(shí)

在GAMMA Group數(shù)據(jù)庫的5個(gè)不同數(shù)據(jù)集中，分別對(duì)本文所提算法和文獻(xiàn)[10]中的HYBBRID算法進(jìn)行對(duì)比試驗(yàn)，包圍效果如圖10所示.因?yàn)槟Ｐ蛡€(gè)體形狀差異較大，所以選取算法在不同數(shù)據(jù)集中最優(yōu)、中等和最差各情況表現(xiàn)比較所得OBB包圍盒與原模型的體積之比，比值越小表示可以更緊密的包圍.其中Optimal、Median、Max為本文所提算法數(shù)據(jù)，與之對(duì)比的是HYBBRID Optimal、HYBBRID Median、HYBBRID Max 三個(gè)指標(biāo).從圖中可以看出，本算法在最優(yōu)情況下，包圍效果與HYBBRID算法相同或者略優(yōu)；在中位數(shù)情況下明顯優(yōu)于HYBBRID算法；在最壞情況下，表現(xiàn)比HYB-BRID算法略差.而從圖11可以看出，在5個(gè)不同的數(shù)據(jù)集上，本算法的平均耗時(shí)均低于HYBBRID算法，具有更好的計(jì)算性能.

圖10 與HYBBRID算法包圍效果對(duì)比

圖11 與HYBBRID算法性能對(duì)比

5 總結(jié)與展望

本文首先對(duì)三維點(diǎn)集凸包中點(diǎn)線面關(guān)系進(jìn)行分析，總結(jié)了凸包與其最小OBB包圍盒的4種邊面接觸類型.并提出了一種計(jì)算三維點(diǎn)數(shù)據(jù)的最小定向包圍盒的新算法，該方法首先針對(duì)輸入點(diǎn)集構(gòu)造凸包，通過快速迭代凸包邊的組合，唯一確定OBB的最優(yōu)方向.最后通過實(shí)驗(yàn)證明，該算法能夠精確地找到所有模型的最小OBB包圍盒，且具有更好的性能表現(xiàn).

該算法是一個(gè)離散的過程，不使用連續(xù)統(tǒng)計(jì)的數(shù)值優(yōu)化或迭代.因此，該方法是穩(wěn)定和可預(yù)測(cè)的.同時(shí)，與以前公開的結(jié)果不同，該方法相對(duì)容易實(shí)現(xiàn)，并且可以以不同的方法對(duì)其進(jìn)行編程，以平衡實(shí)現(xiàn)復(fù)雜度與運(yùn)行時(shí)復(fù)雜度.

此外，因?yàn)樗惴ㄔ谕拱倪吋仙现蛔x順序遍歷，它可以很容易被改寫為并行算法，因此也適用于處理大數(shù)據(jù)集.

針對(duì)模型極端復(fù)雜的場(chǎng)景，該算法的包圍效果還存在進(jìn)一步優(yōu)化空間.且該算法只適用于計(jì)算最小體積OBB包圍盒，暫未考慮對(duì)于追求最小表面積的OBB包圍盒場(chǎng)景.因此，后續(xù)研究可以就復(fù)雜模型的包圍優(yōu)化，以及針對(duì)最小表面積情況進(jìn)行進(jìn)一步探索.