宋省身，全吉成，趙秀影，王宏偉，王 宇

（1.空軍航空大學 航空航天情報系，吉林 長春130022；2.軍事仿真技術研究所，吉林 長春130022）

0 引 言

近年來，關于地形場景的渲染技術在三維仿真的諸多領域得到了廣泛的應用，當前主流的研究集中在視點相關的LOD 算法上，通常將之分為兩類，前GPU 算法和后GPU 算法［1］。早期基于CPU 的算法如ROAM 和VDPM，每次都要計算優(yōu)化誤差并依此選擇優(yōu)化的方案，需要耗費大量的內(nèi)存和CPU 時間?，F(xiàn)在的圖形處理器GPU 具備強大的浮點運算能力和多條流水線，如Chunked LOD 使用了塊狀四叉樹結(jié)構(gòu)，僅需要最小限度的CPU 參與就可以繪制大量的多邊形表面。

然而這項技術以靜態(tài)數(shù)據(jù)作為渲染源，即將預處理好的地形網(wǎng)格按層次呈現(xiàn)，并不具備實時添加新細節(jié)的能力，當視點觀察的網(wǎng)格深入到數(shù)據(jù)的最高分辨率層級時，系統(tǒng)就無法繼續(xù)細化，此時就會出現(xiàn)地形紋理模糊和網(wǎng)格棱角化的現(xiàn)象。同時，文獻 ［2］還指出Chunked LOD 對視點距離的計算過于簡單，僅提供了近似三維距離的誤差度量，造成了細節(jié)分配不均。

為了充分利用GPU 的繪制速度，增強細節(jié)視效，本文在研究了Chunked LOD 的基礎上，提出了實時增加細節(jié)的改進方案，相對于文獻［3］的局部三角面化簡算法和誤差評估與控制算法，該算法結(jié)合了Geomipmap的思想［4，5］，以規(guī)則格網(wǎng)為處理單位修改細節(jié)的生成和過渡算法，以及誤差度量的計算和判斷準則，更高效地利用GPU 的批處理能力實現(xiàn)繪制，經(jīng)過實驗證明，達到了實時增強細節(jié)的效果。

1 Chunked LOD 基本算法

Ulrich在Siggraph 2002 年會上提出了一種基于GPU的地形LOD 算法，稱之為Chunked LOD［6］。

該算法的核心是構(gòu)建一個四叉樹結(jié)構(gòu)，樹上的每個節(jié)點 （Node）包含一塊地形，每個子節(jié)點包含其父節(jié)點地形的1／4，但其分辨率卻更高。這樣自上而下，根節(jié)點包含整個地形區(qū)域，是其最粗糙的表示，葉子節(jié)點則是數(shù)據(jù)集中所能達到的最高分辨率進行分塊得到。節(jié)點與節(jié)點之間相互獨立，節(jié)點中的地形數(shù)據(jù)以靜態(tài)的方式存儲在網(wǎng)格中，稱之為Chunk。每個塊內(nèi)的數(shù)據(jù)可以通過一個繪制命令和一個高級的混合通道來完成繪制。

Chunked LOD 創(chuàng)新的另一處是對縫隙的消除［7］。在塊的周圍構(gòu)造垂直的裙邊來消除縫隙，裙邊的上邊與塊邊相接，下邊則延伸到比所有的細節(jié)層次都低，裙邊只影響本塊，不與其他塊聯(lián)系，紋理也可以直接采用原來塊的紋理，這樣的方法可以有效地消除縫隙。由于塊之間相互獨立，方便實現(xiàn)out－of－core算法對數(shù)據(jù)進行分頁管理和預讀調(diào)度，開啟獨立的線程專門用于調(diào)用不同區(qū)域的地形塊即可。但這需要在服務器或是硬盤存儲事先處理好的數(shù)據(jù)。

該算法的主要缺陷就是預處理工作量大，處理出來的數(shù)據(jù)為靜態(tài)數(shù)據(jù)，無法實時更新或者增強細節(jié)，面對分辨率有限的地形數(shù)據(jù)，當視點高度離地面很近時，顯示的視覺效果真實感不足。

