雷軍環(huán)，曾凡喜，吳名星

（1. 長沙民政學(xué)院 計算機系，長沙 410004；2. 中南大學(xué) 計算機與科學(xué)系，長沙 410007；3. 空軍工程大學(xué) 理學(xué)院，西安 710061)

0 引言

當(dāng)要求可視化的地形過大，那么同時處理的信息量就比較大，怎樣實現(xiàn)精簡網(wǎng)格數(shù)據(jù)而又不影響顯示質(zhì)量，實現(xiàn)對大規(guī)模地形實時顯示也是一個難點問題。細節(jié)層次模型(Level of Detail)等技術(shù)的應(yīng)用便成為解決這一難題的有效技術(shù)途徑層次。細節(jié)(LOD)技術(shù)[1]是一種符合人的視覺特性的技術(shù)。采用LOD技術(shù)來繪制地形，在不降低表現(xiàn)效果的前提下，可以盡量減少三角形的數(shù)目，大大提高圖形繪制效率，實現(xiàn)地形的實時交互可視化。

近十幾年來，國內(nèi)外大批學(xué)者致力于LOD地形模型的研究，促進了LOD地形模型的發(fā)展，Lindstrom等人于1996年提出了基于四叉樹連續(xù)細節(jié)層次模型(Continuous Level of Detail)的構(gòu)建算法[2]，是基于規(guī)則格網(wǎng)類的具有代表性的研究成果之一。Duchaineau等人于1997年提出的自適應(yīng)優(yōu)化網(wǎng)格算法(Real-time Optimally Adapting Meshes)是另一種有顯著影響的算法[3]。該算法基于二叉樹結(jié)構(gòu)，對三角網(wǎng)格進行動態(tài)剖分和合并，也具有較優(yōu)的實時性能。Hugues Hoppe針對一般物體的多分辨率顯示提出了一種基于TIN網(wǎng)格的Progressive Mesh(漸近網(wǎng)格)算法[4]。后來又將該算法改進應(yīng)用到地形的簡化[5,6]。

本文主要圍繞怎樣對地形網(wǎng)格進行精簡而提出來的。用四叉樹的方法對地形網(wǎng)格進行了簡化，針對網(wǎng)格簡化中產(chǎn)生的幾何突變問題和裂縫問題提出了自己的處理算法。最后利用上述方法進行地形生成實驗，給出地形生成的結(jié)果。

1 基于四叉樹結(jié)構(gòu)的LOD算法的結(jié)構(gòu)

為了更清楚地描述算法的思想，對三維地形做出規(guī)定：地形必須是正方形區(qū)域，其大小必須是(2''+1)(2''+1)。

將一塊大地形數(shù)據(jù)用一個四叉樹結(jié)構(gòu)[7]組織起來，如圖4.1。每個正方形代表一個節(jié)點，每個節(jié)點包含9個高程點，其中有1個中心點，4個角點和4個位于4條邊上的中點。一個大正方形里包含4個小正方形(葉子節(jié)點除外)，這4個小正方形所代表的節(jié)點就是大正方形節(jié)點的子節(jié)點。

圖1 地形的四叉樹結(jié)構(gòu)

首先應(yīng)該按照地形的大小把整個地形分割成一棵滿四叉樹。滿四叉樹的概念是從滿二叉樹引申過來的，除了葉子節(jié)點，每個節(jié)點都有四個子節(jié)點，且所有的子節(jié)點都位于同一層上，如圖2所示。地形越大，四叉樹的深度越大。

圖2 滿四叉樹

這樣，每個節(jié)點表示一塊地形，節(jié)點的層次愈低(根節(jié)點的層次最低，為0)，所代表的正方形面積越大，該節(jié)點的細節(jié)程度(Level)愈低。顯然，葉子節(jié)點的Level最高。

格網(wǎng)DEM數(shù)據(jù)保存在一個二維數(shù)組中。由于該算法是規(guī)則網(wǎng)格的，很容易找到節(jié)點的九個點在二維數(shù)組中的對應(yīng)高程數(shù)據(jù)。

該算法采用三角形扇的方式來渲染細節(jié)已滿足要求的節(jié)點，這是一種很自然的方式，因為每個節(jié)點包括一個中心點和若干個圍繞著中心點的點，剛好排成一個三角形扇。

用多分辨率的算法來簡化地形的過程就是自上而下遍歷四叉樹的過程。如果節(jié)點的細節(jié)程度已滿足某種節(jié)點簡化準(zhǔn)則，就渲染該節(jié)點，否則不渲染該節(jié)點，繼續(xù)考察它的四個子節(jié)點。因此，算法必須建立一種能夠?qū)?jié)點進行評估的簡化準(zhǔn)則，以決定對某塊地形細化到何種細節(jié)。

