鄭德華,龐逸群,曹 操

(河海大學(xué) 土木工程學(xué)院,江蘇 南京 210098)

基于橢球面投影的散亂點(diǎn)云建立三角格網(wǎng)方法

鄭德華,龐逸群,曹 操

(河海大學(xué) 土木工程學(xué)院,江蘇 南京 210098)

空間點(diǎn)云數(shù)據(jù)建立三角格網(wǎng)是三維激光掃描數(shù)據(jù)處理中重要的處理內(nèi)容之一。已有的點(diǎn)云三角格網(wǎng)建立方法的網(wǎng)形結(jié)構(gòu)良好,但存在數(shù)據(jù)量大、計算效率低的特點(diǎn)。提出借助橢球面進(jìn)行高斯投影建立點(diǎn)云的空間三角格網(wǎng)建立方法,有效地實(shí)現(xiàn)四周型點(diǎn)云數(shù)據(jù)格網(wǎng)建立過程。結(jié)合某礦井點(diǎn)云數(shù)據(jù)實(shí)例,對基于圓柱面和橢球面投影的兩種方法建立的三角格網(wǎng)進(jìn)行對比,結(jié)果表明,利用橢球面投影法建立三角格網(wǎng)能更有效地建立頂部和底部點(diǎn)云數(shù)據(jù)的拓?fù)潢P(guān)系。

散亂點(diǎn)云;三角格網(wǎng);橢球面投影;高斯投影

三維激光掃描目前已廣泛應(yīng)用于計算機(jī)可視化、人工智能以及逆向工程等方面,三角格網(wǎng)貫穿于三維激光點(diǎn)云數(shù)據(jù)處理的整個過程。S-M Hur等人研究了基于Delaunay三角化過程中實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的縮減[1],1997年Chen Liang-Chia和 Grier CI L IN提出了將構(gòu)建的三角格網(wǎng)進(jìn)行最小二乘自由曲面模型的重建[3]。三角格網(wǎng)的建立在點(diǎn)云數(shù)據(jù)處理中具有十分重要的作用,研究合適的三角格網(wǎng)建立方法是建立復(fù)雜物體模型的一項(xiàng)重要內(nèi)容。目前許多文獻(xiàn)對此都進(jìn)行了大量的研究,發(fā)現(xiàn)直接在三維空間中利用點(diǎn)與點(diǎn)之間的關(guān)系構(gòu)建三角格網(wǎng),當(dāng)點(diǎn)云數(shù)據(jù)量較大時,構(gòu)網(wǎng)非常耗時,計算效率低下,且在點(diǎn)密度不均勻或存在噪聲的情況下,難以判斷點(diǎn)對之間的真正鄰接關(guān)系。作者提出了利用圓柱面坐標(biāo)系在可保證點(diǎn)云中各點(diǎn)之間的相對關(guān)系不變的前提下,將三維點(diǎn)坐標(biāo)轉(zhuǎn)換成可以用來生成平面三角格網(wǎng)的二維坐標(biāo)[7],實(shí)現(xiàn)四周形點(diǎn)云數(shù)據(jù)的格網(wǎng)構(gòu)建;張帆等提出了利用球面投影對單站地面激光掃描點(diǎn)云的構(gòu)網(wǎng)方法[8],但對于多站三維激光掃描數(shù)據(jù)其適用性仍有待探討。本文將三維點(diǎn)云數(shù)據(jù)分別采用圓柱面坐標(biāo)系統(tǒng)和橢球面坐標(biāo)系統(tǒng)投影至二維平面上,然后利用平面上的坐標(biāo)計算Delaunay三角形方法建立三維物體表面格網(wǎng)模型,有效地建立了具有頂部和底部點(diǎn)云數(shù)據(jù)的拓?fù)潢P(guān)系。

1 橢球面投影法

1.1 橢球面坐標(biāo)系統(tǒng)

橢球面坐標(biāo)系[9]是在三維直角坐標(biāo)系統(tǒng)中定義一個長、短半軸分別為a、b的橢圓繞其短軸旋轉(zhuǎn)而形成的橢球基準(zhǔn)面,橢球面的中心為右手系的原點(diǎn)O(見圖1)。若橢球面坐標(biāo)系中包含一點(diǎn)P,則在橢球面上一定存在一點(diǎn)P′,P′為P點(diǎn)相對于橢球中心O在橢球面上的投影。圖1中B表示P′點(diǎn)在橢球面上的法線與xoy平面的夾角;L表示PP′連線在xoy平面上的投影與ox軸的夾角。

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

在計算過程中,ti前一次迭代值,第一次迭代令

