基于四叉树和LOD的地形模型绘制

郝萌 余天豪 杨阳 易辉平 付浩海

摘要：为了提高地形场景的高效渲染表示，需要在保证地形精度的前提下对其进行模型化简，即根据实际需要构建多分辨率地形模型。本文通过对基于四叉树的规则地形场景自适应LOD表示进行了研究，提出了一种基于四叉树和LOD的地形绘制算法。实验结果表明，当渲染场景很大的时候，本算法可以有效降低运算量提高地形模型的绘制效率和交互性，提高用户的使用体验。

关键词：四叉树; LOD; 地形绘制

1.简介

随着空间测绘技术的发展，越来越多的大规模地形数据获取变的可能。很多应用领域也越来越多地使用地形数据实现地形的三维可视化，如“数字地球”、全球环境变化监测、灾害的预报预警、资源可持续开发、大型工程设计、国防安全乃至战争等^[1]。另外，在3D游戏、虚拟现实和影视娱乐领域有时也需要渲染呈现室外三维地形模型，以实现场景的仿真和虚拟漫游^[2]。

由于三维地形模型精度越来越高，尺寸越来越大，导致了在实际应用中由于计算机存储容量、处理速度、绘制速度和传输效率的限制，无法有效实时实现如此大规模数据的高分辨率渲染绘制，从而导致不能满足应用需求。另外，在很多应用场合，高分辨率模型并不总是需要的，甚至在有些大场景应用中，全部使用高分辨率模型是完全没有必要的。因此，人们希望在模型的逼真程度和模型需要处理的计算代价之间有一个合适的折中。为了提高地形场景的高效渲染表示，需要在保证地形精度的前提下对其进行模型化简，即根据实际需要构建多分辨率地形模型，也称细节层次模型（Level of Detail， LOD）。本文通过对基于四叉树的规则地形场景自适应LOD表示进行了研究，提出了一种基于四叉树和LOD的地形绘制算法，提高地形模型的绘制效率和交互性，提高了用户的使用体验，更好地驱动上述各个领域的发展^[3-4]。

2.算法描述

地形的尺寸信息和海拔信息存儲在图片文件中，本算法采用的图片格式为bmp格式，也可以使用其他格式的文件。文件中每个像素的值即为对应网格的海拔高度，即y值。使用四叉树表示图片对应的地形。对每一帧画面实时计算视锥大小，视锥意外的地形区域不参与绘制。在四叉树地形基础上，按照物体远近和指定三角面的数量作为LOD划分的标准，实现整个地形自适应LOD表示。算法核心流程如图1所示。

3.实验结果与讨论

（a）LEVEL=1，整个场景网格密度一样（b）LEVEL=2，网格密度近密远疏

当LEVEL=1时，渲染效果等同于只进行了四叉树优化的效果，如图2（a）中区域A，B，C显示;LEVEL大于等于2时，渲染同时应用了四叉树和LOD进行画面优化，如图2（b）中区域A，B，C显示，其中区域C距离视点近，细分程度要大。

通过指标FPS可以看出，LEVEL等于1和2时，优化效率最大。原因如下：当LEVEL=1时，CPU和GPU的算力不能快速地计算全部顶点的信息，导致FPS比LEVEL=2时低;而LEVEL等于2以后，CPU和GPU的算力已经能满足顶点信息需要的要求了，所以提升幅度不明显了。

4.小结

本文提出了一种基于四叉树和LOD的地形绘制算法，提高地形模型的绘制效率和交互性，优化程序性能，提高了用户的使用体验。当计算机的性能良好的情况下，本算法和四叉树算法在性能上没有明显的差距;但当渲染工作量足够大的时候，本算法可以有效降低运算量，具体幅度需要具体分析。本算法在使用上，需要根据实际情况，调试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] 蒋杰. 全球大规模虚拟地理环境构建关键技术研究[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年吉林省大学生创新创业训练计划项目“基于LOD的大规模地形的实时绘制”;吉林省科技发展计划项目（20200201176JC）