2 基于四叉樹結(jié)構(gòu)的LOD算法的具體設(shè)計

2.1 基于最小二乘粗糙度的節(jié)點簡化準(zhǔn)則

上節(jié)已經(jīng)講到，應(yīng)該確定一種節(jié)點簡化準(zhǔn)則，來判斷某節(jié)點是否應(yīng)該繼續(xù)往下細化或者往上簡化。不論簡化準(zhǔn)則采用何種誤差計算法，它都要符合以下原則：1）如某節(jié)點離視點很近，或者它代表的地形塊很“粗糙”，就應(yīng)該對該節(jié)點往下細化，即把它分裂成四個子節(jié)點；2）如果某節(jié)點離視點很遠，或者它代表的地形塊很“平滑”，就應(yīng)該對該節(jié)點往上簡化；3）如果某節(jié)點與視點的距離適中，或者不太粗糙也不太平滑，則應(yīng)該獨立的繪制該節(jié)點。這樣才符合地形多分辨率表示的核心思想。

如圖3，A、B、C、D是O的四個子節(jié)點，采用簡化準(zhǔn)則對四個子節(jié)點進行評估之后，發(fā)現(xiàn)A、B兩個節(jié)點不夠粗糙，C、D兩個節(jié)點粗糙度適中。那么只有C、D兩個節(jié)點被獨立的繪制，各用八個三角形表示；A、B兩個節(jié)點各用2個三角形表示即可。

對節(jié)點進行評估時，應(yīng)該考慮3種因素：1）地形塊的大??；2）地形塊與視點之間的距離；3） 地形塊的粗糙度。

圖3 節(jié)點簡化后的網(wǎng)格模型

簡化準(zhǔn)則通常都是通過誤差模型(Error Model)來實現(xiàn)的。除了Level最高的節(jié)點之外，其他節(jié)點相對原始數(shù)據(jù)都具有一定的誤差，因此可以用誤差的大小來決定節(jié)點的Level是否符合簡化準(zhǔn)則。

Lindstrom在他的文章中提出了基于頂點的簡化準(zhǔn)則 (Vertex-based Simplification)[2]。以地形塊ΘACIG為例，如圖4.5所示，該塊含有9個高程點A～I，δB、δD、δF、δH為B、D、F、H點到四個邊的中點之間的誤差。

圖4 頂點簡化準(zhǔn)則

Lindstrom的頂點簡化準(zhǔn)則的思想是：節(jié)點是否被忽略是由δB、δD、δF、δH最終投影到屏幕上的大小決定的。節(jié)點誤差δ投影到屏幕之后的大小用σ表示。以節(jié)點B為例，δ與σ之間的關(guān)系如圖4所示，θ為視見向量(頂點到視點之間的向量)和垂線(與水平面垂直的直線)之間的夾角。那么σ可由下列公式表示：

可見投影誤差σ不僅和δ的誤差有關(guān)，還和頂點和視點之間的距離和視見向量的角度有關(guān)，這才符合LOD算法與視點位置有關(guān)的思想。記σmax為σB、σD、σF、σH中的最大值，并把它當(dāng)作節(jié)點誤差，如果σmax小于誤差限τ，則該節(jié)點應(yīng)該向上簡化，否則對之獨立進行繪制[2,8]。

但述誤差模型僅考慮到四個邊中點的投影誤差，而忽略了其他頂點，比如它的子節(jié)點的邊中點。有可能出現(xiàn)這樣一種情況，子節(jié)點的投影誤差比父節(jié)點的誤差大，而這顯然是不符合常理的。因此，做出以下規(guī)定，如果某個子節(jié)點的誤差比父節(jié)點大，那么用子節(jié)點誤差代替父節(jié)點誤差，用公式描述就是：

其中σi(i=1,2,3,4)是子節(jié)點誤差。這樣， 的計算就與遍歷樹的順序有關(guān)，當(dāng)自下而上的遍歷樹時，很自然地應(yīng)用公式(2)計算出每個頂點的投影誤差。然而，當(dāng)自上而下的遍歷樹時(很顯然，自上而下的遍歷算法要比自下而上的時間復(fù)雜度小)，子節(jié)點的誤差未知，怎么確定父節(jié)點的誤差呢？這時，就應(yīng)該對對誤差計算方法作出一些簡化。假定節(jié)點離視點的距離很遠，節(jié)點的大小可以忽略不計，那么對于該節(jié)點內(nèi)部的每個頂點，a/dsin(θ)的值都相同。這時，公式(2)就可以簡化為

