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

胡志剛 秦啟飛

摘 ???要：針對(duì)復(fù)雜物體三維點(diǎn)集的建模問題，提出一種基于凸包的最小體積的封閉有向包圍盒生成算法.對(duì)凸包和其最小體積有向包圍盒的關(guān)系進(jìn)行分析，總結(jié)了其4種邊面接觸類型.通過枚舉凸包中邊的所有可能的組合，唯一確定包圍盒的最優(yōu)方向.實(shí)驗(yàn)證明，該算法可以快速生成符合模型體積特征的最小有向包圍盒，且擬合效果良好.

關(guān)鍵詞：有向包圍盒;幾何計(jì)算;凸包;三維點(diǎn)集;圖搜索

中圖分類號(hào)：TP30 ?????????????????????????????文獻(xiàn)標(biāo)志碼：A

Algorithm for Finding Minimum Volume Oriented

Bounding Boxes Based on Convex Hull

HU Zhigang，QIN Qifei

（School of Software，Central South University，Changsha 410083，China）

Abstract： A new method was presented for computing the tight-fitting enclosing minimum volume oriented bounding boxes for constructing the model of complex object point sets in three dimensions. The relationship between the convex hull and its minimum volume oriented bounding box with the smallest volume was analyzed，and four kinds of edge contact types were summarized. The optimal box orientations are uniquely determined by combinations of edges in the convex hull of the input point set. Empirical evidence shows that this process always yields the globally minimum bounding box by volume feature， which concludes that this method provides a good simulation.

Key words： oriented bounding box;computational geometry;convex hull;three-dimensional point set;graph search

物體的包圍盒廣泛應(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)確地得到其最小有向包圍盒一直是國(guó)內(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 和HarPeled提出一個(gè)（1+α）逼近方案[6]，而另一方面，Larsson和 K？覿llberg則提出可以采用預(yù)定義的啟發(fā)式方法來獲得更好的計(jì)算速度[7].國(guó)內(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ī)因子，不能保證在所有情況下都找到最佳包圍盒.

法國(guó)的Chang等提出混合包圍盒旋轉(zhuǎn)識(shí)別算法HYBBRID，采用遺傳搜索方法對(duì)SO（3，R）的所有方向進(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)證明，該算法可以快速生成符合模型體積特征的最小有向包圍盒，且擬合效果良好.

1 ??系統(tǒng)模型及問題描述

1.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，邊集E，表面集F;

輸出：最小有向包圍盒O.

1.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，則稱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）的簡(jiǎn)寫.顯然，如果一條邊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，x1）.

因此，遍歷對(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)橥拱峭剐?，所以所有的二面角的范圍都在?，180）內(nèi).最后，在邊e兩側(cè)指向凸包外側(cè)的兩個(gè)相鄰面的法線表示為f <（e）和f ?>（e）.這些法向量具有以下屬性：

引理1 ??如果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)生簡(jiǎn)并零向量.

證畢.

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

引理2 ??給定凸包的一個(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ù)引理2，與邊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á)式相乘就可以得到引理2.

證畢

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

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

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

圖1中算法輸入為：頂點(diǎn)v，邊e;輸出為：頂點(diǎn)和邊是否是對(duì)向關(guān)系.圖2中算法輸入為：凸包的兩條邊e1，e2，輸出為：使得兩條滿足對(duì)向關(guān)系的單位向量.同樣，可以使用圖3中算法來判斷兩條邊是否為側(cè)向關(guān)系.圖3中算法輸入為：凸包的邊e1，e2;輸出為：兩條邊是否是側(cè)向關(guān)系.

2 ??最小體積有向包圍盒生成算法

2.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接觸的邊以粗線條突出顯示：

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

該類別的實(shí)例如圖4-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í)例如圖4-B所示，其中頂點(diǎn)坐標(biāo)為：

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

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

