結(jié)合分形的多分辨率ＬＯＤ地形建模簡(jiǎn)化技術(shù)研究

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

關(guān)鍵詞：分形地形；多分辨率；LOD地形；地形建模

中圖分類(lèi)號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-2374（2009）07-0005-02

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

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

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

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

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

二、多分辨率地形的表示過(guò)程

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

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

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

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

（一）面元形狀

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

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

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

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

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

（四）層次模型的類(lèi)別

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

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

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

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

（六）誤差測(cè)度

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

四、簡(jiǎn)化約束條件

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

構(gòu)建多分辨率表示的過(guò)程是以不依賴(lài)于視野的方式離線(xiàn)進(jìn)行的，為了支持可視化時(shí)依賴(lài)于視野來(lái)選取簡(jiǎn)化表示，一方面要求在兩個(gè)過(guò)程（建模和選?。┲卸疾捎猛瑯拥暮?jiǎn)化操作，另一方面要在模型中保留可供計(jì)算與視野相關(guān)的誤差測(cè)度的信息。這樣在可視化階段才能通過(guò)一些預(yù)定的簡(jiǎn)化操作（如頂點(diǎn)消去、邊收縮等）和指定誤差選取出與視野相關(guān)的簡(jiǎn)化表示。

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

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

幀速率也是約束簡(jiǎn)化的一個(gè)條件。用戶(hù)指定幀速率等價(jià)于限定了每個(gè)簡(jiǎn)化表示的三角形面元的數(shù)目，盡管這種對(duì)應(yīng)關(guān)系是與平臺(tái)有關(guān)的。

五、結(jié)語(yǔ)

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

作者簡(jiǎn)介：蔣軍榮（1974－），男，廣西全州人，永州市勘測(cè)設(shè)計(jì)院工程師，研究方向：測(cè)繪。