高林，李潔，蘇光義

(中國民航大學(xué)中歐航空工程師學(xué)院，天津 300300)

基于Android的三維地形建模和實(shí)時(shí)顯示技術(shù)

高林，李潔，蘇光義

(中國民航大學(xué)中歐航空工程師學(xué)院，天津 300300)

以Android智能移動(dòng)設(shè)備為研究對(duì)象，通過OpenGL ES嵌入式三維圖形接口實(shí)現(xiàn)移動(dòng)端三維地形的建模和顯示。針對(duì)大規(guī)模地形場景渲染時(shí)，面元數(shù)目過多導(dǎo)致的繪制速率低下問題，使用LOD技術(shù)進(jìn)行改進(jìn)。通過面向?qū)ο缶幊?，模擬ROAM算法的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)分割判據(jù)確定其網(wǎng)格生成方式，在Android平臺(tái)上實(shí)現(xiàn)ROAM算法，有效減少面元數(shù)目。同時(shí)，對(duì)于ROAM算法生成的地形裂縫，研究產(chǎn)生原因并采用強(qiáng)制分割方法成功地將之消除。

三維地形建模；OpenGL ES；LOD技術(shù)；ROAM算法；裂縫消除

0 引言

近年來，手機(jī)、平板電腦等智能移動(dòng)設(shè)備快速發(fā)展，其硬件性能、存儲(chǔ)能力、圖形繪制能力等不斷提升，移動(dòng)應(yīng)用中三維圖形交互的需求也不斷增加。其中，Android設(shè)備不僅具有市場第一的占有率，而且其平臺(tái)開源性可以大幅增加開發(fā)的效率和自由度[1]。三維地形作為最常見的三維場景，其在Android等智能移動(dòng)設(shè)備上的建模和顯示技術(shù)成為了一個(gè)新的研究方向。

對(duì)于大規(guī)模三維地形的顯示技術(shù)，在PC端的研究已經(jīng)趨近成熟，但是在移動(dòng)端的研究依然稀少。目前，移動(dòng)端三維圖形顯示大都使用遠(yuǎn)程繪制方式，即依靠遠(yuǎn)程計(jì)算機(jī)進(jìn)行三維繪制生成圖像。隨著移動(dòng)設(shè)備硬件性能的加強(qiáng)，已經(jīng)能夠滿足本地繪制的需求，遠(yuǎn)程繪制不再是唯一選擇。通過Java IO流可以將DEM地形數(shù)據(jù)從本地文件導(dǎo)入到程序中；基于地形數(shù)據(jù)，通過OpenGL ES接口可以實(shí)現(xiàn)在嵌入式移動(dòng)設(shè)備上的三維地形建模。

另外，大規(guī)模地形場景繪制時(shí)，由于地形數(shù)據(jù)量龐大，面元數(shù)目的急劇增加導(dǎo)致了繪制速率的低下和顯示實(shí)時(shí)性的降低。目前解決該問題的主要思路通過LOD（Level of Details）技術(shù)，即多細(xì)節(jié)層次網(wǎng)格建模技術(shù)，來減少畫面中需要渲染的面元數(shù)目。不同于以往在所有區(qū)域使用相同密度網(wǎng)格的方式，LOD技術(shù)根據(jù)需求在不同區(qū)域繪制密度不同的網(wǎng)格，從而達(dá)到減少面元總數(shù)的目的[2]。ROAM（Real-time Optimally Adaptive Meshes）算法作為一種LOD技術(shù)，能夠根據(jù)視點(diǎn)位置實(shí)時(shí)更新各區(qū)域的網(wǎng)格密度，具有優(yōu)秀的顯示實(shí)時(shí)性[3]。本文主要研究Android設(shè)備上的三維地形建模，并通過實(shí)現(xiàn)ROAM算法提升大規(guī)模地形的顯示實(shí)時(shí)性。

1 移動(dòng)端三維地形建模

圖1 OpenGL ES三維建模流程

通過OpenGL ES圖形接口在Android設(shè)備上實(shí)現(xiàn)三維地形建模的主要流程如圖1所示，各步驟主要功能如下所述：

（1）三維模型描述是數(shù)據(jù)準(zhǔn)備的階段。模型描述的數(shù)據(jù)主要有頂點(diǎn)三維數(shù)據(jù)，渲染紋理數(shù)據(jù)等。地形建模所用的DEM（Digital Elevation Model，數(shù)字高程模型）數(shù)據(jù)文件可從Google Earth中，通過高程值采樣提取并生成csv類型文件。使用Java IO流中的字符流可以讀取csv文件中的數(shù)據(jù)，以供程序后續(xù)建模使用。紋理數(shù)據(jù)則大都以圖片格式保存在應(yīng)用的資源文件夾內(nèi)，通過方法getResources()來調(diào)用。

