虛擬現(xiàn)實(shí)中三維地形建模及其算法探討

陳芬

摘 要：地形可視化與人類的生產(chǎn)生活息息相關(guān)，就是利用計(jì)算機(jī)對(duì)地形數(shù)據(jù)進(jìn)行模擬仿真，并通過對(duì)相關(guān)技術(shù)的應(yīng)用實(shí)現(xiàn)對(duì)地形模型的表達(dá)、顯示以及傳輸。該技術(shù)涉及到測(cè)繪學(xué)、圖像處理、現(xiàn)代數(shù)學(xué)以及計(jì)算機(jī)網(wǎng)絡(luò)等多個(gè)學(xué)科，如今，該技術(shù)在虛擬現(xiàn)實(shí)、地理信息系統(tǒng)以及計(jì)算機(jī)仿真等領(lǐng)域的應(yīng)用越來越廣泛，是當(dāng)前計(jì)算機(jī)圖形學(xué)的一個(gè)重要研究課題。隨著地形仿真應(yīng)用要求的不斷提高，地形可視化逐漸向構(gòu)建三維真實(shí)感地形模型的趨勢(shì)發(fā)展，而要生成三維真實(shí)感地形，就需要進(jìn)行較復(fù)雜的數(shù)據(jù)計(jì)算，所以，計(jì)算機(jī)的圖形處理能力非常重要。本研究就是基于數(shù)字地形模型對(duì)三維地形建模技術(shù)進(jìn)行探討，并對(duì)可以生成數(shù)字地形模型的TIN（不規(guī)則三角網(wǎng)模型）的改進(jìn)算法進(jìn)行詳細(xì)分析。

關(guān)鍵詞：三維地形；可視化；建模；算法

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）12-00-02

0 引 言

DTM（數(shù)字地形模型）的定義為“以數(shù)字形式存儲(chǔ)的地球表面上所有信息的總和，是描述地面特征空間分布的數(shù)值的集合，是地形表面形態(tài)等多種信息的一種數(shù)字表示，是描述地形特征空間分布的有序數(shù)值陣列。”數(shù)字地形模型不僅包通過航、衛(wèi)片的立體像對(duì)生成的高程數(shù)據(jù)，還包括公路、建筑物、河流等存在于地形表面的地物數(shù)據(jù)。地形可視化概念自形成以來，國(guó)內(nèi)外學(xué)者就針對(duì)不同的目的對(duì)數(shù)據(jù)模型、相關(guān)算法以及理論進(jìn)行不斷研究，如今依托于計(jì)算機(jī)技術(shù)已經(jīng)成功建立起多種可視化模型。1997年，Mark等人提出了ROAM（實(shí)時(shí)優(yōu)化適應(yīng)網(wǎng)格）算法，ROAM算法規(guī)則是對(duì)傳統(tǒng)LOD（層次細(xì)節(jié)技術(shù)）算法的改進(jìn)，優(yōu)化后的的ROAM算法可以極大地提高地形數(shù)據(jù)的運(yùn)算效率，尤其適合應(yīng)用于大規(guī)模地形數(shù)據(jù)，因?yàn)樗梢愿鶕?jù)視點(diǎn)的位置實(shí)現(xiàn)對(duì)模型細(xì)節(jié)層次的動(dòng)態(tài)計(jì)算。通過近年來的研究，我國(guó)學(xué)者提出一種基于地形特征和參數(shù)的地形生成方法，研究者將地形視為一個(gè)隨機(jī)統(tǒng)計(jì)過程，并綜合應(yīng)用了實(shí)用回歸、分形幾何模型等多種技術(shù)。另外，有學(xué)者將三角網(wǎng)地形生成方法與傳統(tǒng)的分割-合并法融合在一起，提出了基于不規(guī)則三角網(wǎng)模型的自適應(yīng)分塊思想以及相應(yīng)的地形簡(jiǎn)化過程。

1 改進(jìn)的Delaunay三角網(wǎng)法算法

數(shù)字地面模型從數(shù)據(jù)結(jié)構(gòu)的角度可以分為2大類，即TIN（不規(guī)則三角網(wǎng)模型）和Grid（不規(guī)則網(wǎng)格模型），TIN是針對(duì)離散點(diǎn)數(shù)據(jù)，其具有數(shù)據(jù)冗余小的優(yōu)點(diǎn)，而且可以充分顧及到地形特征，能夠?qū)⒌匦胃鞣N復(fù)雜的細(xì)節(jié)特征有效反映出來，但該方法的算法比較復(fù)雜，所以在實(shí)現(xiàn)方面存在一定難度，而且存儲(chǔ)以及空間操作上也很不方便；Grid是基于規(guī)則分布數(shù)據(jù)點(diǎn)，該方法拓?fù)潢P(guān)系簡(jiǎn)單，算法容易實(shí)現(xiàn)，存儲(chǔ)以及空間操作都非常方便，但其數(shù)據(jù)冗余較大，不能有效地對(duì)地形結(jié)構(gòu)和特征進(jìn)行描述。TIN是地形生成算法的基礎(chǔ)，本文著重討論TIN的算法。三角網(wǎng)相對(duì)于TIN和Grid 算法比較簡(jiǎn)單，而且圖形靈活多變，改進(jìn)的Delaunay三角網(wǎng)法可以有效提高 TIN 的建網(wǎng)效率，下面就對(duì)Delaunay的改進(jìn)算法的相關(guān)研究。

