倪 曙，方源敏，李國柱，陳 杰

(1.昆明市測繪研究院，云南昆明 650051；2.昆明理工大學(xué)國土資源工程學(xué)院，云南昆明 650093）

K-鄰近條件下空間實(shí)體三維建模算法研究

倪 曙1，方源敏2，李國柱1，陳 杰2

(1.昆明市測繪研究院，云南昆明 650051；2.昆明理工大學(xué)國土資源工程學(xué)院，云南昆明 650093）

一、引 言

空間形體的三維建模算法是當(dāng)前測繪制圖和GIS領(lǐng)域研究的重點(diǎn)。傳統(tǒng)的建模算法一般以平面作為定義域，實(shí)數(shù)空間的子集作為其值域，定義域與值域存在唯一的映射關(guān)系，由此產(chǎn)生的函數(shù)關(guān)系決定了傳統(tǒng)建模算法的二維本質(zhì)。函數(shù)是用數(shù)學(xué)術(shù)語來描述現(xiàn)實(shí)世界的主要工具。

傳統(tǒng)的建模算法多以Delaunay三角網(wǎng)、Voronoi圖(又稱Thiessen多邊形）為核心進(jìn)行擴(kuò)展，DEM就是其中的典型代表。不管是附加約束條件的DEM[1]，還是分段拼接來表達(dá)空間形體的建模算法，實(shí)際上都在函數(shù)的范圍內(nèi)。前者理論上可以通過一體化的函數(shù)來表示，后者則可以使用分段函數(shù)表示。而對于“懸崖”這樣的地貌，前述算法則無能為力，因為在數(shù)學(xué)上已經(jīng)跨出了函數(shù)的范疇。

針對空間離散點(diǎn)集進(jìn)行三維建模的算法種類較多，包括雕刻家算法[2]、距離函數(shù)算法[3]、表面生長算法[4]和基于空間閉合投影面的建模算法[5-7]等。在點(diǎn)群密度不均勻或存在噪聲的情況下，容易導(dǎo)致拓?fù)溥B接錯誤；而對于基于空間投影面的建模算法，在投影法線確定的前提下，存在多個點(diǎn)投影于同一點(diǎn)的問題等；通過以各點(diǎn)位投影中心進(jìn)行切平面投影的算法[8]建模效率較高，但是無形中也會帶來局部變形。

本文從理論出發(fā)，研究了一種三維建模算法。在逐點(diǎn)插入的過程中進(jìn)行實(shí)時優(yōu)化，同時采用有效的方法規(guī)避了由于K取值有限所導(dǎo)致的局部“孤立點(diǎn)群”的問題，同時對“同棱點(diǎn)”也作了有效的處理。結(jié)合具體應(yīng)用，如針對地下采空區(qū)進(jìn)行激光掃描獲取的點(diǎn)云數(shù)據(jù)進(jìn)行處理時，對點(diǎn)群進(jìn)行逆向計算求定站心坐標(biāo)作為本算法中的虛擬中心，建模結(jié)果能夠最大化地逼近采空區(qū)的真實(shí)形態(tài)。

二、基本約定、研究對象及研究目標(biāo)

研究對象及目標(biāo)：給定空間離散點(diǎn)集

式中，Pi＝(xi，yi，zi），n≥4。當(dāng)且僅當(dāng)n≥4時，4點(diǎn)不共面，對其進(jìn)行三維建模。

關(guān)于方向的確定，本文遵循右手法則。對于給定的三角形面片，對其法線方向使用右手準(zhǔn)則，相對觀察者而言，如果頂點(diǎn)以逆時針順序排列時，則為該三角形面片的正面；反之則為背面。

如圖1中的三棱錐P4―P1P2P3所示，對于面P1P2P3，v1為其外法線方向，按照右手準(zhǔn)則，正面的頂點(diǎn)環(huán)繞順序如圖中箭頭所示為P1→P2→P3→P1，背面的頂點(diǎn)序則為P3→P2→P1→P3。在本文中，面片的記法按照上述的表述進(jìn)行(記法中隱含了該面片的法線方向）。

圖1 右手法則

在給定三角形頂點(diǎn)的環(huán)繞順序后，面片的外法線向量也隨之被確定。以圖1中的面片P1P2P3為例，對應(yīng)的外法線向量v1可通過向量之間的叉積計算得到

對于點(diǎn)集Pn的一種閉合三角構(gòu)造，若內(nèi)部存在一點(diǎn)P，使得P點(diǎn)到各三角面片中心的向量VD與各面片的外法線向量Vn的點(diǎn)積VD·Vn≥0(用于確定三角面片外法線的方向），且不相鄰的三角面片不相交，則稱該構(gòu)造為針對點(diǎn)集Pn的一個簡單空間構(gòu)造，對應(yīng)的實(shí)體模型為簡單空間實(shí)體，點(diǎn)P稱為該構(gòu)造的核點(diǎn)。點(diǎn)P的集合稱為對應(yīng)于該構(gòu)造的核。

三、基本數(shù)據(jù)結(jié)構(gòu)的定義

根據(jù)建模算法的需要，定義一些基本的數(shù)據(jù)結(jié)構(gòu)，主要包括點(diǎn)、邊和面，見表1、表2、表3。

表1 點(diǎn)

點(diǎn)是基本的數(shù)據(jù)單位，其中，標(biāo)志位用于標(biāo)記該點(diǎn)的狀態(tài)，包括未用、已用或是同棱點(diǎn)。

表2 邊

表3 三角面片(外法線逆時針排序）

邊是直接用來描述模型的基本結(jié)構(gòu)之一。使用索引有一系列的優(yōu)點(diǎn)，可以避免由于在建模過程中執(zhí)行處理或后期空間分析時的浮點(diǎn)運(yùn)算導(dǎo)致模型開裂等問題。

如圖2所示，邊P1P2左側(cè)的三角形為P1P2P3，右側(cè)的三角形為P1P4P2，左右側(cè)的三角形拓?fù)湫畔⑹褂孟鄳?yīng)三角形的索引編號進(jìn)行設(shè)置，由此，邊P1P2便成為內(nèi)部邊。對于邊P1P4、P4P2、P2P3和P3P1，只有左側(cè)三角形，左側(cè)三角形的拓?fù)湫畔⑹褂孟鄳?yīng)三角形的索引編號設(shè)置，右側(cè)三角形的索引編號則設(shè)置為-1。邊代表了實(shí)體模型構(gòu)建過程中的一個側(cè)面，如果兩側(cè)均處于使用狀態(tài)，則該側(cè)面位于內(nèi)部；如果只有單側(cè)處于使用狀態(tài)，則為外部側(cè)面。在構(gòu)建模型的過程中，內(nèi)部邊/面將不再參與構(gòu)建工作，算法拓?fù)渫七M(jìn)的過程中只遍歷外側(cè)面。

圖2 邊的拓?fù)湫畔?/p>

