虛擬現實中三維地形建模及其算法探討

陳芬

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

關鍵詞：三維地形；可視化；建模；算法

中圖分類號：TP391.9 文獻標識碼：A 文章編號：2095-1302（2015）12-00-02

0 引 言

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

1 改進的Delaunay三角網法算法

數字地面模型從數據結構的角度可以分為2大類，即TIN（不規則三角網模型）和Grid（不規則網格模型），TIN是針對離散點數據，其具有數據冗余小的優點，而且可以充分顧及到地形特征，能夠將地形各種復雜的細節特征有效反映出來，但該方法的算法比較復雜，所以在實現方面存在一定難度，而且存儲以及空間操作上也很不方便；Grid是基于規則分布數據點，該方法拓撲關系簡單，算法容易實現，存儲以及空間操作都非常方便，但其數據冗余較大，不能有效地對地形結構和特征進行描述。TIN是地形生成算法的基礎，本文著重討論TIN的算法。三角網相對于TIN和Grid 算法比較簡單，而且圖形靈活多變，改進的Delaunay三角網法可以有效提高 TIN 的建網效率，下面就對Delaunay的改進算法的相關研究。

利用數據分塊建網再合并技術對Delaunay算法進行優化處理，因為Delaunay算法的原則同樣適用于TIN建網和合并，所以基于該方法的建網效率與采樣點增長呈線性遞減分布，使得Delaunay三角網的生成速度得到大幅度提高。Delaunay改進算法處理過程如下：

2 處理原始數據（切分采樣點）

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

3 基本三角網的生成

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

3 三維地形可視化系統的實現

3.1 系統設計

地形表面網格模型的構建根據DEM數字高程模型，以實現三維地形可視化系統的設計，并利用光照、立體視覺技術以及紋理映射等實現地形地貌的真實再現。三維地形建模的流程如下圖2所示。

3.2 系統設計結構

本研究的基礎設施為Windows XP操作系統以及VC++6.0、OpenGL，基于以上系統和軟件進行開發，三維地形可視化系統用到的關鍵數據結構可根據三角形面片使用單鏈表形式定義，代碼如下：（來自DEM文件的數據多通過面向對象方法設計出的Cterrain類來處理，這里不再詳細介紹）。

4 結 語

采用逐點插入的方法對Delaunay進行三角劃分是三維地形顯示中非常重要的環節，在原有Delaunay算法基礎上采用采樣數據分塊建網，然后對基本三角網進行合并，這一方法極大的提高的Delaunay三角網的生產速度。

參考文獻

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

[2] 黎華，肖偉，黃海峰，等.三維真實感地形生成的關鍵技術研究[J].測繪科學，2006，31（4）：57-59.

[3] 閆豐亭.大規模三維地形建模與渲染的研究及改進[D].青島：山東科技大學，2011.

[4] 漆澤軍.三維地形建模與渲染的研究和實現[D].武漢：中南民族大學，2012.

[5] 文雄志.關于三維地形建模簡化技術的研究與實現[J].計算機光盤軟件與應用，2015（1）：7-8.

[6] 萬苗，張新家，宋佳音，等.一種交互編輯與自動生成的三維地形綜合構建方法與實現[J].電子設計工程，2014（23）：14-17.