趙學(xué)勝，范德芹，王嬌嬌，王 磊

1.中國礦業(yè)大學(xué)（北京）地球與測(cè)繪工程學(xué)院，北京 100083；2.北京師范大學(xué) 資源學(xué)院，北京 100875

1 引 言

隨著空間數(shù)據(jù)采集技術(shù)的飛速發(fā)展和全球經(jīng)濟(jì)一體化的不斷深入，許多應(yīng)用領(lǐng)域如全球環(huán)境變化監(jiān)測(cè)、災(zāi)害的預(yù)報(bào)預(yù)警、資源可持續(xù)開發(fā)、大型工程設(shè)計(jì)、國防安全乃至戰(zhàn)爭、“數(shù)字地球”等，越來越頻繁地使用大范圍（甚至全球）高分辨率地形數(shù)據(jù)進(jìn)行分析決策。但是，由于受當(dāng)前的計(jì)算機(jī)硬件及網(wǎng)絡(luò)的限制，為了提高顯示效率并實(shí)現(xiàn)全球DEM數(shù)據(jù)的無縫繪制和渲染，就需要在保證地形精度的前提下進(jìn)行DEM格網(wǎng)簡化，即構(gòu)建全球多分辨率DEM表達(dá)模型。這樣就不可避免地在相鄰不同分辨率DEM格網(wǎng)之間產(chǎn)生裂縫，因而消除鄰近格網(wǎng)間的裂縫成為全球地形多分辨率連續(xù)表達(dá)的關(guān)鍵問題之一［1］。

目前傳統(tǒng)的裂縫消除方法主要有：垂直邊緣法、漸變法、調(diào)整高程值法等。垂直邊緣法（vertical skirt）［2－4］即在塊的邊界上建立一個(gè)由地表到水平面的垂直外包體，當(dāng)有塊間裂縫存在時(shí)，在視覺上裂縫將被“垂直裙”擋住，但并未從本質(zhì)上消除。此法只適用于不同分辨率分層加載格網(wǎng)的情況，不適用于消除同一層次不同分辨率格網(wǎng)簡化時(shí)產(chǎn)生的裂縫。漸變法［5－11］采用限制性四叉樹（即控制鄰近格網(wǎng)的剖分層次差），再通過平滑數(shù)據(jù)、增減節(jié)點(diǎn)或網(wǎng)格線等方式實(shí)現(xiàn)裂縫消除。該方法要求相鄰地塊的剖分層次差不能超過1，并需要時(shí)刻檢測(cè)邊界，計(jì)算量大［12－13］，若用于全球會(huì)產(chǎn)生大量冗余三角形。調(diào)整高程值法［14－15］通過調(diào)整裂縫處節(jié)點(diǎn)的高程值實(shí)現(xiàn)無縫拼接，會(huì)導(dǎo)致T型節(jié)及地形失真，也會(huì)帶來繪制時(shí)的光照不連續(xù)現(xiàn)象，對(duì)于有些顯卡也可能導(dǎo)致一些空洞小點(diǎn)。其他方法還有：自適應(yīng)網(wǎng)格法［16］、簇依賴（cluster dependencies）法［17］及跳點(diǎn)法［18］等。

上述研究大都針對(duì)局部地形進(jìn)行可視化操作，若應(yīng)用于全球，將可能大大增加數(shù)據(jù)量，尤其在南北兩極處，將會(huì)出現(xiàn)大量的數(shù)據(jù)冗余，造成不必要的計(jì)算資源消耗，降低顯示效率［19］。針對(duì)上述問題，本文擬采用全球退化四叉樹（degenerate quadtree grid）格網(wǎng)作為實(shí)現(xiàn)全球多分辨率DEM格網(wǎng)無縫表達(dá)的構(gòu)?？蚣堋Ｈ駾QG是一種類似經(jīng)緯度格網(wǎng)的全球離散格網(wǎng)系統(tǒng)，不同的是涉及極點(diǎn)的格網(wǎng)退化為三角形，而這種退化是規(guī)則的和自適應(yīng)的，既可以直接利用以經(jīng)緯度格網(wǎng)為參考系的各種新舊數(shù)據(jù)源，又避免了經(jīng)緯度格網(wǎng)的非均勻性和極點(diǎn)奇異性問題，且易于構(gòu)建空間鄰近關(guān)系和檢索機(jī)制［20］。本文重點(diǎn)探討全球退化四叉樹的層次分塊構(gòu)建方法，設(shè)計(jì)了由于格網(wǎng)簡化所產(chǎn)生的各類裂縫自適應(yīng)消除算法。最后，通過屬性渲染，實(shí)現(xiàn)了全球多分辨率DEM格網(wǎng)的無縫可視化表達(dá)。