模型變換過程通過頂點(diǎn)的坐標(biāo)變換，實(shí)現(xiàn)三維地形的平移、旋轉(zhuǎn)、縮放等操作。OpenGL ES中以列矩陣(xyz1)T來表示頂點(diǎn)在三維空間中的位置，以矩陣變換的方式改變坐標(biāo)。其中，平移變換和縮放變換分別如式（1），（2）所示，通過左乘相應(yīng)的變換矩陣改變了點(diǎn)的坐標(biāo)值，實(shí)現(xiàn)三維模型的平移和縮放。

（3）視圖變換，調(diào)整視圖設(shè)置可以改變觀察方式，從而改變模型最終顯示的效果。以拍照為例，模型變換相當(dāng)于被拍攝物體自身的移動(dòng)、旋轉(zhuǎn)等變換，而視圖變換則是調(diào)整照相機(jī)的位置、朝向等設(shè)置。只有結(jié)合模型變換和視圖變換，才能確定三維模型最終的顯示效果。

投影變換用于確定投影類型和可視范圍。投影類型有正視投影和透視投影兩種。前者的可視空間為長方體，投影效果沒有遠(yuǎn)近區(qū)分，適用于三視圖繪制；后者可視空間為如圖2所示的錐形體，又稱視景體，以現(xiàn)實(shí)生活中投影空間為參考，投影具有近大遠(yuǎn)小的真實(shí)透視效果。OpenGL ES中以方法glFrustum（left,right,bottom,top,zNear,zFar）來定義視景體。其中 left,right,bottom,top四個(gè)值定義了近裁剪平面的大小，zNear表示近裁剪平面到觀察點(diǎn)的距離，zFar表示遠(yuǎn)裁剪平面到觀察點(diǎn)的距離。由這6個(gè)參數(shù)定義的6個(gè)裁剪平面在三維空間空間內(nèi)形成了一個(gè)椎形體。只有當(dāng)三維模型在視景體內(nèi)時(shí)，經(jīng)過投影變換后最后才會(huì)在屏幕上顯示出來，不在視景體內(nèi)的部分將不會(huì)顯示到屏幕上。

（5）視口變換的目的是將投影變換后的物體顯示到設(shè)備二維屏幕上相應(yīng)的區(qū)域，即視口內(nèi)。視口通常為矩形，在 OpenGL ES中通過 glViewport(GLint x,GLint y,GLsizei width,GLsizei height)方法來定義視口。其中（x,y）確定了視口在整個(gè)屏幕中的位置，width和height則定義了視口的寬和高。由于移動(dòng)設(shè)備屏幕較小，一般設(shè)置視口填滿整個(gè)屏幕，即（x,y）?。?，0），寬和高則設(shè)置為屏幕自身的寬度和高度值。

圖2 視景體

如圖3，采用左上角經(jīng)緯度坐標(biāo)（117.3121833

80 E,40.116748810 N）至右下角經(jīng)緯度坐標(biāo)(117.372608185 E,40.061817169 N)矩形區(qū)域內(nèi)地形數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，可得三維地形建模結(jié)果。紋理渲染后效果如圖4。

圖3 三維地形建模結(jié)果

圖4 紋理渲染效果

2 移動(dòng)端ROAM算法實(shí)現(xiàn)

隨著繪制地形面積的增大，三維建模所使用的面元數(shù)目急劇增加，導(dǎo)致繪制速率降低。在同樣的設(shè)備性能前提下，提升繪制速率的一個(gè)方法就是減少面元數(shù)目。通過ROAM算法可以用更少的面元來描述同一個(gè)三維場景并保留地形特征，從而減少每一幀畫面渲染面元所需的總時(shí)間。本節(jié)重點(diǎn)闡述ROAM算法的思路及在移動(dòng)端實(shí)現(xiàn)該算法的過程。

2.1 地形塊

大規(guī)模地形網(wǎng)格繪制時(shí)，首先將整個(gè)地形場景分割成地形塊[4]，然后以各地形塊為單元，進(jìn)行ROAM分割和網(wǎng)格繪制，從而提高網(wǎng)格生成的效率。如圖5，整個(gè)地形場景（LandScape）被分割成地形塊單元(Patch)。每個(gè)Patch內(nèi)又分為左右基節(jié)點(diǎn)，如圖6，這些基節(jié)點(diǎn)就是ROAM算法的實(shí)際操作對(duì)象。地形場景生成時(shí)，遍歷所有Patch，對(duì)其左右基節(jié)點(diǎn)通過ROAM算法進(jìn)行分割生成地形網(wǎng)格。

圖5 地形塊