而δ的大小在地形更新過程中保持不變，其計算可以在數(shù)據(jù)預(yù)處理的過程中完成。這樣對誤差計算方法經(jīng)過簡化后，也適用于自上而下的遍歷算法了。當(dāng)然，簡化之后的誤差模型準(zhǔn)確度下降了，這是基于頂點的簡化準(zhǔn)則的缺點之一。

很顯然，基于頂點的簡化準(zhǔn)則的誤差模型反映的是某個頂點的誤差值，而不是地形塊的整體誤差。這是基于頂點的簡化準(zhǔn)則的缺點之二。

Lindstrom在他的文章[2,9]中也提出了基于塊的簡化準(zhǔn)則(Block-based Simplification)。該準(zhǔn)則用地形的整體粗糙度來確定節(jié)點的誤差大小，而且適用于“自上而下”的遍歷順序。Nielson等人用樣條小波的多分辨率分析能力來估算地形塊的粗糙度，該方法效果較好，但計算復(fù)雜、晦澀難懂，不易于程序?qū)崿F(xiàn)。本文在Lindstrom的基礎(chǔ)上提出一種簡便的粗糙度求取算法——最小二乘法。用zx,y表示地形塊中的某頂點的高度，因為地形塊為一個方形區(qū)域，顯然滿足條件xmin＜x＜xmax，ymin＜y＜ymaxx,y取整數(shù)值。那么，地形塊的平均高度 可以用公式

地形塊的邊長用l表示，地形塊中點與視點之間的距離用d表示?；趬K的簡化準(zhǔn)則可以用公式表示：

θ的涵義與公式(1)中的θ相同，為視見向量和垂線之間的夾角，τ為誤差限。如果條件(6)成立，應(yīng)該獨立的繪制該節(jié)點，否則應(yīng)該往下細化，即繼續(xù)遍歷它的四個子節(jié)點。

地形塊的粗糙度是一個常值，它不隨視點的移動而改變。因而粗糙度的計算過程可以在數(shù)據(jù)預(yù)處理階段完成，之后不需要更新，因此該算法的速度較快。

2.2 裂縫處理算法

LOD算法“分而治之”的思想帶來了地形“裂縫”這個難題。如圖5所示，當(dāng)同時繪制兩個相鄰的分辨率不同的節(jié)點時，便會產(chǎn)生T型裂縫。

圖5 T型裂縫

有兩種技術(shù)可以解決裂縫的初級問題，一種是邊刪除技術(shù)，一種是邊插入技術(shù)。邊刪除技術(shù)在Level較高的節(jié)點的T型裂縫處刪除一條邊，這樣把兩個三角形合并成了一個，要解決圖5中的裂縫問題，共需要刪除3條邊。

邊插入技術(shù)，就是在Level較低的節(jié)點內(nèi)部添加一條邊，這樣就把一個三角網(wǎng)格剖分成了2個，同樣，每添加一條邊，就將一個三角形分裂為2個。

然而，要避免裂縫現(xiàn)象，僅僅依靠邊刪除或邊插入技術(shù)是不夠的。當(dāng)相鄰的2個獨立繪制的節(jié)點之間的level差大于1時，必須強制把level較低的那個節(jié)點分解成4個子節(jié)點。如圖6所示，節(jié)點A和E的level相差2，邊刪除顯然是無能為力的，采用邊插入技術(shù)也將使算法變得過于復(fù)雜，不易實現(xiàn)。此時，將節(jié)點A分裂成四個子節(jié)點再應(yīng)用邊刪除或邊插入技術(shù)即可解決。

圖6 相鄰節(jié)點level差大于1

Rottger在它的文章中介紹了一種更靈活的方法，把四叉樹中各個節(jié)點的狀態(tài)用一個布爾矩陣表示[6,10]。節(jié)點狀態(tài)要么為1，要么為0，要么為“?”。

布爾值1表示該節(jié)點level不夠高，需要進一步向下簡化；0表示該節(jié)點level適中，應(yīng)該對它進行獨立繪制；“?”則表示不需對該節(jié)點進行獨立繪制。如果布爾矩陣同時滿足下列條件：

1）0節(jié)點的父節(jié)點肯定為1；

2）1節(jié)點的相鄰?fù)琹evel節(jié)點的狀態(tài)肯定不為“?”；

則稱該矩陣是完備的。使用完備矩陣方法再配合邊刪除或邊插入技術(shù)就可以表示一個無裂縫的多分辨率地形。將節(jié)點狀態(tài)用一個矩陣表示而不用一個樹結(jié)構(gòu)表示，其優(yōu)點在于便于查找某節(jié)點的同level相鄰節(jié)點。

