摘要：文章介紹了多分辨率LOD地形及分形地形建模技術的相關理論和研究技術，在深入研究地形建模和簡化的典型算法的基礎上，提出了結(jié)合分形的多分辨率LOD地形建模簡化技術。

關鍵詞：分形地形；多分辨率；LOD地形；地形建模

中圖分類號：TP391文獻標識碼：A文章編號：1009-2374（2009）07-0005-02

一、多分辨率LOD地形的概念

（一）地形模型的幾何描述

本文所討論的地形是有一定的要求的，首先地形必須是一方形區(qū)域，且大小必須為（2n+1）×（2n+1），采樣點均勻的格網(wǎng)。通常采用高度圖來保存地形模型數(shù)據(jù)，由于地形模型的規(guī)則性，只要按二維順序保存地形的高度數(shù)據(jù)，然后在需要時根據(jù)二維到三維的映射就可以很容易地得到三維數(shù)據(jù)。

（二）多分辨率連續(xù)地形生成

在圖形硬件處理中，對幾何模型的渲染最后都轉(zhuǎn)換為對三角形的渲染，因此多分辨率連續(xù)地形生成就是要根據(jù)視點位置和地形的起伏程度生成不同細節(jié)層次的地形三角形網(wǎng)格，并盡量使三角形網(wǎng)格的生成簡單、避免冗余，以減少不必要和重復的圖形渲染，提高效率，增強實時性。但是由于地形三角形網(wǎng)格在生成中不同的細節(jié)層次之間必然要出現(xiàn)層次上的差異，因此就會出現(xiàn)裂縫（Cracks）和T型頭（T-Junctions），這就使地形變得不連續(xù)，如圖1所示。因此，為了保持地形網(wǎng)格的連續(xù)性，多細節(jié)層次地形簡化的一個關鍵就是要消除裂縫。消除裂縫就是要保證在不同細節(jié)層次的相鄰塊的層次之差不能夠大于1。

二、多分辨率地形的表示過程

表面多分辨率表示和繪制的典型處理步驟如圖2所示。圖中橢圓框中的內(nèi)容是各種形式的“數(shù)據(jù)”，而矩形框中的內(nèi)容總表示“處理”。

整個框圖分為兩部分。第一部分建立多分辨率表示，它通常是一個離線步驟，即作為非實時的預處理。該部分讀取輸入數(shù)據(jù)，進行必要的初始化預處理之后，按照一定的算法產(chǎn)生對輸入表面的多層次（多分辨率）表示結(jié)構(gòu)，每一個層次具有不同數(shù)量的面元，是對輸入表面的某種程度的逼近。第二部分是可視化部分，它往往是一個循環(huán)。每次循環(huán)都是先讀取約束繪制的條件（如觀察位置、誤差門限、輸出面元數(shù)量），然后通過遍歷上述多分辨率表示結(jié)構(gòu)，為不同的子區(qū)域選取適當分辨率的表示。不同的選取算法所得到的結(jié)果的表示形式不盡相同：有的得到多邊形網(wǎng)格，即可直接用于繪制當前一幀圖像;有的則不是網(wǎng)格形式，還需要進一步生成網(wǎng)格，然后方可用于繪制。

三、多分辨率地形的基本特征

表面的多分辨率表示方面的研究主要集中在多分辨率表示的構(gòu)造策略和構(gòu)造方法上。不同的策略和方法導致不同的模型。我們從模型的基本特征上來認識表面的多分辨率表示。多分辨率模型的基本特征包括：面元形狀、數(shù)據(jù)結(jié)構(gòu)形式、細節(jié)管理方式、層次結(jié)構(gòu)類型、構(gòu)造途徑、誤差測度等。

（一）面元形狀

對表面的表示總是以網(wǎng)格來逼近的。網(wǎng)格的每一個網(wǎng)孔稱為一個面元。面元的形狀是一個多邊形，大多數(shù)情況下為三角形，也有四邊形、六邊形等其他形狀。以三角形為面元對表面實現(xiàn)網(wǎng)格化逼近被稱為表面的三角化（Triangulation）。三角化網(wǎng)格中的面元有的是任意三角形，有的是直角三角形，還有的是等邊三角形。面元是任意三角形的網(wǎng)格被稱為不規(guī)則三角化網(wǎng)絡（TIN），每個面元三角形相似的網(wǎng)格稱為非TIN網(wǎng)格。

（二）結(jié)構(gòu)形式

表面的多分辨率表示可看作是對輸入表面的一系列網(wǎng)格近似。每個近似表示的逼近程度不同，稱為具有不同層次的細節(jié)。將這些近似表示結(jié)構(gòu)起來的方式有兩種：一種是離散的序列結(jié)構(gòu)，另一種是有機的層次結(jié)構(gòu)。序列結(jié)構(gòu)的多分辨率表示不需要復雜的數(shù)據(jù)結(jié)構(gòu)，它就是在不同的k個離散分辨率上產(chǎn)生一個對象的k個模型，并保存起來。繪制該對象時，基于某些準則（如距離），從這組模型中選取某個即可。

（三）細節(jié)管理方式

細節(jié)層次的管理有顯式LOD和隱式LOD兩種模式。在顯式LOD下，網(wǎng)格表面序列中的每一個都顯式地滿足給定的逼近誤差條件;而在隱式LOD模式下，在同一個網(wǎng)格表面上不同部分的逼近誤差可能有較大差別。盡管網(wǎng)格表面序列是由粗略到精細，但不能保證其中接續(xù)的兩個網(wǎng)格表面之間有指定數(shù)量的精度提高，而面元數(shù)量的增加卻可以控制。可以從隱式LOD的模型獲得顯式LOD的模型。

（四）層次模型的類別