圖6 左右基節(jié)點(diǎn)

2.2 節(jié)點(diǎn)分割

ROAM算法以二元三角樹為數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)以等腰直角三角形為節(jié)點(diǎn)，以連接三角形節(jié)點(diǎn)直角頂點(diǎn)和斜邊中點(diǎn)為分割方式。如圖7，三角形ABC為第0層的節(jié)點(diǎn)，連接直角頂點(diǎn)A和斜邊BC的中點(diǎn)D，生成子節(jié)點(diǎn)ABC和ACD作為第1層的節(jié)點(diǎn)。如此遞歸分割得到細(xì)節(jié)層次更深的節(jié)點(diǎn)，從而生成密度更高的地形網(wǎng)格。

圖7 二元三角樹節(jié)點(diǎn)

同時(shí)，每個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)的關(guān)系如圖8所示。以當(dāng)前節(jié)點(diǎn)的直角頂點(diǎn)為基準(zhǔn)，斜邊中垂線左右側(cè)分別為左、右子節(jié)點(diǎn)，左右腰相鄰的分別為左、右鄰居，斜邊相鄰的為基鄰居。此結(jié)構(gòu)可以用內(nèi)嵌類描述：

圖8 節(jié)點(diǎn)位置關(guān)系

每個(gè)三角節(jié)點(diǎn)TriTreeNode擁有5個(gè)成員變量，分別為其左子節(jié)點(diǎn)LeftChild，右子節(jié)點(diǎn)RightChild，基鄰居BaseNeighbor，左鄰居LeftNeighbor和右鄰居Right-Neighbor。同時(shí)這些成員亦皆為TriTreeNode類型。以該類結(jié)構(gòu)進(jìn)行實(shí)例化時(shí)，與每個(gè)TriTreeNode節(jié)點(diǎn)相關(guān)的節(jié)點(diǎn)皆可通過調(diào)用該對(duì)象的成員來描述和操作。節(jié)點(diǎn)分割判據(jù)的確定主要考慮地形粗糙度，到視點(diǎn)距離和整個(gè)地形的尺寸等三個(gè)因素。設(shè)閾值FrameVar為常數(shù)，當(dāng)滿足條件分割判據(jù)TriVar>FrameVar時(shí)，則當(dāng)前節(jié)點(diǎn)需要繼續(xù)進(jìn)行下一次分割。為盡可能保留地形特征，在地形粗糙度（LocalVar）大的區(qū)域，選用密度更高的網(wǎng)格來描述[5]。距離觀察點(diǎn)遠(yuǎn)的區(qū)域由于關(guān)注度減少，所需網(wǎng)格密度越低。地形場景越大，即地形尺寸MAP_SIZE越大，需要更多的圖元才能展現(xiàn)地形特征。綜上，分割判據(jù)TriVar可如式（3）計(jì)算。取a=2，b=1進(jìn)行實(shí)驗(yàn)，效果如圖9，可以發(fā)現(xiàn)ROAM算法生成的地形網(wǎng)格在保留局部特征的前提下，有效地減少了圖元總數(shù)。實(shí)驗(yàn)數(shù)據(jù)顯示，面元數(shù)從原來的平均每幀32768減少到平均每幀9455，減少了71.15%。

2.3 裂縫消除

對(duì)ROAM生成的地形進(jìn)行顏色渲染后，地形表面會(huì)出現(xiàn)黑色裂縫，如圖10。裂縫在細(xì)節(jié)層次（網(wǎng)格密度）突變處產(chǎn)生，即相鄰節(jié)點(diǎn)細(xì)節(jié)層次相差超過2時(shí)，在該相鄰邊上就會(huì)出現(xiàn)裂縫。如圖11，當(dāng)BC左右兩側(cè)節(jié)點(diǎn)細(xì)節(jié)層次相差2時(shí)，OpenGLES對(duì)面元進(jìn)行渲染時(shí)以三角形三個(gè)頂點(diǎn)相連所包圍的平面為目標(biāo)，即三角形面ABC，BDE和CDE分別被渲染，節(jié)點(diǎn)BDE，CDE和節(jié)點(diǎn)ABC的公共邊BC處則會(huì)出現(xiàn)裂縫，如圖12。

圖9 ROAM地形網(wǎng)格

圖10 地形裂縫

圖11 裂縫產(chǎn)生處

圖12 裂縫示意圖