凸包的三條邊位于OBB的兩個(gè)相鄰面，即凸包的一個(gè)面和一條邊與OBB重合.該類別的實(shí)例如圖4-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í)例如圖4-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).

2.2 ??搜索最小體積封閉OBB包圍盒

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

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

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

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所示.算法偽碼包含幾個(gè)中間過程函數(shù).函數(shù)ComputeBasis（e1，e2，e3） 和函數(shù)CompleteBasis（n1，e）是兩個(gè)空間幾何計(jì)算函數(shù)，作用是通過三條邊或者一條邊和一個(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（log n + SideE（e1））.

第一個(gè)最內(nèi)圈循環(huán)（3行-7行）針對(duì)類別A的情況進(jìn)行處理，時(shí)間復(fù)雜度為O（log n + 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（log n + 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（log n + SideE（e1）），對(duì)邊e1的對(duì)向邊集進(jìn)行遍歷，為OBB的第二個(gè)軸確定一個(gè)候選方向，以完成后續(xù)計(jì)算.

第一循環(huán)結(jié)構(gòu)中的步驟總數(shù)為：E（log n + SideE（e*））（log n+SideE（e*，e*）+AntiE（e*））log n，

第二個(gè)循環(huán)為F（log n + SideE（e*））log n. 在

標(biāo)準(zhǔn)球型Sphere（n）數(shù)據(jù)集上，算法運(yùn)行時(shí)間是

O（n3/2（log n）2）. 在最壞的情況下，如在圓柱型Cylinder（n）數(shù)據(jù)集的情況下，算法運(yùn)行在O（n3 log n）時(shí)間.

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

3.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.6 GHz，內(nèi)存為16 GB，操作系統(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ù)庫(kù)[16]，包含5個(gè)不同類別的數(shù)據(jù)集，共計(jì)2 088種不同的3D模型.

1）55個(gè)模型來自數(shù)據(jù)集2001;

2）381個(gè)模型來自數(shù)據(jù)集ANIMALS;

3）530個(gè)模型來自數(shù)據(jù)集ARCHITEC;

4）437個(gè)模型來自數(shù)據(jù)集GEOMETRY;

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

3.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í)間.如圖6所示，對(duì)于相同半徑的球體，當(dāng)凸包頂點(diǎn)數(shù)達(dá)到500時(shí)，已經(jīng)可以較好地還原物體形狀.而本文所述算法搜索到的最小體積封閉OBB包圍盒，可以對(duì)所有的凸包進(jìn)行緊密的包圍，取得了良好的效果.

算法運(yùn)行時(shí)性能如圖7所示，其中X軸表示數(shù)據(jù)凸包中頂點(diǎn)的數(shù)量，Y軸表示計(jì)算OBB所對(duì)應(yīng)的時(shí)間，實(shí)際數(shù)據(jù)以細(xì)線繪制.結(jié)果表明，當(dāng)凸包頂點(diǎn)數(shù)在10 000以下時(shí)，算法表現(xiàn)與預(yù)期的O（n3/2（log n）2）性能回歸曲線有較好的匹配.

由于包圍盒僅取決于模型的凸包，因此先將GAMMA Group真實(shí)模型數(shù)據(jù)集中的模型進(jìn)行預(yù)處理.

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

在GAMMA Group數(shù)據(jù)庫(kù)的5個(gè)不同數(shù)據(jù)集中，分別對(duì)本文所提算法和文獻(xiàn)[10]中的HYBBRID算法進(jìn)行對(duì)比試驗(yàn)，包圍效果如圖10所示.因?yàn)槟Ｐ蛡€(gè)體形狀差異較大，所以選取算法在不同數(shù)據(jù)集中最優(yōu)情況，中位數(shù)情況和最差表現(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)比HYBBRID算法略差.而從圖11可以看出，在5個(gè)不同的數(shù)據(jù)集上，本算法的平均耗時(shí)均低于HYBBRID算法，具有更好的計(jì)算性能.

4 ??總結(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)一步探索.

參考文獻(xiàn)

