【doc】空間封閉點(diǎn)云的八象限三角剖分算法

1、空間封閉點(diǎn)云的八象限三角剖分算法第l4卷第3期2009年6月哈爾濱理工大學(xué)journalofharbinuniversityofscienceandtechnologyvo1.14no.3jun.2009空間封閉點(diǎn)云的八象限三角剖分算法關(guān)明山,周波,韓娜,王洋,陳新河(黑龍江科技學(xué)院計(jì)算機(jī)與信息工程學(xué)院,黑龍江哈爾濱150027)摘要:提出了一種針對(duì)空間封閉點(diǎn)云的三角剖分算法.該算法首先根據(jù)空間封閉點(diǎn)云的分布特征,將其劃分到三維坐標(biāo)的八個(gè)象限中,使每部分點(diǎn)云的包角均小于180.;然后適當(dāng)旋轉(zhuǎn)各部分點(diǎn)云,使其對(duì)應(yīng)投影平面面積最大化,再運(yùn)用平面三角剖分方法對(duì)其進(jìn)行三角剖分,從而得到各部分點(diǎn)云的剖分

2、結(jié)果;最后將已處理的各部分用三角面片對(duì)其邊界進(jìn)行縫合,進(jìn)而形成空間封閉點(diǎn)云的立體三角化.實(shí)驗(yàn)結(jié)果表明,該方法剖分速度快,形成的三角網(wǎng)格質(zhì)量高,能夠較好地再現(xiàn)原三維物體的表面特征.關(guān)鍵詞:封閉點(diǎn)云;散亂點(diǎn)集;平面三角剖分;立體三角剖分中圖分類(lèi)號(hào):tp391文獻(xiàn)標(biāo)志碼:a文章編號(hào):10072683(2009)03002005eightquadrantstriangulationalgorithmaboutspaceclosedpoint-cloudguanmingshan,zhoubo,hanna,wang,chenxinhe(departmentofcomputerandinformatione

3、ngineering,heilongjianginstituteofscienceandtechnology,harbin150027,china)abstract:thispaperputsforwardatriangulationalgorithmusedforspaceclosedpoint-cloud.atfirstthisal-gorithmaccordingdistributingcharactersofspace3dunorganizedpointsets,dividsspaceclosedpointcloudintoeightquadrantsandpointcloudembr

4、acedcentralangleofeachpartislessthan180degrees.thenthedividedpointcloudsarerevolvedproperlyinordertomaximizeprojectionarea,andtriangulatedbyplanetriangulationalgorithmgettingtheresultoftriangulation.intheendthetriangulatedparts'boundaryaresewnupusingtrianglermingthefinaltridimensionaltriangulari

5、zationofspaceclosedpointcloud.theresultprovesthatthisalgorithmprocessestriangulationrapidly,formshighqualitytrianglegridandreproducesinitial3dobject'sexternalcharacteristic.keywords:closedpointcloud;unorganizedpointset;planetriangulation;tridimensionaltriangularizationl引言空間散亂點(diǎn)的三角剖分是計(jì)算機(jī)幾何領(lǐng)域中的重要課題

6、之一,它廣泛應(yīng)用于計(jì)算機(jī)輔助設(shè)計(jì)(cad),醫(yī)學(xué)成像,逆向工程及計(jì)算機(jī)視覺(jué)等領(lǐng)域,也是當(dāng)前計(jì)算機(jī)在圖形圖像方向研究的一個(gè)熱點(diǎn)和收稿日期:20080912基金項(xiàng)目:黑龍江省教育廳科學(xué)研究項(xiàng)目(11511354)作者簡(jiǎn)介:關(guān)明山(1974),男,講師;周波(1963),男,教授.難點(diǎn).對(duì)于空間散亂點(diǎn)的三角剖分,國(guó)內(nèi)外相關(guān)專(zhuān)家,學(xué)者經(jīng)過(guò)多年研究,積累了大量成功的經(jīng)驗(yàn),其中絕大多數(shù)是基于delaunay三角化的剖分算法.文14為國(guó)外關(guān)于三角剖分比較有代表性的算法,國(guó)內(nèi)對(duì)空間曲面重構(gòu)的研究也取得了很大進(jìn)展5.總的看來(lái),空問(wèn)散亂點(diǎn)的三角剖分方法可劃分為直接剖分法和平面投影法兩大類(lèi).直接剖分法基本思想是第3

