數(shù)字地形模型LOD

DEM表示方法數(shù)學方法用數(shù)學方法來表達，可以采用整體擬合方法，即根據(jù)區(qū)域所有的高程點數(shù)據(jù)，用傅里葉級數(shù)和高次多項式擬合統(tǒng)一的地面高程曲面；也可用局部擬合方法，將地表復雜表面分成正方形規(guī)劃區(qū)域或面積大致相等的不規(guī)則區(qū)域進行分塊搜索，根據(jù)有限個點進行擬合形成高程曲面DEM表示方法線模式：等高線是表示地形最常見的形式。其它的地形特征線也是表達地面高程的重要信息源，如山脊谷底線等；

點模式：用離散采樣數(shù)據(jù)點建立DEM是DEM建立常用方法之一。數(shù)據(jù)采樣可按規(guī)則格網(wǎng)采樣，可以是密度一致的或不一致的；可以是不規(guī)則采樣，如不規(guī)則三角網(wǎng)；也可以有選擇性地采樣，采集三峰、洼坑、邊界等重要特征點。圖形表示法等高線DEM散點DEM三角網(wǎng)DEMDEM表示方法DEM主要表示模型規(guī)則格網(wǎng)，通常是正方形，也可以是矩形、三角形等規(guī)則格網(wǎng)。規(guī)則格網(wǎng)將區(qū)域空間切分為規(guī)則的格網(wǎng)單元，每個格網(wǎng)單元對應一個數(shù)值；

數(shù)學上可以表示為一個矩陣，在計算機實現(xiàn)中則是一個二維數(shù)組。每個格網(wǎng)單元或數(shù)組的一個元素，對應一個高程值。規(guī)則格網(wǎng)模型DEM主要表示模型規(guī)則格網(wǎng)的高程矩陣，可以很容易地用計算機進行處理。它還可以很容易地計算等高線、坡度坡向、山坡陰影和自動提取流域地形，使得它成為DEM最廣泛使用的格式；格網(wǎng)DEM的缺點是不能準確表示地形結構和細部，為避免這些問題，可采用附加地形特征數(shù)據(jù)，如地形特征點、三脊線、谷底線、斷裂線，以描述地形結構。DEM主要表示模型格網(wǎng)DEM的另一個缺點是數(shù)據(jù)量過大，給數(shù)據(jù)管理帶來了不便，通常要進行壓縮存儲；DEM數(shù)據(jù)的無損壓縮可以采用普通的柵格數(shù)據(jù)壓縮方式，如游程編碼、塊碼等；但是由于DEM數(shù)據(jù)反映了地形的連續(xù)起伏變化，通常比較“破碎”，普通壓縮方式難以達到很好的效果，可以采用哈夫曼編碼。DEM主要表示模型等高線模型表示高程，高程值的集合是已知的，每一條等高線對應一個已知的高程值，一系列等高線集合和它們的高程值一起就構成了一種地面高程模型等高線模型DEM主要表示模型等高線模型等高線通常被存成一個有序的坐標點對序列，可以認為是一條帶有高程值屬性的簡單多邊形或多邊形弧段；由于等高線模型只表達了區(qū)域的部分高程值，往往需要一種插值方法來計算落在等高線外的其它點高程。DEM主要表示模型不規(guī)則三角網(wǎng)（TriangulatedIrregularNetwork,TIN）在地形平坦的地方，存在大量的數(shù)據(jù)冗余；

在不改變格網(wǎng)大小的情況下，難以表達復雜地形的突變現(xiàn)象。DEM主要表示模型

TIN模型根據(jù)區(qū)域有限個點集將區(qū)域劃分為相連的三角面網(wǎng)絡，區(qū)域中任意點落在三角面的頂點、邊上或三角形內(nèi)。如果點不在頂點上，該點的高程值通常通過線性插值的方法得到（在邊上用邊的兩個頂點高程，在三角形內(nèi)則用三個頂點的高程）。

TINDEM主要表示模型有許多種表達TIN拓撲結構的存儲方式，一般來講，對于每一個三角形、邊和節(jié)點都對應一個記錄，三角形的記錄包括三個指向它三個邊的記錄的指針；邊的記錄有四個指針字段，包括兩個指向相鄰三角形記錄的指針和它的兩個頂點的記錄的指針；也可以直接對每個三角形記錄其頂點和相鄰三角形。