2 基于退化四叉樹的全球分塊結(jié)構(gòu)及格網(wǎng)簡化

2.1 球面退化四叉樹格網(wǎng)剖分原理

球面退化四叉樹格網(wǎng)的初始剖分和QTM（quaternary triangular mesh）一樣，選取球內(nèi)接正八面體作為球面格網(wǎng)劃分的基礎(chǔ)，其頂點(diǎn)占據(jù)球面主要點(diǎn)（包括兩極），而邊的投影則與赤道、主子午線和90°、180°、270°子午線重合，首次剖分將球面劃分成8個(gè)等正球面三角形（亦稱八分體）。在進(jìn)一步對(duì)每一個(gè)初始八分體（三角形）進(jìn)行細(xì)分時(shí)，首先對(duì)初始三角形3個(gè)頂點(diǎn)的經(jīng)緯度進(jìn)行兩兩平分，得到3個(gè)新點(diǎn)（這3個(gè)點(diǎn)位于球面上），將三角形兩腰上的兩個(gè)新點(diǎn)彼此連成一條緯線，再將該緯線的中點(diǎn)與另一新點(diǎn)彼此連成一條經(jīng)線，這樣就形成了一個(gè)新的球面三角形和兩個(gè)四邊形，如圖1（a）所示；在第二層次，對(duì)于三角形部分按第一次剖分的方法進(jìn)行剖分，對(duì)于四邊形部分，將四邊形4個(gè)頂點(diǎn)的經(jīng)緯度進(jìn)行兩兩平分，得到4個(gè)新四邊形，如圖1（b）所示；在第三層次依此類推，如圖1（c）所示；如此遞歸進(jìn)行，直到滿足一定的分辨率要求為止，詳細(xì)請(qǐng)參考文獻(xiàn)［17］。

圖1 球面退化四叉樹層次剖分Fig.1 Hierarchical partition of spherical degenerate quadtree grid

2.2 DQG球面分塊四叉樹結(jié)構(gòu)模型

下面在球面DQG剖分的基礎(chǔ)上對(duì)八分體進(jìn)行分塊，構(gòu)建球面DQG分塊四叉樹結(jié)構(gòu)。當(dāng)剖分層次為4時(shí)，如圖2所示，將北半球的一個(gè)八分體（已劃分為三角形）剖分成10個(gè)部分。由于八分體結(jié)構(gòu)的對(duì)稱性，在用四叉樹方法生成格網(wǎng)時(shí)，只需考慮八分體的一半即可，另一半與其結(jié)構(gòu)相同。以八分體左側(cè)部分為例，將其劃分為Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ5個(gè)地塊。塊Ⅰ為三角形，對(duì)應(yīng)為極點(diǎn)附近三角形塊；塊Ⅱ?yàn)樗倪呅螇K，對(duì)應(yīng)為非四叉樹四邊形塊，其上側(cè)鄰近格網(wǎng)為極點(diǎn)三角形塊Ⅰ，下側(cè)鄰近格網(wǎng)為四叉樹塊Ⅲ；塊Ⅲ的上側(cè)鄰近格網(wǎng)為非四叉樹四邊形塊Ⅱ，下側(cè)鄰近格網(wǎng)為四叉樹塊Ⅳ；塊Ⅳ上側(cè)鄰近格網(wǎng)為四叉樹塊Ⅲ，下側(cè)鄰近格網(wǎng)為四叉樹塊Ⅴ；四叉樹塊Ⅴ上側(cè)鄰近格網(wǎng)為四叉樹塊Ⅳ，下側(cè)鄰近格網(wǎng)為南半球八分體中與其層次相同的四叉樹塊。在此八分體中，極點(diǎn)三角形塊Ⅰ和Ⅹ、非四叉樹四邊形塊Ⅱ和Ⅸ不需要簡化，因其已屬最簡形式，只有在去除所有頂點(diǎn)高程近似相等的格網(wǎng)或去除海面格網(wǎng)（各頂點(diǎn)高程均為0）時(shí)才考慮將其去除；對(duì)于四叉樹塊Ⅲ、Ⅷ、Ⅳ、Ⅴ、Ⅵ 和Ⅶ，則需考慮用四叉樹格網(wǎng)細(xì)分簡化方法進(jìn)行簡化。

