基于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-），男，浙江溫州人，碩士研究生，研究方向為機載電子與空管系統