TINDEM主要表示模型有許多種表達TIN拓撲結構的存儲方式，一般來講，對于每一個三角形、邊和節(jié)點都對應一個記錄，三角形的記錄包括三個指向它三個邊的記錄的指針；邊的記錄有四個指針字段，包括兩個指向相鄰三角形記錄的指針和它的兩個頂點的記錄的指針；也可以直接對每個三角形記錄其頂點和相鄰三角形。

TINDEM主要表示模型空間數(shù)據(jù)模型通過空間數(shù)據(jù)組織和空間數(shù)據(jù)庫對空間對象及其關系進行描述，對空間對象進行提取。空間數(shù)據(jù)模型有兩種分類方法：（1）從認知的的角度：分為基于對象（objectbased）的模型、基于網(wǎng)絡(networkbased)的模型和基于場（fieldbased）的模型；（2）從表達的方式上：分為矢量數(shù)據(jù)模型、鑲嵌數(shù)據(jù)模型和組合數(shù)據(jù)模型。

TINDEM主要表示模型鑲嵌數(shù)據(jù)模型的基本思想是：可以用相互連接在一起的網(wǎng)絡來覆蓋和逼近空間對象。數(shù)字高程模型通常用于刻畫具有連續(xù)變化特征的空間對象，目前最典型的應用就是通過連續(xù)網(wǎng)格單元來實現(xiàn)地形曲面的模擬，應歸類于基于場的鑲嵌數(shù)據(jù)模型.

TINDEM主要表示模型當?shù)匦螖?shù)據(jù)呈規(guī)則分布或由格網(wǎng)DEM向TIN轉換時，其三角剖分與不規(guī)則數(shù)據(jù)域的三角剖分有很大的差異。由于規(guī)則格網(wǎng)分布采樣數(shù)據(jù)的特性，對其進行三角形剖分可以有兩類方法：（1）直接對角線連接三角化（2）Delaunay三角剖分法

TINDEM主要表示模型先來簡要了解一下與Delaunay三角網(wǎng)密切相關的Voronoi圖：Voronoi圖又稱為Dirichlet鑲嵌(tessellation)，其概念由Dirichlet于1850年首先提出;1907年俄國數(shù)學家Voronoi對此作了進一步闡述，并提出高次方程化簡;1911年荷蘭氣候學家A.H.Thiessen為提高大面積氣象預報的準確度，應用Voronoi圖對氣象觀測站進行了有效區(qū)域劃分。因此在二維空間中，Voronoi圖也稱為泰森(Thiessen)多邊形。Voronoi圖是Delaunay三角網(wǎng)的對偶，現(xiàn)在已經(jīng)成為計算幾何中的一種通用的基本幾何結構。Voronoi圖DEM主要表示模型LLLRP1P2P3P4P5ABCDl1l2l3l4①空外接圓準則Delaunay三角形外接圓內(nèi)部包含其它點的性質(zhì)被用作從一系列不重合的平面點建立Delaunay三角網(wǎng)的基本法則。Delaunay三角形由三個相鄰點連接組成，這三個相鄰點對應的Voronoi多邊形有一個公共的頂點，這個頂點同時也是Delaunay三角形外接圓的圓心。在進行Delaunay三角形剖分的過程中，每一個三角形都要經(jīng)過空外接圓檢測，目前常用的計算方法是計算三角形外接圓的圓心和半徑，然后計算圓心和其他點的距離，通過距離和外接圓半徑的比較進行判斷，這種判斷方法的計算包含了開方、除法、平方等復雜的運算。Delaunay三角網(wǎng)②最小角最大準則有很多種方法可以對三角形進行剖分，無論怎樣進行三角剖分，采樣點的高程值都是最準確的。就這個層面來看，無論怎樣剖分效果差別都不大，但是就其外觀的自然性而言，還是能比較出相對較好的一種效果。Delaunay三角網(wǎng)19203628001061920362800106124010009809901008100899098010001240P點高程=985P點高程=23pp翻轉邊合法邊非法邊圖2.4邊翻轉操作非法邊圖2.5圖2.6逐點插入算法從構網(wǎng)過程來看，分割合并算法和三角網(wǎng)生長算法屬于靜態(tài)剖分過程，在整個三角網(wǎng)形成過程中，新點的介入并不會破壞已經(jīng)形成的三角網(wǎng)。而逐點插入算法則是一種動態(tài)的構網(wǎng)過程，新點的插入會導致已有的三角網(wǎng)進行改變。該算法最早由Lawson在1977年提出，隨后LeeSchachter(1980)、Bowyer(1981)、Watson(1981)、Sloan(1987)、Macedonio和Pareschi(1991)、Floriani和Puppo(1992)、Tsai(1993)等人先后對其進行了改進。逐點插入算法的基本過程為：第一步，定義包含所有數(shù)據(jù)點的初始包容盒，并對該包圍盒進行初始三角剖分。形成矩形包容盒的方法是找出數(shù)據(jù)域的坐標極值點，然后用這些點形成包容盒。第二步，對所有數(shù)據(jù)點進行循環(huán)（設當前處理的數(shù)據(jù)點為P），在已經(jīng)存在的三角網(wǎng)中，查找包含P點的三角形t，將P與t的三個頂點相連，形成t的三個初始三角剖分，再用LOP算法對初始三角剖分進行優(yōu)化處理。第三步是對外圍三角形進行處理。（Xmin，Ymin）（Xmin，Ymax）（Xmax，Ymin）（Xmax，Ymax）圖2.9矩形包圍盒圖2.10超級三角形構造矩形包圍盒進行初始三角剖分voidCTiNPrc::getScope(){

pCal->getScope(amCurPt,minPt,maxPt); get4Ori();}//初始化三角網(wǎng)，生成兩個初始三角形voidCTiNPrc::initTicell(){//包圍盒的4個邊界點