球面分塊四叉樹模型的構(gòu)建方法如圖2所示。在一個(gè)八分體中，四叉樹塊Ⅲ、Ⅳ、Ⅴ、Ⅵ、Ⅶ和Ⅷ 均視為球面八分體的一個(gè)地塊。將每一地塊的中心點(diǎn)作為根節(jié)點(diǎn)，從這個(gè)根節(jié)點(diǎn)出發(fā)，檢查根節(jié)點(diǎn)是否滿足某種分割條件，即根據(jù)格網(wǎng)4個(gè)頂點(diǎn)與其各邊中點(diǎn)高差是否在閾值內(nèi)，若在閾值內(nèi)則不再對(duì)格網(wǎng)進(jìn)行細(xì)分，并將其作為葉節(jié)點(diǎn)保存；否則把根節(jié)點(diǎn)遞歸地不斷分割成相等的4個(gè)節(jié)點(diǎn)區(qū)域，直到不能再分割為止，若一直不在閾值內(nèi)就細(xì)分到設(shè)定的最高層次。對(duì)于八分體中的非四叉樹塊Ⅱ、三角形塊Ⅰ，因其已經(jīng)為最簡形式，所以不需對(duì)其繼續(xù)分割。在DQG剖分方法中，全球是由8個(gè)八分體構(gòu)成的，因而當(dāng)剖分層次為4時(shí)，將全球剖分成16個(gè)極點(diǎn)三角形塊，16個(gè)極點(diǎn)附近四邊形塊，48個(gè)四叉樹地塊。

圖2 北半球的一個(gè)八分體（剖分層次為4）Fig.2 An octahedron of northern hemisphere（partition level is 4）

該方法可以避免生成多余三角形，最大限度地實(shí)現(xiàn)格網(wǎng)簡化目標(biāo)。但這樣在節(jié)點(diǎn)拼接處會(huì)產(chǎn)生格網(wǎng)分辨率差大于1的復(fù)雜裂縫。此外，由于是對(duì)全球進(jìn)行分塊退化四叉樹分割，在各個(gè)分塊間進(jìn)行拼接時(shí)也將產(chǎn)生不同類型的裂縫，下節(jié)重點(diǎn)討論裂縫的類型及消除方法。

3 多分辨率格網(wǎng)裂縫的自適應(yīng)消除方法

對(duì)于節(jié)點(diǎn)分辨率層次不同的情況，消除不同類型的裂縫通常有兩種方法：在拼接處增加一條邊，或去掉一條邊。相對(duì)來說，第1種方法更復(fù)雜，但是也更全面，適用于拼接處兩個(gè)節(jié)點(diǎn)的分辨率相差任意大的情況。第2種方法則更加簡單，但它要求拼接處的兩個(gè)節(jié)點(diǎn)的層次差距最多不超過1。本文綜合采用了這兩種消除裂縫的方法，并充分利用四叉樹索引結(jié)構(gòu)的特點(diǎn)，對(duì)格網(wǎng)節(jié)點(diǎn)進(jìn)行搜索，分別對(duì)四叉樹塊內(nèi)、四叉樹塊間及四叉樹塊與非四叉樹塊間的裂縫進(jìn)行了消除。

3.1 四叉樹塊內(nèi)裂縫的消除方法

根據(jù)四叉樹塊內(nèi)簡化格網(wǎng)與鄰近格網(wǎng)相差的層次不同，裂縫的消除分為兩種情況：一種是與鄰近格網(wǎng)相差一個(gè)層次，另一種是相差兩個(gè)及以上層次。

3.1.1 鄰近格網(wǎng)相差一個(gè)層次

此時(shí)去掉1條邊，將相鄰的葉節(jié)點(diǎn)的兩個(gè)子三角形進(jìn)行合并，就可以消除裂縫，具體如圖3所示。

