基于多分辨率半邊的三維地形自適應無縫建模

侯 紹 洋，趙 學 勝，王 鵬 飛

(中國礦業大學(北京)地球科學與測繪工程學院，北京 100083)

?

基于多分辨率半邊的三維地形自適應無縫建模

侯 紹 洋，趙 學 勝，王 鵬 飛

(中國礦業大學(北京)地球科學與測繪工程學院，北京 100083)

“限定四叉樹”法可以實現三維地形自適應無縫建模，但仍存在一些問題，如計算量大、數據冗余等。該文將多分辨率半邊理論引入到三維地形建模中，提出了適合自適應地形格網存儲和格網面提取的方法；設計并實現了三維地形自適應無縫建模的算法；最后，應用C語言和DirectX工具，開發了相應的可視化實驗系統。與“限定四叉樹”法相比，該方法不需要反復檢測相鄰格網的層差，且隨剖分層次的增加，格網數量和渲染數據量的降低率逐漸增大，分別達13.9%和12.2%(剖分層次為7)。

自適應建模；裂縫消除；限定四叉樹；多分辨率半邊

0 引言

地形自適應表達對三維地形建模十分有意義，其在滿足視覺要求的前提下，達到了節省內存空間、減少渲染數據量的目的[1-3]。四叉樹模型是自適應表達常用的模型之一，具有結構規范、層次清晰、易于空間索引、便于紋理鑲嵌等優點。但不同層次相鄰格網邊界處會出現裂縫，不僅影響視覺，而且從地表連續的角度而言，也是一種錯誤。目前，裂縫消除的方法有垂直邊緣法、頂點拉伸法和“限定四叉樹”法等。垂直邊緣法[4，5]是在各節點邊界周圍生成垂直邊，以遮擋裂縫，實際并未真正消除裂縫；頂點拉伸法[6，7]是對裂縫處的頂點高程進行調整，可能會導致T型節及地形失真；“限定四叉樹”法[8-11]雖然克服了以上兩種方法的缺陷，但是要求相鄰格網的剖分層差不大于1，導致數據存在冗余，且需要反復檢測相鄰格網的剖分層差，計算量大。

通過分析發現，產生“裂縫”問題的根本原因是：四叉樹結構將地形格網作為面的集合來存儲，只對面進行管理，剖分過程操作的唯一拓撲實體是面，未涉及格網邊的細分。為了從根本上解決此問題，本文擬將多分辨率半邊引入到三維地形建模中，構建不產生裂縫的地形自適應建模方法。目前，多分辨率半邊理論被應用于計算機圖形學領域，如模型多分辨率編輯和自適應細分等[12-14]。因為該方法將物體表面抽象成具有方向的邊的集合，通過邊管理面，邊剖分時，相應面與之同步細分，所以有望從根本上消除三維地形自適應表達中的“裂縫”現象。

1 基本理論

Fig.1 Adaptive partition based on multiresolution half-edges

除未剖分的半邊外，其余半邊均被多個層次使用。因此該理論下的半邊被稱為多分辨率半邊，可以看出相鄰格網的剖分層差沒有限制。

2 多分辨率半邊存儲原理與格網面提取方法

2.1 存儲原理

如圖2所示，上圖表示第L層引入的兩條半邊he1、he2及其對合關系，反向半邊指針被存儲于數組0位置；下圖表示第L+1層時，邊被剖分，再引入兩個半邊he3、he4，它們作為he1、he2的反向半邊存于數組1位置。即對于第j層引入的半邊he，如果其最大的剖分層次為k，那么he將存儲k-j+1個反向半邊指針，he與第i層的關系存儲于數組i-j位置。需要說明的是，多分辨率半邊用于三維地形自適應建模，其后繼半邊指針在引入后存儲內容不發生變化，所以本文不再贅述；而反向半邊指針如圖2所示，隨著邊的剖分，增加存儲更高層次的反向半邊指針。

圖2 反向半邊的存儲原理

Fig.2Storageprincipleofoppositehalf-edges

2.2 格網面提取方法

多分辨率半邊對格網面的管理是通過復合運算α1(α0(he))實現(圖3)。假設面A內部的半邊排列順序為逆時針，提取面A的所有頂點，可以從面A的任意一個半邊開始(如e1)，先對其求對合運算α0，得到反向半邊e2，再對e2求排列運算α1，得到面A的下一條半邊e3，反復執行α1(α0(he))，直到起始半邊e1，最終得到e1e3e5e7e9e11，半邊的起點集合就是面的頂點。面A此時已不再是四邊形，而是由6個半邊首尾相連組成的六邊形，多分辨率半邊結構能夠自適應的管理多邊形。

圖3 格網面提取方法

Fig.3 Extraction method of faces