目前主要存在三種裂縫消除方式：（1）連接頂點(diǎn)A和頂點(diǎn)D，將節(jié)點(diǎn)ABC分割成ADC和ADB；（2）使用裙邊算法（Skirt）產(chǎn)生新的三角形面元來填充BDC裂縫[6]；（3）強(qiáng)制分割至相鄰節(jié)點(diǎn)細(xì)節(jié)層次相差1以內(nèi)。前兩種方式都將產(chǎn)生新的非二元三角樹結(jié)構(gòu)內(nèi)的數(shù)據(jù)，復(fù)雜化數(shù)據(jù)結(jié)構(gòu)，相比之下對(duì)數(shù)據(jù)結(jié)構(gòu)沒影響的強(qiáng)制分割方法更加適合計(jì)算處理性能有限的移動(dòng)設(shè)備。

分析節(jié)點(diǎn)分割過程可以發(fā)現(xiàn)，當(dāng)前節(jié)點(diǎn)與其基鄰居存在如下兩種情況時(shí)，對(duì)其分割不會(huì)產(chǎn)生裂縫：

（1）當(dāng)前節(jié)點(diǎn)擁有基鄰居，且與其為基鄰居關(guān)系，形成菱形結(jié)構(gòu)，由于ROAM算法在計(jì)算分割判據(jù)時(shí)以節(jié)點(diǎn)斜邊的中點(diǎn)為準(zhǔn)，故此二節(jié)點(diǎn)會(huì)被同時(shí)分割。

（2）當(dāng)前節(jié)點(diǎn)沒有基鄰居，即該節(jié)點(diǎn)在地形邊界上。

如圖13為強(qiáng)制分割過程，13（a）中節(jié)點(diǎn)1的判據(jù)滿足分割要求，需對(duì)其進(jìn)行下一次分割時(shí)，檢測到其擁有基鄰居，且基鄰居節(jié)點(diǎn)2與其并不滿足互為基鄰居的關(guān)系，故需對(duì)節(jié)點(diǎn)2也進(jìn)行分割；同理，節(jié)點(diǎn)3和4也需被分割；而分割節(jié)點(diǎn)4時(shí)，它和基鄰居節(jié)點(diǎn)5滿足互為基鄰居的關(guān)系，即條件1，所以同時(shí)分割節(jié)點(diǎn)4和節(jié)點(diǎn)5就能結(jié)束本次強(qiáng)制分割。遞歸返回分割的判定結(jié)果，并進(jìn)行遞歸分割，圖13(d)所示網(wǎng)格即強(qiáng)制分割結(jié)果。

圖13 強(qiáng)制分割

強(qiáng)制分割后生成的地形網(wǎng)格如圖14，網(wǎng)格細(xì)節(jié)層次變化保持在相鄰變化小于等于1的范圍內(nèi)。如圖15，強(qiáng)制分割后對(duì)地形進(jìn)行顏色渲染，結(jié)果顯示裂縫已被消除。

圖14 強(qiáng)制分割ROAM網(wǎng)格

圖15 強(qiáng)制分割后渲染

4 結(jié)語

三維地形顯示技術(shù)作為一項(xiàng)三維場景繪制的基礎(chǔ)技術(shù)，具有極大的研究和應(yīng)用價(jià)值。本文針對(duì)Android平臺(tái)智能移動(dòng)設(shè)備，研究并實(shí)現(xiàn)了該平臺(tái)上三維地形的建模。同時(shí)，對(duì)大規(guī)模地形的加速繪制技術(shù)進(jìn)行了探討，使用面向?qū)ο缶幊虒?shí)現(xiàn)了ROAM算法，減少了地形繪制的面元數(shù)目，并用強(qiáng)制分割方法消除了地形裂縫。本文實(shí)驗(yàn)都在Android 4.2.2操作系統(tǒng)的AVD虛擬機(jī)上進(jìn)行，并且實(shí)驗(yàn)結(jié)果顯示效果良好，在移動(dòng)端三維地形建模和實(shí)時(shí)顯示技術(shù)方面具有一定參考意義。

[1]齊勝利.基于Android的移動(dòng)電子海圖平臺(tái)研究[D].大連海事大學(xué)，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算法及其在地形可視化中的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)，2007（2）：66-68.

[5]付慧.基于ROAM算法的動(dòng)態(tài)地形可視化研究[J]，計(jì)算機(jī)仿真，2007，5：210-213.

[6]萬明，梁霞，張鳳鳴.一種四叉樹地形渲染裂縫的改進(jìn)消除算法[J]，系統(tǒng)仿真學(xué)報(bào)，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-），男，浙江杭州人，碩士研究生，研究方向?yàn)橥ê綑C(jī)載便攜式導(dǎo)航設(shè)備

李潔（1992-），女，河北保定人，碩士研究生，研究方向?yàn)榍度胧较到y(tǒng)與軟件設(shè)計(jì)

蘇光義（1992-），男，浙江溫州人，碩士研究生，研究方向?yàn)闄C(jī)載電子與空管系統(tǒng)