瓦片塊四叉樹(shù)動(dòng)態(tài)地形層次細(xì)節(jié)算法

張?jiān)ツ?，王冬?，夏乙，李瀚飛

(1.裝甲兵工程學(xué)院 控制工程系，北京100072;2.武漢軍械士官學(xué)校 無(wú)人機(jī)系，湖北 武漢430075;3.重慶航天職業(yè)技術(shù)學(xué)院，重慶400021;4.66222 部隊(duì) 北京100000)

地形可視化是虛擬戰(zhàn)場(chǎng)環(huán)境、三維室外場(chǎng)景游戲以及車輛駕駛訓(xùn)練模擬系統(tǒng)中重要的組成部分，一直是計(jì)算機(jī)圖形學(xué)里研究的熱點(diǎn)問(wèn)題。在某些特殊應(yīng)用中，地形的某個(gè)區(qū)域的屬性(如高程值或顏色等)還可能會(huì)隨時(shí)發(fā)生改變。如多用途工程車等工程裝備對(duì)地表的破壞、炸彈爆炸留下的彈坑、車輛在松軟土地上行駛后留下的車轍等，這類地形被稱作動(dòng)態(tài)地形。動(dòng)態(tài)地形應(yīng)用中典型的是車轍的可視化，且一直是動(dòng)態(tài)地形中研究的熱點(diǎn)問(wèn)題。

以基于圖形處理器(GPU)的動(dòng)態(tài)地形形變算法為基礎(chǔ)，擴(kuò)展并實(shí)現(xiàn)了一種基于GPU 的視點(diǎn)相關(guān)連續(xù)動(dòng)態(tài)地形層次細(xì)節(jié)(LOD)算法。該算法以瓦片塊四叉樹(shù)算法作為地形繪制算法，通過(guò)重復(fù)使用一小塊頂點(diǎn)緩存和索引緩存，結(jié)合不同的縮放和平移因子來(lái)渲染不同細(xì)節(jié)層次的瓦片塊，很好的表現(xiàn)了車轍效果。對(duì)地形塊增加“裙子”頂點(diǎn)，消除了不同細(xì)節(jié)層次的瓦片塊拼接時(shí)可能產(chǎn)生的裂縫現(xiàn)象。最后通過(guò)實(shí)驗(yàn)證明了該算法是可行的和有效的，適合于大規(guī)模動(dòng)態(tài)地形的繪制。

1 動(dòng)態(tài)地形可視化算法概述

Summer 等［1］通過(guò)4 個(gè)渲染步驟來(lái)模擬行人在沙地、泥濘地和雪地上留下的腳印。然而由于該算法只能產(chǎn)生光滑的形變，而且需要手動(dòng)調(diào)節(jié)5 個(gè)渲染參數(shù)來(lái)達(dá)到理想的視覺(jué)效果，因此并不適合實(shí)時(shí)渲染等場(chǎng)合。He 等［2］采用二叉三角樹(shù)結(jié)構(gòu)，通過(guò)對(duì)ROAM 算法進(jìn)行擴(kuò)展，提出了一種實(shí)時(shí)動(dòng)態(tài)地形可視化方法DEXTER.文獻(xiàn)［3］針對(duì)動(dòng)態(tài)地形的特殊情況，采用嵌套球半徑作為誤差，給出了一種實(shí)時(shí)可視化動(dòng)態(tài)地形的完整解決方案。文獻(xiàn)［4］在ROAM算法的基礎(chǔ)上，提出一種基于規(guī)則網(wǎng)格的塊間裂縫解決算法，根據(jù)分裂點(diǎn)在有向無(wú)環(huán)圖(DAG)中的依賴關(guān)系來(lái)消除裂縫。文獻(xiàn)［5］提出了一種基于三角帶模板的車轍實(shí)時(shí)可視化算法。

