基于海量存储的三维地理信息系统应用与研究

宋 娟，张 宏

(哈尔滨理工大学 计算机科学与技术学院，黑龙江 哈尔滨 150080)

0 引 言

近年来，GIS软件的3D功能不断加强。国外3DGIS软件典型代表包括ESRI公司的ArcView的3D Analyst和GEONOVA公司的DILAS。前者支持多维矢量转换和全球多分辨率数据的3D无缝可视化，后者支持LOD的3D建模、关系数据库存储与管理。由于显存和系统内存容量有限，实际应用中大规模地形数据采取最近最少利用(least recent use,LRU)原则的分页方式。针对大规模地形与纹理数据动态可视化的瓶颈，文中提出了多重纹理映射的大规模地形绘制方法，实现了规则网格区域分割的分层(LOD)分块和四队列分页数据库调度、基于视域的LRU算法内存释放、多线程并行处理的场景优化策略。

1 四叉树结构的LOD瓦片组织算法

海量地形3D可视化，采用高精度的DEM作为基础数据，往往能达到几百万个三角形面，渲染每一帧不可能一次性显示，系统帧率无法达到实时渲染的要求。为解决大规模数据和系统显示速率的瓶颈，对海量地形和纹理数据采用基于四叉树结构的LOD简化[1-3]，使纹理映射高效集成到地形3D可视化中，遍历简单，减少选中地形子块的时间。

1.1 四叉树分层分块的LOD算法

该系统预处理方法采用地形和纹理多分辨率建模，构建金字塔模型[4]；按照四叉树算法构建LOD地形和纹理树[5]；对纹理片与地形片进行有效压缩；创建外存的金字塔模型数据库。多分辨率金字塔用网格表示统一区域，相邻层精度为1∶4。按正常的视觉现象，透视投影规律：视点距地面较远时，绘制较少的三角形；较近时，绘制较多的三角形。采用四叉树算法将原始地形划分为多网格模型，再分别进行递归分割，直到最后一级分块为最高分辨率。

1.1.1 分块四叉树

采用等间隔划分方法对大规模数据金字塔模型进行分层分块处理，根据由上而下的方法进行简化。以地形图为基础，进一步进行规则格网划分。例如一幅1∶2 000图幅的大小为1 000×800，根据需要把部分单图幅按2×2等分，即500×400，部分按照4×4等分，即250×200。以左上角为原点，四叉树场景结构划分如图1所示。

图1 四叉树结构划分

模型每节点有两个LOD级别：本身所在的粗糙网格模型级别和四等分后的子块级别。分层分块策略，一次读写访问一节点，且动态调度中只访问需要的节点。很大程度上缩短了数据访问时间又能表示多分辨率数据；与四叉树结构相结合，具备了快速数据索引的功能。

四叉树层与瓦片的层对应，节点编号是层号和网格坐标，拓扑关系如图2所示。上下层父子关系、同一层邻接关系。邻接包括角邻接、边邻接，上下层包括向上继承、向下分解。

图2 瓦片拓扑关系和网格坐标系

1.1.2 块结构与LOD建模编程实现

采用hash map的数据结构，索引作为键，指针内容作为值。采用块结构保存，如下：

struct Chunk

{

int chunkIndex;//块索引

int swIndex,seIndex,neIndex,nwIndex;//4个子节点索引

int lod_level;//节点层

int xIndex,yIndex;//节点块所在层的位置

int min_h,max_h;//块的最小和最大高程

int mesh_pos;//三角网数据位置

}

利用递归思想实现四叉树LOD模型建立的过程如下：

void UpdateQuadTr(int nXCenter,int nZCenter,int nSize,int lod_level,int xIndex,int yIndex)

