徐秀川,花向紅,龔子楨,郝 旦

(1.武漢大學(xué) 測繪學(xué)院,湖北 武漢 430079;2.武漢大學(xué) 災(zāi)害監(jiān)測與防治研究中心,湖北 武漢 430079)

基于球面投影的散亂點(diǎn)云三維建模算法實(shí)現(xiàn)與效果分析

徐秀川1,2,花向紅1,2,龔子楨1,2,郝 旦1,2

(1.武漢大學(xué) 測繪學(xué)院,湖北 武漢 430079;2.武漢大學(xué) 災(zāi)害監(jiān)測與防治研究中心,湖北 武漢 430079)

介紹基于球面投影的散亂點(diǎn)云三維建模算法步驟,運(yùn)用VC++編程語言結(jié)合OpenGL圖形接口實(shí)現(xiàn)該算法,并結(jié)合實(shí)例說明球面投影法相對(duì)于圓柱面投影法、橢球面投影法在三維建模中的優(yōu)勢。

球面投影法;散亂點(diǎn)云;Delaunay三角網(wǎng);三維建模

三維激光掃描技術(shù)是目前測繪領(lǐng)域中一個(gè)新的研究熱點(diǎn),其中散亂點(diǎn)云數(shù)據(jù)建模主要采用基于體剖分、基于面剖分和基于面投影3種方式建立?；诿嫱队笆窍葘⑷S空間數(shù)據(jù)投影到平面上進(jìn)行平面構(gòu)網(wǎng),再映射到三維空間最終達(dá)到三維建模目的。這種方法相對(duì)于基于體剖分和基于面剖分構(gòu)造三角網(wǎng)出錯(cuò)率較低,構(gòu)網(wǎng)效率相對(duì)較高。而基于面投影法分為基于平面投影、臨近區(qū)域切平面投影、圓柱面投影法。平面投影法只適用于平坦點(diǎn)云;臨近區(qū)域切平面投影處理復(fù)雜的點(diǎn)云時(shí),生成的格網(wǎng)有重疊現(xiàn)象,不利于結(jié)構(gòu)復(fù)雜的大型點(diǎn)云的數(shù)據(jù)處理;由于圓柱面投影法是將空間點(diǎn)沿著半徑方向投影到圓柱面上,頂部和底部數(shù)據(jù)點(diǎn)的投影易產(chǎn)生重疊,無法維持點(diǎn)云中原有的點(diǎn)之間的相對(duì)位置關(guān)系。針對(duì)圓柱面投影法的缺陷,曹操提出橢球面投影法,該方法是沿著橢球中心將各點(diǎn)投影到橢球面上,這就避免了點(diǎn)的重疊,然后根據(jù)高斯投影投影到平面上,在平面上構(gòu)造Delaunay三角網(wǎng)后再映射成三維空間三角格網(wǎng)。橢球面投影雖然避免了圓柱面投影的缺陷,但是由于該方法需要涉及到迭代計(jì)算,且正算公式復(fù)雜,應(yīng)用橢球面投影法建網(wǎng)效率明顯低于圓柱面投影法,且隨著點(diǎn)數(shù)的增多,這種差異越明顯。為此,本文從提高橢球面投影效率的角度出發(fā),提出球面投影法。詳細(xì)論述了基于球面投影的散亂點(diǎn)云三維建模算法步驟,并結(jié)合實(shí)例證明球面投影法相對(duì)于圓柱面投影法、橢球面投影法在三維建模中的優(yōu)勢。

1 基于球面投影的散亂點(diǎn)云三維建模的實(shí)現(xiàn)

基于球面投影的建模方法的基本思路是:經(jīng)過數(shù)據(jù)配準(zhǔn)[1],由三維激光掃描儀獲得的點(diǎn)云原始坐標(biāo)都轉(zhuǎn)化為統(tǒng)一空間坐標(biāo)系下的坐標(biāo)(Xi,Yi,Zi)。以球面為媒介將空間散亂點(diǎn)云(Xi,Yi,Zi)投影到平面上,得到相應(yīng)二維坐標(biāo)(xi,yi),在平面內(nèi)通過Delaunay算法構(gòu)造平面三角網(wǎng),最后將平面三角格網(wǎng)映射到空間完成三維建模。

1.1 散亂點(diǎn)云投影到平面

圖1為球面坐標(biāo)系,O為球心,且盡量定位在掃描對(duì)象的幾何中心,球的半徑 r大小可根據(jù)計(jì)算簡便需要任意選擇,OX、OY、OZ軸構(gòu)成右手坐標(biāo)系,投影方向沿著球心指向各點(diǎn)。

圖1 球面坐標(biāo)系

設(shè) P(X,Y,Z)為任一點(diǎn)云數(shù)據(jù),經(jīng)投影后在球面上有唯一的 P′與點(diǎn) P對(duì)應(yīng)。球面坐標(biāo)用(L,B)表示,與大地測量中大地經(jīng)度與大地緯度定義類似,L表示OP′連線在XOY平面上的投影與OX軸的夾角(0°＜L≤360°),B 表示直線 OP′與 XOY面的

