瓦片塊四叉樹動態地形層次細節算法

張豫南，王冬，2，夏乙，李瀚飛

(1.裝甲兵工程學院 控制工程系，北京100072;2.武漢軍械士官學校 無人機系，湖北 武漢430075;3.重慶航天職業技術學院，重慶400021;4.66222 部隊 北京100000)

地形可視化是虛擬戰場環境、三維室外場景游戲以及車輛駕駛訓練模擬系統中重要的組成部分，一直是計算機圖形學里研究的熱點問題。在某些特殊應用中，地形的某個區域的屬性(如高程值或顏色等)還可能會隨時發生改變。如多用途工程車等工程裝備對地表的破壞、炸彈爆炸留下的彈坑、車輛在松軟土地上行駛后留下的車轍等，這類地形被稱作動態地形。動態地形應用中典型的是車轍的可視化，且一直是動態地形中研究的熱點問題。

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

1 動態地形可視化算法概述

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

隨著圖形硬件的發展，為了充分利用現代GPU特性，Aquilio［6］提出了一種基于GPU 的動態地形形變算法，該算法利用幀緩沖區對象和2 次頂點紋理拾取操作，將對形變頂點的處理由CPU 轉移到GPU，釋放了CPU 負擔，為動態地形的可視化引入了一個新的研究方向。王冬［7］等在文獻［6］的基礎上進一步將每幀更新的動態地形深度紋理作為拾取對象，只進行一次頂點紋理拾取操作來產生地形形變效果。

由于文獻［6-7］在繪制形變后的地形時采用的是強迫分割算法，且并沒有進一步給出如何將該算法和基于GPU 的地形LOD 算法相結合，因此限制了其在大規模動態地形上的應用。本文在文獻［7］的基礎上，結合瓦片塊四叉樹地形LOD 繪制算法，提出并實現了一種基于GPU 的動態地形LOD算法。

2 基于GPU 的動態地形LOD 算法

整個基于GPU 的動態地形LOD 算法分為動態地形形變算法和動態地形繪制算法2 個部分。

2.1 基于GPU 的動態地形形變算法

整個動態地形形變算法的偽代碼描述如下:

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

2.2 基于GPU 的地形繪制算法

由于文獻［7］在繪制形變后的地形時采用的是強迫分割算法，沒有考慮LOD 簡化技術，占用了較多的系統資源，因此本文采用瓦片塊四叉樹多分辨率網格來繪制地形。

2.2.1 基本思想

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

2.2.2 誤差估計

算法使用一種簡單的基于距離的評估標準，距離視點較遠的地形塊將覆蓋更多的區域，離視點越近的地方細節越豐富。另外，還可以采用文獻［10］里的對地形塊使用最大屏幕空間誤差方法，這將不僅考慮視點與地形塊的距離，還包括地形表面的粗糙程度。

基于距離的評估標準由下式給出)

圖1 基于GPU 動態地形形變算法原理Fig.1 Dynamic terrain deformation algorithm

式中:l 為地形塊中心到視點的距離;d 為世界坐標系下地形塊網格間距;C 為一個可調節的控制地形渲染質量的參數。如果測試成功，地形塊分割成4個子節點，并向下遞歸繼續校驗;如果測試失敗，則渲染地形塊。

對于地形塊大小的選擇，如果地形塊太大，會導致地形太過粗糙或太精細。使用小的地形塊雖然可以在細節層次上有更大的變化，但是會增加渲染函數調用的次數。因此，需要根據試驗來確定合適的地形塊大小，以達到渲染調用的次數和三角形大小多樣化之間的一種平衡。

2.2.3 裂縫消除

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

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

將這些額外的“裙子”頂點添加在頂點緩存的最后，繪制時首先在索引緩存里正常繪制地形瓦片塊，接著通過添加一個褪化三角形來開始繪制裙子三角形。同時，為了優化性能需要將裙子三角形和地形瓦片塊三角形通過一次性三角形條帶(Triangle_Strip)來繪制。

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

2.2.4 碰撞檢測

通常碰撞檢測是由CPU 來查詢存放在內存里的地形高程數據來獲取相應位置的頂點高程，即操作是在CPU 和內存之間完成。然而，這樣做會增加CPU 的負擔，對于需要查詢大量的外部實體與地形碰撞檢測的應用場合，這種負擔將急劇增加。

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

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

為了在2 ×2 大小的紋理中區分這4 個像素值，繪制時需要對這4 個輸入點進行平移使它們分別位于如圖3所示的P1，P2，P3，P4四個區域內。

圖3 2 ×2 大小的渲染目標紋理Fig.3 2 ×2 target texture

3 實驗結果與分析

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

對2 049 ×2 049 大小的地形數據，地形塊大小為33 ×33，窗口大小為800 ×600，系統的平均幀率在90 f/s 以上。

圖4給出了系統運行時的截圖。圖4(a)、圖4(b)為視點離車輛較遠時，車輛所在的瓦片塊具有較低的細節層次，雖然此時的網格間距大于輪胎寬度，相應的頂點高度并沒有發生改變，但由于場景離視點較遠，通過車轍紋理就能夠很好的表現出車轍效果。圖4(c)為視點離車輛較近時，車輛附近的瓦片塊具有較高細節層次水平，從中可以清晰的看出車輪下的地形發生的形變。

使用1 024 ×1 024 大小的地形，對本文算法和文獻［7］算法的性能進行比較，結果如表1所示，從中可以看出使本文的算法提高了系統性能。

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

4 結論

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

后續的研究工作包括進一步優化該算法的性能，使用最大屏幕空間誤差方法來進一步減小需要繪制的三角形數量;關于進一步如何突破單張紋理大小限制的問題，考慮使用地形的多分辨率金字塔模型和外存技術來實現大規模地形的存儲，并結合紋理數組技術來加載需要繪制的地形。

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］ 王林旭，李思昆，潘曉輝.動態地形的實時可視化［J］.計算機學報，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］ 蔡興泉，李鳳霞，李立杰，等.基于三角帶模板的車轍實時可視化方法［J］.系統仿真學報，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］ 王冬，張豫南，李瀚飛，等，基于GPU 的動態地形實時可視化［J］.計算機工程與應用，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］ 王冬，張豫南，李瀚飛，等.一種基于GPU 的瓦片塊四叉樹地形繪制算法［J］.系統仿真學報，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］ 宋漢辰，魏迎梅，吳玲達.三維對象模型與地形的匹配方法研究［J］.計算機輔助設計與圖形學學報，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)