APP下载

三维地形数据塔式结构模型与可视化方法研究

2016-12-28李鹤元柯希林

地理空间信息 2016年9期
关键词:边界点纹理绘制

李鹤元,陈 刚,柯希林

(1.信息工程大学 地理空间信息学院,河南 郑州 450052;2.地理信息工程国家重点实验室,陕西 西安 710054)

三维地形数据塔式结构模型与可视化方法研究

李鹤元1,2,陈 刚1,柯希林2

(1.信息工程大学 地理空间信息学院,河南 郑州 450052;2.地理信息工程国家重点实验室,陕西 西安 710054)

针对在地形绘制中三维地形数据量巨大和绘制速度慢等问题,提出了一种基于GPU加速的大区域三维地形数据的塔式结构模型及实时可视化新方法。首先构建细节层次模型来减少大区域地形实时绘制的地形数据量,然后建立DEM数据和DOM数据的金字塔式数据模型来实现大容量三维数据的实时装载和动态卸载,并采用CUDA编程实现了大区域三维地形可视化的GPU加速。

地形可视化;细节层次模型;计算机视觉

大区域三维地形数据的交互可视化中一直存在着一对矛盾,即地形数据大容量和可视化速度无延迟要求之间的矛盾。描述一个大区域地形通常需要10 G以上的数据,如果对每一块数据进行详细处理显示会是一个很大的工程,而在地形可视化过程中,视域内的地形范围只是整个地形的一部分,为提高地形绘制效率,将三维地形数据分块存储,在地形绘制时只处理视域内的部分,一直是解决矛盾的突破口。除此之外,由于各地形块距视点的远近不同,绘制时绘制分辨率也不必要求一致。因此在地形可视化过程中,根据视域的地形裁剪以及视相关的地形简化能提高地形绘制速度,同时地形绘制精度也能得到保证。

海量三维地形数据可视化算法的要求为:①便于生成和管理海量三维数据;②便于根据场景窗口查找可视的地形区域;③便于快速装载、卸载相关地形数据;④便于在实时地形绘制中快速计算地形块的相应细节层次(LOD)等级;⑤便于对地形进行交互式高精度绘制。为达到上述要求,就需对三维地形数据进行预处理。通过地形数据的金字塔式管理,从原始数据派生得到多分辨率数据,由此可生成连续LOD四叉树数据结构,从而简单地实现三维地形的快速动态绘制。

1996年,Lindstrom等首次提出了实时连续LOD地形绘制方法[1-6]。该方法基于自下向上的地形分块策略,第一次根据地形块在屏幕上的投影精度误差来确定地形块绘制时的层次等级,在地形绘制中,增加那些误差精度大于一定阈值的顶点,并通过在相邻块间采用不同的绘制等级来消除块间的地形裂缝,在相邻地形块的接边处共用相同的顶点。该算法通过预处理减少帧之间的顶点数从而实现帧之间的连贯性;通过地形的四叉树分割来自动生成地形格网。1997年,Duchaineauy等使用ROAM方法绘制地形[7-14]。该方法继承了Lindstrom算法中的一些思想,地形绘制速度更快。ROAM主要是基于三角形树结构进行地形三角形的分割或合并,这一点和Lindstrom的算法中顶点二元化处理相似,都是采用自下向上的方式进行处理。ROAM算法使用了分割队列和合并队列2个棱形队列的地形三角形网格,三角形网格根据精度误差或其他误差数值确定优先级,再进行排序。该算法不但严格控制了误差精度,而且能控制场景绘制过程中三角形的个数,从而实现场景绘制中帧之间的连贯性和连续的帧速。此外还有其他一些关于实时地形三维可视化的算法[15-19],Hoppe在地形绘制中运用连续视相关LOD控制技术[20],Rottger在1998年提出高度场连续LOD模型实时生成算法,Jonathan在2000年提出高精度LOD模型的地形绘制。但这些方法依然存在绘制大数据量高精度地形图时易出现时延较大、精度不够高等问题,且有些是相似的,如场景的视景体裁剪、LOD方法的使用和地形裂缝的消除等。针对这些问题,本文结合LOD模型、多分辨率金字塔结构模型和基于GPU的加速处理,提出了一种三维地形数据的塔式管理和实时可视化新方法。