此外，當視點逐漸接近一個塊時，這個塊將會根據(jù)誤差控制分裂為很多的小塊，屏幕上會產(chǎn)生明顯的突跳現(xiàn)象，這種現(xiàn)象比逐三角形的LOD 算法如ROAM 算法等要明顯的多［8］，而當視點位置恰好處于兩個層級的臨界點時，這種閃爍現(xiàn)象會變得尤為突出，其解決辦法便是借助于幾何過渡來減緩網(wǎng)格結(jié)構(gòu)的變化。

2 Chunked LOD 細節(jié)增強的改進

2.1 細節(jié)增強的基本原理

為當前的高度場添加細節(jié)，即增加更多的采樣點。根據(jù)Geomipmap的思想，細節(jié)的添加是其簡化過程的逆運算，通過隔行隔列添加的方法使采樣點密度變?yōu)樵瓉淼?倍，分裂出4個子節(jié)點，如圖1所示。

圖1 細節(jié)的添加過程

在這里，我們將節(jié)點分為兩類，一種是靜態(tài)節(jié)點，即在預處理過程中通過采樣獲取同一區(qū)域不同分辨率節(jié)點，在渲染時，我們可以通過將對應分辨率的節(jié)點調(diào)入顯存中直接進行渲染；另外一種是動態(tài)節(jié)點，它是在四叉樹結(jié)構(gòu)延伸至葉子節(jié)點時，若還不能滿足視點閾值的需求，由計算機實時計算生成并加入四叉樹中的節(jié)點，作為本文研究的重點，這里僅介紹動態(tài)節(jié)點的生成算法。

新生成的節(jié)點，理想上要與已有的節(jié)點相關聯(lián)，保持原來的拓撲關系，顯然，線性插值不能滿足這種要求，它僅能提供C0連續(xù)性，原來的結(jié)構(gòu)并沒有發(fā)生任何變化，為此我們需要一種高階的插值算法，并結(jié)合位移函數(shù)來制造出均勻的變化，增強真實感，其過程如圖2所示。

圖2 動態(tài)節(jié)點的生成過程

2.2 算法的具體實現(xiàn)

地形網(wǎng)格進行線性插值后，原本尖銳的網(wǎng)格仍保持尖銳，盡管對某些崎嶇的地形可以接受，但我們還是希望能夠移除這些突兀的邊緣，代之以平滑連續(xù)的地勢，獲得流暢的視覺觀感。

本文結(jié)合并改進了的文獻 ［8］的插值算法——Kobbelt算法，使之能夠適用于地形模型的細分。該算法在構(gòu)造復雜的曲線曲面中都取得了很好的效果，由于細分方法構(gòu)造簡單、計算快速且能夠保證生成圖形的光滑連續(xù)等性質(zhì)，由于Kobbelt插值細分基于四邊形網(wǎng)格模型，正適用于RSG 類型的地形網(wǎng)格進行細分。

Kobbelt細分的基本思想是在四邊形網(wǎng)格的原始頂點上根據(jù)細分掩膜插入面點和邊點，并與原始頂點連接成新的四邊形，這樣原來的一個四邊形面片被分割成4個新的四邊形，從而實現(xiàn)對原始網(wǎng)格進行細分的目的。在細化過程中，所有新生成的非邊界頂點度數(shù)為4，邊界頂點度數(shù)為3，都是正則點，從而可以迭代進行。

其細分規(guī)則如下：

如圖3所示，當我們對四邊形V5V6V7V8進行細分時，會在其4條邊上形成4個邊點E0E1E2E3，同時還有一個面點F，使原來的面片分裂成4個子面片。E0，E1，E2，E3的值如下公式

面點F 的值由下公式得出

圖3 細分過程

這種細分算法只能應用于正則點所在規(guī)則格網(wǎng)上，對于奇異點不予考慮。由于Chunked LOD 算法的特點，細化過程是在每個塊內(nèi)獨立進行的，對于鄰塊內(nèi)的網(wǎng)格無從知曉，當掩膜移動至塊的邊緣時，傳統(tǒng)的邊外推和對角點替換都會產(chǎn)生假邊緣，為了保證視覺上的真實感，我們在塊結(jié)構(gòu)中再存儲上鄰塊的邊采樣點，只有在對邊進行細化時才使用其作為控制點，塊內(nèi)的細分則對其不予考慮，以少量增加數(shù)據(jù)為代價換取邊緣的連續(xù)性。