隨著圖形硬件的發(fā)展，為了充分利用現(xiàn)代GPU特性，Aquilio［6］提出了一種基于GPU 的動(dòng)態(tài)地形形變算法，該算法利用幀緩沖區(qū)對(duì)象和2 次頂點(diǎn)紋理拾取操作，將對(duì)形變頂點(diǎn)的處理由CPU 轉(zhuǎn)移到GPU，釋放了CPU 負(fù)擔(dān)，為動(dòng)態(tài)地形的可視化引入了一個(gè)新的研究方向。王冬［7］等在文獻(xiàn)［6］的基礎(chǔ)上進(jìn)一步將每幀更新的動(dòng)態(tài)地形深度紋理作為拾取對(duì)象，只進(jìn)行一次頂點(diǎn)紋理拾取操作來(lái)產(chǎn)生地形形變效果。

由于文獻(xiàn)［6-7］在繪制形變后的地形時(shí)采用的是強(qiáng)迫分割算法，且并沒(méi)有進(jìn)一步給出如何將該算法和基于GPU 的地形LOD 算法相結(jié)合，因此限制了其在大規(guī)模動(dòng)態(tài)地形上的應(yīng)用。本文在文獻(xiàn)［7］的基礎(chǔ)上，結(jié)合瓦片塊四叉樹(shù)地形LOD 繪制算法，提出并實(shí)現(xiàn)了一種基于GPU 的動(dòng)態(tài)地形LOD算法。

2 基于GPU 的動(dòng)態(tài)地形LOD 算法

整個(gè)基于GPU 的動(dòng)態(tài)地形LOD 算法分為動(dòng)態(tài)地形形變算法和動(dòng)態(tài)地形繪制算法2 個(gè)部分。

2.1 基于GPU 的動(dòng)態(tài)地形形變算法

整個(gè)動(dòng)態(tài)地形形變算法的偽代碼描述如下:

動(dòng)態(tài)地形形變算法分為4 個(gè)階段［7］，其基本思想是首先利用幀緩沖區(qū)對(duì)象的渲染到紋理功能將地形高程圖轉(zhuǎn)化為原始的地形深度紋理，如圖1(a)所示。為了計(jì)算由于車輛對(duì)地面的壓力造成的地表頂點(diǎn)的沉陷位移，需要通過(guò)模型視點(diǎn)變換和投影變換產(chǎn)生車輛的深度紋理(通過(guò)視點(diǎn)在地面下方垂直向上觀察地形表面得到)，如圖1(b)所示。將第1 步產(chǎn)生的原始地形深度紋理減去第2 步產(chǎn)生的車輛深度紋理，這樣就可以在片元著色器里得到表示車輪陷入到地表以下深度值的偏移圖，如圖1(c)所示。在片元著色器里通過(guò)對(duì)原始地形深度紋理和深度偏移圖進(jìn)行運(yùn)算，產(chǎn)生此刻形變地形的深度紋理，最后通過(guò)頂點(diǎn)紋理拾取操作產(chǎn)生連續(xù)車轍效果，如圖1(d)所示。

2.2 基于GPU 的地形繪制算法

由于文獻(xiàn)［7］在繪制形變后的地形時(shí)采用的是強(qiáng)迫分割算法，沒(méi)有考慮LOD 簡(jiǎn)化技術(shù)，占用了較多的系統(tǒng)資源，因此本文采用瓦片塊四叉樹(shù)多分辨率網(wǎng)格來(lái)繪制地形。

2.2.1 基本思想

瓦片塊四叉樹(shù)算法里每一個(gè)地形塊可以用統(tǒng)一的縮放和平移變量來(lái)表示不同細(xì)節(jié)層次的地形塊，因此更適合于在GPU 上實(shí)現(xiàn)地形繪制［8-9］。該算法的基本思想是，所有地形塊組織成(2k+1)×(2k+1)規(guī)則網(wǎng)格，每個(gè)頂點(diǎn)都對(duì)應(yīng)于高程圖(2n+1)×(2n+1)中的某一個(gè)元素。所有地形塊在送入圖形管線時(shí)都是平面網(wǎng)格，地形塊的高程值在頂點(diǎn)著色器通過(guò)拾取高程圖紋理來(lái)獲得。由于地形塊頂點(diǎn)的位置是在頂點(diǎn)著色器里計(jì)算而不是在CPU 中計(jì)算，而且由于每個(gè)地形塊包含相同數(shù)量的頂點(diǎn)以及相同的網(wǎng)格連接關(guān)系，因此所有地形塊可以重復(fù)使用同一個(gè)頂點(diǎn)緩存和索引緩存。

