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

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

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

關(guān)鍵詞：四叉樹; LOD; 地形繪制

1.簡介

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

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

2.算法描述

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

3.實驗結(jié)果與討論

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

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

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

4.小結(jié)

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

參考文獻

[1] 侯紹洋，趙學(xué)勝，官亞勤.利用多分辨率半邊進行全球多分辨率DEM無縫表達[J].武漢大學(xué)學(xué)報（信息科學(xué)版），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)境構(gòu)建關(guān)鍵技術(shù)研究[D].國防科學(xué)技術(shù)大學(xué)，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年吉林省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目“基于LOD的大規(guī)模地形的實時繪制”;吉林省科技發(fā)展計劃項目（20200201176JC）