amCurPt[0]=oriP0; amCurPt[1]=oriP1; amCurPt[2]=oriP2; amCurPt[3]=oriP3;

CTICell

tiCell;渲染海量三維幾何數(shù)據(jù)需要大量的計算機資源，很多時候已經(jīng)遠遠超出了目前圖形設備的承受能力，解決超大規(guī)模數(shù)據(jù)問題成為三維場景實時繪制的最大瓶頸。圖形硬件GPU的飛速發(fā)展極大地提高了圖形渲染的效率，但是對于海量數(shù)據(jù)而言仍是不堪重負。若不應用LOD技術對數(shù)據(jù)進行分層多級顯示很難實現(xiàn)地形的實時可視化。多分辨率LOD算法不僅能簡化數(shù)據(jù)，還能使視覺效果更接近真實。多分辨率LOD的基本思想是：用不同的LOD表示一個三維場景，LOD級別取決于可視區(qū)域與視點的關系，并隨著視點移動更新各個區(qū)域LOD的級別。多分辨率LOD在地形應用中分為規(guī)則格網(wǎng)和不規(guī)則格網(wǎng)兩種，國內(nèi)外學者對此都進行了深入研究，相關文獻很多，相對而言，規(guī)則格網(wǎng)LOD技術較為成熟。從提出LOD應用于地形三維可視化到現(xiàn)在，其研究發(fā)展大致分為離散LOD（DLOD，DiscreteLOD）、連續(xù)LOD（CLOD，ContinuousLOD）和多分辨率LOD（MRLOD，Multi-ResolutionLOD）。離散LOD的基本原理是建立原始模型幾個不同精度的幾何模型，每個模型均保持一定的細節(jié)層次，在渲染時會出現(xiàn)視覺“跳躍”。為了從根本上解決離散LOD技術的缺陷，1996年Lindstrom和Koller提出地形繪制的連續(xù)LOD概念，但是在不同細節(jié)層次切換時仍然有所謂“poping”現(xiàn)象。目前，比較著名的LOD算法有：基于TIN的層次結構的漸進格網(wǎng)（VDPM，View-DependentProgressiveMeshes）算法、實時自適應優(yōu)化格網(wǎng)（Real-timeOptimallyAdaptingMeshes）算法、基于Grid樹結構的GeoMipmapping幾何多分辨率算法和四叉樹(QuadTree)算法。VDPM算法第一步，讀入TIN模型，并建立頂點與三角形的鄰接關系；第二步，根據(jù)頂點與三角形的鄰接關系，計算每個頂點和每條邊的誤差；第三步，根據(jù)邊誤差建立邊誤差鏈表，并從小到大排隊；第四步，從邊誤差表中誤差最小的邊開始，依次進行收縮，同時建立頂點層次樹結構，并按頂點誤差大小依次排列；第五步，根據(jù)視點的位置依次判斷頂點樹中的頂點誤差是否超出給定的閾值，若是，則對該頂點進行分裂操作；否則，進行頂點合并，同時更新頂點層次樹結構；第六步，重復第五步，直到滿足要求為止。vsvtv1v2v3v4v5v6v7v8hshtviv1v2v3v4v5v6v7v8選擇被刪除的頂點折疊邊的選擇QuadTree算法四叉樹是一個二維數(shù)據(jù)結構，由于四叉樹模型與矩形格網(wǎng)DEM坐標系有著天然的相似性，因此對于描述地形來講，它是很理想的一種數(shù)據(jù)結構。QuadTree算法將整個地形區(qū)域看作四叉樹的母節(jié)點，地形母節(jié)點覆蓋整個地形區(qū)域。樹中的每一個節(jié)點都覆蓋地形中的一塊相應的矩形區(qū)域。上層的節(jié)點涉及的采樣點較少，用其來表示地形時具有更高的繪制效率；但具有較低的分辨率，地形表示的誤差較大。底層地形的分辨率高，誤差小，但繪制效率低。在滿足給定誤差閾值的條件下，動態(tài)地選擇地形節(jié)點來實現(xiàn)對地形模型的連續(xù)多分辨率表示。同時為了提高運算效率，要先對數(shù)據(jù)節(jié)點進行預處理，計算每一個地形節(jié)點的誤差精度，從而確定簡化過程中節(jié)點操作的執(zhí)行順序。Leve1Leve2Leve3TIN結構多分辨率LOD模型的建立