2.2.2 誤差估計(jì)

算法使用一種簡(jiǎn)單的基于距離的評(píng)估標(biāo)準(zhǔn)，距離視點(diǎn)較遠(yuǎn)的地形塊將覆蓋更多的區(qū)域，離視點(diǎn)越近的地方細(xì)節(jié)越豐富。另外，還可以采用文獻(xiàn)［10］里的對(duì)地形塊使用最大屏幕空間誤差方法，這將不僅考慮視點(diǎn)與地形塊的距離，還包括地形表面的粗糙程度。

基于距離的評(píng)估標(biāo)準(zhǔn)由下式給出)

圖1 基于GPU 動(dòng)態(tài)地形形變算法原理Fig.1 Dynamic terrain deformation algorithm

式中:l 為地形塊中心到視點(diǎn)的距離;d 為世界坐標(biāo)系下地形塊網(wǎng)格間距;C 為一個(gè)可調(diào)節(jié)的控制地形渲染質(zhì)量的參數(shù)。如果測(cè)試成功，地形塊分割成4個(gè)子節(jié)點(diǎn)，并向下遞歸繼續(xù)校驗(yàn);如果測(cè)試失敗，則渲染地形塊。

對(duì)于地形塊大小的選擇，如果地形塊太大，會(huì)導(dǎo)致地形太過(guò)粗糙或太精細(xì)。使用小的地形塊雖然可以在細(xì)節(jié)層次上有更大的變化，但是會(huì)增加渲染函數(shù)調(diào)用的次數(shù)。因此，需要根據(jù)試驗(yàn)來(lái)確定合適的地形塊大小，以達(dá)到渲染調(diào)用的次數(shù)和三角形大小多樣化之間的一種平衡。

2.2.3 裂縫消除

瓦片塊地形算法中相鄰的不同細(xì)節(jié)層次瓦片塊之間會(huì)出現(xiàn)裂縫問(wèn)題。本文使用一種簡(jiǎn)單而且高效的“裙子”縫合方法，每個(gè)瓦片塊四周都有一個(gè)沿著垂直邊界擴(kuò)展的“裙擺”，如圖2所示。

圖2 瓦片塊四周沿著邊界添加垂直裙擺Fig.2 Added vertical skirt to tile block's borde

將這些額外的“裙子”頂點(diǎn)添加在頂點(diǎn)緩存的最后，繪制時(shí)首先在索引緩存里正常繪制地形瓦片塊，接著通過(guò)添加一個(gè)褪化三角形來(lái)開(kāi)始繪制裙子三角形。同時(shí)，為了優(yōu)化性能需要將裙子三角形和地形瓦片塊三角形通過(guò)一次性三角形條帶(Triangle_Strip)來(lái)繪制。

即使利用裙子算法可能會(huì)引起一些光照及紋理拉伸問(wèn)題，然而由于填充的裂縫一般都很小，因此這些問(wèn)題不容易被察覺(jué)到。另外，雖然這樣做會(huì)增加一些多邊形的數(shù)量，然而相對(duì)于利用CPU 做縫合，這種消耗可以忽略不記，而且這種方式很容易在GPU 上實(shí)現(xiàn)。

2.2.4 碰撞檢測(cè)

通常碰撞檢測(cè)是由CPU 來(lái)查詢存放在內(nèi)存里的地形高程數(shù)據(jù)來(lái)獲取相應(yīng)位置的頂點(diǎn)高程，即操作是在CPU 和內(nèi)存之間完成。然而，這樣做會(huì)增加CPU 的負(fù)擔(dān)，對(duì)于需要查詢大量的外部實(shí)體與地形碰撞檢測(cè)的應(yīng)用場(chǎng)合，這種負(fù)擔(dān)將急劇增加。

