EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 7: 810 - 815

DOI: https://doi.org/10.3724/SP.J.1047.2015.00810

Orginal Article

Research on Spatial Objects Fast Visualization Based on GeoSOT-3D

  • LI Zhiqiang , 1 ,
  • CHENG Chengqi , 2, * ,
  • LI Shuang 1
Expand
  • 1. Institute of Remote Sensing and Geographic Information System, Peking University, Beijing 100871, China
  • 2. College of Engineering, Peking University, Beijing 100871, China
*Corresponding author: CHENG Chengqi, E-mail:

Received date: 2014-12-29

  Request revised date: 2015-05-21

  Online published: 2015-07-08

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Earth observation technology has developed rapidly nowadays, accumulating a great amount of data for studying earth system science and other global issues. But when facing the massive, multi-source and multi-resolution global data, how could it be rationally organized and managed to improve the efficiency of data analysis has become a challange. The geospatial information subdivision organization, as a new organizational idea of spatial information, is regarded as a potential solution. Among various domestic and international geospatial information subdivision organization frameworks, the GeoSOT-3D subdivision framework, proposed by the team of Professor Cheng Chengqi from Peking University, has obtained extensive close attention. Nevertheless, the spatial data at global scale are often massive and rich in content, resulting in a contradiction that the amount of data to be processed is far beyond the processing ability of the computer when expressing geospatial objects. To solve this problem, this paper combines the geospatial information subdivision model with the existing 3D rapid visualization technology, and proposes a clipping and hidden face removal strategy assisted by the octree to achieve the rapid subdivision expression of geospatial objects based on the GeoSOT-3D. Taking the expression of space electromagnetic field for example, we developed a demo system and discussed the simulation results. The simulation results demonstrate that the proposed method exhibited a better effect and to some extent resolved the issue of efficiency in the expression of spatial objects.

Key words： subdivision; GeoSOT; expression; 3D visualization; octree

Cite this article

LI Zhiqiang , CHENG Chengqi , LI Shuang . Research on Spatial Objects Fast Visualization Based on GeoSOT-3D[J]. Journal of Geo-information Science, 2015 , 17(7) : 810 -815 . DOI: 10.3724/SP.J.1047.2015.00810

1 引言

近年来,高分辩率对地观测与导航技术迅速发展,使数据获取与更新的能力不断提高,在测绘、气象、海洋、环境等领域积累了海量数据,形成了多维空间信息源[1-4]。空间数据基础设施建设日臻完善,数字地球概念深入人心,有效地集成和管理海量空间数据及相关信息,为人们认识、保护和改造自然提供支持,已成为各方关注的焦点[5]。
全球尺度的空间数据应用,对空间信息组织的数据量和尺度范围,提出了全新的要求。在各类空间信息组织框架[6]中,北京大学程承旗教授团队提出的GeoSOT-3D地球剖分框架以其全球性、层次性、多尺度性等优良特性,吸引了国内外学者的关注。然而,由于全球尺度的空间数据具有数据量巨大、内容丰富等特点,使得应用中要处理的空间数据量远远超出了当前计算机硬件的处理能力,该特点已经成为GeoSOT-3D在各领域应用的制约性因素。在以往三维表达研究中,层次细节（Level of Detail,LOD）这一思想,成为许多专家学者所采用的技术和方法,利用GPU的并行批处理计算能力,实现LOD算法是一种重要的技术途径和方向。Ulrich等提出了Chunked LOD算法[7],使用块状四叉树,对每块数据都预先生成不同细节,根据视点选择相应的地形分块导入内存,对地形进行批处理绘制,但该算法中,地形块顶点在GPU顶点缓冲中的分布离散性较大,对GPU不友好。Losasso、Hoppe 提出的几何裁剪（Geometry Clipmaps,GC）算法[8]及Asirvatham、Hoppe提出的GC改进算法[9],充分发挥GPU批处理与并行计算的优势,但LOD评价因子仅与视点的高度有关,地形的自适应性较差。Strugar在Chucked LOD算法的基础上,提出了连续距离依赖的LOD算法（CDLOD）[10],该算法基于三维空间距离实现渲染网格的LOD选择,并给出了一个实现LOD过渡的方法,缺点是LOD地形块的可视范围是固定的,无法动态调整。张兵强等提出了一种综合LOD因子的自适应GPU地形渲染算法[11],考虑了LOD因子中静态地形块误差、动态视点依赖误差和视点移动速度等多方面因素。不足之处是静态地形块误差的计算量较大,耗费时间多。由于研究背景和目的不同,前人的研究无法兼顾所有情况,故直接用于GeoSOT-3D对象表达效果不佳。