ti=t0。將點(diǎn)云中的點(diǎn)坐標(biāo)(X,Y,Z)和自定義的橢球的長、短半軸a、b分別代入式(1)、(2)中,計算點(diǎn)在橢球面坐標(biāo)系統(tǒng)中的坐標(biāo)(B,L)。

1.2 平面坐標(biāo)計算

1.2.1 高斯投影坐標(biāo)計算公式

在高斯投影中,將大地坐標(biāo)(B,L)轉(zhuǎn)化成高斯平面直角坐標(biāo)系下的坐標(biāo)采用以下公式計算:

1.2.2 平面坐標(biāo)計算

利用自定義的橢球長、短半軸a、b和橢球坐標(biāo)系坐標(biāo)(B,L)直接代入X、l、N、t、η的計算公式,將計算結(jié)果代入式(4)即可計算出三維空間點(diǎn)利用橢球面投影后的平面坐標(biāo)(x,y)。

由高斯投影原理可知,按某一度數(shù)劃分投影帶后,不同帶的點(diǎn)通過高斯投影坐標(biāo)正算公式獲得的平面坐標(biāo)位于不同的平面直角坐標(biāo)系中,因此無法保持點(diǎn)與點(diǎn)之間原有的相對位置關(guān)系,通過式(5)可將計算獲得的平面點(diǎn)歸化到同一坐標(biāo)系中。

式中:x、y為歸化前的坐標(biāo),x1、y1為歸化后的坐標(biāo),a為橢球長半軸,n為分帶度數(shù)。

2 基于橢球面投影的空間三角格網(wǎng)建立方法

2.1 三角格網(wǎng)建立的基本思路

利用面投影將點(diǎn)云中的所有點(diǎn)投影到二維平面后,空間三角格網(wǎng)的建立則轉(zhuǎn)化到二維平面上進(jìn)行。建立三角格網(wǎng)的原則為由鄰近的散亂點(diǎn)組成三角格網(wǎng)時,應(yīng)盡可能地確保每個三角形三邊長度接近相等,避免出現(xiàn)過大鈍角和過小鈍角的三角形。建立三角格網(wǎng)時,首先建立一個核心三角形,由此三角形的三個邊向外圍建立擴(kuò)展三角形,建立方法是根據(jù)已構(gòu)三角形的邊與外圍一點(diǎn)構(gòu)成三角形的外接圓半徑最小建立擴(kuò)展三角形,然后由原三角形的三個頂點(diǎn)和新搜索的點(diǎn)構(gòu)成四邊形,若構(gòu)成凸四邊形則根據(jù)連接四邊形對角線短邊來重構(gòu)兩個三角形以達(dá)到優(yōu)化三角形形狀的目的,若構(gòu)成凹四邊形則不需進(jìn)行三角形形狀連接優(yōu)化。

2.2 三角格網(wǎng)實(shí)現(xiàn)方法

根據(jù)上述思想,采用數(shù)據(jù)庫設(shè)計方法實(shí)現(xiàn)三維空間建立點(diǎn)的三角格網(wǎng)算法。首先在Access數(shù)據(jù)庫中建立一個數(shù)據(jù)表格,即原始點(diǎn)云三維坐標(biāo)point表,在程序中定義了5個向量類模板 vector的變量:ThreeVertex,Twow Vertex,Twoww Vertex, LaterList,TriangleList。XCoor、Ycoor、Zcoor和Intens四個元素分別表示三維激光掃描點(diǎn)的三維坐標(biāo)和點(diǎn)的反射強(qiáng)度,m_index、X、Y、Z4個元素分別存儲投影前的三維點(diǎn)云坐標(biāo)的順序點(diǎn)號和對應(yīng)點(diǎn)的三維坐標(biāo),m_pindex、x、y元素分別存儲投影后的二維點(diǎn)云數(shù)據(jù)的順序點(diǎn)號和對應(yīng)點(diǎn)的二維坐標(biāo), num元素表示在進(jìn)行擴(kuò)展三角形時,從 Twow Vertex中選取的滿足條件的點(diǎn)的點(diǎn)號,m_Tindex、m_ point1、m_point2、m_point3四個元素分別用于存儲三角形的序號和相應(yīng)的三角形三個頂點(diǎn)的序號,m_ Lindex元素用于存儲邊的序號,m_point1、m_ point2分別存儲邊的起點(diǎn)和終點(diǎn),m_LatDist存儲邊的長度,m_Old Tri、m_New Tri分別用于存儲原三角形和擴(kuò)展三角形的序號,m_Old Trip t、m_New TriPt分別用于存儲原三角形第三個頂點(diǎn)和擴(kuò)展三角形第三個頂點(diǎn)的序號,m_CroDist用于存儲Old TriPt和New TriPt兩點(diǎn)的距離。