首先運用Quadtree算法將整個區(qū)域的DEM數(shù)據(jù)進行靜態(tài)分塊，其基本操作是不斷地將一個矩形（本次研究中其實是嚴格的正方形）地形塊四等分，然后對各個子塊分別構TIN，通過VDPM算法將TIN簡化生成不同分辨率的層次模型，并將其保存到LOD模型庫中，最后應用四叉樹算法建立有效的空間索引模型實現(xiàn)顯示時的動態(tài)調(diào)度。當視點位置改變時，實時調(diào)整四叉樹結構，從而實現(xiàn)地形的實時可視化。地形數(shù)據(jù)分塊在建立大區(qū)域模型的實踐中，待調(diào)用的地形數(shù)據(jù)和影像數(shù)據(jù)量是很大的，撫仙湖流域的數(shù)據(jù)量在沒有進行壓縮的情況下達到了20多個G，即使進行了壓縮還有4個多G，目前的技術條件下若要將整個地形區(qū)域全部裝入計算機內(nèi)存很難辦到?？梢圆扇〉匦畏謮K的方法來解決該問題，地形數(shù)據(jù)分塊的基本步驟是：①先將整個地形模型分成若干個子塊，并且每一塊內(nèi)的采樣點數(shù)目必須為？。②對每一個子塊按照四叉樹的形式進行細分，同樣必須要滿足每一個下級子塊的采樣點數(shù)目為。③對子塊的分辨率進行需求評估，判斷是否需要繼續(xù)細分，若需要進行進下一步細分則重復上述操作，直到分辨率達到所需要的級別為止。TIN的簡化

地形模型的簡化應用VDPM算法中的TIN簡化思想，即邊折疊法。該方法需要解決的關鍵問題是：①如何選擇被刪除的點；②如何確定折疊邊。讀入TIN模型建立點-面關系刪除折疊邊及其所在三角形指定一個新的頂點進行局部優(yōu)化構網(wǎng)形成一個細節(jié)層次的地形模型

細節(jié)層次地形模型生成基本流程判斷刪除點及折疊邊