1 金字塔结构模型

1.1 多分辨率结构数据模型

金字塔数据模型是在地形数据和影像数据预处理基础上建立的[21-23],其策略是建立DEM和DOM数据的多分辨率数据模型。最顶层设为0级,分辨率最低;级数越高,数据分辨率越高;最高级数据的分辨率与原始数据的分辨率一致,如图1。

图1 金字塔结构数据模型

假定地形水平方向的范围是(MinCol,MaxCol)、垂直方向范围是(MinRow,MaxRow),地形的根节点是M×N块,每块大小是(2n+1)×(2n+1), 通常为17×17 或33×33,相邻地形节点间有条公共边。对于DOM数据,纹理数据的大小通常强制设为2k×2k。如果当前地形层次等级是t,那么该层地形水平方向和垂直方向的地形分辨率为:

为了使地形节点大小固定,DEM和DOM数据的分辨率比率通常为1∶16或1∶32。为确保地形绘制效果,地形水平和垂直方向的分辨率比率采用同一个值。如图2所示,在金字塔结构数据模型构建时,下一级地形块的块数是上一级地形块的4倍,依次类推建立金字塔数据模型。

数据管理采用四叉树结构来进行,高一级地形节点数是低一级的4倍,如图3所示。

图4是地形四叉树结构层中的数据,根节点为0级,节点格网大小为n=2k+1。t级节点分辨率为:

图2 金字塔模型地形分层分块策略

图3 地形数据管理中的四叉树结构

其顶点位于上一级t-1顶点中心位置(图4中的白点)。

图4 金字塔模型中的四叉树结构

1.2 多层纹理压缩技术

在海量地形数据可视化时,DEM和DOM数据量很大,如果将原始数据一次性载入显示列表,数据量肯定大大超过计算机内存和性能,从而降低了地形可视化的速度,影响交互可视化效果。而且用高分辨率影像数据可视化时,原始高分辨率与视觉习惯不相适应,因为视距的不同,有不同的视觉效果。事实上,离视点近的场景看起来细节详细些,而离视点远的场景细节几乎是不体现的。因此对于纹理图像数据,LOD技术非常有用。

1976年,Clark[24]提出了LOD模型的构建方法。当地形覆盖的屏幕区域较小时,采用较粗略的模型描述要进行绘制的地形,并构建了可见面判定算法的几何层次模型来对复杂地形进行快速绘制。在不影响地形观察者的视觉效果的前提下,LOD技术通过逐次简化地形场景的表面细节来降低地形场景的复杂性,从而提高绘制算法的效率。对地形原始数据建立几个不同逐次逼近真实地形精度的几何模型,与原始地形数据相比,每个LOD等级模型均保留了一定层次的细节。在绘制时,根据不同的选择标准确定适当的层次地形LOD等级来绘制地形场景。地形场景LOD等级确定方法通常有3类:基于距离和物体尺寸标准的方法,基于偏心率、视野深度、运动速度等标准的方法和考虑保持恒定帧率的方法。本文忽略视距较远的地形细节,因此选择距离标准计算对应的分辨率。

首先对纹理数据进行分块分级,建立金字塔结构模型。根据地形区域范围和位置对纹理数据进行分块,再对每块数据进行不同分辨率的分级处理,分辨率分为256×256、128×128、64×64、32×32和16×16五 级。纹理数据块的分辨率取决于块到视点的距离,距视点越远分辨率越低;反之越高。

即使使用多层纹理,每块地形的纹理数据量约为256 KB,若绘制地形区域为60块,则地形纹理高达15 MB。而实际地形块一般都多于60块,所以在地形绘制过程中,存储、装载和可视化这么大的纹理数据的效率是很低的,往往会消耗计算机性能和内存。为很好解决这个问题,需要对纹理数据进行压缩,本文采用DXT1格式对纹理数据进行压缩。DXT是一种图片压缩格式[25],使用了由S3 公司发明的一种有损图像压缩算法,现在已为绝大多数 3D 显卡硬件所支持。DXT1格式主要适用于不具透明度的贴图或Alpha贴图,其中Alpha贴图是一个8位的灰度图片,用256 级灰度来记录图像中的透明度,定义透明、不透明和半透明区域,分别用白、黑和灰色表示。DXT1将每4×4个像素块视为一个压缩单位,压缩后占用64位,其中有2个16位的RGB颜色和16个2 位索引,格式描绘如图5所示。

