基于Android的三维地形建模和实时显示技术

高林，李洁，苏光义

(中国民航大学中欧航空工程师学院，天津 300300)

基于Android的三维地形建模和实时显示技术

高林，李洁，苏光义

(中国民航大学中欧航空工程师学院，天津 300300)

以Android智能移动设备为研究对象，通过OpenGL ES嵌入式三维图形接口实现移动端三维地形的建模和显示。针对大规模地形场景渲染时，面元数目过多导致的绘制速率低下问题，使用LOD技术进行改进。通过面向对象编程，模拟ROAM算法的数据结构，设计分割判据确定其网格生成方式，在Android平台上实现ROAM算法，有效减少面元数目。同时，对于ROAM算法生成的地形裂缝，研究产生原因并采用强制分割方法成功地将之消除。

三维地形建模；OpenGL ES；LOD技术；ROAM算法；裂缝消除

0 引言

近年来，手机、平板电脑等智能移动设备快速发展，其硬件性能、存储能力、图形绘制能力等不断提升，移动应用中三维图形交互的需求也不断增加。其中，Android设备不仅具有市场第一的占有率，而且其平台开源性可以大幅增加开发的效率和自由度[1]。三维地形作为最常见的三维场景，其在Android等智能移动设备上的建模和显示技术成为了一个新的研究方向。

对于大规模三维地形的显示技术，在PC端的研究已经趋近成熟，但是在移动端的研究依然稀少。目前，移动端三维图形显示大都使用远程绘制方式，即依靠远程计算机进行三维绘制生成图像。随着移动设备硬件性能的加强，已经能够满足本地绘制的需求，远程绘制不再是唯一选择。通过Java IO流可以将DEM地形数据从本地文件导入到程序中；基于地形数据，通过OpenGL ES接口可以实现在嵌入式移动设备上的三维地形建模。

另外，大规模地形场景绘制时，由于地形数据量庞大，面元数目的急剧增加导致了绘制速率的低下和显示实时性的降低。目前解决该问题的主要思路通过LOD（Level of Details）技术，即多细节层次网格建模技术，来减少画面中需要渲染的面元数目。不同于以往在所有区域使用相同密度网格的方式，LOD技术根据需求在不同区域绘制密度不同的网格，从而达到减少面元总数的目的[2]。ROAM（Real-time Optimally Adaptive Meshes）算法作为一种LOD技术，能够根据视点位置实时更新各区域的网格密度，具有优秀的显示实时性[3]。本文主要研究Android设备上的三维地形建模，并通过实现ROAM算法提升大规模地形的显示实时性。

1 移动端三维地形建模

图1 OpenGL ES三维建模流程

通过OpenGL ES图形接口在Android设备上实现三维地形建模的主要流程如图1所示，各步骤主要功能如下所述：

（1）三维模型描述是数据准备的阶段。模型描述的数据主要有顶点三维数据，渲染纹理数据等。地形建模所用的DEM（Digital Elevation Model，数字高程模型）数据文件可从Google Earth中，通过高程值采样提取并生成csv类型文件。使用Java IO流中的字符流可以读取csv文件中的数据，以供程序后续建模使用。纹理数据则大都以图片格式保存在应用的资源文件夹内，通过方法getResources()来调用。

模型变换过程通过顶点的坐标变换，实现三维地形的平移、旋转、缩放等操作。OpenGL ES中以列矩阵(xyz1)T来表示顶点在三维空间中的位置，以矩阵变换的方式改变坐标。其中，平移变换和缩放变换分别如式（1），（2）所示，通过左乘相应的变换矩阵改变了点的坐标值，实现三维模型的平移和缩放。

（3）视图变换，调整视图设置可以改变观察方式，从而改变模型最终显示的效果。以拍照为例，模型变换相当于被拍摄物体自身的移动、旋转等变换，而视图变换则是调整照相机的位置、朝向等设置。只有结合模型变换和视图变换，才能确定三维模型最终的显示效果。

投影变换用于确定投影类型和可视范围。投影类型有正视投影和透视投影两种。前者的可视空间为长方体，投影效果没有远近区分，适用于三视图绘制；后者可视空间为如图2所示的锥形体，又称视景体，以现实生活中投影空间为参考，投影具有近大远小的真实透视效果。OpenGL ES中以方法glFrustum（left,right,bottom,top,zNear,zFar）来定义视景体。其中 left,right,bottom,top四个值定义了近裁剪平面的大小，zNear表示近裁剪平面到观察点的距离，zFar表示远裁剪平面到观察点的距离。由这6个参数定义的6个裁剪平面在三维空间空间内形成了一个椎形体。只有当三维模型在视景体内时，经过投影变换后最后才会在屏幕上显示出来，不在视景体内的部分将不会显示到屏幕上。