折疊邊選擇的不同會導致不同的簡化結果，大致可以分成三類情況：①折疊邊的兩個端點都不是邊界點此類情況下會刪除折疊邊的一個端點以及共用折疊邊的兩個三角形，得到的簡化網(wǎng)格將被指定一個新頂點，剩余的頂點和三角形之間的拓撲關系得到了維持。②折疊邊的其中一個頂點為邊界點此類情況下定會刪除非邊界點，同樣會刪除共用折疊邊的兩個三角形，得到的簡化網(wǎng)格的頂點必為邊界點，剩余的頂點和三角形之間的拓撲關系不會改變。③折疊邊的兩個端點都為邊界點，即折疊邊為邊界邊，顯然，這種情況下只能刪除一個邊界頂點和折疊邊所在的一個三角形，剩余的頂點和三角形之間的拓撲關系不會改變。邊折疊法運用邊折疊法的基本實現(xiàn)步驟為：⑴首先要選擇被刪除的點進行刪除操作這一步中的關鍵問題是被刪除點選取準則的設定問題：設頂點vi到其所在平均平面距離為hi，設定一個點到其所在的平均平面的距離參考值h0，并設定一個閾值ξ；設頂點vi到其所在平均平面的距離hi與參考值h0之間的差距為△hi，即：△hi=hi－h(huán)0；若△hi＜ξ，則vi將要被刪除。如圖3.3所示：橙色線條和藍色線條分別表示以vs、vt為頂點的凸多邊形區(qū)域，共用了兩個三角形。vs、vt距離其所在平均平面的高度分別為hs、ht，若△hs＜ξ，則刪除vs；同理，若△ht＜ξ則刪除vt。vsvtv1v2v3v4v5v6v7v8hshtviv1v2v3v4v5v6v7v8選擇被刪除的頂點折疊邊的選擇⑵然后選擇點刪除后將要被折疊的邊進行刪除操作這一步的關鍵問題依然是選取標準的設定問題：如圖3.4所示，設頂點vi到其環(huán)鄰點（v１，v２，v３，v４，v５，v６，v７，v８）的邊長為di（i=1,2…8）,分別計算所有頂點到其環(huán)鄰點的邊長并進行列隊，首先選擇邊長最短的三角形邊作為折疊邊，判斷刪除該邊后重新構成的三角網(wǎng)。⑶刪除頂點和折疊邊的同時，也刪除了折疊邊所在的三角形，則需要對格網(wǎng)進行三角網(wǎng)重構和優(yōu)化。⑷重復以上操作，直到生成所需要的各個細節(jié)層次的格網(wǎng)。四叉樹的構造Quadtree算法繪制地形時，首先根據(jù)地形四叉樹子塊網(wǎng)格中心點到視點的距離來確定各地形子塊是否需要細分，并對細分標記和細分等級進行記錄，形成QuadTree矩陣。圖中0表示該節(jié)點不需要細分，1表示該節(jié)點需要細分，？表示該節(jié)點未知。？10？？？？0110001110？0110？？1000？？//bool型數(shù)組記錄nx*ny的地塊的細分標記classCByteFlag

{public:

CLevelMx

m_cLevel;

int

m_nScale;

bool

Create(int

x,inty);

bool

IsTrue(intx,inty); voidSet(int

x,int

y,int

nLevel,float

nHeight,bool

bFlag); voidReset();//細分數(shù)組清零

CByteFlag(); virtual~CByteFlag();

int

nx,ny;public:

bool*m_pFlag;}//int型數(shù)組記錄nx*ny的地塊的細分等級classCLevelMx

{public: voidSet(int

x,inty,UINTnLevel); voidReset();

bool

Create(int

x,inty); UINT*m_pLevel; CPt3d*m_pt3d;

CLevelMx(); virtual~CLevelMx();private:

int

nx;

int

ny;}裂縫的修補由于對整個DEM進行了分區(qū)計算，不同分辨率級別的TIN地塊的接邊處進行結合顯示時會因為公共頂點不一致而產(chǎn)生裂縫，為了能無縫地顯示地形模型，必須解決裂縫的消除問題?？刹捎昧嗽黾印叭埂钡姆椒ㄏ芽p，該方法的基本原理是：在每一級子塊的周圍加上一個“裙”，只需要對坐標中的ｙ值向下拉伸，在邊界處紋理坐標重復指定便可以進行“裙”的構建。撫仙湖流域DEM數(shù)據(jù)，采樣點正方形規(guī)則分布，采樣點個數(shù)為10848×4507。將整個地形模型分為256×256塊，可分7個細節(jié)層次顯示:4×4、8×8、16×16、32×32、64×64、128×128、256×256。各層次實際渲染的塊數(shù)分別為：4×2、7×3、14×6、27×11、53×22、106×44、212×88。局部4×4細節(jié)層次局部