图5 DXT1格式压缩示意图

图6为采用DXT1格式的多分辨率纹理数据,数据分辨率逐渐成倍减小,数据块的大小也随之减小,地形越来越模糊。

图6 DXT1格式的多分辨率纹理数据

纹理数据经过DXT1格式压缩后,存储和实时装载速度大大提高,内存消耗少,极大提高了大场景地形的绘制效率。

1.3 GPU的加速处理

近年来,GPU广泛应用于图像处理和科学计算领域,GPU的大规模并行硬件使得数以万计的线程并行成为可能。同时,采用CUDA和OpenGL图形渲染混合编程方法是可视化技术的重要应用方向,也是提高性能和编程效率的理想选择。

压缩后的纹理数据块提高了装载和存储速度,但对每块数据的处理仍然是串行的。对于大区域海量数据而言,随着纹理数据块数量级的增加,程序的延时导致了实时性差和响应慢,因此采用GPU加速技术,对每块纹理数据并行处理,提高数据处理的实时性和效率。

1.4 大区域三维地形的动态装载和绘制

首先确定处于可视场景中的地形节点,再根据地形节点到视点的距离采用不同的细节层次进行绘制。纹理数据也同样使用不同的分辨率来对地形块进行映射,如图7所示。

图7 同一地形节点在不同场景中的分辨率

计算地形节点是否处于可视场景内,首先要计算场景可视矩阵,再判断地形节点的4个角点是否在可视矩阵内。只要4个角点中有1个在可视矩阵内,则该地形节点被划分到可视场景内。

确定需要进行绘制的地形节点后,根据地形节点距视点的距离和地形的精度误差来计算地形节点的绘制等级,以实现地形快速绘制。为了适用于任意范围的地形区域,本算法利用动态装载和卸载相关地形块数据的方法优化了计算机性能和内存。当某块地形离开场景时,从内存中卸载掉该块地形节点数据;而当某块地形正从场景外进入场景时,则实时动态装载该块数据。这种优化方法使得算法中用来调度数据的内存始终只占固定的内存容量。

1.5 地形相邻节点间裂缝的消除

根据地形节点距视点距离以及自身精度误差的差异,绘制时使用的LOD等级层次也不同。当地形离视点近时,绘制的分辨率较高;反之,则采用较低的分辨率进行绘制。如图8所示,颜色越深表示分辨率越高。本文采用一种适合GPU加速的裂缝消除算法。该算法要求地形模型符合2个要求:边界点个数满足n2+1(n≥3);如果是RSG/TIN 混合结构,要求TIN 边界点与RSG边界点一致。该算法的基本思想是在低级地块的边界上等间隔插入备用点,地形场景实时绘制时,通过低等级LOD地形块中备用点来参与地形场景绘制,从而消除相邻地形块绘制时的裂缝;最大的特点是既可用于规则格网RSG,也可用于TIN,且适用于RSG/TIN 混合结构。

图8 地形可视化中多分辨率绘制

本算法中有关顶点和三角形的分类,如图9。

边界点:所有位于地形块凸壳上的点为边界点,如点E1、E2和E3。

图9 顶点及三角形分类

内部点:除边界点外所有参与地形场景构网的地形节点为内部点,如点I1、I2和I3。如果分别以E、I表示边界点集合和内部点集合,那么构网点集合Q 就等于E 和I 的并集,即Q=E∪I,且E∩I=Φ。

备用点:每条边界上两相邻边界点的中点为备用点,如点S1、S2和S3。

边界三角形:构成地形格网三角形中的3点至少有2点是边界点的地形场景三角形格网为边界三角形,如△E1E2I1和△E2E3I1。

内部三角形:构成地形格网三角形中的3点至少有2点是内部点的地形场景三角形格网为内部三角形,如△I1I2I3和△I1I3E3。

备用三角形:构成地形格网三角形中的3点至少有1点是备用点的地形场景三角形格网为备用三角形,如△E1I1S1、△E2I1S1、△E2I1S2和△E3I1S2。

