三維地形可視化研究綜述*

楊剛

(陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，漢中 723000)

地形，可以說(shuō)是自然界最復(fù)雜的景物.因此，三維真實(shí)感地形的繪制一直是國(guó)內(nèi)外計(jì)算機(jī)圖形學(xué)領(lǐng)域關(guān)注的熱點(diǎn)［1］.三維真實(shí)感地形圖能逼真地反映外部外部真實(shí)世界，它具有許多優(yōu)點(diǎn)如:可視化程度高、實(shí)用方便、存儲(chǔ)和查詢方便、可實(shí)時(shí)生成等.三維地形的模擬是開(kāi)發(fā)可視系統(tǒng)中最基本也是最重要的技術(shù)之一.本文主要敘述三維地形可視化研究的現(xiàn)狀、趨勢(shì)及其此類系統(tǒng)開(kāi)發(fā)的常用工具等.

1 國(guó)內(nèi)外研究現(xiàn)狀

早期，最簡(jiǎn)單的地形仿真方法是由稀疏分布點(diǎn)的高程值構(gòu)成一些簡(jiǎn)單的三角形平面，從而形成地形框架，并貼以紋理圖像.這種方法的顯示速度很快，但基本框架過(guò)于簡(jiǎn)略，且有較強(qiáng)的卡通效果，因此地景的真實(shí)感受到影響［2］.后來(lái)，三維地形生成也采用計(jì)算幾何方法，即利用一些常用的參數(shù)曲面，如Bezier曲面、B樣條曲面，通過(guò)插值、擬合生成所需要的三維地形.該方法不僅計(jì)算復(fù)雜、計(jì)算量大，且生成的物體一般具有光滑的表面、規(guī)則的形狀.但是，自然地形是粗糙的、不規(guī)則的，用這種方法無(wú)法生成令人滿意的、真實(shí)感效果好的自然地形.

目前，實(shí)際應(yīng)用中使用最多的方法是基于數(shù)字地形模型DTM(Digital Terrain Model)生成技術(shù).DTM數(shù)據(jù)是由規(guī)則網(wǎng)格地形圖上采樣所得的高程值組成，與飛機(jī)或衛(wèi)星上所拍攝的遙感紋理圖像相對(duì)應(yīng)，這些紋理圖像在地形重構(gòu)時(shí)被影射到相應(yīng)的位置便得到逼真的地形圖.但這種算法的效率很低，因?yàn)檫@種算法在渲染時(shí)需將遙感獲得的紋理圖像以最高分辨率影射到對(duì)應(yīng)的多邊形，而多邊形和遙感圖像紋理像素的數(shù)量非常大，因此如果用DTM直接生成地形，對(duì)硬件要求非常高，需要對(duì)DTM數(shù)據(jù)進(jìn)行一些簡(jiǎn)化.數(shù)字地形模型中地形屬性為高程時(shí)稱為數(shù)字高程模型DEM(Digital Elevation Model)，DEM是建立DTM的基礎(chǔ)數(shù)據(jù).DEM通常用地表規(guī)則網(wǎng)格單元構(gòu)成的高程矩陣表示，廣義的DEM還包括等高線、三角網(wǎng)等所有表達(dá)地面高程的數(shù)字表示.

1.1 DEM的分類

(1)規(guī)則網(wǎng)格模型［3］.規(guī)則網(wǎng)格，通常是指正方形、矩形、三角形等規(guī)則網(wǎng)格.規(guī)則網(wǎng)格將區(qū)域空間切分為規(guī)則的網(wǎng)格單元，每個(gè)網(wǎng)格單元對(duì)應(yīng)一個(gè)數(shù)值.數(shù)學(xué)上可以表示為一個(gè)矩陣，在計(jì)算機(jī)實(shí)現(xiàn)中則是一個(gè)二維數(shù)組.每個(gè)網(wǎng)格單元或數(shù)組的一個(gè)元素，對(duì)應(yīng)一個(gè)高程值.任何不是網(wǎng)格中心的數(shù)據(jù)點(diǎn)的高程值都可采用其周圍4個(gè)中心點(diǎn)的高程值的距離加權(quán)平均方法進(jìn)行計(jì)算.