位移函數(shù)用在插值之后，它的作用是提供更加豐富的地形細節(jié)。分形理論就能夠很好地解決這一問題。描述自然界中存在的隨機分形，目前通用的模型是由Mandelbrot等人提出的分形布朗運動 （fractal brown motion，F(xiàn)BM），其二維定義如下。用變量 （x，y）表示曲面上點的坐標，X（x，y）表示該點在曲面上的高。則FBM 曲面定義為在某概率空間上，指數(shù)為H （0＜H＜1）的一個隨機過程。

隨機變量X：R→R2滿足：

（1）以概率1，X（0，0）＝0，即過程自原點開始；且X（t）是t的連續(xù)函數(shù)。

（2）對任意變量 （x，y），（h，k）∈R2，其二維增量X（x＋h，y＋k）服從期望為0，方差為 （h2－k2）H的正態(tài)分布，其概率滿足

使用分形技術繪制的三維地形能夠產(chǎn)生無限具有自相似性的逼真場景，易于進行平滑和插值。Geoclipmap中的細節(jié)合成采用了高斯噪聲函數(shù)，文獻 ［9］采用的是Perlin噪聲函數(shù)，利用有限帶寬頻率的逐次增加合成地形表面，通常需要多次的運算和校正以獲得合適的效果，這會造成較大的計算負載，使得實時獲取變得困難。為了權衡實時性與渲染質(zhì)量，一般的做法是預存分形函數(shù)在不同頻域下的處理結(jié)果，當需要調(diào)用函數(shù)時，僅對結(jié)果進行插值以獲得粗糙的采樣值。這樣做雖然可以節(jié)省計算量，但顆粒度較大，偽渲染的痕跡明顯。

因此算法的效率顯得尤為重要，中點位移法因其實現(xiàn)簡單，運算速度快而被選為本文的分形函數(shù)。

本文采用文獻 ［10］中的Diamond－Square算法作為位移函數(shù)，由種子點組成的正方形開始，通過若干次中點位移法迭代后，不斷細分種子正方形以獲得逼真的三維地形，同時增加自由參數(shù)H 和方差σ構(gòu)成的 “補償項”強化地勢的起伏性并避免 “尖峰”和 “折痕”的出現(xiàn)。由于對其算法并未做出改進，這里不再贅述。

插值與位移遞歸地進行時會遇到這樣一個問題，在某次插值時，其基礎是上一次插值并進行位移之后的節(jié)點，那么會導致新生成的節(jié)點疊加了之前所有的位移量，這樣會造成相對于原始網(wǎng)格難以控制的偏差。為了解決這個問題，需要將插值和位移分離，即設置基礎高度圖和位移高度圖兩個網(wǎng)格，其中，基礎高度圖用于遞歸地插值，位移高度圖則用于將插值得到的點加入其中進行位移調(diào)整?；A高度圖由四叉樹中的葉子節(jié)點所對應的網(wǎng)格得到，但不同的是葉子節(jié)點不可以再細分，而基礎高度圖卻可以插值細分。位移高度圖與高度圖具有相同的大小和采樣點數(shù)目，但其采樣點的值是由基礎圖對應點通過位移函數(shù)計算得出的。

2.3 幾何過渡

為了避免地形繪制時所有節(jié)點同時分裂造成的突變現(xiàn)象，在細節(jié)層次進行變換時采取一種緩慢漸變的方式，即為幾何過渡。這種過程可以根據(jù)時間或是誤差進行，相比之下后者在視點移動時才會進行，有助于減少漸變時產(chǎn)生的 “閃爍”。

由于數(shù)據(jù)存儲在四叉樹結(jié)構(gòu)中，子節(jié)點在各個方向上的采樣點數(shù)量均是父節(jié)點的二倍，但是它們所共有的點具有相同的位置，因此相鄰的兩個層之間由粗到細的過渡僅僅是把子節(jié)點中的精細點添加到父節(jié)點上，反之簡化就是移除相應的頂點即可。雖然過渡變換發(fā)生在三維空間中，但所有頂點僅在豎直方向上變化，因此僅需要一個參數(shù)即可描述所需變換的程度。我們?nèi)∈［0，1］作為其過渡因子，h為該過渡點當前高程與目標高程的差值，變換公式如下