四叉樹塊內(nèi)簡化格網(wǎng)abcd與未簡化格網(wǎng)adgf相差一個(gè)細(xì)分層次，即簡化格網(wǎng)abcd的寬度為未簡化格網(wǎng)adgf的兩倍。根據(jù)設(shè)定的四叉樹節(jié)點(diǎn)可知，簡化格網(wǎng)abcd的中心點(diǎn)o為葉節(jié)點(diǎn)，未簡化格網(wǎng)adgf的中心點(diǎn)e為根節(jié)點(diǎn)，根據(jù)設(shè)定的四叉樹細(xì)分條件，eo之間距離為格網(wǎng)adgf寬度的兩倍，此時(shí)若o點(diǎn)為根節(jié)點(diǎn)則將三角形ade細(xì)分，連接ep點(diǎn)；若o為葉節(jié)點(diǎn)則不再將三角形ade細(xì)分，不連接ep點(diǎn)。類似的，對(duì)于簡化格網(wǎng)abcd與其下側(cè)、左側(cè)、右側(cè)鄰近的未簡化格網(wǎng)層次相差1的情況，均采用此法消除裂縫。

3.1.2 鄰近格網(wǎng)相差兩個(gè)及以上層次

當(dāng)相鄰節(jié)點(diǎn)細(xì)分層次超過1時(shí)，消除裂縫的原理是：先根據(jù)3.1.1的方法消除相鄰節(jié)點(diǎn)間相差一個(gè)層次的裂縫，然后根據(jù)四叉樹節(jié)點(diǎn)之間的關(guān)系，搜索到已簡化的格網(wǎng)，再分別按層次搜索與其鄰近的上側(cè)、下側(cè)、左側(cè)、右側(cè)相同寬度（即相同細(xì)分層次）的格網(wǎng)節(jié)點(diǎn)的標(biāo)識(shí)。若相鄰格網(wǎng)寬度相同，則不需要消除裂縫；若相鄰格網(wǎng)寬度大于簡化的格網(wǎng)，亦不需要消除裂縫；若相鄰格網(wǎng)寬度小于簡化的格網(wǎng)寬度的1／2，則根據(jù)節(jié)點(diǎn)標(biāo)識(shí)記錄裂縫點(diǎn)，并同時(shí)存儲(chǔ)裂縫三角形的坐標(biāo)，最后繪制三角形時(shí)讀出裂縫三角形的坐標(biāo)文件，實(shí)現(xiàn)裂縫的消除繪制與顯示。

如圖4（a）所示，以簡化的四邊形abcd為例，只考慮四邊形abcd格網(wǎng)上側(cè)相鄰的三角形A、B。由于P點(diǎn)高程插值后不一定與直線ad內(nèi)插中點(diǎn)的高程相等，從而格網(wǎng)簡化后可能產(chǎn)生裂縫三角形apd，若要對(duì)其進(jìn)行消除，則需要補(bǔ)充繪制三角形apd。圖4（b）所示為消除格網(wǎng)abcd簡化引起的裂縫后的效果。采用同樣方法進(jìn)行下側(cè)鄰近、左側(cè)鄰近、右側(cè)鄰近的四叉樹格網(wǎng)內(nèi)部裂縫的消除。

圖4 塊內(nèi)簡化格網(wǎng)與鄰近格網(wǎng)相差兩個(gè)及以上層次的裂縫消除Fig.4 Level difference between adjacent grids is two or more

3.2 塊間裂縫的消除方法

根據(jù)裂縫沿緯度方向還是經(jīng)度方向不同，塊間裂縫分為上下塊間裂縫和左右塊間裂縫，下面首先給出上下裂縫的不同類型及相應(yīng)的消除方法。如圖2所示，上下塊間裂縫分為以下幾種不同類型。

類型1：塊邊界上側(cè)為極點(diǎn)三角形塊，下側(cè)為非四叉樹塊，如Ⅰ與Ⅱ。

類型2：塊邊界上側(cè)為非四叉樹塊，下側(cè)為四叉樹塊，如Ⅱ與Ⅲ。

類型3：塊邊界上側(cè)為四叉樹塊，下側(cè)也為四叉樹塊，如Ⅲ與Ⅳ、Ⅳ與Ⅴ。