（5）视口变换的目的是将投影变换后的物体显示到设备二维屏幕上相应的区域，即视口内。视口通常为矩形，在 OpenGL ES中通过 glViewport(GLint x,GLint y,GLsizei width,GLsizei height)方法来定义视口。其中（x,y）确定了视口在整个屏幕中的位置，width和height则定义了视口的宽和高。由于移动设备屏幕较小，一般设置视口填满整个屏幕，即（x,y）取（0，0），宽和高则设置为屏幕自身的宽度和高度值。

图2 视景体

如图3，采用左上角经纬度坐标（117.3121833

80 E,40.116748810 N）至右下角经纬度坐标(117.372608185 E,40.061817169 N)矩形区域内地形数据进行实验，可得三维地形建模结果。纹理渲染后效果如图4。

图3 三维地形建模结果

图4 纹理渲染效果

2 移动端ROAM算法实现

随着绘制地形面积的增大，三维建模所使用的面元数目急剧增加，导致绘制速率降低。在同样的设备性能前提下，提升绘制速率的一个方法就是减少面元数目。通过ROAM算法可以用更少的面元来描述同一个三维场景并保留地形特征，从而减少每一帧画面渲染面元所需的总时间。本节重点阐述ROAM算法的思路及在移动端实现该算法的过程。

2.1 地形块

大规模地形网格绘制时，首先将整个地形场景分割成地形块[4]，然后以各地形块为单元，进行ROAM分割和网格绘制，从而提高网格生成的效率。如图5，整个地形场景（LandScape）被分割成地形块单元(Patch)。每个Patch内又分为左右基节点，如图6，这些基节点就是ROAM算法的实际操作对象。地形场景生成时，遍历所有Patch，对其左右基节点通过ROAM算法进行分割生成地形网格。

图5 地形块

图6 左右基节点

2.2 节点分割

ROAM算法以二元三角树为数据结构，该结构以等腰直角三角形为节点，以连接三角形节点直角顶点和斜边中点为分割方式。如图7，三角形ABC为第0层的节点，连接直角顶点A和斜边BC的中点D，生成子节点ABC和ACD作为第1层的节点。如此递归分割得到细节层次更深的节点，从而生成密度更高的地形网格。

图7 二元三角树节点

同时，每个节点和其他节点的关系如图8所示。以当前节点的直角顶点为基准，斜边中垂线左右侧分别为左、右子节点，左右腰相邻的分别为左、右邻居，斜边相邻的为基邻居。此结构可以用内嵌类描述：

图8 节点位置关系

每个三角节点TriTreeNode拥有5个成员变量，分别为其左子节点LeftChild，右子节点RightChild，基邻居BaseNeighbor，左邻居LeftNeighbor和右邻居Right-Neighbor。同时这些成员亦皆为TriTreeNode类型。以该类结构进行实例化时，与每个TriTreeNode节点相关的节点皆可通过调用该对象的成员来描述和操作。节点分割判据的确定主要考虑地形粗糙度，到视点距离和整个地形的尺寸等三个因素。设阈值FrameVar为常数，当满足条件分割判据TriVar>FrameVar时，则当前节点需要继续进行下一次分割。为尽可能保留地形特征，在地形粗糙度（LocalVar）大的区域，选用密度更高的网格来描述[5]。距离观察点远的区域由于关注度减少，所需网格密度越低。地形场景越大，即地形尺寸MAP_SIZE越大，需要更多的图元才能展现地形特征。综上，分割判据TriVar可如式（3）计算。取a=2，b=1进行实验，效果如图9，可以发现ROAM算法生成的地形网格在保留局部特征的前提下，有效地减少了图元总数。实验数据显示，面元数从原来的平均每帧32768减少到平均每帧9455，减少了71.15%。

2.3 裂缝消除

对ROAM生成的地形进行颜色渲染后，地形表面会出现黑色裂缝，如图10。裂缝在细节层次（网格密度）突变处产生，即相邻节点细节层次相差超过2时，在该相邻边上就会出现裂缝。如图11，当BC左右两侧节点细节层次相差2时，OpenGLES对面元进行渲染时以三角形三个顶点相连所包围的平面为目标，即三角形面ABC，BDE和CDE分别被渲染，节点BDE，CDE和节点ABC的公共边BC处则会出现裂缝，如图12。

图9 ROAM地形网格