7、期關(guān)明山,等:空間封閉點(diǎn)云的八象限三角剖分算法21直接由三維點(diǎn)構(gòu)造三角面片,最終連接成空間曲面;平面投影法基本思想是將空間三維點(diǎn)云投影到某平面上,然后對(duì)投影點(diǎn)集做平面三角剖分.上述關(guān)于空間散亂點(diǎn)的三角剖分方法很多,優(yōu)化準(zhǔn)則也有數(shù)種,但無(wú)論是直接剖分法還是平面投影法,都只針對(duì)空間曲面片的點(diǎn)云做三角剖分,對(duì)于空問(wèn)自封閉散亂點(diǎn)云的三角剖分尚在探索之中,而醫(yī)學(xué)成像,逆向工程等實(shí)際問(wèn)題恰恰需要對(duì)三維物體進(jìn)行整個(gè)表面的重建.為此,本文提出一種基于分治思想的八象限空間立體三角剖分算法,有效解決了空間閉合曲面的三角剖分問(wèn)題.2基本概念本文所涉及到的一些基本概念如下:1)平面曲線包角:平面曲線擬合圓上對(duì)應(yīng)該曲線

8、的那段圓弧所對(duì)應(yīng)的圓心角即為平面曲線包角.當(dāng)平面曲線是閉合的時(shí)候,該平面曲線的包角為360.2)點(diǎn)云的包角:對(duì)于攝像機(jī)或者ccd獲取的一片點(diǎn)云數(shù)據(jù),通過(guò)點(diǎn)云擬合球體的球心及點(diǎn)云幾何中心的平面與點(diǎn)云交線所對(duì)應(yīng)的包角中最大的角即為點(diǎn)云的包角.一般攝像機(jī),ccd一次獲取的一片點(diǎn)云包角都小于180.3)點(diǎn)云朝向:對(duì)于攝像機(jī)或者ccd獲取的一片點(diǎn)云數(shù)據(jù),其外邊緣線(只有一條且封閉)上的所有點(diǎn)擬合成一個(gè)平面的法向方向就為點(diǎn)云的朝向.4)圓準(zhǔn)則:嚴(yán)格凸的四邊形中的3個(gè)點(diǎn)確定一個(gè)圓,如果第4個(gè)頂點(diǎn)落在圓內(nèi),則將第四個(gè)頂點(diǎn)與其相對(duì)的頂點(diǎn)相連,否則將另兩個(gè)相對(duì)頂點(diǎn)相連,從而得到兩個(gè)優(yōu)化的三角形.如圖1所示.日3算

