• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2018-11-15 12:23:08秦啟飛胡志剛
    關(guān)鍵詞:側(cè)向頂點(diǎn)類別

    秦啟飛,胡志剛

    (中南大學(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)槟P蛡€(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)一步探索.

    猜你喜歡
    側(cè)向頂點(diǎn)類別
    軍航無人機(jī)與民航航班側(cè)向碰撞風(fēng)險(xiǎn)評(píng)估
    過非等腰銳角三角形頂點(diǎn)和垂心的圓的性質(zhì)及應(yīng)用(下)
    關(guān)于頂點(diǎn)染色的一個(gè)猜想
    彎月薄鏡的側(cè)向支撐
    側(cè)向風(fēng)場(chǎng)中無人機(jī)的飛行研究
    基于 L1自適應(yīng)控制的無人機(jī)橫側(cè)向控制
    服務(wù)類別
    新校長(2016年8期)2016-01-10 06:43:59
    論類別股東會(huì)
    商事法論集(2014年1期)2014-06-27 01:20:42
    中醫(yī)類別全科醫(yī)師培養(yǎng)模式的探討
    聚合酶鏈?zhǔn)椒磻?yīng)快速鑒別5種常見肉類別
    国产日韩一区二区三区精品不卡| 亚洲欧美一区二区三区国产| 亚洲国产精品国产精品| 国产成人精品福利久久| 日本色播在线视频| 青青草视频在线视频观看| 丝袜脚勾引网站| 欧美成人午夜免费资源| 亚洲精品美女久久av网站| 天天躁夜夜躁狠狠久久av| 日韩大片免费观看网站| 大片免费播放器 马上看| 99热这里只有是精品在线观看| 国产xxxxx性猛交| 久久精品人人爽人人爽视色| 一区在线观看完整版| 欧美精品av麻豆av| 狂野欧美激情性bbbbbb| 考比视频在线观看| 亚洲精品视频女| 国产欧美另类精品又又久久亚洲欧美| 日本欧美国产在线视频| 成人综合一区亚洲| 男女下面插进去视频免费观看 | 国产日韩欧美视频二区| 午夜免费观看性视频| 中文字幕另类日韩欧美亚洲嫩草| 久久久久视频综合| videossex国产| 晚上一个人看的免费电影| 亚洲精华国产精华液的使用体验| 日韩人妻精品一区2区三区| 久久久久视频综合| 亚洲欧美中文字幕日韩二区| 久久这里有精品视频免费| 免费观看在线日韩| 午夜激情久久久久久久| 国产 精品1| 在线观看一区二区三区激情| 亚洲欧美一区二区三区黑人 | 成人无遮挡网站| 三上悠亚av全集在线观看| 国产伦理片在线播放av一区| 欧美人与性动交α欧美精品济南到 | 国产精品无大码| av一本久久久久| 国产精品久久久久久精品电影小说| 丁香六月天网| 大话2 男鬼变身卡| 国产亚洲午夜精品一区二区久久| 九色亚洲精品在线播放| 国产成人午夜福利电影在线观看| 欧美亚洲 丝袜 人妻 在线| 国产男女内射视频| 秋霞在线观看毛片| 伦精品一区二区三区| 18在线观看网站| 国产亚洲最大av| 国产 精品1| 成年女人在线观看亚洲视频| 精品人妻偷拍中文字幕| 黑人猛操日本美女一级片| 在现免费观看毛片| 又黄又爽又刺激的免费视频.| 国产精品.久久久| 如日韩欧美国产精品一区二区三区| 国产高清国产精品国产三级| 人妻系列 视频| 久久精品aⅴ一区二区三区四区 | 精品一区二区三区四区五区乱码 | 考比视频在线观看| 亚洲精品日韩在线中文字幕| 精品第一国产精品| 女人被躁到高潮嗷嗷叫费观| 国产成人精品福利久久| 色吧在线观看| 国产精品久久久久成人av| 乱码一卡2卡4卡精品| 国产高清不卡午夜福利| 日韩不卡一区二区三区视频在线| 精品国产国语对白av| 国产精品久久久久久久久免| 大香蕉久久网| 亚洲精品乱久久久久久| 国产精品熟女久久久久浪| 亚洲国产毛片av蜜桃av| 欧美精品人与动牲交sv欧美| 中文字幕最新亚洲高清| 人妻系列 视频| 欧美激情 高清一区二区三区| 亚洲精品久久久久久婷婷小说| 欧美另类一区| 亚洲欧美日韩另类电影网站| 国产又色又爽无遮挡免| 亚洲精品,欧美精品| 国产亚洲最大av| 天堂俺去俺来也www色官网| 久久亚洲国产成人精品v| 只有这里有精品99| 成人18禁高潮啪啪吃奶动态图| 亚洲欧美日韩另类电影网站| 伦精品一区二区三区| 如日韩欧美国产精品一区二区三区| 日本av手机在线免费观看| 91精品国产国语对白视频| 国产精品一二三区在线看| 国产不卡av网站在线观看| 欧美日韩成人在线一区二区| 久久午夜综合久久蜜桃| 国产成人欧美| 久久久久久久久久久免费av| 国产男人的电影天堂91| 97精品久久久久久久久久精品| 日韩一区二区视频免费看| 高清黄色对白视频在线免费看| 亚洲精品乱久久久久久| 51国产日韩欧美| 欧美变态另类bdsm刘玥| 午夜av观看不卡| 在线观看美女被高潮喷水网站| 婷婷成人精品国产| 国产一区二区三区综合在线观看 | 91成人精品电影| 99国产综合亚洲精品| 亚洲av男天堂| 国产片特级美女逼逼视频| 男女无遮挡免费网站观看| 男女下面插进去视频免费观看 | videosex国产| 一级毛片 在线播放| 一级毛片我不卡| 欧美精品高潮呻吟av久久| 亚洲国产精品一区二区三区在线| 各种免费的搞黄视频| 精品一区二区三区视频在线| 欧美激情 高清一区二区三区| 制服诱惑二区| av国产久精品久网站免费入址| 国产乱人偷精品视频| 人体艺术视频欧美日本| www.熟女人妻精品国产 | 一本色道久久久久久精品综合| 亚洲精品国产av成人精品| 国产免费又黄又爽又色| 日产精品乱码卡一卡2卡三| 色视频在线一区二区三区| 女的被弄到高潮叫床怎么办| 日本免费在线观看一区| 成人漫画全彩无遮挡| 如何舔出高潮| 成年美女黄网站色视频大全免费| 精品一区在线观看国产| 国产精品蜜桃在线观看| 欧美日韩一区二区视频在线观看视频在线| 91久久精品国产一区二区三区| 少妇熟女欧美另类| 欧美激情极品国产一区二区三区 | 国产精品人妻久久久久久| 两性夫妻黄色片 | 18+在线观看网站| 日本av免费视频播放| 91在线精品国自产拍蜜月| 亚洲av在线观看美女高潮| 久久人妻熟女aⅴ| 有码 亚洲区| 99热6这里只有精品| 亚洲精品美女久久久久99蜜臀 | 成人综合一区亚洲| 99香蕉大伊视频| 亚洲国产最新在线播放| 免费看不卡的av| 国产 一区精品| 卡戴珊不雅视频在线播放| 91成人精品电影| 纵有疾风起免费观看全集完整版| 免费av中文字幕在线| a级毛色黄片| 国产一区二区三区综合在线观看 | 免费人成在线观看视频色| 久久免费观看电影| 亚洲精品av麻豆狂野| 精品亚洲乱码少妇综合久久| 精品人妻偷拍中文字幕| 免费观看性生交大片5| 欧美成人午夜免费资源| 最近最新中文字幕大全免费视频 | 看十八女毛片水多多多| 日韩av免费高清视频| 一级黄片播放器| 97超碰精品成人国产| 最黄视频免费看| 亚洲精品国产av成人精品| 精品人妻在线不人妻| 免费人妻精品一区二区三区视频| 黄色怎么调成土黄色| 国产乱人偷精品视频| 精品国产露脸久久av麻豆| 街头女战士在线观看网站| 啦啦啦中文免费视频观看日本| 欧美xxxx性猛交bbbb| 男女无遮挡免费网站观看| 日本与韩国留学比较| 美女福利国产在线| 久久久欧美国产精品| 亚洲熟女精品中文字幕| 精品一区二区三区视频在线| 国产免费现黄频在线看| 欧美另类一区| 国产日韩欧美亚洲二区| 91aial.com中文字幕在线观看| 精品卡一卡二卡四卡免费| 亚洲丝袜综合中文字幕| 少妇被粗大猛烈的视频| 9热在线视频观看99| 在线天堂中文资源库| 桃花免费在线播放| 国产69精品久久久久777片| 少妇高潮的动态图| 狂野欧美激情性xxxx在线观看| 国产精品蜜桃在线观看| 婷婷色麻豆天堂久久| 免费观看无遮挡的男女| 热99久久久久精品小说推荐| 最近最新中文字幕免费大全7| 欧美xxxx性猛交bbbb| 黄色一级大片看看| 搡老乐熟女国产| 男人舔女人的私密视频| 亚洲精品视频女| av国产久精品久网站免费入址| 久久久精品免费免费高清| 久久精品国产自在天天线| 国产亚洲精品久久久com| 少妇被粗大的猛进出69影院 | 欧美成人午夜精品| 中文字幕另类日韩欧美亚洲嫩草| 制服人妻中文乱码| 丁香六月天网| 久久99精品国语久久久| 欧美 亚洲 国产 日韩一| 精品少妇黑人巨大在线播放| 亚洲综合色网址| 欧美亚洲日本最大视频资源| 日韩av在线免费看完整版不卡| 欧美亚洲 丝袜 人妻 在线| 嫩草影院入口| 亚洲,欧美,日韩| 18禁裸乳无遮挡动漫免费视频| 妹子高潮喷水视频| 99国产综合亚洲精品| 国产高清国产精品国产三级| 免费少妇av软件| 如日韩欧美国产精品一区二区三区| 亚洲欧美清纯卡通| 午夜福利,免费看| 成人国语在线视频| 天天躁夜夜躁狠狠躁躁| 亚洲精品乱码久久久久久按摩| 美女内射精品一级片tv| 国产成人精品一,二区| 亚洲成人av在线免费| 日韩av在线免费看完整版不卡| 少妇被粗大的猛进出69影院 | 亚洲欧洲国产日韩| 久久99热这里只频精品6学生| 在线免费观看不下载黄p国产| 国产av一区二区精品久久| 国产一区二区三区综合在线观看 | av线在线观看网站| 欧美xxⅹ黑人| 久久人人爽人人爽人人片va| 曰老女人黄片| 熟女av电影| 美女主播在线视频| 亚洲欧美日韩卡通动漫| 久久精品国产亚洲av天美| 99视频精品全部免费 在线| 亚洲综合色网址| 亚洲国产成人一精品久久久| 最近最新中文字幕大全免费视频 | 欧美成人精品欧美一级黄| 不卡视频在线观看欧美| 一级毛片 在线播放| 人妻一区二区av| videosex国产| 97在线视频观看| 亚洲图色成人| 日本午夜av视频| 亚洲人与动物交配视频| 大陆偷拍与自拍| 成人漫画全彩无遮挡| 成人综合一区亚洲| 亚洲成国产人片在线观看| 九色亚洲精品在线播放| 免费观看在线日韩| 欧美日韩视频高清一区二区三区二| 日日啪夜夜爽| 搡女人真爽免费视频火全软件| 久久人人爽人人片av| 久久久久久久久久人人人人人人| 久久热在线av| 亚洲人成网站在线观看播放| 又粗又硬又长又爽又黄的视频| 99久久人妻综合| 午夜av观看不卡| 一二三四在线观看免费中文在 | av免费观看日本| 久久国内精品自在自线图片| 天天影视国产精品| 欧美3d第一页| 男人舔女人的私密视频| xxxhd国产人妻xxx| 日韩免费高清中文字幕av| 熟女av电影| 99热国产这里只有精品6| 熟女人妻精品中文字幕| 国产不卡av网站在线观看| 1024视频免费在线观看| 最近中文字幕高清免费大全6| 黄网站色视频无遮挡免费观看| 人人妻人人爽人人添夜夜欢视频| 精品国产乱码久久久久久小说| 美女福利国产在线| 欧美97在线视频| 免费高清在线观看视频在线观看| 人人妻人人添人人爽欧美一区卜| 女人被躁到高潮嗷嗷叫费观| 成人亚洲精品一区在线观看| 亚洲综合色网址| 一边摸一边做爽爽视频免费| 看十八女毛片水多多多| 免费不卡的大黄色大毛片视频在线观看| 丝袜脚勾引网站| 欧美+日韩+精品| www.色视频.com| a级毛片黄视频| 不卡视频在线观看欧美| 亚洲伊人久久精品综合| 免费日韩欧美在线观看| 亚洲精华国产精华液的使用体验| 中文字幕人妻熟女乱码| 国产精品嫩草影院av在线观看| 97超碰精品成人国产| 少妇被粗大猛烈的视频| www日本在线高清视频| 欧美老熟妇乱子伦牲交| 五月伊人婷婷丁香| 在现免费观看毛片| 精品少妇黑人巨大在线播放| 亚洲av.av天堂| www日本在线高清视频| 一区二区日韩欧美中文字幕 | 精品久久久久久电影网| 中文乱码字字幕精品一区二区三区| 18禁国产床啪视频网站| 大话2 男鬼变身卡| 国产激情久久老熟女| 中文字幕亚洲精品专区| 99国产综合亚洲精品| 精品一区二区三区四区五区乱码 | 最新的欧美精品一区二区| 久久久久人妻精品一区果冻| 欧美3d第一页| 亚洲av电影在线进入| 色婷婷av一区二区三区视频| av电影中文网址| 日韩欧美一区视频在线观看| 婷婷色麻豆天堂久久| av在线播放精品| 97在线人人人人妻| 男女免费视频国产| 久久热在线av| 黑人巨大精品欧美一区二区蜜桃 | 久久青草综合色| tube8黄色片| 永久免费av网站大全| 黄片播放在线免费| 韩国精品一区二区三区 | 免费观看性生交大片5| 97在线人人人人妻| freevideosex欧美| 久久97久久精品| 国产成人精品一,二区| 亚洲av中文av极速乱| 多毛熟女@视频| 97精品久久久久久久久久精品| 午夜福利,免费看| 中文字幕人妻熟女乱码| 亚洲成人手机| 欧美 日韩 精品 国产| 成人亚洲精品一区在线观看| 一本—道久久a久久精品蜜桃钙片| 在现免费观看毛片| 精品人妻在线不人妻| 街头女战士在线观看网站| 久久久久久久精品精品| 久久精品久久久久久久性| 成人免费观看视频高清| 亚洲伊人久久精品综合| 最近2019中文字幕mv第一页| 在线精品无人区一区二区三| 亚洲精品国产色婷婷电影| 丝袜喷水一区| 日韩中文字幕视频在线看片| 国产成人精品一,二区| 成人国语在线视频| 在线观看一区二区三区激情| 大码成人一级视频| 在线观看一区二区三区激情| 亚洲综合色网址| 国产又爽黄色视频| 18禁裸乳无遮挡动漫免费视频| videos熟女内射| 一区二区av电影网| 新久久久久国产一级毛片| 少妇人妻 视频| 中文字幕亚洲精品专区| 精品国产一区二区久久| 亚洲美女搞黄在线观看| 亚洲国产精品专区欧美| 十八禁高潮呻吟视频| www.色视频.com| 内地一区二区视频在线| 国产一区亚洲一区在线观看| 午夜影院在线不卡| 亚洲内射少妇av| kizo精华| 中文字幕av电影在线播放| 夫妻性生交免费视频一级片| 中文乱码字字幕精品一区二区三区| 一级,二级,三级黄色视频| 久久久精品区二区三区| 成人国产麻豆网| 日本91视频免费播放| 少妇的逼好多水| 国产精品不卡视频一区二区| 亚洲色图综合在线观看| 色网站视频免费| 在线观看免费高清a一片| 久久精品aⅴ一区二区三区四区 | 国产亚洲最大av| 久久精品久久久久久久性| 亚洲国产精品一区二区三区在线| 看免费av毛片| 亚洲人成网站在线观看播放| 日韩大片免费观看网站| 国产日韩欧美视频二区| 免费高清在线观看日韩| 国产精品欧美亚洲77777| 80岁老熟妇乱子伦牲交| 国产一区有黄有色的免费视频| 日韩大片免费观看网站| 欧美97在线视频| 国产成人免费观看mmmm| 九九爱精品视频在线观看| 婷婷色综合大香蕉| 色视频在线一区二区三区| 久久久久精品人妻al黑| av电影中文网址| 久久精品国产鲁丝片午夜精品| 五月伊人婷婷丁香| 久久精品久久精品一区二区三区| 色94色欧美一区二区| 久久青草综合色| 久久女婷五月综合色啪小说| 91精品国产国语对白视频| 精品国产露脸久久av麻豆| 啦啦啦视频在线资源免费观看| 香蕉丝袜av| 久久午夜福利片| 国产成人精品一,二区| 中文字幕最新亚洲高清| 亚洲丝袜综合中文字幕| 亚洲精品久久午夜乱码| 日韩精品免费视频一区二区三区 | 亚洲国产色片| 色94色欧美一区二区| www日本在线高清视频| 国产高清不卡午夜福利| 国产精品久久久久久精品电影小说| 亚洲成人av在线免费| a 毛片基地| 人体艺术视频欧美日本| 久久久久国产精品人妻一区二区| 欧美xxⅹ黑人| 欧美丝袜亚洲另类| 欧美亚洲 丝袜 人妻 在线| 熟妇人妻不卡中文字幕| 少妇被粗大猛烈的视频| 精品一区二区三卡| 久久久久视频综合| 国产伦理片在线播放av一区| 丰满迷人的少妇在线观看| 久久亚洲国产成人精品v| 亚洲美女黄色视频免费看| 久久综合国产亚洲精品| 十八禁网站网址无遮挡| 一本大道久久a久久精品| 波野结衣二区三区在线| 黄色视频在线播放观看不卡| 男女下面插进去视频免费观看 | 亚洲av日韩在线播放| 国产国拍精品亚洲av在线观看| 另类亚洲欧美激情| 国产国拍精品亚洲av在线观看| 99re6热这里在线精品视频| 久久人人爽av亚洲精品天堂| 色94色欧美一区二区| 国产精品久久久久久av不卡| 精品人妻偷拍中文字幕| 欧美xxxx性猛交bbbb| 久久久久精品久久久久真实原创| 国产精品久久久久久精品电影小说| 中文天堂在线官网| 王馨瑶露胸无遮挡在线观看| 最近中文字幕2019免费版| 亚洲五月色婷婷综合| 伊人亚洲综合成人网| 国产精品国产三级国产专区5o| 国产黄频视频在线观看| 97精品久久久久久久久久精品| 免费播放大片免费观看视频在线观看| 国产成人欧美| 亚洲精品色激情综合| videos熟女内射| 久久影院123| 91成人精品电影| 久久人人爽人人爽人人片va| 亚洲在久久综合| 精品少妇内射三级| 一级,二级,三级黄色视频| 少妇 在线观看| 极品人妻少妇av视频| 亚洲精品一区蜜桃| 制服人妻中文乱码| 97超碰精品成人国产| 亚洲国产最新在线播放| 日韩,欧美,国产一区二区三区| 精品第一国产精品| 亚洲人成77777在线视频| 国国产精品蜜臀av免费| 一级黄片播放器| 亚洲成av片中文字幕在线观看 | 一区二区三区乱码不卡18| 天天影视国产精品| 国产成人精品福利久久| 久久热在线av| 丝瓜视频免费看黄片| 一级片免费观看大全| av国产久精品久网站免费入址| 成年女人在线观看亚洲视频| 亚洲美女黄色视频免费看| 男人爽女人下面视频在线观看| 熟女电影av网| 欧美另类一区| 在线亚洲精品国产二区图片欧美| 又粗又硬又长又爽又黄的视频| 欧美精品高潮呻吟av久久| 日本av手机在线免费观看| 黄色一级大片看看| 欧美xxxx性猛交bbbb| 久久久亚洲精品成人影院| 成年av动漫网址| 亚洲国产精品专区欧美| 人人妻人人爽人人添夜夜欢视频| 男女国产视频网站| 国产高清不卡午夜福利| 王馨瑶露胸无遮挡在线观看| 久久99蜜桃精品久久| 久久人人爽人人片av| 中文欧美无线码| 午夜精品国产一区二区电影| 又大又黄又爽视频免费| 国产又色又爽无遮挡免| 国产成人av激情在线播放| 纵有疾风起免费观看全集完整版| 午夜福利视频精品| 日产精品乱码卡一卡2卡三| 中文字幕精品免费在线观看视频 | 亚洲五月色婷婷综合| 亚洲精华国产精华液的使用体验| 国产精品成人在线| 啦啦啦在线观看免费高清www| 在线观看一区二区三区激情| av天堂久久9| 国产不卡av网站在线观看| 精品少妇久久久久久888优播| 日韩精品免费视频一区二区三区 | 国产精品一国产av| 国产成人a∨麻豆精品| 成人免费观看视频高清| 精品第一国产精品| 日韩精品免费视频一区二区三区 | 七月丁香在线播放| 国产一级毛片在线| 中文字幕人妻熟女乱码| 侵犯人妻中文字幕一二三四区| 久久久久久久久久成人| 亚洲精品久久午夜乱码| 亚洲欧美成人精品一区二区| 七月丁香在线播放| www日本在线高清视频| 色94色欧美一区二区| 日日爽夜夜爽网站| 五月开心婷婷网| 丰满迷人的少妇在线观看| 欧美 日韩 精品 国产| 97在线视频观看| a级片在线免费高清观看视频| 美国免费a级毛片| 欧美bdsm另类| 精品人妻一区二区三区麻豆| 久久青草综合色| 欧美最新免费一区二区三区| 国产一级毛片在线|