基于四叉樹和LOD的地形模型繪制

郝萌 余天豪 楊陽 易輝平 付浩海

摘要：為了提高地形場景的高效渲染表示，需要在保證地形精度的前提下對其進行模型化簡，即根據(jù)實際需要構建多分辨率地形模型。本文通過對基于四叉樹的規(guī)則地形場景自適應LOD表示進行了研究，提出了一種基于四叉樹和LOD的地形繪制算法。實驗結果表明，當渲染場景很大的時候，本算法可以有效降低運算量提高地形模型的繪制效率和交互性，提高用戶的使用體驗。

關鍵詞：四叉樹; LOD; 地形繪制

1.簡介

隨著空間測繪技術的發(fā)展，越來越多的大規(guī)模地形數(shù)據(jù)獲取變的可能。很多應用領域也越來越多地使用地形數(shù)據(jù)實現(xiàn)地形的三維可視化，如“數(shù)字地球”、全球環(huán)境變化監(jiān)測、災害的預報預警、資源可持續(xù)開發(fā)、大型工程設計、國防安全乃至戰(zhàn)爭等^[1]。另外，在3D游戲、虛擬現(xiàn)實和影視娛樂領域有時也需要渲染呈現(xiàn)室外三維地形模型，以實現(xiàn)場景的仿真和虛擬漫游^[2]。

由于三維地形模型精度越來越高，尺寸越來越大，導致了在實際應用中由于計算機存儲容量、處理速度、繪制速度和傳輸效率的限制，無法有效實時實現(xiàn)如此大規(guī)模數(shù)據(jù)的高分辨率渲染繪制，從而導致不能滿足應用需求。另外，在很多應用場合，高分辨率模型并不總是需要的，甚至在有些大場景應用中，全部使用高分辨率模型是完全沒有必要的。因此，人們希望在模型的逼真程度和模型需要處理的計算代價之間有一個合適的折中。為了提高地形場景的高效渲染表示，需要在保證地形精度的前提下對其進行模型化簡，即根據(jù)實際需要構建多分辨率地形模型，也稱細節(jié)層次模型（Level of Detail， LOD）。本文通過對基于四叉樹的規(guī)則地形場景自適應LOD表示進行了研究，提出了一種基于四叉樹和LOD的地形繪制算法，提高地形模型的繪制效率和交互性，提高了用戶的使用體驗，更好地驅動上述各個領域的發(fā)展^[3-4]。

2.算法描述

地形的尺寸信息和海拔信息存儲在圖片文件中，本算法采用的圖片格式為bmp格式，也可以使用其他格式的文件。文件中每個像素的值即為對應網(wǎng)格的海拔高度，即y值。使用四叉樹表示圖片對應的地形。對每一幀畫面實時計算視錐大小，視錐意外的地形區(qū)域不參與繪制。在四叉樹地形基礎上，按照物體遠近和指定三角面的數(shù)量作為LOD劃分的標準，實現(xiàn)整個地形自適應LOD表示。算法核心流程如圖1所示。

3.實驗結果與討論

（a）LEVEL=1，整個場景網(wǎng)格密度一樣（b）LEVEL=2，網(wǎng)格密度近密遠疏

當LEVEL=1時，渲染效果等同于只進行了四叉樹優(yōu)化的效果，如圖2（a）中區(qū)域A，B，C顯示;LEVEL大于等于2時，渲染同時應用了四叉樹和LOD進行畫面優(yōu)化，如圖2（b）中區(qū)域A，B，C顯示，其中區(qū)域C距離視點近，細分程度要大。

通過指標FPS可以看出，LEVEL等于1和2時，優(yōu)化效率最大。原因如下：當LEVEL=1時，CPU和GPU的算力不能快速地計算全部頂點的信息，導致FPS比LEVEL=2時低;而LEVEL等于2以后，CPU和GPU的算力已經能滿足頂點信息需要的要求了，所以提升幅度不明顯了。

4.小結

本文提出了一種基于四叉樹和LOD的地形繪制算法，提高地形模型的繪制效率和交互性，優(yōu)化程序性能，提高了用戶的使用體驗。當計算機的性能良好的情況下，本算法和四叉樹算法在性能上沒有明顯的差距;但當渲染工作量足夠大的時候，本算法可以有效降低運算量，具體幅度需要具體分析。本算法在使用上，需要根據(jù)實際情況，調試MAX_TRIANGLES、LEVEL、SCALE這三個變量，平衡性能和效果，以滿足實際需求。

參考文獻

[1] 侯紹洋，趙學勝，官亞勤.利用多分辨率半邊進行全球多分辨率DEM無縫表達[J].武漢大學學報（信息科學版），2018，43（03）：372-378.

[2] Musialski P， Wonka P， Aliaga D G， et al. A Survey of Urban Reconstruction[J]. Computer Graphics Forum， 2013， 32（6）.

[3] 蔣杰. 全球大規(guī)模虛擬地理環(huán)境構建關鍵技術研究[D].國防科學技術大學，2010.

[4] D. Luebke， M. Reddy， J. Cohen， A. Varshney， B. Watson， and R. Huebner. Level of Detail for 3D Graphics[M]. Morgan Kaufmann Publishers. 2003

基金項目：2020年吉林省大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目“基于LOD的大規(guī)模地形的實時繪制”;吉林省科技發(fā)展計劃項目（20200201176JC）