對(duì)于塊邊界裂縫類型1，只考慮八分體的左側(cè)部分，如圖5（a）所示，可見極點(diǎn)三角形塊Ⅰ與其底邊鄰近的非四叉樹四邊形塊Ⅱ間不存在裂縫。

對(duì)于塊間裂縫類型2（如圖2中的Ⅱ部分和Ⅲ部分）：① 若下側(cè)四叉樹塊Ⅲ已簡化，如圖5（b）所示，此時(shí)上下塊Ⅱ、Ⅲ間不存在裂縫；② 若下側(cè)四叉樹塊Ⅲ未簡化（如圖5（c）），由于非四叉樹格網(wǎng)的層次比其塊邊界下側(cè)四叉樹格網(wǎng)層次大1，將可能在ab中點(diǎn)p處產(chǎn)生裂縫，可通過添加三角形apb消除裂縫，如圖5（d）所示。

圖5 類型1和類型2Fig.5 Type 1and type 2

對(duì)于塊邊界裂縫類型3，又可根據(jù)塊邊界上下側(cè)簡化情況不同細(xì)分為3種情況：① 塊邊界上側(cè)鄰近格網(wǎng)未簡化，下側(cè)亦未簡化或簡化后格網(wǎng)寬度小于等于塊邊界上側(cè)格網(wǎng)，此種情況記為類型3－1；② 塊邊界上側(cè)格網(wǎng)簡化，下側(cè)未簡化或簡化后寬度小于等于邊界上側(cè)格網(wǎng)，此種情況記為類型3－2；③ 塊邊界下側(cè)格網(wǎng)簡化后寬度大于塊邊界上側(cè)鄰近格網(wǎng)未簡化或簡化后的寬度，此種情況記為類型3－3。

對(duì)于塊邊界類型3－1，由于上下塊間在進(jìn)行DQG剖分時(shí)已相差一個(gè)剖分層次，而不同塊的四叉樹結(jié)構(gòu)是相對(duì)獨(dú)立的，因此在塊間邊界處將出現(xiàn)裂縫。如圖6所示，塊邊界上側(cè)四叉樹格網(wǎng)iack未簡化，其寬度為ab，塊邊界下側(cè)格網(wǎng)adeb未簡化，其寬度為ap＝ab／2，塊邊界下側(cè)格網(wǎng)befc已簡化，寬度為bc＝ab?？梢娫谔砑痈叱虝r(shí)上下塊邊界p點(diǎn)處出現(xiàn)裂縫。

圖6 類型3－1裂縫消除前后Fig.6 Before and after type 3－1cracks elimination

消除裂縫方法為：

（1）根據(jù)塊邊界上側(cè)四叉樹格網(wǎng)的四叉樹結(jié)構(gòu)節(jié)點(diǎn)標(biāo)識(shí)，搜索出邊界上側(cè)鄰近的未簡化格網(wǎng)的中心點(diǎn)j的坐標(biāo)及格網(wǎng)寬度ab。

（2）根據(jù)j點(diǎn)坐標(biāo)及格網(wǎng)寬度ab確定塊邊界下側(cè)鄰近格網(wǎng)搜索的最大寬度為ab。

（3）根據(jù)塊邊界下側(cè)四叉樹的標(biāo)識(shí)，確定下側(cè)鄰近格網(wǎng)的寬度，由此可知未簡化格網(wǎng)adeb的寬度小于上側(cè)格網(wǎng)iack的寬度，因此在上下塊邊界拼接處產(chǎn)生裂縫，并確定裂縫點(diǎn)為p。簡化格網(wǎng)bcef的寬度等于上側(cè)格網(wǎng)iack的寬度，因此塊邊界上側(cè)三角形jbc與塊邊界下側(cè)三角形bec之間不存在裂縫。

（4）根據(jù)p點(diǎn)和已知的a、b點(diǎn)，存儲(chǔ)三角形apb的坐標(biāo)。將四叉樹中三角形格網(wǎng)坐標(biāo)轉(zhuǎn)換為經(jīng)緯度坐標(biāo)，再將經(jīng)緯度坐標(biāo)轉(zhuǎn)換為三維空間坐標(biāo)，存儲(chǔ)在三維坐標(biāo)文件中，用于最終三維圖形的繪制與顯示。