文獻(xiàn)［8］在地形漫游時(shí)為了避免視點(diǎn)陷入到地面以下，提出了一種基于GPU 的查詢視點(diǎn)所在位置處地形高度的方法，該方法將高程圖載入到顯存之后，就釋放系統(tǒng)內(nèi)存里的相應(yīng)資源，然后，在像素著色器里查詢高程圖紋理中視點(diǎn)所在位置處的像素顏色信息;接著，利用幀緩沖區(qū)對(duì)象將該像素顏色信息渲染到一個(gè)1 ×1 大小的紋理中;最后，通過(guò)讀取該紋理來(lái)獲得查詢點(diǎn)的高程值。整個(gè)操作在GPU 和顯存之間完成，能夠有效降低CPU 的負(fù)擔(dān)。

在車輛與地形的匹配算法中，通常需要查詢的匹配點(diǎn)不止一個(gè)，通常為3 點(diǎn)或4 點(diǎn)匹配算法［11］。本文擴(kuò)展了文獻(xiàn)［8］中的方法，使得可以同時(shí)查詢多個(gè)高程值。初始化時(shí)利用幀緩沖區(qū)對(duì)象創(chuàng)建一個(gè)大小為2 ×2 的紋理作為渲染目標(biāo)。在渲染到紋理時(shí)，將我需要查詢的4 個(gè)點(diǎn)的x，z 世界坐標(biāo)歸一化成0～1 范圍內(nèi)的紋理坐標(biāo)，并以點(diǎn)圖元(GL_POINTS)進(jìn)行繪制。

為了在2 ×2 大小的紋理中區(qū)分這4 個(gè)像素值，繪制時(shí)需要對(duì)這4 個(gè)輸入點(diǎn)進(jìn)行平移使它們分別位于如圖3所示的P1，P2，P3，P4四個(gè)區(qū)域內(nèi)。

圖3 2 ×2 大小的渲染目標(biāo)紋理Fig.3 2 ×2 target texture

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

針對(duì)本文的思想和方法，已經(jīng)在微機(jī)上實(shí)現(xiàn)了一個(gè)基于GPU 的車轍實(shí)時(shí)可視化演示系統(tǒng)，很好的表現(xiàn)了車輛在松軟地面行駛時(shí)留下的車轍效果。硬件配置為:CPU Intel Pentium Dual-Core 2.5 GHz，2 GBRAM，NVIDIA GeForce9500 顯卡，128 M 顯存;軟件環(huán)境為:Windows XP，VC++.Net 2003、OpenGL 2.0，GLSL v1.2.

對(duì)2 049 ×2 049 大小的地形數(shù)據(jù)，地形塊大小為33 ×33，窗口大小為800 ×600，系統(tǒng)的平均幀率在90 f/s 以上。

圖4給出了系統(tǒng)運(yùn)行時(shí)的截圖。圖4(a)、圖4(b)為視點(diǎn)離車輛較遠(yuǎn)時(shí)，車輛所在的瓦片塊具有較低的細(xì)節(jié)層次，雖然此時(shí)的網(wǎng)格間距大于輪胎寬度，相應(yīng)的頂點(diǎn)高度并沒(méi)有發(fā)生改變，但由于場(chǎng)景離視點(diǎn)較遠(yuǎn)，通過(guò)車轍紋理就能夠很好的表現(xiàn)出車轍效果。圖4(c)為視點(diǎn)離車輛較近時(shí)，車輛附近的瓦片塊具有較高細(xì)節(jié)層次水平，從中可以清晰的看出車輪下的地形發(fā)生的形變。

使用1 024 ×1 024 大小的地形，對(duì)本文算法和文獻(xiàn)［7］算法的性能進(jìn)行比較，結(jié)果如表1所示，從中可以看出使本文的算法提高了系統(tǒng)性能。

表1 繪制1 024 ×1 024 大小地形時(shí)的性能比較Tab.1 Performance comparison in rendering 1 024 ×1 024 terrain

4 結(jié)論

本文以動(dòng)態(tài)地形中的車轍實(shí)時(shí)可視化為研究對(duì)象，提出了一種基于GPU 的瓦片塊四叉樹(shù)動(dòng)態(tài)地形LOD 算法;并針對(duì)車輛與地形的匹配問(wèn)題，提出了基于GPU 的同時(shí)查詢多個(gè)高程值的方法。理論分析與實(shí)驗(yàn)結(jié)果表明，本文算法中的將GPU 的加速能力同地形多分辨率繪制算法相結(jié)合，對(duì)于提高動(dòng)態(tài)地形的繪制效率是很有效果的，并且該方法還可以在其他類型的地形形變可視化中推廣應(yīng)用，均有一定的理論和使用價(jià)值。