2.3 突起現(xiàn)象處理算法

當(dāng)視點移動的時候，地形網(wǎng)格在不斷的更新，當(dāng)節(jié)點的level發(fā)生變化時，地形的某點會由一個高度跳變至另一個高度，這種現(xiàn)象稱為“突起”現(xiàn)象(Poping-up)。為消除這種不自然的行為，引入一種“形變”算法。形變的涵義是，當(dāng)節(jié)點從一個Level過渡到另一個Level時，其中某點平穩(wěn)緩慢的從一個高度過渡到另一個高度。

以基于塊的簡化準(zhǔn)則為例，討論如何構(gòu)建“形變”算法。將公式(6)變形，得

將f截止到(0,1)區(qū)間，則如果0＜f＜1/2，說明該節(jié)點狀態(tài)為0，如果1/2＜f＜1，說明該節(jié)點狀態(tài)為1。因為突起現(xiàn)象僅僅發(fā)生在節(jié)點的狀態(tài)由0跳變?yōu)?，或由1跳變?yōu)?的時候，可以將f作為參數(shù)來混合(blend)頂點的高度值。如圖7所示，節(jié)點的Level從1跳變至0時，有5個頂點會發(fā)生pop現(xiàn)象，它們分別是地形塊的中心點O和四條邊的中點A、B、C、D。

圖7 poping-up現(xiàn)象

以A點為例，Level=1時，A點的高度為zA。Level=0時，A點的高度為(zE+zF)/2，那么混合后的高度應(yīng)為

同理，B、C、D、O的“形變”高度也可以由公式(7)求得。

3 實驗結(jié)果

本文基于VC++ .NET平臺和DirectX圖形語言開發(fā)了一套基于四叉樹的LOD地形實時漫游程序。該程序使用基于塊的地形簡化準(zhǔn)則，消除了地形的裂縫和突起現(xiàn)象，實現(xiàn)了空間連續(xù)和時間連續(xù)。下面列出兩組實驗結(jié)果數(shù)據(jù)：

圖8 地形漫游程序截圖

圖9 地形網(wǎng)格劃分俯瞰圖

1）三角網(wǎng)格數(shù)：5000-6000；刷新率：約為40FPS；地形大小：1024*1024，屏幕分辨率：1024*768。實驗截圖如圖8所示。

2）三角網(wǎng)格數(shù)：7000-8000；刷新率：約為30FPS；地形大小：1024*1024，屏幕分辨率：1024*768。實驗截圖(俯瞰圖)如圖9所示。

實驗硬件配置：處理器Intel Pentium M 1.73GHz，內(nèi)存512MB，顯卡ATI MOBILITY RADEON X700，顯存64MB。

4 結(jié)束語

本文針對大地形的實時顯示問題，研究了基于四叉樹的視點相關(guān)LOD地形算法，并提出了消除T型裂縫、解決地形突起現(xiàn)象的方法，實現(xiàn)了精簡網(wǎng)格而必要的細節(jié)沒有損失，并實現(xiàn)了大地形的仿真

[1] ?？∮? 三維景觀多分辨率模型構(gòu)建及其可視化技術(shù)研究[D].西安:西安電子科技大學(xué),2005.5-7．

[2] Peter Lindstrom,David Koller,William Rebarsky.Real-time,continuous level of detail rendering of height fields[J].In Computer Graphics(proceedings Siggraph'96),page 109-118,1996.

[3] Duchaineau M,Wolinsky M.ROAMing Terrain: Real-time optimally adapting meshes[J].Proceedings of Visualization'97,page 81-88.

[4] Hugues Hoppe.Progressive Meshes [J].In Siggraph'96 Proceedings,page 99-108,August 1996.

[5] Hugues Hoppe.View-dependent refinement of progressive meshes [J].In Siggraph'97 Proceedings,page,August 1997.

[6] Hugues HoppeSmooth View-dependent level-of-detail control and its app lication to terrain rendering[J].IEEE Visualization '98,October 1998,page 35-42.

[7] 何暉光,田潔,等.網(wǎng)格模型化簡綜述[J].軟件學(xué)報,2005,13(12).

[8] 張黨勝.三維地形可視化系統(tǒng)研究及實現(xiàn)[D].河海大學(xué),2001.

[9] 彭儀普.地形三維可視化及其實時繪制技術(shù)研究[D].西南交通大學(xué),2002.

[10]牛俊英.三維景觀多分辨率模型構(gòu)建及其可視化技術(shù)研究[D].西安電子科技大學(xué),2005.