图10 地形裂缝

图11 裂缝产生处

图12 裂缝示意图

目前主要存在三种裂缝消除方式：（1）连接顶点A和顶点D，将节点ABC分割成ADC和ADB；（2）使用裙边算法（Skirt）产生新的三角形面元来填充BDC裂缝[6]；（3）强制分割至相邻节点细节层次相差1以内。前两种方式都将产生新的非二元三角树结构内的数据，复杂化数据结构，相比之下对数据结构没影响的强制分割方法更加适合计算处理性能有限的移动设备。

分析节点分割过程可以发现，当前节点与其基邻居存在如下两种情况时，对其分割不会产生裂缝：

（1）当前节点拥有基邻居，且与其为基邻居关系，形成菱形结构，由于ROAM算法在计算分割判据时以节点斜边的中点为准，故此二节点会被同时分割。

（2）当前节点没有基邻居，即该节点在地形边界上。

如图13为强制分割过程，13（a）中节点1的判据满足分割要求，需对其进行下一次分割时，检测到其拥有基邻居，且基邻居节点2与其并不满足互为基邻居的关系，故需对节点2也进行分割；同理，节点3和4也需被分割；而分割节点4时，它和基邻居节点5满足互为基邻居的关系，即条件1，所以同时分割节点4和节点5就能结束本次强制分割。递归返回分割的判定结果，并进行递归分割，图13(d)所示网格即强制分割结果。

图13 强制分割

强制分割后生成的地形网格如图14，网格细节层次变化保持在相邻变化小于等于1的范围内。如图15，强制分割后对地形进行颜色渲染，结果显示裂缝已被消除。

图14 强制分割ROAM网格

图15 强制分割后渲染

4 结语

三维地形显示技术作为一项三维场景绘制的基础技术，具有极大的研究和应用价值。本文针对Android平台智能移动设备，研究并实现了该平台上三维地形的建模。同时，对大规模地形的加速绘制技术进行了探讨，使用面向对象编程实现了ROAM算法，减少了地形绘制的面元数目，并用强制分割方法消除了地形裂缝。本文实验都在Android 4.2.2操作系统的AVD虚拟机上进行，并且实验结果显示效果良好，在移动端三维地形建模和实时显示技术方面具有一定参考意义。

[1]齐胜利.基于Android的移动电子海图平台研究[D].大连海事大学，2012.

[2]Jacek Zienkiewicz,Akis Tsiotsios,Andrew Davison.Monocular,Real-Time Surface Reconstruction using Dynamic Level of Detail[J].International Conference on 3D Vision,2016（4）：37-47.

[3]Dichaineau,M.ROAMing:Real-time Optimally Adapting Meshes[C].Proceedings of IEEE Visualization,1997:81-88.

[4]魏楠，江南.ROAM算法及其在地形可视化中的应用[J].计算机工程与科学，2007（2）：66-68.

[5]付慧.基于ROAM算法的动态地形可视化研究[J]，计算机仿真，2007，5：210-213.

[6]万明，梁霞，张凤鸣.一种四叉树地形渲染裂缝的改进消除算法[J]，系统仿真学报，2015.7（7）：1520-1524.

Abstract：

Takes the Android smart mobile device as the research object,realizes the 3D terrain modeling and display on mobile devices by OpenGL ES,a 3D graphics interface for embedded systems.For large-scale terrain scene rendering,the problems of low rate drawing caused by the large number of surface units are solved through the use of LOD technology.Through the object-oriented programming,simulates the data structure of ROAM algorithm,and determines its grid generation method by design of segmentation criteria.Eventually the ROAM algo⁃rithm is achieved on Android platform,effectively reduces the number of surface units.At the same time,for the terrain cracks generated by the ROAM algorithm,the cause is studied and cracks are successfully eliminated by the forced segmentation method.

Keywords：

3D Terrain Modeling;Opengl ES;LOD Technology;ROAM;Crack Elimination

3D Terrain Modeling and Real-Time Display Technology Based on Android

GAO Lin，LI Jie，SU Guang-yi
（Civil Aviation University of China,Sino-European Institute of Aviation Engineering，Tianjin 300300）

2017-04-10

2017-06-18

1007-1423（2017）18-0052-05

10.3969/j.issn.1007-1423.2017.18.013

高林（1992-），男，浙江杭州人，硕士研究生，研究方向为通航机载便携式导航设备

李洁（1992-），女，河北保定人，硕士研究生，研究方向为嵌入式系统与软件设计

苏光义（1992-），男，浙江温州人，硕士研究生，研究方向为机载电子与空管系统