其中，d 表示視點到當前點的距離，dchild表示視點到子節(jié)點的距離，dparent表示視點到父節(jié)點的距離。同時，利用矩陣模板進行計算方便利用GPU 頂點著色器進行實現(xiàn)。幾何過渡的效果圖如圖4所示。

圖4 頂點的幾何過渡

2.4 誤差度量的調(diào)整

傳統(tǒng)的四叉樹結(jié)構(gòu)其葉子節(jié)點的誤差設為0，因此對四叉樹的遍歷可以在此停止，這些是針對預先生成的靜態(tài)節(jié)點所設計的，當為四叉樹添加動態(tài)節(jié)點時，就必須給葉子節(jié)點也加入誤差，當視點靠近時，若當前塊已到達底層，但誤差仍大于設定閾值，則可以利用之前的算法繼續(xù)細化。

原理上對葉子節(jié)點的插值和細分可以無限地進行，因而誤差的大小也需要無限地嵌套，但這并不符合實際要求，所以誤差需要用一種逼近的表示方法。我們通過對葉子節(jié)點的數(shù)據(jù)使用位移函數(shù)進行處理，在經(jīng)過多次的動態(tài)節(jié)點插入后，取與原始網(wǎng)格距離最大的值作為該節(jié)點的誤差。由于四叉樹結(jié)構(gòu)中的誤差度量自下而上嵌套，葉子節(jié)點誤差改變后就必須對整個四叉樹節(jié)點的誤差進行調(diào)整，而這些可以在預處理階段完成。實時加入的動態(tài)節(jié)點，按照Chunked LOD 的方法，將其誤差設為其父節(jié)點的1／2即可。

總結(jié)上述過程，用偽代碼表示改進的LOD 生成算法：

3 實驗與分析

為了檢驗本算法的實用性與實際效果，使用一塊地形數(shù)據(jù)大小為16385×8193的高度圖，原始網(wǎng)格中共包含了268435456個三角形，預處理時采取33×33進行分塊，共構(gòu)建了8 層LOD。實驗所用的計算機主要配置為：AMD AthlonⅡ處理器，4G 內(nèi)存，GTX580 顯卡，屏幕分辨率為1920×1080，操作系統(tǒng)為Win2003Server，編程語言為C＋＋和DirectX。圖5 （a）為沒有采用細節(jié)添加前效果，（b）為添加了兩層節(jié)點后的結(jié)果。表1給出了在不同LOD 層級的載入時間和漫游時間。

圖5 仿真效果

表1 靜態(tài)節(jié)點與動態(tài)節(jié)點的運行時間比較

數(shù)據(jù)顯示，隨著視點的降低，LOD 層級也逐漸深入，三角形數(shù)目不斷增長，但同時與視見體相交的塊也減少了，所以第8級LOD 的三角形數(shù)目在高度較低的情況下突然減少。第9級和第10級是動態(tài)節(jié)點加入后的結(jié)果，三角形數(shù)目開始增加，但載入速度也有所減慢。同樣，前8 級是由預處理過程生成的靜態(tài)節(jié)點，瀏覽時僅需從存儲中讀取對應的地形塊，幀速較為穩(wěn)定，而動態(tài)節(jié)點的插入給實時渲染帶來一定負擔，幀速的變化取決于地形復雜度和三角形數(shù)目。

由圖5可以看出，算法對于增強視效的作用顯而易見，在整個渲染過程中，圖5 （a）的三角形數(shù)目為672，而圖5（b）則為10752，恰好為前者的16倍，這是由于算法在視錐裁剪上并未做優(yōu)化，對于背離視點和距離視點較遠的網(wǎng)格不加區(qū)分地動態(tài)細分造成的結(jié)果。漫游時的幀速穩(wěn)定在45－50f／s間，當添加細節(jié)時在復雜地形區(qū)域會產(chǎn)生幀速下降現(xiàn)象，但繪制完成后會恢復穩(wěn)定，基本達到了預期的效果。

4 結(jié)束語