2 GeoSOT-3D剖分表达模型与八叉树索引

2.1 GeoSOT-3D剖分框架与编码

GeoSOT,即基于2n及整型一维数组全球经纬度剖分格网,是一套全球立体空间范围内二、三维统一的剖分框架,具有全球多尺度划分、无缝无叠、二进制一维整形编码等特性[12]。
GeoSOT-3D立体剖分网格由32级构成,0级网格定义为：在以经纬度为坐标的地球立体空间中,与其原点重合的512°方格,即将经纬度空间由-90°到90°与-180°到180°都扩展至-256°到256°。1级网格定义为：在0级网格基础上平均分为8份,每个1级网格大小256°;2级网格定义为：在1级网格基础上平均分为8份,每个2级网格大小128°;以此类推,至9级网格为度级网格,即1°网格。10-15级网格为分级网格、16-21级为秒级网格、22-32级为秒以下网格。分级网格根节点与9级网格（1°网格）一一对应,但网格大小从60′扩展到64′。秒级网格根节点与15级网格（1′网格）一一对应,但网格大小从60″扩展到64″。除涉及到3次扩展的剖分层级外,其他层级都严格按照八叉树划分,由此形成0-32层级的完整GeoSOT-3D剖分框架。
GeoSOT-3D编码有4种形式：十进制三维编码、二进制三维编码、二进制一维编码、八进制一维编码。4种编码形式之间完全对应、一致。编码分为：度级编码、分级编码、秒级编码及秒以下网格编码。当利用编码长度来隐含网格层级时,编码越长表明剖分级数越高,网格越细。

2.2 GeoSOT-3D剖分表达模型

在GeoSOT-3D剖分框架下,剖分单元表现为空间中的一个立方体区域,称为剖分体元,对应于剖分体元的剖分编码称为球体剖分编码。所有三维空间对象都由一个或者多个剖分体元组成,任意空间对象都具有“体”的属性。因此,可将三维空间对象划分为简单体对象与复杂体对象2种类型。简单体对象用单个剖分体元表示空间对象,记录空间对象的位置信息： EO = { V } ,其中,V代表一个剖分体元。
复杂体对象用多个相邻的剖分体元表示空间对象,可记录空间对象的位置、形状、面积、体积等空间属性。
CO = ⋂ V i （1）
GeoSOT-3D剖分表达模型,可由式（2）-（5）表示。
N 3 = ⋃ i = 0 n V i （2）
V j ⋂ V k = ∅ , j ≠ k （3）
V i ⊂ X 1 , Y 1 , Z 1 , X 2 , Y 2 , Z 2 （4）
N 3 l ⇌ N 3 l - 1 （5）
式（2）表示空间对象由n个剖分体元组成;式（3）表示任意2个不同的剖分体元交集为空;式（4）表示任何一个剖分体元对应一定的立体空间区域;式（5）表示相邻层剖分体元可通过聚合和拆分互相转换。三维空间对象的剖分建模如图1所示。
Fig. 1 The subdivision modeling of 3D spatial object

图1 三维空间对象的剖分建模

2.3 基于八叉树的GeoSOT-3D空间索引