(2)等高線模型.等高線模型表示高程、高程值的集合是已知的，每一條等高線對(duì)應(yīng)一個(gè)已知的高程值，這樣一系列等高線集合和它們的高程值一起就構(gòu)成了一種地面高程模型.等高線通常可用二維的鏈表來(lái)存儲(chǔ)，另外的一種方法是用圖來(lái)表示等高線的拓?fù)潢P(guān)系.這類圖可以改造成一種無(wú)圈的自由樹(shù).圖1為一個(gè)等高線圖和它相應(yīng)的自由樹(shù).

(3)不規(guī)則三角網(wǎng)(TIN)模型.不規(guī)則三角網(wǎng)TIN(Triangulated Irregular Network)是另外一種表示數(shù)字高程模型的方法，它既減少規(guī)則網(wǎng)格方法帶來(lái)的數(shù)據(jù)冗余;同時(shí)，在計(jì)算效率方面又優(yōu)于純粹基于等高線的方法.圖2是用不規(guī)則三角網(wǎng)生成的地形.

多年以來(lái)，人們對(duì)地形的生成從不同角度或利用不同的算法做出了大量的工作，也取得了許多成就.

圖1 地形的等高線圖和它所對(duì)應(yīng)的自由樹(shù)

圖2 用TIN模型生成的地形

1.2 國(guó)外三維地形可視化研究現(xiàn)狀

國(guó)外在三維地形方面研究的比較早，Lindstrom等于1996年，首次針對(duì)Gird提出了多分辨率地形模型實(shí)時(shí)繪制算法［4］，他的算法采用四叉樹(shù)結(jié)構(gòu)，自底向上遞歸合并三角形直到屏幕投影誤差超出閾值，得到最終的地形LOD(Level of Detail)模型.其算法思想為以后一系列地形LOD模型算法打下了基礎(chǔ).2001年，Lindstrom等又提出了基于外存(out-of-core)的大規(guī)模地形可視化技術(shù)［5］，使地形數(shù)據(jù)在自頂向下細(xì)分的過(guò)程中安排數(shù)據(jù)在內(nèi)、外存中調(diào)度.2002年，他又提出的SOAR(Stateless One-pass Adaptive Refinement)算法，類似于先前的幾種方法，在規(guī)則網(wǎng)格上采用基于視點(diǎn)的最長(zhǎng)邊剖分方法，自頂向下逐步求精，每一幀均采用相同的步驟，并且把三角形條帶化、視區(qū)裁剪以及幾何過(guò)渡都集中在這一步驟，使得執(zhí)行起來(lái)更為方便.此外，Heckbert提出的一種通用的多分辨率LOD地景選擇方法、Eck提出的一種通用不規(guī)則網(wǎng)格表面細(xì)分方法［6］以及Staadt提出的一種基于小波分析的地形LOD層次細(xì)節(jié)模型生成方法［7］.Luebke采用分級(jí)動(dòng)態(tài)簡(jiǎn)化法(HDS)，并用視相關(guān)方法來(lái)對(duì)大的多邊形場(chǎng)景進(jìn)行自適應(yīng)的簡(jiǎn)化，HDS通過(guò)頂點(diǎn)對(duì)收縮操作建立的頂點(diǎn)層次樹(shù)結(jié)構(gòu)稱為頂點(diǎn)樹(shù)，這種頂點(diǎn)樹(shù)提供了一種整個(gè)場(chǎng)景的連續(xù)LOD表示方法.實(shí)時(shí)繪制時(shí)，HDS遍歷頂點(diǎn)樹(shù)，對(duì)場(chǎng)景中任何有效的多邊形進(jìn)行繪制，并通過(guò)有效多邊形來(lái)確定屏幕空間誤差門限、輪廓邊界和三角形概算等.這些算法和技術(shù)在某種程度上，極大地促進(jìn)了地形可視化領(lǐng)域的發(fā)展.總之，國(guó)外對(duì)地形可視化的研究比較早，取得的成果比較豐富，這里不再贅述.

1.3 國(guó)內(nèi)三維地形可視化研究現(xiàn)狀