對(duì)于塊邊界裂縫類型3－2、3－3，雖然塊邊界上下側(cè)簡化情況不同，但裂縫消除原理同第1種情況。如圖7至8所示，裂縫點(diǎn)分別為p1和p2，消除裂縫需添加的三角形分別為ap1b和p1p2b、ap1d和p1p2d。

圖7 類型3－2裂縫消除前后Fig.7 Before and after type 3－2cracks elimination

圖8 類型3－3裂縫消除前后Fig.8 Before and after type 3－3cracks elimination

左右塊間簡化只存在一種情況：塊邊界左右側(cè)均為四叉樹塊Ⅴ和Ⅵ（如圖2），它們?cè)试S細(xì)分的最小寬度相同。當(dāng)塊邊界兩側(cè)簡化格網(wǎng)寬度與未簡化格網(wǎng)寬度不同時(shí)，將會(huì)在邊界處出現(xiàn)裂縫，消除裂縫的原理及方法與四叉樹塊內(nèi)左右側(cè)消除裂縫方法類似。

4 試驗(yàn)結(jié)果與分析

試驗(yàn)采用美國地質(zhì)測(cè)量局（USGS）發(fā)布的地形數(shù)據(jù)GTOPO30為數(shù)據(jù)源，根據(jù)雙線性插值方法獲取格網(wǎng)點(diǎn)高程。應(yīng)用VC＋＋6.0語言和OpenGL三維工具，設(shè)計(jì)開發(fā)了基于球面退化四叉樹的全球多分辨率DEM無縫可視化原型系統(tǒng)。根據(jù)GTOPO30數(shù)據(jù)精度，在本次試驗(yàn)中格網(wǎng)剖分層次最高為12層。試驗(yàn)結(jié)果得到裂縫消除前后對(duì)照?qǐng)D（如圖9a）以及相應(yīng)的屬性渲染圖（如圖9b）。紅色面片及圈出部分表示消除裂縫所需添加的三角形。由于是在球面顯示，有些裂縫三角形由于球體旋轉(zhuǎn)的角度不同，在屏幕上捕捉圖時(shí)看不見，而局部放大圖裂縫則清晰可見（如圖10）。

圖9 全球DQG格網(wǎng)裂縫消除前后對(duì)照及相應(yīng)的屬性渲染圖Fig.9 Before and after cracks elimination of global DQG and the corresponding render

圖10 局部放大圖Fig.10 Enlarged figures in local area

格網(wǎng)簡化、裂縫消除前后的格網(wǎng)數(shù)目及對(duì)比分析結(jié)果見表1。其中：

（1）裂縫消除代價(jià)——定義為以消除裂縫增加的三角形數(shù)與格網(wǎng)簡化減少的三角形數(shù)之比（以%表示）；

（2）簡化效率——表示為簡化前總格網(wǎng)數(shù)（qz）減去格網(wǎng)簡化及裂縫消除后總格網(wǎng)數(shù)qj除以簡化前總格網(wǎng)數(shù)qz（以%表示）。

可見，DQG格網(wǎng)簡化數(shù)目隨著剖分層次的遞增迅速增加，而消除裂縫增加的三角形數(shù)隨著剖分層次的遞增僅有小幅增加，這使得最終的簡化效果十分明顯。其中，裂縫消除代價(jià)隨著剖分層次的遞增迅速下降（如圖11）；而簡化效率隨剖分層次的增加而增加（如圖12），剖分層次越高，簡化效果越明顯，12層時(shí)的簡化效率已接近67%，優(yōu)于傳統(tǒng)的經(jīng)緯度格網(wǎng)（其簡化效率在7層之后趨近于常值45%，如表1和圖12）。

5 結(jié) 論