為大地經(jīng)度與中央子午線的差值;t=tan B,r為球半徑。

雖然掃描對(duì)象不像地球那樣龐大,但考慮到計(jì)算結(jié)果的準(zhǔn)確性,從盡量減小變形的角度出發(fā),仍然對(duì)球面進(jìn)行分帶投影,選用6度帶投影。然而不同帶的點(diǎn)通過正算式(3)獲得的平面坐標(biāo)并不在同一個(gè)平面直角坐標(biāo)系中,這樣就不能保證點(diǎn)與點(diǎn)之間原有的相對(duì)位置關(guān)系,通過式(4)可將計(jì)算所得的平面點(diǎn)歸化到統(tǒng)一坐標(biāo)系中。x、y為歸化后的坐標(biāo)。

1.2 Delaunay生長算法構(gòu)造平面三角網(wǎng)

經(jīng)過以上各步驟的投影后,就將空間點(diǎn)云數(shù)據(jù)投影到統(tǒng)一的平面坐標(biāo)系中,根據(jù)各平面點(diǎn)坐標(biāo)(xi,yi),可由Delaunay生長算法構(gòu)造平面三角網(wǎng)。其基本步驟如下:

1)創(chuàng)建點(diǎn)point表,邊list表,三角形 triangle表,point表存儲(chǔ)各點(diǎn)坐標(biāo)信息及順序點(diǎn)號(hào),list表存儲(chǔ)邊號(hào)、兩個(gè)端點(diǎn)點(diǎn)號(hào)、對(duì)面點(diǎn)點(diǎn)號(hào)以及各邊的usetime值。Triangle表存儲(chǔ)三角形順序號(hào)、三條邊順序號(hào)。

2)構(gòu)建初始基線:在點(diǎn)point表中選擇順序點(diǎn)號(hào)點(diǎn)為1的點(diǎn) A作為初始點(diǎn),然后遍歷所有點(diǎn),找到距點(diǎn)A最近的點(diǎn)B,連接后作為初始基線。將該邊放入邊表edge中,并將該邊的usetime值設(shè)為1。如圖2(a)所示。

圖2 Delaunay生長算法示意圖

3)構(gòu)建核心三角形:運(yùn)用Delaunay法則搜尋第3點(diǎn),具體的做法是:遍歷所有點(diǎn),查找距此初始基線距離最短的點(diǎn),可由余弦定理求該邊對(duì)應(yīng)角最大的點(diǎn)為第3點(diǎn)。將新形成的兩個(gè)邊放入邊表list表尾,邊usetime值均設(shè)為1,三角形放入三角形列表triangle中。如圖2(b)所示。

4)擴(kuò)展核心三角形:由核心三角形的各邊分別向外擴(kuò)展新的三角形,具體做法是:在該擴(kuò)展邊在原三角形中的對(duì)應(yīng)點(diǎn)異側(cè)的所有點(diǎn)中,如步驟2)按照余弦定理查找與該邊對(duì)應(yīng)角最大的點(diǎn),并組成新的三角形,加入 triangle表尾,兩條新邊加入 list表尾,usetime值設(shè)為1,已擴(kuò)展的初始邊usetime值變?yōu)?。如圖2(d)所示。

5)在list表中依次按步驟3)擴(kuò)展所有usetime值為1的邊,擴(kuò)展后usetime值變?yōu)?,擴(kuò)展的新邊順序放到edge表中,usetime均設(shè)為1,新三角形加入triangle表中。

6)重復(fù)步驟3)、4),直至邊表中所有邊的 usetime值變?yōu)?,或usetime值為1的邊無法再找到滿足擴(kuò)展要求的點(diǎn)。

7)三角格網(wǎng)優(yōu)化:根據(jù)最小內(nèi)角最大準(zhǔn)則,對(duì)所建成的三角格網(wǎng)進(jìn)行優(yōu)化。

1.3平面三角格網(wǎng)映射為空間三角格網(wǎng)

由于投影前后保證了點(diǎn)的相對(duì)位置不變,且點(diǎn)表中包含點(diǎn)號(hào)信息,將三維點(diǎn)按照平面三角格網(wǎng)確定的拓?fù)潢P(guān)系根據(jù)點(diǎn)號(hào)進(jìn)行連接,可以將平面三角格網(wǎng)映射為空間三角格網(wǎng),實(shí)現(xiàn)空間建模。

2 程序?qū)崿F(xiàn)與效果分析

根據(jù)上述所介紹的基于球面投影的散亂點(diǎn)云三維建模步驟,運(yùn)用VC++編程語言結(jié)合OpenGL圖形接口實(shí)現(xiàn)。

2.1 球面投影法與圓柱面投影法效果分析

選取皇冠模型原始數(shù)據(jù)(共含14443個(gè)點(diǎn)云數(shù)據(jù)),如圖3所示,分別采用圓柱面投影法與球面投影法進(jìn)行建模,圓柱參數(shù)底面圓半徑 R=1,球參數(shù)半徑 r=1。其建模效果見圖4、圖5。