國(guó)內(nèi)學(xué)者對(duì)地形的可視化研究比較晚，但近年來(lái)發(fā)展比較迅速，取得諸多成就.如涂超、毋河海、王新生發(fā)表了論文［8］:大規(guī)模地形快速渲染算法的研究，文中主要對(duì)原有的算法進(jìn)行改進(jìn)，目的在于減少繪制的三角形數(shù)量、處理的時(shí)間，以及合理地組織數(shù)據(jù);李鳳霞、王尚洋、黃都培發(fā)表的論文:大規(guī)模地形模型的多分辨率顯示技術(shù)研究，提出了一種基于塊的大地形模型多分辨率顯示技術(shù)，用此技術(shù)生成的地形如圖3所示;武玉國(guó)、杜瑩、王曉明等發(fā)表的論文［9］:大規(guī)模地形TIN模型的LOD算法設(shè)計(jì)與實(shí)現(xiàn)，主要利用LOD細(xì)節(jié)分層思想提出了一種地形TIN模型，重點(diǎn)解決不同分辨率TIN模型間的連續(xù)過(guò)渡問(wèn)題;趙友兵、石教英、周驥等發(fā)表的論文:一種大規(guī)模地形的快速漫游算法，通過(guò)地形分塊和視見(jiàn)體投影三角形掃描算法實(shí)現(xiàn)快速裁剪，通過(guò)調(diào)整頂點(diǎn)的高度值消除裂縫，通過(guò)基于三角形的四叉分割實(shí)現(xiàn)連續(xù)細(xì)節(jié)層次地形簡(jiǎn)化，簡(jiǎn)化了算法實(shí)現(xiàn)，提高了算法效率.除此之外，有些研究是主要針對(duì)提高三維模擬地形的真實(shí)感而展開(kāi)的.例如:張繼賢等提出的利用小波進(jìn)行多尺度地形的生成方法;另一類方法則注重根據(jù)地學(xué)圖形數(shù)據(jù)的精確描述，來(lái)進(jìn)行真實(shí)地形的仿真，如薛安等提出的基于OpenGL實(shí)現(xiàn)真實(shí)感地形表現(xiàn)的研究.

圖3 用多分辨率模型生成的地形

近年來(lái)，通過(guò)增強(qiáng)預(yù)處理功能等手段，研究人員發(fā)展了很多減輕CPU實(shí)時(shí)計(jì)算負(fù)擔(dān)、充分利用GPU計(jì)算和繪制能力的算法［10］.通過(guò)這些算法可以減輕CPU在地形模擬中的計(jì)算負(fù)擔(dān)，但GPU技術(shù)的發(fā)展推動(dòng)了人們對(duì)更高質(zhì)量渲染畫(huà)面的追求，同時(shí)也受到了CPU計(jì)算能力的制約.這些緣由加上兩者之間的性能差距還在不斷擴(kuò)大等因素，促使地形繪制領(lǐng)域的研究人員開(kāi)始重新審視傳統(tǒng)的單純按照頂點(diǎn)最少原則設(shè)計(jì)的地形繪制算法.在這種背景下，以簡(jiǎn)化地形網(wǎng)格和減少CPU計(jì)算負(fù)擔(dān)為雙重目標(biāo)的GPU友好型算法成為一個(gè)的研究熱點(diǎn).然而，有許多應(yīng)用并不需要針對(duì)某個(gè)特定地區(qū)的真實(shí)地形數(shù)據(jù)來(lái)進(jìn)行仿真，而是希望可以靈活地生成不同特征的地形，以滿足不同的要求，或者是為了保證整個(gè)虛擬環(huán)境的真實(shí)感，需要臨時(shí)增加一個(gè)具有良好視覺(jué)效果的地形作為輔助環(huán)境建模，這時(shí)如果仍然采用基于DTM數(shù)據(jù)的地形生成方法顯得并不經(jīng)濟(jì)適用，但應(yīng)用分形技術(shù)生成地形可以解決這一問(wèn)題，利用分形技術(shù)可以用盡量少的數(shù)據(jù)量來(lái)實(shí)現(xiàn)具有真實(shí)感虛擬地形的生成.

分形幾何是Mandelbort于1957年造出的一個(gè)名詞，分形幾何關(guān)注的是物體的隨機(jī)性、奇異性和復(fù)雜性，它試圖透過(guò)混亂現(xiàn)象和不規(guī)則構(gòu)型揭示隱藏在背后的局部與整體的本質(zhì)聯(lián)系和運(yùn)動(dòng)規(guī)律［11］.分形幾何具有細(xì)節(jié)無(wú)限，以及統(tǒng)計(jì)自相似性的典型特性，它用遞歸算法使復(fù)雜的景物可用簡(jiǎn)單的規(guī)則來(lái)生成，在現(xiàn)代的計(jì)算機(jī)圖形學(xué)中，分形幾何在對(duì)自然現(xiàn)象的真實(shí)繪制和建模方面起著重要作用.