面也是模型的基本拓?fù)浣Y(jié)構(gòu)之一。本文中涉及的面由三角形表示。對于頂點(diǎn)的索引，從頂點(diǎn)1→頂點(diǎn)2→頂點(diǎn)3，按照外法線右手法則確立；對于邊信息，采用相應(yīng)的邊索引號填充。標(biāo)志位記錄了構(gòu)成當(dāng)前面片邊的方向信息。如果構(gòu)成當(dāng)前三角形的邊與邊表中的邊同向，則相應(yīng)的bit置位；否則復(fù)位。

如圖3所示，如果構(gòu)成當(dāng)前三角面片的1號邊與邊表中的邊同向，則b0設(shè)置為1，反向則設(shè)置為 0；同理，如果2號邊與邊表中的邊同向，則b1設(shè)置為1，反向則設(shè)置為 0；如果3號邊與邊表中的邊同向，則b2設(shè)置為1，反向則設(shè)置為0。

最終建模算法中用到的主要數(shù)據(jù)容器包括主點(diǎn)集列表、K-鄰接表、邊表和面表。

圖3 三角面片的標(biāo)志位

四、三維構(gòu)造算法

以空間點(diǎn)集Pn為對象，具體的三維構(gòu)造算法如下：1）剔除同位點(diǎn)，并建立鄰接表。設(shè)立閾值Epsilon，對于給定的兩點(diǎn)P1和P2，如果兩點(diǎn)間的距離