全球尺度应用最显著的特点是数据量大,要实现海量数据三维场景的组织和表达,建立高效的空间索引是必须解决的问题之一。在各种三维空间索引方法中,八叉树和R树是应用最多的方法[13]。考虑GeoSOT-3D的特点,选用八叉树作为GeoSOT-3D空间索引。
八叉树将空间递归地分成8个子树,本质是四叉树向三维的扩展[14]。所有空间对象限制在范围[0,0,0,2N,2N,2N]内,坐标单位与相应GeoSOT-3D剖分体元大小一致,如一个单位可以代表1″,2″,4″,8″,16″,32″,1′,2′,4′,8′,16′,32′,1°,2°,4°,8°,16°,32°,64°,128°等。
索引的建立需考虑如下问题[15]：（1）划分的原则,本文规定阈值K（空间对象的个数）,当且仅当某子树中空间对象数多于K时,对该子树做进一步划分;（2）分辨率的确定,这里根据对象表达精度指定最小剖分层级,规定一个不再需要分割的剖分体元大小来表示。
八叉树结点与特定剖分体元对应,数学描述为（L,B,H,I）。I表示该剖分体元的层级,决定了剖分体元的粒度。（L,B,H）为剖分体元的二进制三维编码（L为经向编码,B为纬向编码,H为高程编码）,唯一表示剖分体元的具体位置和大小。
设第(I-1)层上的结点表示为NODE(I-1),则每个NODE(I-1)最多有8个子结点,分别编号为0,1,2,3,4,5,6,7。若NODE(I-1)的索引坐标为(L0, B0, H0)（单位为2(n-I+1)）,则其子结点的位置分别为：（单位为2(n-I)）(2L0, 2B0, 2H0),(2L0+1, 2B0, 2H0),(2L0+1, 2B0+1, 2H0),(2L0, 2B0+1, 2H0),(2L0, 2B0, 2H0+1),(2L0+1, 2B0, 2H0+1),(2L0+1, 2B0+1, 2H0+1),(2L0, 2B0+1, 2H0+1)。
图2中,P0-P7为指向孩子结点的指针,若结点为叶结点,则P0-P7为空指针。M为结点包含对象数量,P为该剖分区域中对象链表的指针,若结点为中间结点,P可为空。对象链表中每一个结点与一具体的空间对象相对应,包含对象的简要信息,（如指向该对象存储位置的指针、指向对象链表中下一个结点的指针等）。
Fig. 2 The node structure of octree

图2 八叉树结点示意

3 GeoSOT-3D空间对象快速表达策略

3.1 GeoSOT-3D空间对象裁剪策略

视景体由6个面组成,是一个封闭的锥形结构。处在视景体之外的多边形不可见,直接剔除;若多边形部分可见,可直接渲染,或将其切割后渲染视景体内的部分[16]。
如不采用其他技术,对场景中每一个空间对象均需通过其6个面进行可见性测试,其时间复杂度为 O ( n ) 。借助八叉树空间索引,将场景中的剖分体元组织起来,配合视景体裁剪。当空间被分割,剖分体元被组织到八叉树结构中,可从根节点开始进行视景体裁剪测试,若该节点测试失败,即直接忽略其子孙节点的测试,即可将时间复杂度减少到 O ( logn ) 。
可直接利用八叉树结点进行检测,但更简单的方式是利用其外包球体。测试中,将球体看做一个点和半径,只要检查该点到平面的距离是否大于等于半径即可。这里点为剖分体元中心点坐标,半径为其对角线长的一半。如果6个面同时大于等于半径,说明这个球位于视景体内。在比较距离时采用负的半径,也就是说,如果函数返回值为false,证明这个球体完全位于视景体之外;如果返回的是正值,则说明这个球体全部或者部分处于视景体之内。

3.2 GeoSOT-3D空间对象消隐策略