分形布朗運(yùn)動(dòng)FBM(Fractional Brownian Motion)可用來(lái)模擬地形，許多分形地景建模方法都與這一數(shù)學(xué)模型有關(guān).分形布朗運(yùn)動(dòng)是現(xiàn)代非線性時(shí)序分析中的重要隨機(jī)過(guò)程，它能有效地表達(dá)自然界中許多非線性現(xiàn)象，也是迄今為止能夠描述真實(shí)地形的最好的隨機(jī)過(guò)程［12］.FBM有多種不同的實(shí)現(xiàn)方法，根據(jù)實(shí)現(xiàn)方法的不同，F(xiàn)BM生成算法可細(xì)分為泊松階躍法、傅立葉濾波法、中點(diǎn)位移法、逐次隨機(jī)增加法和帶限噪聲累積法等.分形布朗運(yùn)動(dòng)的幾個(gè)實(shí)現(xiàn)方法中，中點(diǎn)位移法是標(biāo)準(zhǔn)的分形幾何法，時(shí)間復(fù)雜度僅是n的線性次項(xiàng)，可用作快速地景生成.它是利用細(xì)分過(guò)程中，在兩個(gè)點(diǎn)或多個(gè)點(diǎn)之間進(jìn)行插值的方法來(lái)進(jìn)行地景建模，因此中點(diǎn)位移法產(chǎn)生了真正的分形地表.但不同細(xì)分階段產(chǎn)生的點(diǎn)在相鄰區(qū)域中有不同的統(tǒng)計(jì)特性，這常會(huì)產(chǎn)生所謂的“折痕問(wèn)題”.另外，由于這種算法地形的高程值是隨機(jī)產(chǎn)生的，生成的山脈地形形狀無(wú)法預(yù)測(cè)和控制.雖然中點(diǎn)位移法有這樣的缺陷，但因其實(shí)現(xiàn)非常容易，代碼簡(jiǎn)單，可遞歸進(jìn)行;可以合成任意分辨率地形;圖像對(duì)于放大縮小具有不變性.因此，此法已經(jīng)成為計(jì)算機(jī)模擬中一個(gè)有代表性的方法.

2 開(kāi)發(fā)工具的選擇

當(dāng)前，關(guān)于三維地形生成的系統(tǒng)多在Visual C++開(kāi)發(fā)環(huán)境下進(jìn)行的，采用的圖形庫(kù)是OpenGL或Direct3D，但以O(shè)penGL為主.OpenGL是一個(gè)開(kāi)放的圖形硬件的軟件接口，是SGI公司于1972年7月首次發(fā)布的作為三維圖形編程的接口，目前已成為國(guó)際上通用的開(kāi)放式三維圖形標(biāo)準(zhǔn)［13］.它集成了所有曲面造型、圖形變換、光照、材質(zhì)、紋理、像素操作、融合、反走樣、霧化等復(fù)雜的計(jì)算機(jī)圖形學(xué)算法，開(kāi)發(fā)人員可利用這些函數(shù)對(duì)整個(gè)三維圖形輕松進(jìn)行渲染，達(dá)到數(shù)字化現(xiàn)實(shí)生活景象的目的.

在Visual C++開(kāi)發(fā)環(huán)境下進(jìn)行OpenGL編程，就是要把OpenGL命令函數(shù)融入到Visual C++程序的事件機(jī)制之中，使之與程序的其它部分結(jié)合成一個(gè)整體.此類可視化系統(tǒng)的開(kāi)發(fā)框架有:glut框架、Win 32 Application、Win 32 Console Application、基于MFC的OpenGL程序框架(具體又可以細(xì)分:基于對(duì)話框、基于單文檔、基于多文檔)等.

3 地形可視化研究的發(fā)展趨勢(shì)

由上述可以看出地形可視化研究發(fā)展的趨勢(shì)如下:①對(duì)原算法進(jìn)行改進(jìn)，減少繪制數(shù)據(jù)的數(shù)量，進(jìn)而提高繪制速度;②對(duì)改進(jìn)算法或原算法產(chǎn)生的某些視覺(jué)效果缺陷進(jìn)行修正、補(bǔ)償，從而得到更好的繪制效果;③對(duì)三維真實(shí)感地形生成的真實(shí)性進(jìn)行研究，從而提高其真實(shí)感;④發(fā)展簡(jiǎn)化地形網(wǎng)格和減少CPU計(jì)算負(fù)擔(dān)的GPU友好型算法.