本文提出一種基于退化四叉樹格網(wǎng)的全球多分辨率DEM無縫可視化表達(dá)方法。該方法在不限制相鄰節(jié)點(diǎn)間剖分層次的前提下，根據(jù)地形粗糙度對(duì)格網(wǎng)進(jìn)行充分簡化，并對(duì)簡化過程中產(chǎn)生的各種塊內(nèi)、塊間裂縫進(jìn)行自適應(yīng)消除。試驗(yàn)結(jié)果表明：采用本文方法進(jìn)行格網(wǎng)簡化并消除裂縫后，格網(wǎng)數(shù)目大大減少，呈現(xiàn)簡化效率隨格網(wǎng)剖分層次遞增而提高的規(guī)律，當(dāng)格網(wǎng)剖分層次為12層時(shí)，簡化效率為66.8%，明顯優(yōu)于傳統(tǒng)的經(jīng)緯度格網(wǎng)。初步實(shí)現(xiàn)了全球多分辨率DEM的無縫可視化表達(dá)，基本滿足了全球多分辨DQG格網(wǎng)模型繪制過程中對(duì)繪制速度和逼真度的要求。盡管如此，該方法還不是很完善，下一步的工作包括：DQG格網(wǎng)簡化和裂縫消除的高效性、交互性設(shè)計(jì)與空間分析及其大區(qū)域地形應(yīng)用模式等。

表1 格網(wǎng)簡化數(shù)目對(duì)比分析Tab.1 Comparison and analysis of the simplified grid numbers

圖11 DQG格網(wǎng)的裂縫消除代價(jià)Fig.11 Costs of crack elimination in DQG

圖12 DQG和經(jīng)緯度格網(wǎng)簡化效率對(duì)比Fig.12 The simplification efficiency of DQG and Long／Lag grid

［1］ XING Wei，SUN Yankui，TANG Zesheng.View－dependent and Multi－resolution Simplification Algorithm of a Terrain Model［J］.Journal of Tsinghua University：Science and Technology，2004，44（1）：29－33.（邢偉，孫延奎，唐澤圣.與視點(diǎn)相關(guān)的多分辨率地表模型簡化算法［J］清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，44（1）：29－33.）

［2］ HU Jinxing，MA Zhaoting，WU Huanping，et al.3D Visualization of Massive Terrain Data Based on Grid Partition［J］.Journal of Computer Aided Design ＆ Computer Graphics，2004，16（8）：1164－1168.（胡金星，馬照亭，吳煥萍，等.基于格網(wǎng)劃分的海量地形數(shù)據(jù)三維可視化［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2004，16（8）：1164－1168.）

［3］ MA Zhaoting，PAN Mao，HU Jinxing，et al.A Fast Walkthrough Method for Massive Terrain Based on Data Block Partition［J］.Acta Scicentiarum Naturalum Universitis Pekinesis，2004，40（4）：619－625.（馬照亭，潘懋，胡金星，等.一種基于數(shù)據(jù)分塊的海量地形快速漫游方法［J］.北 京 大 學(xué) 學(xué) 報(bào)：自 然 科 學(xué) 版，2004，40（4）：619－625.）

［4］ HU Aihua，HE Zongyi，MA Xiaoping.Rendering Technique for Large Scale Terrain Based on LOD［J］.Bulletin of Surveying and Mapping，2009（12）：23－26.（胡愛華，何宗宜，馬曉萍.基于LOD的大規(guī)模地形實(shí)時(shí)繪制方法［J］.測(cè)繪通報(bào)，2009（12）：23－26.）

［5］ LIU Ding，XU Huiping，CHEN Huagen.A LOD Algorithm for Large Scale Ocean Based on OpenGL Index Vertex Array［J］.Journal of Tongji University：Natural Science，2009，37（3）：414－418.（劉丁，許惠平，陳華根.基于OpenGL索引頂點(diǎn)數(shù)組的大尺度海面LOD算法［J］.同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，37（3）：414－418.）

［6］ XU Miaozhong.Research on Real－time Rendering for Large Scale Terrain［J］.Geomatics and Information Science of Wuhan University，2005，30（5）：392－395.（許妙忠.大規(guī)模地形實(shí)時(shí)繪制的算法研究［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30（5）：392－395.）

［7］ ROTTGER S，HEIDRICH W，SLUSALLEK P，et al.Realtime Generation of Continuous Levels of Detail for Height Fields［C］∥Proceedings of the 6th International Conference in Central European Computer Graphics and Visualization.Plzen：［s.n.］，1998：315－322.

［8］ ZENG Wei，HAN Zhanxiao，ZHU Xuefang.Research of Application of LOD Algorithm to 3DTerrain Simulation［J］.Journal of System Simulation，2009，21（1）：292－294.（曾維，韓占校，朱學(xué)芳.LOD算法在3D地表模擬中的應(yīng)用研究［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21（1）：292－294.）