后續(xù)的研究工作包括進(jìn)一步優(yōu)化該算法的性能，使用最大屏幕空間誤差方法來(lái)進(jìn)一步減小需要繪制的三角形數(shù)量;關(guān)于進(jìn)一步如何突破單張紋理大小限制的問(wèn)題，考慮使用地形的多分辨率金字塔模型和外存技術(shù)來(lái)實(shí)現(xiàn)大規(guī)模地形的存儲(chǔ)，并結(jié)合紋理數(shù)組技術(shù)來(lái)加載需要繪制的地形。

References)

［1］ Sumner R W，O'Brien J F，Hodgins J K.Animatingsand，mud，and snow［J］.Computer Graphics Forum，1999，18(1):17-26.

［2］ Yefei He，James Cremer，Yiannis Papelis.Real-time extendibleresolution display of on-line dynamic terrain［C］∥Proceedings of the 2002 Conference on Graphics Interface.Calgary，Alberta:A K Peters，Ltd，2002:151-160.

［3］ 王林旭，李思昆，潘曉輝.動(dòng)態(tài)地形的實(shí)時(shí)可視化［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26(11):1524-1531.WANG Lin-xu，LI Si-kun，PAN Xiao-hui.Real time visualization of dynamic terrain［J］.Chinese Journal of Computers，2003，26(11):1524-1531.(in Chinese)

［4］ Chen Guojun，Zhang Jing，Xu Xiaoli，et al.Real-time visualization of tire tracks in dynamic terrain with LOD［C］∥Proceedings of the 2nd International Conference on Technologies for E-Learning and Digital Entertainment.Berlin，Heidelberg:Springer-Verlag，2007:655-666.

［5］ 蔡興泉，李鳳霞，李立杰，等.基于三角帶模板的車轍實(shí)時(shí)可視化方法［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18(10):2843- 2846.CAI Xing-quan，LI Feng-xia，LI Li-jie，et al.Real-time visualization of ruts based on strip masks［J］.Journal of System Simulation，2006，18(10):2843-2846.(in Chinese)

［6］ Anthony S.Aquilio，Jeremy C.Brooks，Ying Zhu，et al.Realtime GPU-based simulation of dynamic terrain［J］.ISVC，LNCS 4291，2006:891-900.

［7］ 王冬，張?jiān)ツ?，李瀚飛，等，基于GPU 的動(dòng)態(tài)地形實(shí)時(shí)可視化［J］.計(jì)算機(jī)工程與應(yīng)用，2010(14):177-179.WANG Dong，ZHANG Yu-nan，LI Han-fei，et al.Real-time visualization of dynamic terrain based on GPU［J］.Journal of Computer Engineering and Application，2010(14):177-179.(in Chinese)

［8］ Mike Dickheiser.Game programming gems 6［M］.Boston，Massachusetts:Carles River Media，2006:461-471.

［9］ 王冬，張?jiān)ツ?，李瀚飛，等.一種基于GPU 的瓦片塊四叉樹(shù)地形繪制算法［J］.系統(tǒng)仿真學(xué)報(bào)，2009，(增刊1):106-109.WANG Dong，ZHANG Yu-nan，LI Han-fei，et al.Tiled block quadtree terrain rendering algorithm based on GPU［J］.Journal of System Simulation，2009(S1):106-109.(in Chinese)

［10］ Ulrich T.Rendering massive terrains using chunked level of detail control［EB/OL］.［2002-04-01］.http:∥tulrich.com/geekstuff/chunklod.html.

［11］ 宋漢辰，魏迎梅，吳玲達(dá).三維對(duì)象模型與地形的匹配方法研究［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15 (9):1167-1171.SONG Han-chen，WEI Ying-mei，WU Ling-da.Matching research of 3D object model with terrain in virtual environment［J］.Journal of Computer-aided Design ＆ Computer Graphics，2003，15(9):1167-1171.(in Chinese)