{

……

//判断地形子节点是否需要分割，若是，则执行以下代码

m_bQuadMat [chunkIndex][nXCenter+ nZCenter* m_nMapSize]=true;

UpdateQuadTr(nXCenter-nSize/2,nZCenter-nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割西南节点

UpdateQuadTr(nXCenter+nSize/2,nZCenter-nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割东南节点

UpdateQuadTr(nXCenter+nSize/2,nZCenter+nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割东北节点

UpdateQuadTr(nXCenter-nSize/2,nZCenter+nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割西北节点

}

1.2 地形数据库管理策略

在纹理叠加到地形的过程中，根据地形和纹理数据的大小，根据不同层不同块分辨率大小及粗糙程度，对纹理和地形不断进行LOD处理、计算并叠加。不同层由不同分辨率块与纹理片组成。把同时打包纹理的地形块保存为三维模型写入磁盘，表示多段数据块的组合体，以常用的“.ive”格式，把场景树保存为二进制文件，按不同层次数据块存储。

每数据层有一特定的标识名。命名方式如下：

FILENAME=地名+数据类型+数据层+行文件夹+数据文件

地块模型命名为name _root/subtile(数据类型)_L(层)_r(行号)_c(列号).ive，如beijing_subtile_L3_X0_Y1.ive。由于系统中每个文件夹容纳的文件数量有限，通过对层做分级，可避免文件夹文件过多。分级后，在外存中，3D地形纹理库存储管理图如图3所示。

图3 地形纹理数据库存储管理图

构建3D地形库，有效组织特定区域相关的数据[6]。通过地理坐标关联视域范围的数据，统一分配空间位置索引，快速调度3D库中的地形纹理数据，提高纹理地形节点的访问效率和场景裁剪效率，达到整个大规模地形的无缝渲染漫游。

2 动态调度策略算法

2.1 动态调度内存释放方法

三维场景实时浏览时，根据视点的位置，计算视域内块的索引，根据空间索引快速计算与上一步建立的四叉树各块中心点的距离，并根据事先指定的空间阈值判断是否需要加载或卸载数据，并根据视点的变化，不断调整内存中模型的细节层次(LOD)级别。

2.1.1 基于视域的LRU算法

LRU页面置换算法在管理内存时移出短时间内不用的数据块，提高了空间利用率。采取虚拟页存储管理，将所需空间划分为多个页面，内存中存放当前所需页面，其余页面放入外存。基于视点的加载过程如图4所示。

图4 基于视点的数据加载卸载

文中在LRU算法[7]的基础上，采用基于可视范围的数据内存释放算法，内存达到上限时，计算下一帧视域外的地形块，根据优先级高低将地形数据从内存缓冲区卸载。

2.1.2 动态调度实现

大规模地形3D场景浏览，有效采用数据库分页技术。分页调度划分空间页面，页面为地形基本调度单位，场景浏览时动态加载。整个地形按照四叉树构建原则进行划分，自顶而下、逐级建立各级R+树空间索引。空间索引方法是为了加速场景遍历，最大限度地缩短数据加载与卸载的响应时间。

根据LOD技术，利用视角高度与瓦片尺寸的比，判定当前显示的瓦片是否需要进一步分解。为了利用GPU图形处理能力，对每一地形瓦片，采用Chunlod网格(Mesh)模型算法，利用后台线程加载网格数据，GPU对其进行批处理运算，调整地形几何网格块的LOD层。

地形动态调度和可视化流程如图5所示。

图5 地形数据动态调度和可视化流程

3D场景漫游中，计算和渲染视域内的网格数据[8-10]，在很大程度上降低了运行时间复杂度，高效地实现了大规模地形数据的构建与绘制。

2.2 四队列多线程调度机制

通过上述调度策略，基本实现了大规模地形3D场景的实时浏览与交互。为进一步提高场景渲染效率，采用缓存区四队列机制、多线程加载、区域索引的场景裁切和纹理共享。

2.2.1 缓冲区机制

缓冲区包括内存和外存缓存。内存缓存中，已加载的数据直接用于场景绘制，实现高速缓存。外存缓存用于预存储数据。高速缓存大小设有上限，控制瓦片数。内外存置换采用所述的LRU算法。漫游常在部分场景附近进行，刚渲染的数据不应立即卸载。当后台线程需要获得渲染数据时，先在缓冲区中查找，如未找到则在外存中继续搜索。

2.2.2 四队列调度

数据动态调度机制[11-12]：显示当前可视范围时，预判断下一步可能载入的数据；判断在最近时间内不可能出现在可视范围内的数据；正确地进行数据加载、卸载、预编译和合并处理。保证场景浏览的稳定性和畅通性。数据调度流程如图6所示。

2.2.3 多线程处理

每一层单独设置线程负责不同LOD数据的加载卸载，可提高大规模场景反复加载卸载的性能。原理如下：

图6 数据调度处理流程

主线程：地形数据获取，LOD简化，视域剔除，实现实时绘制和渲染。

数据预调度线程：根据当前视点计算可见域和预可见域，若需要的地形数据块未在内存中,载入队列加入地形快索引，从外存库动态读取地形块，且剔除不可见节点以避免资源浪费，同时进行预可见数据调度。

事件处理线程：接收事件，计算相机参数，设置相机视图矩阵、漫游器、视口等。

3 3DGIS平台应用

地形/影像三维模型处理工具，实现多重纹理映射地形构建金字塔模型，按层在本地存放组织，实现多重纹理映射。为减小渲染负担，将多个原始影像分别预处理成不同分辨率纹理，使用OSG中Mipmap纹理映射技术[13-15]。2D纹理宽度高度是2的幂次方，单位为纹素(texel)。一般的，较小纹理图像分辨率是下一层4个纹理片(单元)的平均值。

如图7所示，纹理使用多幅分辨率不同的遥感影像(10 m分辨率的普通遥感影像、1 m分辨率的城区高分辨率遥感影像)叠加拼接而成。场景中明显地展现了不同分辨率纹理的效果，很好地实现了多幅遥感影像的无缝拼接，可在尽量减少大规模数据且保证较高的加载渲染效率的条件下，使场景研究主题更突出。

图7 三维地理信息系统

4 结束语

针对Mipmap纹理的大规模三维地形可视化技术进行了研究，并应用于3DGIS平台。基于四叉树分层分块的LOD算法，建立多分辨率金字塔模型并进行有效的组织管理；引入四叉树空间索引的动态调度机制，对场景中地形数据进行纹理映射，并进行动态调度可视化；通过场景裁剪和纹理共享，实现地形场景的快速优化。加快了存取速度，降低了裁剪计算的复杂度，实现了高效渲染。该课题开发的3DGIS平台为一个基础应用架构，并未充分利用2D矢量数据的拓扑关系，网络分析、邻域分析、缓冲区分析等空间分析应用功能需进一步完善。

参考文献:

[1] 岳利群,夏 青,柳佳佳,等.全球海量地形数据组织管理方法的研究[J].测绘科学,2009,34(3):121-123.

[2] 戴晨光,张永生,邓雪清.一种用于实时可视化的海量地形数据组织与管理方法[J].系统仿真学报,2005,17(2):406-409.

[3] 王璐锦,唐泽圣,唐 龙.基于三角形二叉树的地表模型动态简化算法[J].清华大学学报:自然科学版,2002,42(1):92-95.

[4] 张恒国,王合龙,吴清香.基于ROAM算法的数字地面模型研究与实现[J].信息技术,2008,32(1):95-97.

[5] 杜 莹,武玉国,王晓明,等.全球多分辨率虚拟地形环境的金字塔模型研究[J].系统仿真学报,2006,18(4):955-958.

[6] MINOUX C.Enabling virtual-globe browsing on memory-constrained platforms visualization and exploration of geospatial data[R].[s.l.]:[s.n.],2007.

[7] SUN M,LYU G L,LEI C.Large-scale vector data displaying for interactive manipulation in 3D landscape map[R].[s.l.]:[s.n.],2008.

[8] BLOW J.Terrain rendering at high levels of detail[C]//Game developers conference.[s.l.]:[s.n.],2000:119-124.

[9] DAI C G,ZHANG Y S,YANG J Y.Rendering 3D vector data using the theory of stencil shadow volume[R].[s.l.]:[s.n.],2008.

[10] 申闫春,王 锐,翟春丽.海量地形的GIS特征数据实时渲染算法研究[J].计算机仿真,2011,28(10):223-227.

[11] 马柳青,宋关福,郭 会,等.一种海量地形影像数据的快速漫游算法[J].地球信息科学学报,2009,11(5):604-609.

[12] 宋 敏,申闫春.基于空间数据库VRGIS的研究与应用[J].测绘与空间地理信息,2012,35(8):47-52.

[13] BHATFACHARJEE S,PATIDAR S,NARAYANAN P J.Real-time rendering and manipulation of large terrains[C]//Proceedings of 6th Indian conference on computer vision,graphics an image processing.Washington DC,USA:IEEE Computer Society,2008:551-559.

[14] 黄超超,凌永顺,吕相银.地形纹理映射方法研究[J].计算机仿真,2005,22(1):209-212.

[15] 姜翰青,王博胜,章国锋,等.面向复杂三维场景的高质量纹理映射[J].计算机学报,2015,38(12):2349-2360.