根據(jù)建立的數(shù)據(jù)結(jié)構(gòu),利用橢球面投影法實(shí)現(xiàn)三維激光掃描點(diǎn)云的空間三角格網(wǎng)建立的步驟:

1)坐標(biāo)投影轉(zhuǎn)換。首先,將point表中的點(diǎn)坐標(biāo)依次存入向量 ThreeVertex中,m_index元素值從1開始依次累加1,表示點(diǎn)的序號;然后,將每個點(diǎn)的三維坐標(biāo)經(jīng)過上述的橢球面投影轉(zhuǎn)換變?yōu)槎S平面坐標(biāo),存儲到向量 Twow Vertex中,其元素m_ pindex的值與向量 ThreeVertex中相對應(yīng)的點(diǎn)的元素m_index的值一致。

2)構(gòu)建核心三角形。選取 Twow Vertex向量中的第一個點(diǎn)作為整個建網(wǎng)的開始,遍歷 Twow-Vertex中的所有點(diǎn)找出其最近的點(diǎn)i形成第1個三角形的一條邊。在尋找核心三角形第三點(diǎn)時,根據(jù)第三點(diǎn)到該邊的距離最短原則確定,即由余弦定理求取該邊對應(yīng)角最大的點(diǎn)k作為核心三角形的第3點(diǎn)。首先將核心三角形的3個頂點(diǎn)按選取的先后順序存入到向量 Twoww Vertex,點(diǎn)的序號分別為0、i、k;然后將核心三角形的編號設(shè)為0,3個頂點(diǎn)號按選取的順序即:0、i、k,存儲在向量 TriangleList中;最后根據(jù)向量 TriangleList中的記錄,將三角形的三條邊作為序號為0、1、2的3個記錄存入向量LaterList,并將各邊的邊長、三角形編號及第3點(diǎn)的序號寫入LatDist、Old Tri和Old TriPt中。

3)利用核心三角形擴(kuò)展三角形。依次將向量Twoww Vertex中的點(diǎn)與其向下的每一個點(diǎn)組合成邊,如果該邊在向量LaterList中存在,則該邊為進(jìn)行擴(kuò)展三角形的基礎(chǔ),將向量 Twow Vertex中滿足擴(kuò)展要求的點(diǎn)存入向量Twoww Vertex中。三角形邊擴(kuò)展過程如圖2所示:0-14-15為核心三角形,按順序以0-14為邊擴(kuò)展得到3號點(diǎn),加入到向量Twoww Vertex中;0-15擴(kuò)展得到5號點(diǎn),加入到向量 Twoww Vertex中;0-3擴(kuò)展得到16號點(diǎn);0 -5得到1號點(diǎn);0-16得到1號點(diǎn),加入到向量Twoww Vertex。接著以14號點(diǎn)開始向下遍歷,即以14-15為邊進(jìn)行擴(kuò)展得到6號點(diǎn),依次類推直到所有的點(diǎn)都成為三角格網(wǎng)中的頂點(diǎn)。

圖2 平面三角格網(wǎng)建立示意圖

由一條邊擴(kuò)展三角形時,首先要排除與該邊所對的原三角形的頂點(diǎn)位于同側(cè)的點(diǎn)?？筛鶕?jù)該邊兩個端點(diǎn)坐標(biāo)構(gòu)造的直線方程判別式(6)來進(jìn)行判斷。

將向量LaterList中Old TriPt元素中的三角形頂點(diǎn)所對應(yīng)的坐標(biāo)代入式(6),得到函數(shù)值F0。由于擴(kuò)展三角形的頂點(diǎn)必須與擴(kuò)展邊對應(yīng)原三角形的頂點(diǎn)分別在擴(kuò)展邊的兩側(cè),因此,參與擴(kuò)展三角形的頂點(diǎn)的坐標(biāo)代入式(6)后得到的函數(shù)值F(x,y)的符號應(yīng)與F0的符號相反。對于滿足以上判斷條件的點(diǎn),再根據(jù)余弦定理獲取擴(kuò)展邊對應(yīng)的角最大的點(diǎn),作為擴(kuò)展三角形的第3個頂點(diǎn)。將擴(kuò)展三角形的編號及三個頂點(diǎn)寫入向量 TriangleList,并在向量LaterList中增加兩條新增邊的記錄;然后,將擴(kuò)展三角形的頂點(diǎn)加入向量LaterList的原記錄的New TriPt元素中,并計算Old TriPt和New TriPt所存放的兩點(diǎn)的距離,將計算結(jié)果存放在CroDist元素中。