9、法實(shí)現(xiàn)圖1圓準(zhǔn)則示意圖3.1基本數(shù)據(jù)結(jié)構(gòu)1)點(diǎn)云數(shù)組(ca).ca用來(lái)臨時(shí)存儲(chǔ)點(diǎn)云數(shù)據(jù),每個(gè)元素能夠存儲(chǔ)一個(gè)空間點(diǎn)的三維信息.2)投影表(pn).pn代表pnxrangeyrange二維數(shù)組,每個(gè)元素為一鏈表指針,該鏈表用來(lái)臨時(shí)存儲(chǔ)一個(gè)網(wǎng)格內(nèi)投影進(jìn)來(lái)的所有點(diǎn)信息.xrange,yrange表示平面投影沿,y方向的網(wǎng)格個(gè)數(shù).3)待連接點(diǎn)鏈表(tlp).tlp用來(lái)臨時(shí)存儲(chǔ)平面網(wǎng)格中待連接點(diǎn)的三維信息及一個(gè)bool類(lèi)型的域,初始化為false,表示此網(wǎng)格中無(wú)待連接點(diǎn).4)三角形鏈表(tl).tl用來(lái)存儲(chǔ)三角剖分的結(jié)果,每個(gè)節(jié)點(diǎn)包含一個(gè)剖分三角形的三個(gè)頂點(diǎn)信息以及該三角形的法矢量信息.5)起止位置表(

10、be).be代表bexrange2二維數(shù)組,用來(lái)存儲(chǔ)投影網(wǎng)格中每一行待連接點(diǎn)的起止位置,初始化為一1.t6)邊界循環(huán)鏈表(bl).bl用來(lái)存儲(chǔ)每片點(diǎn)云邊界點(diǎn)(按逆時(shí)針順序加人)的信息.7)內(nèi)邊界表(tib)和外邊界表(tob).用來(lái)臨時(shí)存儲(chǔ)縫合曲面的內(nèi),外邊界點(diǎn)的鏈表.3.2算法的實(shí)現(xiàn)過(guò)程1)讀人點(diǎn)云并檢測(cè)點(diǎn)云空間大小:讀入點(diǎn)云數(shù)據(jù)并保存到ca中.循環(huán)查看ca,計(jì)算點(diǎn)云包圍盒的length,width,height值.據(jù)此再結(jié)合程序的要求,確定在,y,z方向上所要?jiǎng)澐志W(wǎng)格的數(shù)目,就可以算出每個(gè)投影平面上網(wǎng)格的長(zhǎng)和寬,即將投影面上的網(wǎng)格劃分好,等待空間點(diǎn)的投影.2)分割點(diǎn)云:首先依據(jù)下式,即.=

11、p.x/n=0.y=p.y/ni=0.z=p.z/ni=o求出整個(gè)點(diǎn)云集的重心.p(,y,).其中p是點(diǎn)云中的點(diǎn),凡為點(diǎn)云中點(diǎn)的個(gè)數(shù).如圖2所示,過(guò)重心p(,y,z),沿,y,三個(gè)坐標(biāo)軸方向做三個(gè)相互垂直的平面y,l,一z和z,這三個(gè)互相垂直的平面將整個(gè)點(diǎn)云分割在8個(gè)區(qū)域中,將這8個(gè)區(qū)域中的點(diǎn)云數(shù)據(jù)分別存人ca1一ca8八個(gè)數(shù)組中,這八個(gè)數(shù)組元素的數(shù)據(jù)結(jié)構(gòu)和ca完全一樣.圖2點(diǎn)云分割圖22哈爾濱理工大學(xué)第l4卷3)旋轉(zhuǎn)投影及平面剖分:點(diǎn)云經(jīng)過(guò)分割,形成八個(gè)朝向各異,包角都小于180.的部分點(diǎn)云,可以用平面網(wǎng)格法對(duì)每部分進(jìn)行三角化.為優(yōu)化程序,也防止同一部分點(diǎn)云不同位置的點(diǎn)在投影時(shí)發(fā)生重疊,在投

12、影前對(duì)每塊部分點(diǎn)云都進(jìn)行適當(dāng)?shù)男D(zhuǎn),使其點(diǎn)云朝向正對(duì)某個(gè)平面,以保證各塊部分點(diǎn)云三角化的曲面片法向矢量的一致性,以及投影面積最大化.對(duì)于旋轉(zhuǎn)后的部分點(diǎn)云中的每一點(diǎn),利用其旋轉(zhuǎn)坐標(biāo)的值和平面上網(wǎng)格的長(zhǎng),寬,即可計(jì)算出該點(diǎn)投影的網(wǎng)格位置,進(jìn)而將點(diǎn)加入該網(wǎng)格.將這八個(gè)象限的部分點(diǎn)云投影分別記錄在pn1至pn8中.由于這時(shí)投影進(jìn)同一個(gè)單元網(wǎng)格中的點(diǎn)可能不止一個(gè),為了能夠連接出最優(yōu)的三角面片,取網(wǎng)格最中間的點(diǎn)做為平面網(wǎng)格剖分的待連接點(diǎn).將選取的八塊部分點(diǎn)云的待連接點(diǎn)分別存進(jìn)數(shù)組tlp1一tlp8中.此時(shí),空間曲面的三角剖分問(wèn)題就轉(zhuǎn)化為平面三角剖分問(wèn)題.最后對(duì)記錄待連接點(diǎn)的數(shù)組進(jìn)行遍歷,分別找到每個(gè)待連接