［9］ LINDSTROM P，PASCUCCI V.Terrain Simplification Simplified：A General Framework for View－dependent Out－of－core Visualization ［J］.IEEE Transactions on Visualization and Computer Graphics，2002，8（3）：239－254.

［10］ WANG Yuan，LIU Jianyong，JIANG Nan，et al.A Dynamic Triangulation Algorithm for the View－dependent and Real time LOD Model of Terrain［J］.Acta Geodaetica et Cartographica Sinica，2003，32（1）：47－52.（王源，劉建永，江南，等.視點(diǎn)相關(guān)實(shí)時(shí)LOD地形模型動(dòng)態(tài)構(gòu)網(wǎng)算法［J］.測(cè)繪學(xué)報(bào)，2003，32（1）：47－52.）

［11］ ZHAO Xuesheng，BAI Jianjun，WANG Zhipeng.An Adaptive Visualized Model of the Global Terrain Based on QTM［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：316－320.（趙學(xué)勝，白建軍，王志鵬.基于QTM的全球地形自適應(yīng)可視化模型［J］.測(cè)繪學(xué)報(bào)，2007，36（3）：316－320.）

［12］ CIGNONI P，GANOVELLI F，GOBBETTI E，et al.Planet－sized Batched Dynamic Adaptive Meshes （PBDAM）［J］.Proceedings of the 14th IEEE Visualization 2003（VIS＇03）.Washington DC：IEEE Computer Society Press，2003：147－154.

［13］ HWA L M，DUCHAINEAU M A，JOY K I.Real－time Optimal Adaptation for Planetary Geometry and Texture：4－8Tile Hierarchies［J］.IEEE Transactions on Visualization and Computer Graphics，2005，11（4）：355－368

［14］ ZHAO Youbing，SHI Jiaoying，ZHOU Ji，et al.，A Fast Algorithm for Large Scale Terrain Walkthrough［J］.Journal of Computer Aided Design ＆ Computer Graphics，2002，14（7）：624－628.（趙友兵，石教英，周驥，等.一種大規(guī)模地形的快速漫游算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14（7）：624－628.）

［15］ RUI Xiaoping，ZHANG Yanmin.An Improved Real－time Continuous LOD Algorithm ［J］.Journal of System Simulation，2004，16（11）：2628－2630.（芮小平，張彥敏.一種實(shí)時(shí)連續(xù)LOD技術(shù)的改進(jìn)算法［J］.系統(tǒng)仿真學(xué)報(bào)，2004，16（11）：2628－2630.）

［16］ ZHANG Xiaohu，SHAO Yongshe，YE Qin.New LOD Method Based on Adaptive Quad－tree for Terrain Visualization［J］.Journal of Computer Applications，2009，29（9）：2596－2598.（張小虎，邵永社，葉勤.基于自適應(yīng)四叉樹的地形LOD算法［J］.計(jì)算機(jī)應(yīng)用，2009，29（9）：2596－2598.）

［17］ YOON S E，SALOMON B，GAYLE R.Quick－VDR：Out－of－core View－dependent Rendering of Gigantic Models［J］.IEEE Transactions on Visualization and Computer Graphics，2005，11（4）：369－382.

［18］ LIU Yang，GONG Adu，LI Jing.A Model for Massive 3DTerrain Simplification Based on Data Block Partition and Quad－tree［J］.Acta Geodaetica et Cartographica Sinica，2010，39（4）：410－415.（劉揚(yáng)，宮阿都，李京.基于數(shù)據(jù)分層分塊的海量三維地形四叉樹簡化模型［J］.測(cè)繪學(xué)報(bào)，2010，39（4）：410－415.）

［19］ LI Yachen，JIANG Hongliu，XIONG Hailin，et al.3D Earth Modeling in Visual Simulation［J］.Computer Engineering，2007，33（12）：225－227.（李亞臣，蔣紅柳，熊海林，等.視景仿真中三維地球的建模［J］.計(jì)算機(jī)工程，2007，33（12）：225－227.）

［20］ ZHAO Xuesheng，CUI Majun，LI Ang，et al.An Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet［J］.Geomatics and Information Science of Wuhan University，2009，34（4）：479－482.（趙學(xué)勝，崔馬軍，李昂，等.球面退化四叉樹格網(wǎng)單元的鄰近搜索算法［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2009，34（4）：479－482.）