3 自適應無縫建模算法流程

如圖4所示，基于多分辨率半邊的三維地形自適應無縫建模算法流程分為3個階段：第一，單層次格網建模：1)對初始格網建立半邊結構，并加入節點哈希表中。2)初始格網建立后，遍歷節點哈希表中上一層次剖分的節點(原節點)：如果原節點位于邊界處，則直接對3個半邊建立半邊結構，如果節點為非邊界點，那么求原節點相鄰的節點(鄰節點)；然后，判斷鄰節點是否存在：如果不存在，則對3個半邊建立半邊結構，如果存在，繼續判斷鄰節點是否剖分；如未剖分，則建立3個半邊的半邊結構，如剖分但未建立半邊結構，則建立4個半邊的半邊結構。3)遞歸執行前兩步，直到完全遍歷上一層次所有節點。第二，多層次格網建模：1)計算本層節點的細分準則，計算4個頂點和中心點的最大高差；2)如果超出閾值則繼續剖分，將下一層節點添加到節點哈希表，標注該層節點已剖分，求得新加入節點哈希表中的節點數n，并將判斷層次加1；遞歸執行步驟1，直到沒有新的節點加入，即n=0時，建模過程結束。第三，格網面的提取及可視化：1)遍歷半邊哈希表，若半邊沒有被繪制，執行復合運算α1(α0(he))，實現單個格網面的提取，并將找到的半邊標注為已繪制，直到半邊哈希表結尾；2)應用DirectX對提取的面進行逐個渲染，得到無縫三維地形。

4 實驗與分析

4.1 實驗設計

4.2 地形簡化分析

如表1所示，未簡化數據是指完全四叉樹剖分得到的數據，每個節點存儲9個指針，包括1個父節點，4個子節點和4個頂點坐標；簡化后的數據是指通過本文算法獲得的數據，每個半邊存儲1個頂點坐標、多個反向半邊和1個后繼半邊；簡化程度是簡化前后相關指標的比值。可以看出，隨剖分層次增加，簡化后/簡化前的值越來越小；當剖分層次達到7時，存儲空間和渲染三角形分別是未簡化數據的33.88%和22.16%。

圖4 自適應無縫建模算法流程

Fig.4 Flow chart of adaptive seamless modelling algorithm

圖5 基于多分辨率半邊的三維地形自適應表達

Fig.5 Adaptive expression of 3D terrain based on multiresolution half-edges

4.3 地形簡化對比分析

基于“限定四叉樹”對同一區域、按同一簡化標準進行自適應無縫建模，如圖6所示，與本文圖5e、圖5f形成對比。從圖6中可以看出，“限定四叉樹”法可以消除裂縫，但需滿足相鄰格網剖分層差不大于1，因此導致數據冗余；且該算法需要反復檢測格網間的剖分層差，導致計算量大。表2將本文算法與“限定四叉樹”法進行對比，其中四邊形個數、渲染三角形兩個指標，隨著剖分層次的提高，差距增大，當剖分到第7層時，本文算法比“限定四叉樹”法分別減少13.9%和12.2%；對于每個四邊形，“限定四叉樹”需要存儲13個指針，包括1個父節點、4個子節點、4個鄰節點、4個頂點坐標，當剖分到第7層時，本文方法已略小于“限定四叉樹”法。從變化趨勢可以看出，剖分層次越高，本文方法優勢越明顯。

表1 地形簡化

Table1Terrainsimplification

層次M1未簡化簡化后簡化程度存儲量M2渲染量M3存儲量M4渲染量M5存儲量M6=M4/M2渲染量M7=M5/M3094244266．67100136168016222．2210021446423254161．1184．383576256736191127．7874．61423041024224861597．5760．065921640966720190272．9246．446368641638419120551351．8733．65714745665536499521452033．8822．16

5 結論

圖6 基于“限定四叉樹”的三維地形自適應表達

Fig.6 Adaptive expression of 3D terrain based on "restrained quadtree"

表2 地形簡化對比分析

Table 2 Contrastive analysis of terrain simplification

層次(Q1)簡化后四邊形的個數對比簡化后需繪制的三角形個數對比簡化后的存儲空間對比限定四叉樹(Q2)多分辨率半邊(Q3)降低率M4=(Q2-Q3)/Q3?100限定四叉樹(Q5)多分辨率半邊(Q6)降低率Q7=(Q5-Q6)/Q5?100限定四叉樹(Q8)多分辨率半邊(Q9)降低率Q10=(Q8-Q9)/Q8?1000110．0440．01324-84．621440．016160．05280-53．85213130．054540．0169232-37．28349466．12011915．0637736-15．5441541455．86486155．120022248-12．2954934459．7207519028．364096720-4．8561426127610．5606955139．21853819120-3．1473859332213．9165461452012．250167499520．43

