侯 紹 洋，趙 學 勝，王 鵬 飛

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

?

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

侯 紹 洋，趙 學 勝，王 鵬 飛

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

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

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

0 引言

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

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

1 基本理論

Fig.1 Adaptive partition based on multiresolution half-edges

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

2 多分辨率半邊存儲原理與格網(wǎng)面提取方法

2.1 存儲原理

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

圖2 反向半邊的存儲原理

Fig.2Storageprincipleofoppositehalf-edges

2.2 格網(wǎng)面提取方法

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

圖3 格網(wǎng)面提取方法

Fig.3 Extraction method of faces

3 自適應(yīng)無縫建模算法流程

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

4 實驗與分析

4.1 實驗設(shè)計

4.2 地形簡化分析

如表1所示，未簡化數(shù)據(jù)是指完全四叉樹剖分得到的數(shù)據(jù)，每個節(jié)點存儲9個指針，包括1個父節(jié)點，4個子節(jié)點和4個頂點坐標；簡化后的數(shù)據(jù)是指通過本文算法獲得的數(shù)據(jù)，每個半邊存儲1個頂點坐標、多個反向半邊和1個后繼半邊；簡化程度是簡化前后相關(guān)指標的比值?？梢钥闯觯S剖分層次增加，簡化后/簡化前的值越來越小；當剖分層次達到7時，存儲空間和渲染三角形分別是未簡化數(shù)據(jù)的33.88%和22.16%。

圖4 自適應(yīng)無縫建模算法流程

Fig.4 Flow chart of adaptive seamless modelling algorithm

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

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

4.3 地形簡化對比分析

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

表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 結(jié)論

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

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

表2 地形簡化對比分析

Table 2 Contrastive analysis of terrain simplification

層次(Q1)簡化后四邊形的個數(shù)對比簡化后需繪制的三角形個數(shù)對比簡化后的存儲空間對比限定四叉樹(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

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

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

[2] 花海洋，趙懷慈．保持地形特征的網(wǎng)格模型簡化算法[J].計算機輔助設(shè)計與圖形學學報，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] 靳海量，高井祥．大規(guī)模地形實時可視化算法[J]．測繪科學技術(shù)學報，2006，23(1)：65-68．

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

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

[7] 芮小平，張彥敏.一種實時連續(xù)LOD技術(shù)的改進算法[J].系統(tǒng)仿真學報，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的全球地形自適應(yīng)可視化模型[J].測繪學報，2007，36(3)：316-320.

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

[11] 王源，劉建永，江南，等.視點相關(guān)實時LOD地形模型動態(tài)構(gòu)網(wǎng)算法[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

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

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

10.3969/j.issn.1672-0504.2015.02.003

P208

A

1672-0504(2015)02-0012-04