圖3 散亂點(diǎn)云

由圖4、圖5可以看出:對(duì)于頂部的點(diǎn)云利用圓柱面投影實(shí)現(xiàn)空間建模時(shí),頂部點(diǎn)云格網(wǎng)拓?fù)潢P(guān)系較混亂,而利用球面投影法生成的三角形的形狀較為均勻,網(wǎng)形結(jié)構(gòu)較為合理,能較好地維持原始的拓?fù)潢P(guān)系?？梢?球面投影法很好地彌補(bǔ)了圓柱面投影法由于投影方式造成的頂部數(shù)據(jù)投影重疊這一缺陷,可以更好地維持頂部或底部點(diǎn)云的拓?fù)潢P(guān)系。

2.2 球面投影法與橢球面投影法效果分析

同樣選取圖3所示點(diǎn)云數(shù)據(jù),分別采用橢球面投影法和球面投影法構(gòu)造空間三角格網(wǎng),橢球面投影法橢球參數(shù)長半軸 a=2,短半軸 b=1,球面投影法球參數(shù)半徑 r=1。圖6為橢球面投影法建模效果局部截圖,圖7為球面投影法建模效果局部截圖。為了更好地進(jìn)行效率對(duì)比,從原始點(diǎn)云中任意抽取1132、3842個(gè)點(diǎn)云數(shù)據(jù),分別采用橢球面投影法和球面投影法進(jìn)行建模,并記錄完成時(shí)間,實(shí)驗(yàn)結(jié)果如表1所示。

圖6 橢球面投影法效果圖(局部)

圖7 球面投影法效果圖(局部)

表1 點(diǎn)云數(shù)據(jù)建模效率對(duì)比

由表1可以看出:對(duì)于相同數(shù)量的點(diǎn)云數(shù)據(jù),利用球面投影法構(gòu)造三角格網(wǎng)速度更快,且點(diǎn)云數(shù)量越多,這種優(yōu)勢越明顯。由圖6和圖7效果對(duì)比可以看出:對(duì)于較平坦區(qū)域,橢球面投影法與球面投影法效果類似,但對(duì)于表面曲率變化較大的區(qū)域,球面投影法比橢球面投影法構(gòu)造三角網(wǎng)出錯(cuò)率更低,建模效果更好。由于球的特殊性,球面投影相對(duì)于橢球面投影,投影間的轉(zhuǎn)換公式簡單且精確,采用球面投影法建模效率更高,且效果更好。

3 結(jié)束語

實(shí)驗(yàn)結(jié)果表明,基于球面投影的散亂點(diǎn)云三維建模方法,可以避免圓柱面投影過程中造成的頂部或底部點(diǎn)云數(shù)據(jù)缺失問題,同時(shí),在建模效率及效果方面,球面投影法也優(yōu)于橢球面投影法。球面投影法具有很好的實(shí)用價(jià)值。

[1]曹操.三維激光掃描數(shù)據(jù)三角格網(wǎng)建立方法的研究[D].南京:河海大學(xué),2008:33-35.

[2]鄭德華.三維激光掃描數(shù)據(jù)處理的理論與方法[D].上海:同濟(jì)大學(xué),2005:64-70.

[3]孔祥元,郭際明,劉宗泉.大地測量學(xué)基礎(chǔ)[M].武漢:武漢大學(xué)出版社,2005:156-158,103-104,108-109,112-113.

[4]武曉波,王世新,肖春生.Delaunay三角網(wǎng)的生成算法研究[J].測繪學(xué)報(bào),1999,28(1):28-35.

[5]江劍霞,劉少華,吳漢英.VB環(huán)境下不規(guī)則三角網(wǎng)的算法設(shè)計(jì)與實(shí)現(xiàn)[J].四川測繪,2006,29(2):64-67.

[6]蔣紅雯,涂鵬,李國忠.基于生長算法構(gòu)建Delaunay三角網(wǎng)的研究[J].公路交通科技,2004(12):38-40.

The im plementation algorithm of three-dimensionalmodeling to point cloud based on spherical surface projection and effect analysis

XU Xiu-chuan1,2,HUA Xiang-hong1,2,GONG Zi-zhen1,2,HAO Dan1,2
(1.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China;2.Research Center for Hazard Monitoring and Prevention,Wuhan University,Wuhan 430079,China)

The algo rithm of three-dimensional modeling to point cloud based on spherical surface p rojection is introduced in the paper,and the algorithm is achieved through the app lication of VC++combining graphical interfaces OpenGL,and the superiority of spherical p rojection methods against the cylindrical p rojection methods and ellipsoidal p rojection methods is demonstrated by instance.

spherical p rojection methods;point cloud;Delaunay triangulation netwo rk;three-dimensional modeling

TP309

A

1006-7949(2011)03-0005-04

2010-05-07

國家自然科學(xué)基金資助項(xiàng)目(40901214);精密工程與工業(yè)測量國家測繪局重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(PF2009-2)

徐秀川(1985-),男,碩士研究生.

[責(zé)任編輯劉文霞]