消隐的基本思路为：（1）将剖分体元转换到相应的线性八叉树结点;（2）通过该节点所在体元的剖分编码,确定其父子节点和相邻结点[17],建立线性八叉树结构;（3）通过编码代数运算[18]确定八叉子树相应于特定观察方向的先后顺序,按照先后顺序建立深度优先顺序表,然后递归遍历八叉树,从而剔除不可见结点,同时绘制可见结点。
可见性测试的实现,按照剖分编码建立八叉树结构后对其进行处理,在特定观察方向,部分体元可见,部分不可见。若该子体元有一个面可见,称为该体元前面的面,而该方向下不可见的面相应的称为后面的面;对于特定的观察者而言,该体元前面的面是可见的,而其后面的子体元或者兄弟体元均被其遮挡而不可见。
从图3所示方向观察八叉树,根据前述规则0、1、2、3为前面的面,4、5、6、7为后面的面。按照先后顺序遍历,则后面的面将被剔除,即0、1、2、3代表的体元将在4、5、6、7代表的体元被访问之前访问;同样,0、1、2、3的子体元必然在4、5、6、7的子体元被访问之前访问,依此类推。
Fig. 3 Observe the octree from a particular direction

图3 从特定方向观察八叉树

按照前述方式遍历八叉树,并将可见部分映射到对应四叉树,然后只需显示该四叉树即可（图4）。
Fig. 4 Map the octree to the quadtree

图4 将八叉树映射到四叉树

空间八叉树向相应平面四叉树转换的具体算法流程如图5所示。
Fig. 5 The algorithm of transforming octree to the corresponding quadtree

图5 空间八叉树向相应平面四叉树转换算法流程

4 空间对象快速可视化实验与分析

4.1 应用实例

在GIS中,空间场的概念往往通过离散的数据形式表达,空间电磁场数据是离散化空间场数据的一种形式。空间电磁场三维表达利用普通微机模拟近地面空间中电磁场的分布,为低空飞行器的制导和控制提供帮助[19]。其主要解决3个方面问题：（1）空间曲面重构的数据生成和精炼;（2）三维可视化的映射;（3）映射结果的绘制和互动显示[20]。为了将空间电磁场数据进行可视化表达和操作,需将场数据转化为特定的对象或在特定框架上进行显示。GeoSOT-3D剖分框架为三维空间场数据的表达,提供了一个新的解决思路。通过使用GeoSO-3D剖分框架作为三维场数据的表达框架,本文以空间信息剖分表达模型,实现了三维空间场数据的快速建模与可视化。图6是据此对空间电磁场可视化表达的一个原型系统。
Fig. 6 The visualization expression of space electromagnetic field

图6 空间电磁场可视化表达

4.2 实验结果分析

上述原型系统中,对加速算法的效果进行了分析。实验中模拟了不同数据量的空间电磁场数据,电磁场中剖分体元的数量从100-1000万,分别记录采用文中加速策略前后的可视化时间开销（由于每次拖动具有随机性,实验中采用10次随机拖动开销时间的平均值作为其时间开销）。
图7中虚线和实线分别为加速前和加速后时间消耗随体元数量的变化,短竖线表示10次测试时间消耗的标准差。结果表明：（1）采用加速策略后,效率提升较为明显,大约在4-10倍之间;（2）随着体元数量的增加,效率提升的程度更大。在体元数量较少时,时间消耗差别也较小,这是因为此时位于视场内或未被遮挡的体元占比较高;在体元数量较大时,时间消耗差别也较大,这是因有大量体元位于视场之外或被其他体元遮挡,视场内可见体元占比极小。随着体元数量的增加,本文所述加速策略增加的时间仅为判断可视性耗费的时间。由于判断是从根节点自上而下判断,一旦父节点不在视景体内或者被遮挡,就无须进一步判断子节点,因而总的时间开销并不会显著增加。（3）加速前后,对一定数量的体元,耗费时间的标准差很小,时间消耗比较稳定。
Fig. 7 The comparison of time before and after acceleration