利用數(shù)據(jù)分塊建網(wǎng)再合并技術(shù)對(duì)Delaunay算法進(jìn)行優(yōu)化處理，因?yàn)镈elaunay算法的原則同樣適用于TIN建網(wǎng)和合并，所以基于該方法的建網(wǎng)效率與采樣點(diǎn)增長(zhǎng)呈線性遞減分布，使得Delaunay三角網(wǎng)的生成速度得到大幅度提高。Delaunay改進(jìn)算法處理過程如下：

2 處理原始數(shù)據(jù)（切分采樣點(diǎn)）

圖 1所示是采用數(shù)據(jù)切分的過程圖，圖中的“A為原始采樣點(diǎn)。首先對(duì)原始采樣點(diǎn)A插入二叉樹根節(jié)點(diǎn)，并根據(jù)采樣點(diǎn)的地理位置置入葉子節(jié)點(diǎn)，如果葉子節(jié)點(diǎn)中采樣點(diǎn)的最終數(shù)量大于三角網(wǎng)采樣點(diǎn)的最大允許數(shù)量值，將該葉子節(jié)點(diǎn)作成根節(jié)點(diǎn)形成兩個(gè)葉子節(jié)點(diǎn)，此時(shí)形成了兩部分?jǐn)?shù)據(jù)，實(shí)現(xiàn)了區(qū)域二分，反復(fù)進(jìn)行此操作模式直到數(shù)據(jù)插入完畢”。圖1中采樣點(diǎn)處理完畢后一共形成4個(gè)三角網(wǎng)，各個(gè)三角網(wǎng)的合并好結(jié)合其在二叉樹中的位置進(jìn)行， 其中有父節(jié)點(diǎn)相同時(shí)先合并。圖1中11由110和111合并而成，1由10和11合并而成，完整的Delaunay三角網(wǎng)最終由1和0合成。

3 基本三角網(wǎng)的生成

首先要生成初始三角網(wǎng)，然后逐個(gè)插入其余點(diǎn)，并采用LOD對(duì)初始三角網(wǎng)的形成以及數(shù)據(jù)插入過程進(jìn)行優(yōu)化，以保證形成有效的Delaunay三角網(wǎng)。初始三角網(wǎng)的形成過程：一是根據(jù)采集的原始采樣點(diǎn)特征構(gòu)造凸殼；二建立用于逆時(shí)針存儲(chǔ)凸殼形成過程中各個(gè)點(diǎn)的鏈表；三是 將鏈表中的P0點(diǎn)（凸殼上最小的點(diǎn)） 以及后續(xù)點(diǎn)P1、P2構(gòu)成第一個(gè)三角形；四是從P2開始重復(fù)步驟三的操作，形成新的三角形，直到鏈表頭部，整體過程采用LOD進(jìn)行優(yōu)化。初始三角網(wǎng)形成后，再逐點(diǎn)插入所有數(shù)據(jù)，以形成完整的Delaunay三角網(wǎng)。之后就可完成基本三角網(wǎng)的合并。

3 三維地形可視化系統(tǒng)的實(shí)現(xiàn)

3.1 系統(tǒng)設(shè)計(jì)

地形表面網(wǎng)格模型的構(gòu)建根據(jù)DEM數(shù)字高程模型，以實(shí)現(xiàn)三維地形可視化系統(tǒng)的設(shè)計(jì)，并利用光照、立體視覺技術(shù)以及紋理映射等實(shí)現(xiàn)地形地貌的真實(shí)再現(xiàn)。三維地形建模的流程如下圖2所示。

3.2 系統(tǒng)設(shè)計(jì)結(jié)構(gòu)

本研究的基礎(chǔ)設(shè)施為Windows XP操作系統(tǒng)以及VC++6.0、OpenGL，基于以上系統(tǒng)和軟件進(jìn)行開發(fā)，三維地形可視化系統(tǒng)用到的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)可根據(jù)三角形面片使用單鏈表形式定義，代碼如下：（來自DEM文件的數(shù)據(jù)多通過面向?qū)ο蠓椒ㄔO(shè)計(jì)出的Cterrain類來處理，這里不再詳細(xì)介紹）。

4 結(jié) 語

采用逐點(diǎn)插入的方法對(duì)Delaunay進(jìn)行三角劃分是三維地形顯示中非常重要的環(huán)節(jié)，在原有Delaunay算法基礎(chǔ)上采用采樣數(shù)據(jù)分塊建網(wǎng)，然后對(duì)基本三角網(wǎng)進(jìn)行合并，這一方法極大的提高的Delaunay三角網(wǎng)的生產(chǎn)速度。

參考文獻(xiàn)

[1] 賈瑞生，姜巖，孫紅梅，等.三維地形建模與可視化研究[J].系統(tǒng)仿真學(xué)報(bào)，2006，18（z1）：330-332.

[2] 黎華，肖偉，黃海峰，等.三維真實(shí)感地形生成的關(guān)鍵技術(shù)研究[J].測(cè)繪科學(xué)，2006，31（4）：57-59.

[3] 閆豐亭.大規(guī)模三維地形建模與渲染的研究及改進(jìn)[D].青島：山東科技大學(xué)，2011.

[4] 漆澤軍.三維地形建模與渲染的研究和實(shí)現(xiàn)[D].武漢：中南民族大學(xué)，2012.

[5] 文雄志.關(guān)于三維地形建模簡(jiǎn)化技術(shù)的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2015（1）：7-8.

[6] 萬苗，張新家，宋佳音，等.一種交互編輯與自動(dòng)生成的三維地形綜合構(gòu)建方法與實(shí)現(xiàn)[J].電子設(shè)計(jì)工程，2014（23）：14-17.