边角三角形:构成地形格网三角形中的3点全为边界点的地形场景三角形格网为边角三角形,如△E4E5E6。

该算法消除相邻地形节点间的地形裂缝的步骤为:

1)备用点插入。在每条边界的任意两个边界点中点处按同样的顺序插入等间隔备用点,备用点插入后所有边界点仍然保持从左到右、从下到上、从右到左、从上到下的顺序,如图10所示。

图10 接边算法之插入备用点

2)边角三角形分割。首先判断地形块中是否存在边角三角形。若存在,则在边角三角形的斜边上强行插入图11b中的点I1,对边角三角形进行分割,分割后的三角形与原边角三角形共斜边。

图11 边角三角形分割

3)边界三角形分割。使用备用点将所有边界三角形一分为二,如图12所示,并将分割后的三角形追加到地形块结尾。

经过备用点插入和边角三角形分割后,只需判断是否接边就可实现不同分辨率地形模型接边处的裂缝消除。如图13所示,当左右两边地形LOD等级不等时,在低等级的地形LOD块使用备用点可很好地解决地形绘制接边裂缝问题。

图12 边界三角形分割

图13 经过接边处理后的地形块拼接

图14是采用本文算法实现的地形场景,可以看出,靠近视点的区域使用高级LOD地形块,远离视点的区域使用低级地块,同时在接边处使用了其边界备用点。

2 实验与分析

实验是在HP Z600 Workstation、9 GB RAM、NVIDIA GeForce GTX 750显卡计算机上,用Windows Visual C++、 OpenGL和CUDA编程环境实现的。实验设备的CPU、GPU配置分别为:CPU 8核Intel(R) Xeon(R)处理器,内存容量9 GB;GPU GeForce GTX 750,DDR5,1G显存,80.2 GB/s。

实验中,地形数据包括DEM和DOM,约为16 GB,对实验数据建立了7层金字塔结构数据模型。纹理数据经过DXT1格式压缩后,存储数据量不到700 MB,仅使用CPU处理,数据预处理时间约为30 min,而使用GPU加速后,数据预处理时间为17 828 ms(约18 s)。地形绘制中的速度约为60 fps,每帧显示三角形个数约为20 000个,地形绘制速度可满足地形实时交互式浏览的要求。

图14 地形绘制效果图

3 结 语

本文针对三维地形数据量大,难以快速绘制的问题,把地形数据划分为可视场景与非可视场景。将可视场景内部的数据动态载入内存,非可视场景的数据从内存卸载,减少了内存容量。首先,通过LOD技术将可视场景区域划分为不同细节层次,根据视距划分的不同场景确定相应的分辨率。然后,根据不同的分辨率对三维数据进行塔式结构模型表示,压缩了数据量,并充分利用了显卡的GPU加速,提高了大区域三维地形场景数据处理和快速渲染速度,较好地满足了大区域三维地形场景实时交互式浏览的要求。参考文献

[1] 游雄.基于虚拟现实技术的战场环境仿真[J].测绘学报, 2002,31(1)∶7-11

[2] Koller D,Lindstrom P,Ribarsky W,et al.Virtual GIS∶ a Real-time 3D Geographic Information System[C].IEEE Computer Society Proceedings of the 6th Conference on Visualization'95, Atlanta,1995

[3] Lindstrom P,Koller D,Hodges L F,et al.Level-of-detail Management for Real-time Rendering of Phototextured Terrain[J].GVU TR,1995(2)∶15-20

[4] Lindstrom P,Koller D,Ribarsky W,et al.An Integrated Global GIS and Visual Simulation System[J].GVU TR,2007(2)∶38-44

[5] Lindstrom P,Koller D,Ribarsky W,et al.Real-time, Continuous Level of Detail Rendering of Height Fields[C].Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 2006

[6] Lindstrom P,Pascucci V.Visualization of Large Terrains Made Easy[C].IEEE Visualization Conference,San Diego,2001

[7] Lindstrom P, Pascucci V. Terrain Simplification Simplified∶a General Framework for View-dependent Out-of-core Visualization[J].IEEE Transactions on Visualization and Computer Graphics,2002,8(3)∶239-254