4)三角格網(wǎng)優(yōu)化。如果原三角形3個頂點(diǎn)與新擴(kuò)展的頂點(diǎn)構(gòu)成凸四邊形,則要判斷CroDist值是否小于LatDist值。當(dāng)CroDist值小于LatDist值時,原三角形與擴(kuò)展三角形的圖形結(jié)構(gòu)要進(jìn)行優(yōu)化。在進(jìn)行三角形圖形優(yōu)化時,只需根據(jù)向量LaterList中Old Tri和New Tri值查找到向量TriangleList中相應(yīng)的兩條記錄,并將重構(gòu)成的三角形作為兩個記錄分別替換向量TriangleList中相應(yīng)的記錄。

5)格網(wǎng)映射。經(jīng)過上述2)、3)、4)過程,實(shí)現(xiàn)平面上三角格網(wǎng)建立后,需將平面三角格網(wǎng)映射為三維空間三角格網(wǎng)。由于點(diǎn)間相對位置不變,所以向量TriangleList中保存的每個平面三角形的信息與三維空間三角格網(wǎng)的信息一致,即:三維空間三角形的3個頂點(diǎn)與向量 TriangleList中存儲的三角形的3個頂點(diǎn)相對應(yīng)。

3 兩種投影法建立礦井基坑格網(wǎng)實(shí)例

某礦井基坑深約為 10 m,水平截面約為4.7 m×4.7 m的方形截面,基坑內(nèi)表面不光滑,并且有一定的起伏。對該基坑進(jìn)行三維激光數(shù)據(jù)采集,共獲得了46 365個基坑內(nèi)表面的點(diǎn),平均點(diǎn)間隔約為60 mm。為了清晰的反映利用橢球面投影法建立包含頂部或底部數(shù)據(jù)的空間格網(wǎng)效果,在Access數(shù)據(jù)庫中分別截取表示基坑底部的三維點(diǎn)(共計2 341個點(diǎn))和礦井中部一段點(diǎn)云(共計4 000個點(diǎn))(見圖3(a)、(b)、(c))。對基坑底部的點(diǎn)云分別利用圓柱面投影法和橢球面投影法進(jìn)行坐標(biāo)轉(zhuǎn)換后,生成三維空間的礦井基坑底部三角格網(wǎng),并通過OpenGL三維圖形函數(shù)庫繪制和顯示(見圖3中的(d)和(e));對礦井中部點(diǎn)云先整體繞X軸旋轉(zhuǎn)90°,然后分別利用圓柱面投影法和橢球面投影法建立三維空間的礦井基坑中部三角格網(wǎng)(見圖3中的(f)和(g))。

從圖3可知,借助面投影法,利用平面建立Delaunay三角形的方法建立點(diǎn)云三角格網(wǎng),生成的三角形形狀均勻,整體圖形結(jié)構(gòu)合理。對于四周型物體表面的三維激光掃描點(diǎn)云利用橢球面投影法建立三角格網(wǎng)與利用圓柱面投影法建立的三角格網(wǎng)具有相同的網(wǎng)形效果。對于包含頂部和底部數(shù)據(jù)的點(diǎn)云利用圓柱面投影法實(shí)現(xiàn)三維空間三角格網(wǎng)建立時,頂部和底部的點(diǎn)云所生成格網(wǎng)的拓?fù)潢P(guān)系比較混亂;利用橢球面投影法實(shí)現(xiàn)三維空間三角網(wǎng)建立時,生成三角形的形狀較為均勻,整體的網(wǎng)形結(jié)構(gòu)較為合理,能夠較好的保持三維空間點(diǎn)原始的拓?fù)潢P(guān)系。但利用橢球面投影法實(shí)現(xiàn)空間三角格網(wǎng)建立的效率比圓柱面投影法的效率低,且隨著點(diǎn)云數(shù)量越多,這種差異越明顯。這是由于在利用橢球面投影法需運(yùn)用迭代方法計算橢球面坐標(biāo)B,且坐標(biāo)值x1和y1的計算較復(fù)雜。

因此當(dāng)點(diǎn)云的數(shù)據(jù)量較大時,用圓柱面投影法實(shí)現(xiàn)空間三角格網(wǎng)的建立在效率上優(yōu)于橢球面投影;當(dāng)點(diǎn)云數(shù)據(jù)為具有頂部和底部數(shù)據(jù)的情況下,采用橢球面投影法建立空間三角格網(wǎng)在網(wǎng)形上具有明顯的優(yōu)勢。