除了前面提及的地形模擬研究的幾個(gè)發(fā)展趨勢(shì)外，地形的可控性(或可修改性)的研究也是一個(gè)熱點(diǎn).在地形的可控性研究中多采用分形算法生成的地形.目前來(lái)說(shuō)，針對(duì)可控性這個(gè)方向的研究較少，雖然康曉清等提出過(guò)基于融合曲面造型方法的預(yù)定形狀山脈地形生成，許社教等提出過(guò)基于散亂點(diǎn)網(wǎng)格化的可控地形圖技術(shù)，但這些研究并不能徹底的解決分形地形不可控制和預(yù)測(cè)的缺點(diǎn)，如何將地形生成的真實(shí)感和可控性很好地結(jié)合是地形研究的另一個(gè)發(fā)展趨勢(shì).

4 結(jié)語(yǔ)

地形可視化研究的內(nèi)容十分豐富，如數(shù)字地形模型研究、地形的簡(jiǎn)化、相關(guān)算法的改進(jìn)、地形多分辨率模型的建立或改進(jìn)、地形真實(shí)感的研究、GPU友好型算法研究、可控性地形研究、空間數(shù)據(jù)結(jié)構(gòu)的研究等.經(jīng)過(guò)人們多年不斷的努力，取得了許多可喜成果.但本領(lǐng)域仍然有一些遺留問(wèn)題值得人們繼續(xù)研究和探索，如漫游地形的實(shí)時(shí)性顯示、地形數(shù)據(jù)壓縮、可控地形的研究問(wèn)題等.

［1］和平鴿工作室.OpenGL高級(jí)編程與可視化系統(tǒng)開(kāi)發(fā)高級(jí)編程篇(第二版)［M］.北京:中國(guó)水利水電出版社，2006:140-141.

［2］范乃梅，熊 坤.基于OpenGL的三維地形的生成與簡(jiǎn)化［J］.鄭州輕工業(yè)學(xué)院學(xué)報(bào)(自然科學(xué)版)，2006，21(3):84-87.

［3］高 穎，黃羅軍，許志國(guó)，黃建國(guó).飛行模擬用三維數(shù)字地形動(dòng)態(tài)修改技術(shù)研究［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2006，24(6):721-725.

［4］Lindstrom P，Koller D.Real-time，continuous level of detail rendering of height fields［A］.In:Proceedings of SIGGRA PH’96［C］，Held in New Orleans，Louisiana，August 1996.

［5］Peter Lindstrom，Valeiro Pascucci.Visualization of Large Terrains Made Easy［A］.In:Proceedings of IEEE Visualization’2001 Conference［C］，Held in Sen Diego California，October.2001.

［6］EckM，DeRose T，Duchamp Tetal.Multireso lution analysis of arbitrary meshes.In:Proceedings of SIGGRAPH’95［C］，Held in Los Angles，California，August 1995.

［7］Staadt O，Gross M，Gatti R.Fast multiresolution surface meshing［A］.In:Proceedings of IEEE Visualization’95 Conference［C］，Held in Atlanta Georgia，October 1995.

［8］涂 超，毋河海，王新生.大規(guī)模地形快速渲染算法的研究［J］.昆明理工大學(xué)學(xué)報(bào)，2002，27(1):1-5.

［9］武玉國(guó)，杜 瑩，王曉明，游 雄.大規(guī)模地形TIN模型的LOD算法設(shè)計(jì)與實(shí)現(xiàn)［J］.系統(tǒng)仿真學(xué)報(bào)，2005，17(3):665-669.

［10］黃爭(zhēng)舸.虛擬自然場(chǎng)景建模和可視化的若干問(wèn)題研究［D］.杭州:浙江大學(xué)，2000.

［11］高秀榮.基于FBM的可控性真實(shí)感地形的生成方法研究［D］.青島:中國(guó)海洋大學(xué)，2007.

［12］李慶忠，高秀榮.三維可控真實(shí)感地形生成方法研究［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20(11):2938-2941.

［13］李權(quán)國(guó)，劉鴻福.OpenGL在三維地形模型中的應(yīng)用［J］.太原理工大學(xué)學(xué)報(bào)，2004，35(1):36-38.