13、點(diǎn)的下鄰接點(diǎn)進(jìn)行三角形的連接,并用圓的準(zhǔn)則進(jìn)行優(yōu)化,計(jì)算出三角形的單位法向量,再將三角形的三個(gè)頂點(diǎn)和單位法向量記錄進(jìn)tl中.關(guān)于平面三角剖分的具體實(shí)現(xiàn)過(guò)程見(jiàn)文.4)尋找部分點(diǎn)云邊界:如圖3所示,點(diǎn)云已經(jīng)投影進(jìn)了平面網(wǎng)格中.首先遍歷tlp,記錄下各行中第一個(gè)和最后一個(gè)待連接點(diǎn)的位置,將這些位置信息存儲(chǔ)到數(shù)組be中.找到各行待連接點(diǎn)的起止位置后,就開(kāi)始沿逆時(shí)針?lè)较蚣尤氩糠贮c(diǎn)云的邊界點(diǎn),八塊部分點(diǎn)云的邊界分別加入到bl1bl8八個(gè)邊界點(diǎn)數(shù)組中.下面以第一象限點(diǎn)云邊界搜索過(guò)程為例表述其具體步驟.87一6一4氣,321o123456,了8母1011l213140圖3部分點(diǎn)云邊界的尋找首先掃描be1數(shù)組,

14、找到第一行有非負(fù)值的行號(hào),記做top,找到最后一行有非負(fù)值的行號(hào)記做bottom.加入零行待連接點(diǎn):取出位置從be1top0到be!top1中的待連接點(diǎn),并按從左到右順序依次加入邊界數(shù)組bl1中;加入右側(cè)邊界點(diǎn):加入右側(cè)邊界時(shí)是依次從第top行加-n第bottom行減一分別加入的,如圖3右側(cè)的箭頭所示,具體加入過(guò)程偽代碼如下:fbr(i=top+1;i<bottom;i+)t1=be1i1一be1i一11;t2=be1i1一be1i+11;if(t11andt21)/情況1如圖中的行七,則將be1i1位置的待連接點(diǎn)加人bl1中;elseif(t1>1)/情況2如圖中

15、的行一,行二則將當(dāng)前行從be1i一11+1到be1i1的待連接點(diǎn)從左到右順序加入bl1中;elseif(t2>1)/情況3如圖中的行三則將當(dāng)前行從be1i+11+1到be1i1的待連接點(diǎn)逆序加入bl1中;else出錯(cuò)處理;lj加入最后行待連接點(diǎn):從be1bottom0到be1bottom1位置讀取最后行的待連接點(diǎn),然后逆序加入到邊界數(shù)組bl1中;加入左邊界點(diǎn):加左邊界與加右邊界相似,只不過(guò)是從bottom一1行到top+1行依次加入的,而且加入是從各行的起待連接點(diǎn)一側(cè)加入,如圖3左側(cè)的箭頭所示,具體加人偽代碼如下:for(i=bottom一1;i>top;i一一)t

16、1:be1i0一be1i+10;t2=be1i0一be1i一10;if(tl一1andt2一1)/情況1如圖中的行七,則將be1i0位置的待連接點(diǎn)加入bl1中;elseif(t1<一1)/情況2如圖中的行四,則將當(dāng)前行從be1i兒0到be1i+10一1的待連接點(diǎn)逆序加人bl1中;elseif(t2<一1)/情況3如圖中的行二,則將當(dāng)前行從be1i0到be1i一10一1的待連接點(diǎn)順序加入bl1中;else出錯(cuò)處理;找邊界中的轉(zhuǎn)折點(diǎn):由圖4可見(jiàn),每塊點(diǎn)云的邊界需要和三塊部分點(diǎn)云的邊界進(jìn)行縫合,而一塊點(diǎn)云的邊界只有一條,所以這條邊界應(yīng)分為三部分,分別對(duì)應(yīng)與它相鄰的三塊點(diǎn)云