本文在分析了經(jīng)典算法Chunked LOD 的基礎上，結(jié)合了其利用四叉樹塊結(jié)構(gòu)對地形數(shù)據(jù)進行分組，提高獨立渲染速度的優(yōu)勢，針對其只能處理構(gòu)建靜態(tài)數(shù)據(jù)，無法實時添加細節(jié)的不足，提出了利用插值和分形實時地生成動態(tài)節(jié)點，強化視覺的真實感，彌補由于數(shù)據(jù)分辨率不足產(chǎn)生的地形變形，該算法利用掩膜對地形網(wǎng)格進行處理，適用于GPU 編程實現(xiàn)。實驗結(jié)果表明，該算法可以在普通計算機上實現(xiàn)大范圍地形的快速繪制和實時漫游。

本文研究所采用的地形數(shù)據(jù)仍然是一種靜態(tài)數(shù)據(jù)，即不支持實時的編輯和變形，諸如爆炸和山體滑坡之類的實時改變地形無法實現(xiàn)，而渲染過程中添加的細節(jié)是一種計算結(jié)果，非真實數(shù)據(jù)，今后我們將對于實時的地形編輯和數(shù)據(jù)更新做進一步的研究。此外，利用視見體的背面剔除和遮擋剔除，考慮在選擇繪制時刪除不必要的數(shù)據(jù)塊，以提高顯示的實時性也是下一步研究的重點。

［1］CAI Chang.Theory and key technology research on 3DGIS web service ［D］.Zhengzhou：PLA Information Engineering University，2011 （in Chinese）.［蔡暢.三維地理信息網(wǎng)絡服務的理論與關鍵技術研究 ［D］.鄭州：解放軍信息工程大學博士學位論文，2011.］

［2］Strugar F.Continuous distance－dependent level of detail for rendering heightmaps ［J］.Journal of Graphics GPU and Game Tools，2009，14 （4）：57－74.

［3］SHEN Yanchun，ZHU Youhong，WEN Zhuanping，et al.Procedual level of detail enhancement algorithm of Chunklod real time terrain rendering ［J］.Journal of System Simulation，2008，20 （21）：5763－5766 （in Chinese）.［申閆春，朱幼虹，溫轉(zhuǎn)萍，等.Chunklod地形的過程化細節(jié)度增強算法 ［J］.系統(tǒng)仿真學報，2008，20 （21）：5763－5766.］

［4］LIU Huiyuan.Research and implement on 3Dseabed digital terrain ［D］.Harbin：Harbin Engineering University，2009 （in Chinese）.［劉惠媛.三維海底地形繪制方法研究與實現(xiàn) ［D］.哈爾濱：哈爾濱工程大學，2009.］

［5］JIANG Jie.Research on key technologies in global virtual geographic environment construction ［D］.Changsha：National University of Defense Technology，2010 （in Chinese）.［蔣杰.全球大規(guī)模虛擬地理環(huán)境構(gòu)建關鍵技術研究 ［D］.長沙：國防科學技術大學，2010.］

［6］JIANG Jie，WU Lingda，CAO Rui，et al.management and web publication of global satallite remote－sensing images［C］／／7th International Conference on Information，Communications and Signal Processing，2009.

［7］ZHANG Yunan，WANG Dong，XIA Yi.A quad－tree dynamic terrain levels algorithm ［J］.ACTA Armamentaria，2011，32（11）：1411－1415 （in Chinese）.［張豫南，王東，夏乙.瓦片塊四叉樹動態(tài)地形層次細節(jié)算法 ［J］.兵工學報，2011，32（11）：1411－1415.］

［8］LIN Mouguang.Research on mesh simplification and display method for interactive mobile 3D graphics ［D］.Guangzhou：Zhongshan University，2008 （in Chinese）.［林謀廣.面向交互式移動三維圖形的網(wǎng)格簡化與顯示方法研究 ［D］.廣州：中山大學，2008.］

［9］LIAO Xuejun，WANG Rongfeng.Digital battlefield visualization and application ［M］.Beijing：National Defense Industry Press，2010：39－42（in Chinese）.［廖學軍，王榮峰.數(shù)字戰(zhàn)場可視化與應用［M］.北京：國防工業(yè)出版社，2010：39－42.］

［10］MA Shufang.Generating method based on GPU acceleration for fractal terrain ［D］.Dalian：Dalian University of Technology，2008 （in Chinese）.［馬淑芳.基于GPU 加速的分形地形生成方法 ［D］.大連：大連理工大學，2008.］