[1] ???史旭升，喬立紅，朱作為. 基于改進(jìn)OBB包圍盒的碰撞檢測(cè)算法[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，41（5）：26—31.

SHI X S，QIAO L H，ZHU Z W. Algorithm of collision detection based on improved oriented bounding box [J]. Journal of Hunan University（Natural Sciences），2014，41（5）：26—31.（In Chinese）

[2] ???陳華. 確定任意形狀物體最小包圍盒的一種方法[J]. 工程圖學(xué)學(xué)報(bào)，2010，31（2）：49—53.

CHEN H. A method to generate the minimum bounding boxes for shape-arbitrary objects [J]. Journal of Engineering Graphics，2010，31（2）：49—53. （In Chinese）

[3] ???O′ROUKRE J. Finding minimal enclosing boxes[J]. International Journal of Computer & Information Sciences，1985，14（3）：183—199.

[4] ???陳柏松，葉雪梅，安利. 基于非線性主成分分析的最小包圍盒計(jì)算方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2010，16（11）：2375—2378.

CHEN B S，YE X M，AN L. Minimum bounding box calculation based on nonlinear principle component analysis [J]. Computer Integrated Manufacturing Systems，2010，16（11）：2375—2378. （In Chinese）

[5] ??DIMITROV D，KNAUER C，KRIEGEL K，et al. Bounds on the quality of the PCA bounding boxes[J]. Computational Geometry Theory & Applications，2009，42（8）：772—789.

[6] ???BAREQUET G，HAR-PELED S. Efficiently approximating the minimum[J]. Journal of Algorithms，2001，38（1）：91—109.

[7] ???LARSSON T，KLLBERG L. Fast computation of tight fitting oriented bounding boxes[J]. Game Engine Gems，2011，2： 3—19.

[8] ???BORCKMANS P B，ABSIL P A. Oriented bounding box computation using particle swarm optimization[C]//European Symposium on Artificial Neural Networks. Bruges，Belgium，2010.

[9] ???孫殿柱，史陽，劉華東，等. 基于遺傳算法的散亂點(diǎn)云最小包圍盒求解[J]. 北京航空航天大學(xué)學(xué)報(bào)，2013，39（8）：995—998.

SUN D Z，SHI Y，LIU H D，et al. Solution of minimum bounding box of scattered points based on genetic algorithm [J]. Journal of Beijing University of Aeronautics and Astronautics，2013，39（8）：995—998. （In Chinese）

[10] ?CHANG C T，GORISSEN B，MELCHIOR S. Fast oriented bounding box optimization on the rotation group SO（3，R）[J]. ACM Transactions on Graphics，2011，30（5）：1—16.

[11] ?FREEMAN H， SHAPIRA R. Determining the minimum-area encasing rectangle for an arbitrary closed curve[J]. Communications of the ACM， 1975， 18（7）：409—413.

[12] ?BARBER C B，DOBKIN D P，HUHDANPAA H. The quickhull algorithm for convex hulls[J]. ACM Transactions on Mathematical Software，1996，22（4）：469—483.

[13] ?IMAI H，IRI M. Polygonal approximations of a curve[J]. Computational Morphology，2014，6（1）： 71—86.

[14] ?李仁忠，楊曼，劉陽陽，等. 一種散亂點(diǎn)云的均勻精簡(jiǎn)算法[J]. 光學(xué)學(xué)報(bào)，2017，37（7）：89—97.

LI R Z，YANG M，LIU Y ?Y，et al. An uniform simplification algorithm for scattered point cloud[J]. Acta Optica Sinica，2017，37（7）：89—97. （In Chinese）

[15] ?A C++ library for linear algebra and geometry manipulation for computer graphics[EB/OL]. https：//github.com/juj/MathGeoLib. 2017 March.

[16] ?GAMMA GROUP，2008. 3D meshes research database. [EB/OL]. https：//www-roc.inria.fr/gamma/gamma/download/ download.php.