則視點(diǎn)P1和P2為同位點(diǎn)，將其中的一點(diǎn)從主點(diǎn)集中剔除。同時，在遍歷點(diǎn)集的過程中，以每個點(diǎn)為鄰接表的表頭，計算出與其相鄰的最近K個點(diǎn)，并記錄在鄰接表中，本文中選K＝8(經(jīng)驗值）。在構(gòu)建鄰接表的過程中，對每條記錄內(nèi)部的K個鄰接點(diǎn)按照距離由小到大進(jìn)行排序，對于全部的鄰接表則依全部記錄中每條記錄的第1個鄰接點(diǎn)的距離由小到大進(jìn)行排序處理，所采用鄰接表的形式見表4。

表4 鄰接表的形式

3）起始邊及起始面片的確立。從鄰接表中選取最短邊作為起算邊，并通過篩選該最短邊的K臨近點(diǎn)，按照最小角最大化的原則選擇最優(yōu)點(diǎn)建立起始三角面片。以點(diǎn)C為中心，構(gòu)建初始三棱錐。使用公式VD·Vn≥0，確立三角面片的環(huán)繞方向。其中，VD為點(diǎn)C到三角面片中心的方向向量，Vn為自然順序下求得的法線向量。如果兩個向量的點(diǎn)積滿足大于等于0的條件，則使用自然順序；反之則將點(diǎn)位反序排列。創(chuàng)建面片變量，按計算確定的順序填充對應(yīng)的頂點(diǎn)信息域，并將其加入到面表中。

創(chuàng)建3個邊變量，使用初始面片的信息填充變量的各個域，并將它們加入到邊表中。按照邊表中邊的信息，填充面片中相應(yīng)邊的索引信息，將構(gòu)成該起始面片的3個頂點(diǎn)設(shè)置為“已使用”的狀態(tài)。

4）建立循環(huán)遍歷鄰接表。在遍歷鄰接表的時候遵循兩個原則，在建模的過程中建立變量跟蹤待插入點(diǎn)。優(yōu)先從前插入點(diǎn)的K個近鄰中選擇點(diǎn)作為當(dāng)前插入點(diǎn)；如果其近鄰都已執(zhí)行完插入操作，則順次遍歷鄰接表，取下一個表頭點(diǎn)作為當(dāng)前點(diǎn)。這種處理能夠有效地解決由于鄰接表K取值的有限性所導(dǎo)致的局部點(diǎn)群“被孤立”的問題。

判斷當(dāng)前點(diǎn)與以C為中心的已有各表面片的位置關(guān)系。在本文中，邊是有方向的。對于給定的點(diǎn)P，點(diǎn)P和邊PiPj的位置關(guān)系可轉(zhuǎn)換為向量VCP和面PiPjC的位置關(guān)系。計算PiPjC的外法線向量Vn，并計算點(diǎn)積VCP·Vn。設(shè)定閾值Epsilon2，如果VCP·Vn的絕對值小于Epsilon2，則認(rèn)為點(diǎn)P位于邊PiPj上；如果VCP·Vn＞Epsilon2，則點(diǎn)P位于邊PiPj的左側(cè)；反之，則位于右側(cè)。

如果點(diǎn)P位于面表中某一面片3條邊的左側(cè)，計算向量VCP與當(dāng)前面片外法線向量的點(diǎn)積，如果大于等于0，則該點(diǎn)位于三棱錐內(nèi)部。如果點(diǎn)P位于某條邊上，繼續(xù)測試點(diǎn)P與起點(diǎn)的距離是否小于當(dāng)前邊的長度，如果小于則位于邊上；反之則位于外部；如果點(diǎn)P既不在棱錐內(nèi)部，又不在某條邊上，則為外部點(diǎn)。待插入點(diǎn)與三棱錐構(gòu)成如下3種位置關(guān)系。

a.矢量VCPi在三棱錐內(nèi)部，如圖4所示。

圖4 當(dāng)前點(diǎn)位于某三棱錐內(nèi)部

b.矢量VCPi在三棱錐側(cè)面上，如圖5所示。

圖5 當(dāng)前點(diǎn)位于某棱錐的側(cè)面上

由于邊和面的拓?fù)湫畔⑹窍嚓P(guān)的，需做好新增面片和邊的記錄，以便于在插入完成后，更新相應(yīng)的拓?fù)湫畔ⅰ?/p>