根據(jù)其組織幾何信息的方式，多分辨率表面的層次模型可分為兩類：一類是基于面元層次的模型，一類是基于頂點層次的模型。面元層次模型是較為傳統(tǒng)的多分辨率表示模型，這種模型著重描述不同細節(jié)層次的網(wǎng)格面元之間的關系。優(yōu)點是便于在對表面做近似描述時保持其拓撲結(jié)構(gòu)。基于這種模型發(fā)表的多分辨率表示及可視化的算法較多。面元層次模型可進一步分為兩個子類：層次子分模型和金字塔面元模型。這兩種模型最先是由DeFloriani和Puppo針對地形表示提出的。后來DeFloriani還提出了一般面元層次模型“多重三角化”（Multi-Triangulation），并指出，現(xiàn)有多分辨率模型都可理解為多重三角化MT的特例。

頂點層次模型是按照不同逼近程度的近似表面中頂點之間的關系來構(gòu)造層次的。層次中的每個節(jié)點對應一組頂點，即一個節(jié)點的所有子節(jié)點所表示的頂點則是在作更精確的近似時用來替代本節(jié)點所對應的頂點的。每個節(jié)點都可存貯它所對應的誤差度量。由于僅有頂點信息不足以確定網(wǎng)格，所以還需要有保存如何形成網(wǎng)格的信息?？梢暬瘯r，選取了適當?shù)暮喕硎竞?，還要作“生成網(wǎng)格”的處理。

（五）層次的構(gòu)造順序

從構(gòu)造多分辨率表示的各個層次的先后順序來看，已發(fā)表的算法可以分為兩類方法：一類是求精法（refinement），另一類是簡略法（decimation）。求精法是從對輸入表面的一個最粗糙的近似網(wǎng)格開始，迭代地插入一個或多個頂點或面元到網(wǎng)格中，從而增加網(wǎng)格的細節(jié)，直到使網(wǎng)格符合所要求的最高近似精度。簡略法則是從輸入表面的一個最精確的近似網(wǎng)格（甚至就是輸入模型本身）開始，然后迭代地通過刪除頂點、縮減邊線或面元等方法來簡化網(wǎng)格，直到獲得允許的最粗表示。

（六）誤差測度

多分辨率層次模型中的每一個近似網(wǎng)格與輸入表面之間存在偏差。如何度量這種偏差，有多種方法。從度量范圍上看，有局部誤差和全局誤差。局部誤差是指近似網(wǎng)格的頂點或面元與輸入表面之間的偏差；全局誤差是指整個近似網(wǎng)格與輸入表面之間的偏差。從度量的尺度上看，有的采用歐氏距離，有的是用Hausdorff距離，有的用映射距離，還有采用諸如曲率等高次誤差測度。在許多面向可視化的層次模型中，通常采用屏幕空間的誤差測度以及一些如顏色、紋理等非幾何特性的方法。

四、簡化約束條件

到目前為止，地形可視化方面已建立了多種地形模型簡化約束條件。多分辨率模型中按離散LOD方式選取簡化表示時，會導致切換LOD時在畫面上產(chǎn)生視覺“跳變”，并導致很難調(diào)節(jié)幀速率，這在要求恒定幀速率的應用中是不可取的。因此，在可視化階段，最主要的約束簡化的條件是“視野相關的簡化（View-dependent Simplification）”，即要求實時地基于觀察者的視點位置等自適應地簡化對象的表示，只要滿足指定的允許誤差。這種方法以連續(xù)LOD方式選取簡化表示，可以克服上述問題。

構(gòu)建多分辨率表示的過程是以不依賴于視野的方式離線進行的，為了支持可視化時依賴于視野來選取簡化表示，一方面要求在兩個過程（建模和選?。┲卸疾捎猛瑯拥暮喕僮鳎硪环矫嬉谀Ｐ椭斜Ａ艨晒┯嬎闩c視野相關的誤差測度的信息。這樣在可視化階段才能通過一些預定的簡化操作（如頂點消去、邊收縮等）和指定誤差選取出與視野相關的簡化表示。

Lindstrom等人率先將視野相關的簡化技術用于地形的實時繪制。Duchaineau等以及Hoppe等相繼發(fā)表了類似的用于地形可視化的算法。這些算法的基本簡化操作是頂點消去。Hoppe還采用邊收縮操作將簡化技術推廣到具有任意拓撲結(jié)構(gòu)的不規(guī)則網(wǎng)格上。Luebke和Erlkson提出了一種基于層次的數(shù)據(jù)結(jié)構(gòu)，運用頂點聚合操作完成與視野相關的簡化的處理框架。

約束簡化的另一個條件是誤差門限。在可視化階段的簡化中，這一門限通常是用戶在屏幕空間指定，而簡化算法往往是先計算簡化表面的幾何誤差，然后將該誤差投影到屏幕空間與用戶指定的門限比較。

幀速率也是約束簡化的一個條件。用戶指定幀速率等價于限定了每個簡化表示的三角形面元的數(shù)目，盡管這種對應關系是與平臺有關的。

五、結(jié)語

本文首先介紹了多分辨率LOD地形的相關概念、理論和特征，隨后在研究數(shù)字地形模型及分形理論后，提出一種新的地形建模方法，即利用DEM數(shù)據(jù)生成地形框架，運用分形理論生成細節(jié)?？蚣苌蛇^程中采用層次細節(jié)簡化技術簡化地形，提取大致描繪地形總體形狀特征的數(shù)據(jù)，再運用分形理論進行細節(jié)繪制，并結(jié)合視點變化提出新的面片可見性判別方法。

作者簡介：蔣軍榮（1974－），男，廣西全州人，永州市勘測設計院工程師，研究方向：測繪。