基于四叉樹的視點(diǎn)相關(guān)LOD地形仿真算法研究

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

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

0 引言

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

近十幾年來(lái)，國(guó)內(nèi)外大批學(xué)者致力于LOD地形模型的研究，促進(jìn)了LOD地形模型的發(fā)展，Lindstrom等人于1996年提出了基于四叉樹連續(xù)細(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)，對(duì)三角網(wǎng)格進(jìn)行動(dòng)態(tài)剖分和合并，也具有較優(yōu)的實(shí)時(shí)性能。Hugues Hoppe針對(duì)一般物體的多分辨率顯示提出了一種基于TIN網(wǎng)格的Progressive Mesh(漸近網(wǎng)格)算法[4]。后來(lái)又將該算法改進(jìn)應(yīng)用到地形的簡(jiǎn)化[5,6]。

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

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

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

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

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

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

圖2 滿四叉樹

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

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

該算法采用三角形扇的方式來(lái)渲染細(xì)節(jié)已滿足要求的節(jié)點(diǎn)，這是一種很自然的方式，因?yàn)槊總€(gè)節(jié)點(diǎn)包括一個(gè)中心點(diǎn)和若干個(gè)圍繞著中心點(diǎn)的點(diǎn)，剛好排成一個(gè)三角形扇。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

地形塊的邊長(zhǎng)用l表示，地形塊中點(diǎn)與視點(diǎn)之間的距離用d表示。基于塊的簡(jiǎn)化準(zhǔn)則可以用公式表示：

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

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

2.2 裂縫處理算法

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

圖5 T型裂縫

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

圖8 地形漫游程序截圖

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

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

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

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

4 結(jié)束語(yǔ)

本文針對(duì)大地形的實(shí)時(shí)顯示問(wèn)題，研究了基于四叉樹的視點(diǎn)相關(guān)LOD地形算法，并提出了消除T型裂縫、解決地形突起現(xiàn)象的方法，實(shí)現(xiàn)了精簡(jiǎn)網(wǎng)格而必要的細(xì)節(jié)沒(méi)有損失，并實(shí)現(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)格模型化簡(jiǎn)綜述[J].軟件學(xué)報(bào),2005,13(12).

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

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

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