為了從根本上解決三維地形不同層次相鄰格網間的“裂縫”問題，本文提出基于多分辨率半邊的自適應無縫表達方法。該方法不需要限制相鄰格網間的剖分層差，簡化后的地形數據簡潔、無冗余，且不需要反復檢測相鄰格網的層次，計算量大幅降低。實驗結果表明：本文方法能夠實現三維地形自適應無縫建模，且與“限定四叉樹”法相比，隨剖分層次的增加，格網數量和渲染數據量的降低率逐漸增大，當剖分層次為7時，以上兩個指標分別為13.9%和12.2%，優于 “限定四叉樹”法。下一步研究內容包括基于多分辨率半邊的三維地形數據更新方法、數據查詢方法等。

[1] 孔川，羅大庸．利用動態多分辨率LOD技術的地形簡化研究[J]．計算機工程與應用，2010，46(27)：156-159．

[2] 花海洋，趙懷慈．保持地形特征的網格模型簡化算法[J].計算機輔助設計與圖形學學報，2011，23(4)：594-599．

[3] PAJAROLA R,DECORO C.Efficient implementation of real-time view-dependent multiresolution meshing[J].Visualization and Computer Graphics,IEEE Transactions on,2004,10(3):353-368.

[4] 靳海量，高井祥．大規模地形實時可視化算法[J]．測繪科學技術學報，2006，23(1)：65-68．

[5] 胡愛華，何宗宜，馬曉萍．基于LOD的大規模地形實時繪制方法[J]．測繪通報，2009(12)：23-26．

[6] 孫文彬，趙學勝．基于QTM格網的空間數據無縫層次建模[J]．中國礦業大學學報，2008，37(5)：675-679.

[7] 芮小平，張彥敏.一種實時連續LOD技術的改進算法[J].系統仿真學報，2004，16(1)：2628-2630.

[8] DENG B S,DENG T Q,YU R H,et al.Seamless rendering of large scale terrain[C].Advanced Engineering Forum，2012,6:1026-1030.

[9] 趙學勝，白建軍，王志鵬.基于QTM的全球地形自適應可視化模型[J].測繪學報，2007，36(3)：316-320.

[10] 史文中，吳立新，李清泉，等.三維空間信息系統模型與算法[M].北京：電子工業出版社，2007.196-197.

[11] 王源，劉建永，江南，等.視點相關實時LOD地形模型動態構網算法[J].測繪學報，2003，32(1)：47-52.

[12] KRAEMER P,CAZIER D,BECHMANN D.Extension of half-edges for the representation of multiresolution subdivision surfaces[J].The Visual Computer,2009,25(2):149-163.

[13] KRAEMER P,CAZIER D,BECHMANN D.A general and efficient representation for multiresolution meshes:Application to Quad/triangle subdivision[C].CCCG,2007.257-260.

[14] MOUSA M H,HUSSEIN M K.Multiresolution surface representation using combinatorial maps[J].International Journal of Computers,2012,6(2):103-110.

An Adaptive Seamless Model of 3D Terrain Based on Multiresolution Half-Edges

HOU Shao-yang,ZHAO Xue-sheng,WANG Peng-fei

(CollegeofGeosciencesandSurveyEngineering,ChinaUniversityofMining&Technology(Beijing),Beijing100083,China)

Although the adaptive seamless modelling of 3D terrain can be realized based on "restricted quadtree",there are still some problems,such as abundant calculation,data redundancy,etc.The main contents are as follows.Firstly,the theory of multiresolution half-edges is introduced into the 3D terrain modelling,and a new method suitable for mesh storage and faces extraction is put forward in this paper.Then,an adaptive seamless algorithm of 3D terrain is designed and achieved.Finally,by using Clanguage and DirectX tools,an experimental system is developed.The results show that the adaptive seamless modelling of 3D terrain can be realized based on the multiresolution half-edges structure.Compared with the "restricted quadtree",this method does not need to check the level difference repeatedly between the adjacent nodes,and with the increase of partition level,reduction rate of the grid numbers and rendering data are gradually increasing,reaching 13.9% and 12.2% in 7th level.

adaptive seamless modelling;crack elimination;restrained quadtree;multiresolution half-edges

2014-07-28；

2014-09-18

國家自然科學基金面上項目“顧及多類型數據無縫融合的全球離散格網自適應建模”(41171306)；高等學校博士學科點專項科研基金項目“基于LiDAR點云的地表拓撲建模與形變分析研究”(20130023110001)

侯紹洋(1986-)，男，博士研究生，從事全球離散格網建模研究。E-mail:housaoyang@163.com

10.3969/j.issn.1672-0504.2015.02.003

P208

A

1672-0504(2015)02-0012-04