17、的邊界.如圖4中的點(diǎn)1,點(diǎn)2和點(diǎn)3就為點(diǎn)云邊界中的轉(zhuǎn)折點(diǎn),這3個(gè)點(diǎn)將一個(gè)閉合的邊界分為三段邊界,分別與其第3期關(guān)明山,等:空間封閉點(diǎn)云的八象限三角剖分算法23相鄰的三塊點(diǎn)云邊界進(jìn)行縫合三角化.只要求取邊界中離兩個(gè)坐標(biāo)平面距離之和最小的點(diǎn)就為邊界中的轉(zhuǎn)折點(diǎn).例如只要在邊界中尋找到離平面y和平面yz距離之和最小的點(diǎn),即min(z+xz)就可以找到轉(zhuǎn)折點(diǎn)1.同樣,找到點(diǎn)2和點(diǎn)3的位置并分別將點(diǎn)1,點(diǎn)2,點(diǎn)3在邊界中的位置記錄到bl的頭節(jié)點(diǎn)中.圖4尋找邊界中的轉(zhuǎn)折點(diǎn)5)邊界縫合:在邊界縫合時(shí),首先找到要縫合的內(nèi),外邊界,如圖5所示.對(duì)于點(diǎn)云1的邊界即為要縫合的內(nèi)邊界,因?yàn)樵诩尤氩糠贮c(diǎn)云邊界點(diǎn)時(shí)就是按照

18、逆時(shí)針加人,所以部分點(diǎn)云1的邊界已經(jīng)有序.對(duì)于縫合的外邊界就需要從部分點(diǎn)云2,3和4的邊界中截取相應(yīng)部分并連接起來(lái)而形成.由于在前邊已經(jīng)將各塊部分點(diǎn)云邊界的轉(zhuǎn)折點(diǎn)找到并存儲(chǔ)起來(lái),故只要找到相應(yīng)的轉(zhuǎn)折點(diǎn)分別截取再連接就可以了.本例依次在點(diǎn)云2,4,3的邊界中取出相應(yīng)邊界段上的點(diǎn),然后將這些部分邊界段進(jìn)行連接.由圖5可以看到,這樣加進(jìn)來(lái)的外邊界是按順時(shí)針?lè)较蚺帕械?為了和內(nèi)邊界進(jìn)行正確的縫合連接,就必須將外邊界的點(diǎn)序進(jìn)行反序,使內(nèi),外邊界點(diǎn)序一致.最后將找到的內(nèi),外邊界分別存儲(chǔ)到兩個(gè)以點(diǎn)對(duì)象為元素的動(dòng)態(tài)數(shù)組tib和tob中,準(zhǔn)備進(jìn)行邊界縫合.,'_.1''蠹縫合邊界過(guò)程如圖

19、6所示,偽代碼如下:讀取tib起始點(diǎn)作為nowptl;nextptr圖6縫合內(nèi),外邊界示意圖讀取tob中與nowptl距離最近點(diǎn)作為nowptr;讀取內(nèi)邊界數(shù)組起始點(diǎn)的鄰下邊界點(diǎn)nextptl;讀取外邊界數(shù)組起始點(diǎn)的鄰下邊界點(diǎn)nextptr;while(runl<numlandrunr<numr)/runl,runr分別為左右讀數(shù)組元素的計(jì)數(shù)器,numl,numr為左右邊界數(shù)組中元素個(gè)數(shù)$/計(jì)算圖6中的1,2;if(/1>l2)/此處實(shí)際是依據(jù)圓準(zhǔn)則進(jìn)行的優(yōu)化處理將以nextptl,nowptl,nowptr為頂點(diǎn)的三角形及其法向量存入三角形鏈表tl中