4 結(jié)束語

采用圓柱面投影法和橢球面投影法將點(diǎn)云數(shù)據(jù)投影至二維平面上,將復(fù)雜的三維問題轉(zhuǎn)化為二維問題在平面上進(jìn)行構(gòu)網(wǎng),然后格網(wǎng)映射成整體的三維模型,能夠取得較好的構(gòu)網(wǎng)效果,且具有較高的效率。通過對比實(shí)驗(yàn)表明,對于具有頂部和底部數(shù)據(jù)的點(diǎn)云數(shù)據(jù),利用圓柱面投影法建立三維空間三角格網(wǎng),頂部和底部的點(diǎn)云所生成格網(wǎng)的拓?fù)潢P(guān)系比較混亂;利用橢球面投影法實(shí)現(xiàn)三維空間三角網(wǎng)建立時,生成三角形的形狀較為均勻,整體的網(wǎng)形結(jié)構(gòu)較為合理,能夠較好的保持三維空間點(diǎn)原始的拓?fù)潢P(guān)系。但當(dāng)點(diǎn)云數(shù)據(jù)量較大時,用圓柱面投影法實(shí)現(xiàn)空間三角格網(wǎng)的建立在效率上優(yōu)于橢球面投影。因此針對不同的點(diǎn)云數(shù)據(jù)選擇必須不同的投影方法方能有效保證點(diǎn)云構(gòu)網(wǎng)的精度和效率。

[1]S-M HUR,H-C KIM,S-H LEE.STL File generation w ith data reduction by the delaunay triangulation method in reverse engineering[J].The International Journal of Advanced Manufacturing Technology.2002,19:669-678

[2]H-C KIM,S-M HUR,S-H LEE.Segmentation of the measured point data in reverse engineering[J].International Journal of Advanced Manufacturing Technology, 2002,20:571-580.

[3]CHEN L IANG-CH IA,GRIER C IL IN.A vision-aided reverse engineering app roach to reconstructing free-form surface[J].Robotics&Computer-Integrated Manufacturing.1997,13:323-336

[4]CHO IBK,SH IN HY,YOON YI,et al..Triangulation of scattered data in 3D space[J].Compute Aided Des. 1988,0(5):239-248.

[5]FANG TP,PIEGL L.Delaunay triangulation in three dimensions[J].IEEE Comput Graph App l.1995,15(5): 62-69.

[6]XIANG-YANG L I.Sliver-free tree dimensional delaunay mesh generation[D].PhD Dissertation of the University of Illinois at U rbana Champaign.January,2001.

[7]鄭德華,張云濤.基于物體表面散亂三維激光掃描點(diǎn)的三角形格網(wǎng)建立[J].測繪工程,2004,13(4):62-65.

[8]張帆,黃先鋒,李德仁.基于球面投影的單站地面激光掃描點(diǎn)云構(gòu)網(wǎng)方法[J].測繪學(xué)報,2009,38(1):48-54.

[9]孔祥元,郭際明.大地測量學(xué)基礎(chǔ)[M].武漢:武漢大學(xué)出版社,2001.

[10]黃淼,張海朝.散亂點(diǎn)云的三角劃分算法研究[J].微計算機(jī)應(yīng)用,2007,28(10):1 039-1 042.

Triangular grid establishment based on disordered point cloud of ellipsoidal surface projection

ZHENGDe-hua,PANG Yi-qun,CAO Cao
(College of Civil Engineering,Hohai University,Nanjing 210098,China)

The spatial point cloud data to establish a triangular grid in 3D laser scan data p rocessing is one impo rtant p rocess.Previousmethods of establishing triangular grid are shape and structurally sound,but have p roblem to calculate the characteristics of low efficiency w ith large amount of points.In this paper, carried out w ith Gaussian ellipsoid p rojection for the establishment of point cloud to establish triangular grid method,effective imp lementation of the surrounding grid-based point cloud data building p rocess. Combination of point cloud data instance of amine,based on cylindrical surface and the ellipsoid p rojection to establish a triangular grid of two methodswere compared;results showed that the use of ellipsoid to establish a triangular grid p rojection method is more effective in building the top and bottom of the points cloud data topology.

disordered point cloud;triangular mesh;ellipsoidal surface p rojection;Gauss p rojection

P226

A

1006-7949(2010)04-0019-05

2009-11-24

江蘇省交通科學(xué)研究計劃項(xiàng)目(09Y08)

鄭德華(1972-),男,副教授,博士.

[責(zé)任編輯:張德福]