图7 加速前后耗费时间比较

实际上,由于全球尺度的空间数据应用,经常需对大数据量三维空间对象进行组织和管理;但在单次可视化表达时,屏幕中需显示的空间对象仅为场景中的一小部分。采用本文加速策略,在GeoSOT-3D剖分框架下,对空间对象进行剖分化表达,既满足了大数据场景下空间信息剖分组织与表达的需要,也避免了表达中不必要的时间开销、提升了系统效率。

5 结语

本文面向大数据量空间对象快速表达的需求,在GeoSOT-3D立体剖分框架下,基于GeoSOT-3D剖分表达模型与八叉树空间索引,提出了GeoSOT-3D空间对象快速剖分表达的策略,并以空间电磁场表达为例验证了该方法的有效性,对GeoSOT-3D空间对象快速剖分表达做了初步探索。今后,对算法还需进一步地改进和完善,拓展GeoSOT-3D剖分表达模型,在测绘、气象、海洋等更多领域的应用。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
陈述彭. 遥感地学分析的时空维[J].遥感学报,1997,1(3):161-171.

[2]
李德仁. 论RS、GPS与GIS集成的定义、理论与关键技术[J].遥感学报,1997,1(1):64-68.

[3]
李德仁,邵振峰.空间信息多级网格及其功能[J].地理空间信息,2005,3(4):1-5.

[4]
Wright D J, Goodchild M F.Data from the deep: Implications for the GIS community[J]. International Journal of Geographical Information Science, 1997,11(6):523-528.

[5]
Gore A.The digital earth: Understanding our planet in the 21th century[A]. The Lecture Note on the Science Center of California[M]. 1998.

[6]
程承旗,任伏虎,濮国梁,等.空间信息剖分组织导论[M].北京:科学出版社,2012.

[7]
Ulrich T.Rendering massive terrains using chunked level of detail control[C]. Computer Graphics Proceedings Annual Conference Series, ACM, 2002.

[8]
Losasso F, Hoppe H.Geometry clipmaps: Terrain rendering using nested regular grids[J], ACM Transactions on Graphics, 2004,23(3):769-776.

[9]
Asirvatham A, Hoppe H.Terrain rendering using GPU-based geometry clipmaps, GPU gems 2[M]. Boston, MA: Addison Wesley, 2005:27-46.

[10]
Strugar F.Continuous distance-dependent level of detail for rendering heightmaps (CDLOD)[J]. Journal of Graphics GPU and Game Tools, 2009,14(4):57-74.

[11]
张兵强,张立民,艾祖亮,等.基于综合LOD因子的自适应GPU地形渲染[J].计算机工程. 2012,38(12):201-204.

[12]
郭辉. 地球空间立体剖分格网研究[D].北京:北京大学,2012.

[13]
李绍俊,周芹,王尔琪.SuperMap高性能海量空间数据管理策略[A].中国地理信息系统协会,2009中国地理信息产业论坛暨第二届教育论坛就业洽谈会论文集[C].中国地理信息系统协会,2009:11.

[14]
张宇. 复杂动态三维场景的管理与方法[D].天津:中国民航大学,2008.

[15]
惠文华,郭新成.3维GIS中的八叉树空间索引研究[J].测绘通报,2003(1):25-27.

[16]
黄翔. 大规模复杂场景可见性判断及剔除技术研究与实现[D].成都:电子科技大学,2010.

[17]
金安. 地球空间剖分编码代数模型及应用初探[D].北京:北京大学,2013.

[18]
周明亚. GeoSOT-3D三维空间编码代数研究[D].北京:北京大学,2014.

[19]
辛建华. 空间电磁场三维可视化技术研究[D].武汉:华中科技大学,2005.

[20]
肖何,何明耘,白忠建,等.基于VTK的电磁场三维可视化研究及实现[J].计算机应用,2007(11):2773-2775.

Options
Outlines

/

〈 〉