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

時間：2021-08-24 13:13:29

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

手機看文章

掃描二維碼
隨時隨地手機看文章

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

引言

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

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

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

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

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

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

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

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

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

3.1 系統(tǒng)設計

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

3.2 系統(tǒng)設計結(jié)構

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

“Typedef struct triangle {

Int tripointID_1 ；//‘三角面片頂點 1 所在網(wǎng)格 ID 號’

Int tripointID_2 ；

Int tripointID_3 ；

}Triangle，*Ptriangle ；

Type struct TriNode{

Ptriangle tri ；//tri‘為指向一個三角形面片的指針’

TroNode*next ；

}TriNode，*PtriNode ；”

4 結(jié) 語

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