20、;nowptlc=nextptl;從內(nèi)邊界數(shù)組讀取下一點(diǎn)做為nextptl;runl+:else將以nextptr,nowptl,nowptr為頂點(diǎn)的三角形及其法向量存入三角形鏈表tl中;nowptrnextptr;從外邊界數(shù)組讀取下一點(diǎn)做為nextptr;runr+;/endwhileif(runli>numl)將以nextptr,nowptl,nowptr為頂點(diǎn)的三角形及其法向量存人三角形鏈表,i'l中;if(runrnumr)將以nextptl,nowptl,nowptr為頂點(diǎn)的三角形及其法向量存人三角形鏈表tl中;4實(shí)驗(yàn)結(jié)果及分析本程序利用一個(gè)完整的鼠標(biāo)空間點(diǎn)云進(jìn)

21、行三角化檢驗(yàn),點(diǎn)云原來(lái)包含128826個(gè)點(diǎn),包含該點(diǎn)云的n>左邊界點(diǎn)哈爾濱理工大學(xué)第l4卷最小盒子的長(zhǎng),寬,高分別為126.513,66.4591和40.7198,該點(diǎn)云重心p(,y,z)的坐標(biāo)為(一6.23912,一273.537,一223.420),y方向上的投影網(wǎng)格個(gè)數(shù)都為8o個(gè),網(wǎng)格的長(zhǎng)寬分別為1.5814125和0.83073875,分割后的八塊部分點(diǎn)云經(jīng)過(guò)投影選點(diǎn)后總共剩下17583個(gè)點(diǎn),第一到第八象限的部分點(diǎn)云其邊界上的點(diǎn)數(shù)分別為125,131,128,126,117,119,119和120,最后剖分的三角面片數(shù)總共為20378.圖7為整個(gè)鼠標(biāo)空間點(diǎn)云三角化的最終結(jié)

22、果.(a)點(diǎn)視圖(b)三角連接視圖(c)實(shí)體渲染視圖圖7整個(gè)鼠標(biāo)空間點(diǎn)云三角化的結(jié)果以上實(shí)驗(yàn)結(jié)果同直接剖分法比較,大大減少了參與三角剖分的點(diǎn)的數(shù)量(參與直接剖分的點(diǎn)數(shù)為128826個(gè);實(shí)際參與三角剖分點(diǎn)數(shù)為17583個(gè)),提高了程序執(zhí)行的速度;同普通的平面投影法比較,平面網(wǎng)格投影法對(duì)投影點(diǎn)進(jìn)行了有效篩選,使剖分的三角形質(zhì)量更高.5結(jié)語(yǔ)1)本算法采用分治思想,將空間散亂點(diǎn)集劃分成八部分,再分別對(duì)各部分點(diǎn)集進(jìn)行旋轉(zhuǎn)投影及平面網(wǎng)格三角剖分,最后找到各部分點(diǎn)云的邊界進(jìn)行三角縫合,從而使整個(gè)空間點(diǎn)云得到三角化,有效解決了空間閉合點(diǎn)云的三角剖分問(wèn)題.2)平面網(wǎng)格投影的三角剖分方法可實(shí)現(xiàn)對(duì)空間曲面上點(diǎn)云的有效篩選,降低了無(wú)效的三角剖分計(jì)算,優(yōu)化了生成的三角面片,從而大大提高了程序執(zhí)行的效率及三角剖分質(zhì)量.實(shí)驗(yàn)結(jié)果表明,八象限空間立體三角剖分算法是一個(gè)有效率的,成功的三角剖分算法.參考文獻(xiàn):1amentan,bernm,kamvysselism.anewvoronoibasedsurfacereconstructionalgorithmc/proceedingsoftheacmsiggraphconferenceoncomputergraphics,orlando,fl,newyork,usa,1998:415421.2atrenem,spagnuoo