[8] Asano T,Ranjan D,Roos T,et al.Space-filling Curves and Their Use in the Design of Geometric Data Structures[J]. Theoretical Computer Science,1997,181(1)∶3-15

[9] Balmelli L,Ayer S,Vetterli M.Efficient Algorithms for Embedded Rendering of Terrain Models[C].IEEE International Conference on Image Processing,Chicago,1998

[10] Balmelli L,Liebling T,Vetterli M.Computational Analysis of 4-8 Meshes with Application to Surface Simplification Using Global Error[C].Proc. of the 13th Canadian Conference on Computational Geometry (CCCG),Waterloo,2001

[11] Cignoni P, Montani C, Scopigno R. A Comparison of Mesh Simplification Algorithms[J].Computers & Graphics, 1998,22(1)∶37-54

[12] De Floriani L, Marzano P, Puppo E. Multiresolution Models for Topographic Surface Description[J].The Visual Computer,1996,12(7)∶317-345

[13] Duchaineau M,Wolinsky M,Sigeti D E,et al. Roaming Terrain∶ Teal-time Optimally Adapting Meshes[C].Proceedings of the 8th Conference on Visualization'97,AZ,1997

[14] De Floriani L, Kobbelt L, Puppo E. A Survey on Data Structures for Level-of-detail Models[M]. Springer Berlin Heidelberg∶Advances in Multiresolution for Geometric Modeling,2005

[15] Gerstner T,Pajarola R.Topology Preserving and Controlled Topology Simplifying Multiresolution Isosurface Extraction[C].Proceedings of the Conference on Visualization, Salt Lake City,2000

[16] Pajarola R. Large Scale Terrain Visualization Using the Restricted Quadtree Triangulation[C]. IEEE Visualization'98 Conference,North Carolina,1998

[17] Hwa L M, Duchaineau M A, Joy K I. Real-time Optimal Adaptation for Planetary Geometry and Texture∶ 4-8 Tile Hierarchies[J]. IEEE Transactions on Visualization and Computer Graphics,2005,11(4)∶355-368

[18] Pajarola R, Gobbetti E.Survey of Semi-regular Multiresolution Models for Interactive Terrain Rendering[J]. The Visual Computer,2007,23(8)∶583-605

[19] Levenberg J.Fast View-dependent Level-of-detail Rendering Using Cached Geometry[C]. IEEE Visualization Conference,Boston,2002

[20] Losasso F,Hoppe H. Geometry Clipmaps∶ Terrain Rendering Using Nested Regular Grids[J].ACM Transactions on Graphics (TOG),2004,23(3)∶769-776

[21] Hoppe H.Smooth View-dependent Level-of-detail Control and Its Application to Terrain Rendering[C]. IEEE Visualization'98,North Carolina,1998

[22] Pajarola R,Antonijuan M,Lario R. Quadtin∶ Quadtree Based Triangulated Irregular Networks[C].Proceedings of the Conference on Visualization'02, Boston,2002

[23] Pajarola R,Ohler T,Stucki P,et al. The Alps at Your Fingertips∶Virtual Reality and Geoinformation Systems[C]. IEEE 14th International Conference on Data Engineering,1998

[24] Clark J A.Greenland's Rapid Postglacial Emergence∶ a Result of Ice-water Gravitational Attraction[J].Geology,1976,4(5)∶310-312

[25] JIANG Yifei,HUAN Dandan. Improved Texture Compression for S3TC[C].Picture Coding Symposium (PCS),Poznan,2010

P208

B

1672-4623(2016)09-0012-05

10.3969/j.issn.1672-4623.2016.09.004

李鹤元,博士,高级工程师,主要从事三维地形仿真以及网络地理信息服务研究。

2015-06-23。

项目来源:国家科技支撑计划课题资助项目(2012BAI32B07); 国家自然科学基金青年基金资助项目(41001314)。

猜你喜欢

边界点纹理绘制
基于BM3D的复杂纹理区域图像去噪
超萌小鹿课程表
使用纹理叠加添加艺术画特效
区分平面中点集的内点、边界点、聚点、孤立点
放学后
TEXTURE ON TEXTURE质地上的纹理
基于降维数据边界点曲率的变电站设备识别
多阈值提取平面点云边界点的方法
消除凹凸纹理有妙招!
在转变中绘制新蓝图