c.矢量VCPi在三棱錐的外側(cè)，如圖6所示。

圖6 當(dāng)前點(diǎn)位于已有棱錐的外側(cè)

如果當(dāng)前點(diǎn)位于已建立棱錐的外側(cè)，則進(jìn)一步對其測試是否與已有棱錐的側(cè)棱同棱，如果當(dāng)前點(diǎn)與已有棱錐的某條棱同棱，則將其標(biāo)記置為“同棱點(diǎn)”，等待后續(xù)處理；否則繼續(xù)執(zhí)行主建模流程。

如圖6所示，點(diǎn)Pi位于已有棱錐的外側(cè)，遍歷邊表，如果邊表中當(dāng)前邊的兩側(cè)面片的拓?fù)湫畔⒍加行?不為-1）則跳過；如果只有一側(cè)有效，則判斷向量VCPi和該邊的位置關(guān)系，在一條邊只能被兩個面片所共享的條件下，完成外側(cè)邊的插入操作。圖6(a）中所示的VCPi只能看到部分棱錐，而圖6(b）中的VCPi則能看到當(dāng)前已有棱錐的全部外側(cè)面。執(zhí)行相應(yīng)的插入操作，并更新面表和邊表中相應(yīng)的拓?fù)湫畔ⅰ?/p>

隱含說明：在經(jīng)過上述位置判斷后，如果直接執(zhí)行插入操作，則最終的建模結(jié)果將會包含許多較深的“凹角”，數(shù)學(xué)上就是對應(yīng)二面角的平面角過小所導(dǎo)致的。在執(zhí)行插入操作的過程中，需在最小角最大化原則下，對新增面片執(zhí)行拓?fù)鋬?yōu)化。

5）將當(dāng)前點(diǎn)的標(biāo)志記為“已使用”的狀態(tài)，循環(huán)直到K鄰接表的表頭點(diǎn)全部處于“已使用”或“同棱點(diǎn)”狀態(tài)。

6）同棱點(diǎn)的處理。遍歷主點(diǎn)集列表，將每個標(biāo)記為同棱點(diǎn)的點(diǎn)插入到與其最近鄰的點(diǎn)構(gòu)成的面片中。其中包括了局部面片的打破和重建操作，以獲取最佳拓?fù)溥B接。

五、試 驗

使用C語言對本算法進(jìn)行了實(shí)現(xiàn)，采用兩套數(shù)據(jù)集進(jìn)行了試驗。數(shù)據(jù)集1是采用算法隨機(jī)生成的空間球面上的500個點(diǎn)，數(shù)據(jù)集2是某大型金屬礦山地下采空區(qū)的點(diǎn)云數(shù)據(jù)，其中有頂點(diǎn)23 939個。算法建模效果如圖7、圖8所示。

圖7 球面隨機(jī)采樣點(diǎn)集的建模效果

圖8 地下采空區(qū)點(diǎn)集的建模效果

六、結(jié) 論

本文從幾何的角度出發(fā)，研究了一種三維建模算法。在沒有考慮各點(diǎn)空間屬性的情形下，將各點(diǎn)對虛擬中心向量的權(quán)重選擇為1.0(即各點(diǎn)在數(shù)學(xué)上具有均等性）進(jìn)行建模的工作。最終的模型由三角面片組成，建模的結(jié)果非常方便體積和表面積等的計算。本文的建模算法可作為空間大型復(fù)雜實(shí)體或一體化建模的基石。下一步的研究工作是：①對算法進(jìn)行優(yōu)化，以期能采用更優(yōu)的復(fù)雜度來解決建模問題；②附加頂點(diǎn)屬性的權(quán)重Ki的計算方法及其對最終模型的影響。

[1]陳學(xué)工，李源，曹建，等.Delaunay三角網(wǎng)剖分的約束邊嵌入改進(jìn)算法[J].計算機(jī)工程與應(yīng)用，2009，45(24）：235-237.

[2]EDELSBRUNNER H，MUCKE E P.Three-dimensional Alpha Shapes[J].ACM Transactions on Graphics，1994，13(1）：43-72.

[3]HOPPE H，DEROSE T.Surface Reconstruction from Unorganized Points[J].Computer Graphics，1992，26(2）：71-78.

[4]LIN H，TAI C L，WANG G.A Mesh Reconstruction Algorithm Driven by Intrinsic Property of Point Cloud[J]. Computer-Aided Design，2004，36(1）：1-9.

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

[6]鄭德華，龐逸群，曹操.基于橢球面投影的散亂點(diǎn)云建立三角格網(wǎng)方法[J].測繪工程，2010，19(4）：19-23. [7]鄭德華，張云濤.基于物體表面散亂三維激光掃描點(diǎn)的三角形格網(wǎng)建立[J].測繪工程，2004，13(4）：62-65.

[8]鄭順義，蘇國中，張祖勛.3維點(diǎn)集的自動表面重構(gòu)算法[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2005，30(2）：154-157.

A Method of Three-dimensional Modeling over Spatial Unorganized Points Based on the K-nearest Neighbours

NI Shu，F(xiàn)ANG Yuanmin，LI Guozhu，CHEN Jie

以空間離散點(diǎn)集Pn＝{P1，P2，…，Pi，…，Pn}為研究對象，研究了一種三維建模算法。在預(yù)先約定外法線方向和優(yōu)化原則(最小角最大化）的基礎(chǔ)上進(jìn)行三維建模。第1步，對點(diǎn)集進(jìn)行同位點(diǎn)的剔除，并建立K-鄰近鄰接表；第2步，確定權(quán)重的計算方法，并計算虛擬中心點(diǎn)、各點(diǎn)相對于虛擬中心的向量及其長度范數(shù)；第3步，求定起始邊及起始面片；第4步，遍歷K-鄰接表，選擇當(dāng)前待插入點(diǎn)，分3種情況討論了待插入點(diǎn)與已有面表中面片和已有邊表中邊的關(guān)系，進(jìn)行插入和格網(wǎng)優(yōu)化操作，直到主點(diǎn)集中的點(diǎn)都處于“已使用”或“同棱點(diǎn)”的狀態(tài)；第5步，處理“同棱點(diǎn)”。通過上述環(huán)節(jié)完成對空間離散點(diǎn)集的三維建模操作，最后用C語言對算法進(jìn)行了實(shí)現(xiàn)，并采用相關(guān)的數(shù)據(jù)進(jìn)行了試驗，試驗結(jié)果證明了本算法的有效性。

空間離散點(diǎn)集；三維建模；空間實(shí)體；K-鄰近；地下采空區(qū)

P208

B

0494-0911(2014）10-0036-05

2013-09-09

國家自然科學(xué)基金(41161071）；昆明理工大學(xué)自然科學(xué)研究基金(KKSY201321063）

倪 曙(1969―），男，云南賓川人，高級工程師，主要研究方向為三維GIS、工程測量及大地測量。

倪曙，方源敏，李國柱，等.K-鄰近條件下空間實(shí)體三維建模算法研究[J].測繪通報，2014(10）：36-40.

10.13474/j.cnki.11-2246. 2014.0323