Orginal Article

Organization and Management of Multi-scale 3D Buildings for Generalization

  • GE Lei , 1, 2, * ,
  • LI Jiansheng 1 ,
  • WANG Junya 1
Expand
  • 1. Information Engineering University, Zhengzhou 450000, China
  • 2. State Key Laboratory of Geo-information Engineering, Xi’an 710054, China
*Corresponding author: GE Lei, E-mail:

Received date: 2014-12-02

  Request revised date: 2015-01-07

  Online published: 2015-08-05

Copyright

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

Abstract

With the rapid development of geographical information acquisitions methods, 3D city models are widely used now. Level of detail (LOD) is used to improve the performance of three-dimensional (3D) visualization. Management of multi-scale building data is important in 3D building generalization, and many scholars have studied the indexing model of multi-scale spatial data for 2D map. In order to satisfy the demands of massive spatial data in 3D city modeling, a new spatial indexing model named as GAMR tree (Generalization Area Multi-representation R Tree) is proposed to deal with the multi-scale model of 3D building. Based on the characteristics of 3D building generalization, impact factors for constructing the 3D building generalization areas are analyzed in this paper. Next, the generalization areas are divided into four types which are denoted as big city, city, town and village. As a result, different generalization methods are adopted for the generalization of different areas. In this research, GAMR tree is defined based on the structure of R-Tree while assigned with different node types. Two indexing trees, which are named respectively as the generalization R tree and the child tree of generalization area, are included in the new indexing model. The leaf node of the child tree is consisted of two items, one is the MBR that representing the building ground area, and the other is the corresponding 3D building model for that area. While the branch node is consist of a MBR that accounts for the total area of its child nodes, and pointers that connect to its child nodes. The children trees are generated by a bottom-up method, and the height of a tree is determined by the threshold calculated in generalization. Multi-scale querying method of GAMR tree is furthermore proposed in this paper, and the steps of a rectangle querying instance are presented. Considering the variations of projected length caused by different sight directions, the corresponding LODs of building models that organized by GAMR tree is well determined and chosen to be displayed on the screen, so that the projection of building features can be recognized by users. Generally, the experiment has proved that this spatial indexing tree works well in 3D building generalization and multi-scale representation.

Cite this article

GE Lei , LI Jiansheng , WANG Junya . Organization and Management of Multi-scale 3D Buildings for Generalization[J]. Journal of Geo-information Science, 2015 , 17(8) : 889 -894 . DOI: 10.3724/SP.J.1047.2015.00889

1 引言

建筑是三维城市模型的重要组成部分,其多尺度模型的获取与组织是实现三维城市多尺度表达的基础。通过自动综合的方式能快速获取建筑多尺度模型,同时能较好地保持建筑几何和语义信息的一致性。目前,国内外对于建筑多尺度三维模型自动综合方法的研究很多[1-10],而对于如何解决自动综合中建筑多尺度模型的组织和管理问题的研究不足,难以满足应用的实际需求。
对于二维空间数据综合中多尺度模型的组织和管理问题的研究中,较有代表性的包括:针对R树中的非平衡问题,Chan以Douglas-Peucker算法和RP-file思想为基础,提出了一种支持简化和选取操作的Multi-scale Hilbert R-tree(Ms R树)索引方法[11];为充分描述空间数据随尺度的变化过程,Kwon提出了涉及选取、简化、合并等多种综合操作的Multiple R树索引结构,该索引对各尺度综合结果要求较高,相当于一个全面的地图自动化综合过程,由于目前制图综合难以通过完全自动化的方式实现,其生成过程需要较多的人工干预[12];邓红艳提出了用于空间数据多尺度表达的SDMR树索引[13],该索引结构中假设空间数据多分辨率子空间已经建立,因此具有集成综合算法的能力。三维环境下,由于比例尺的概念已不复存在,只有通过某些因子对三维建筑的尺度问题进行合理表达,才有可能实现综合算法与索引树的集成。
对于建筑而言,其结构特点决定了可根据综合尺度和综合区直接构建多尺度索引。本文借鉴Multiple R树的索引思想,结合三维建筑及其综合的具体特点,以综合区为基础建立了一种用于三维建筑多尺度表达的R树索引,称为GAMR树(Generalization Area Multi-representation R Tree)。

2 三维建筑综合区的影响因子

综合方法的集成是三维建筑综合区表达中需考虑的重要问题。三维建筑综合的具体实现需考虑建筑结构、分布特点及综合控制参数等因素。
建筑结构及分布特点很大程度上受其所属区域的影响,根据区域特点的差别可将综合区分为4类:大城市、城镇、普通村镇和山村。其中,大城市中的建筑高度高、密度大且具有标志性建筑;城镇建筑分布较为规律、高楼较少;普通村镇建筑形态具有相似性且分布有规律;山村以独立建筑为主,地面高程差别大。
三维可视化的最大特点在于视角的存在,同一对象在不同视角下的视觉效果往往差别很大,因此,以视角为基础实现建筑模型综合的方法不具备通用性。影响综合的因素很多,而综合算法中使用过多参数往往会导致尺度表达的混乱,因此综合区构建时应使用尽量少的控制参数。欧式几何长度对于选取、化简及合并等具体综合算子具有重要的度量作用,且被很多综合算法作为阈值以控制综合力度,从利于算法集成考虑,将几何长度作为唯一参数应用于GAMR树。综合算法的选择以综合区类型为基础,如果区域建筑密度越大,复杂度越高,则构建综合区时采用的阈值越小。

3 GAMR树的定义与结构

R树索引最早由Guttman提出,其实质是B树索引在空间维上的扩展,是一种高度平衡的树,由中间结点和叶结点组成,实际数据对象的最小外接矩形存储在叶结点中,中间结点通过聚集其低层结点的最小外接矩形形成,中间结点包含其所有子结点的最小外接矩形[14]图1为R树结构的具体示例。
GAMR树是以R树为基础,来实现三维建筑多尺度表达与综合为目标的一种空间索引。借鉴R树的定义形式,将GAMR树定义为:
(1)GAMR树由综合R树和综合区子树2部分组成,其中,综合R树对建筑多尺度表达与综合进行整体控制,综合区子树负责建筑对象的组织与管理;
(2)各不同LOD建筑对象均存储于综合区子树中,综合R树自身结点中不包含任何实体对象;
(3)根结点至少包含2个子结点,除非它同时也是叶子结点;
(4)综合R树中每个结点所包含的单元个数介于1和M之间,其中,M为结点中单元的最大数目;
(5)中间结点在地理空间上包含了其所有子结点,即所有的综合操作发生在综合R树的同一结点内;
(6)综合操作中,除执行选取操作的对象外,其他综合方法均产生新对象,新对象在GAMR树中位于更高结点的子树中;
(7)综合区子树完全使用传统R树的索引方法管理对应区域内的建筑对象。
综合R树中结点的具体结构形式为(Index,iType,Thres,Concave,PointToGA,PointToChild)。其中,Thres代表当前综合区内允许综合算子执行的最大阈值;iType表达了当前综合区所属的区域类型(1-4分别为大城市、城镇、普通村镇和山村,0表示未分类);PointToGA指向当前的建筑综合区,若其值为空,则表明该综合区尚未生成。PointToChild指向当前结点的子结点,若PointToChild为空,则表示当前结点已经为叶结点,此时综合区内仅包含一个建筑对象,Index代表该对象的最小外界矩形(MBR),Concave为该对象底面轮廓的凸包;若不为空,则Index为包含了其所有子结点MBR的最小矩形区域,Concave为所有子结点凸包所构成的新凸包。其中,保留凸包结构的目的在于使综合区的构造结果更为合理。
Fig. 1 Block partition and structure of R tree[14]

图1 R树分块结果及其结构[14]

综合区子树的表达采用R树索引的结构形式,叶结点索引项为(Index,Obj_ID),其中,Index表示包围空间对象的MBR;Obj_ID标识一个三维建筑的实体对象。中间结点的索引项为(Index,Child_ Pointer),其中,Index为一个矩形区域,该区域为其子结点所有索引项MBR所构成的矩形区域;Child_Pointer指向其子结点。

4 GAMR树的生成

GAMR树的生成以三维建筑综合区为基础,树的高度与所选长度阈值有直接关系。相邻等级结点间的阈值差越大,则由低级结点得到高级结点时的综合力度越大,由叶结点到根结点所执行的综合次数越少,树的高度越低;反之,树的高度越高。
原始模型中所有建筑的细节层次均为同一等级,将这些建筑模型作为GAMR树中最低层次子树的叶结点,按以下步骤建立GAMR树。
(1)如果模型中存在道路、河流等要素,则以其为约束对建筑进行初步划分,分别建立每个区域建筑对象的综合R树。
(2)以各建筑为基础构建综合R树的叶结点和综合区子树,此时综合区子树仅包含一个对象,叶结点的PointToChild为空,Thres=0。初始化阈值 t = t 0 = 0 (其中, t 0 为当前节点阈值,t为高层节点阈值),设叶结点为当前结点,如果当前结点的个数为1,则执行步骤(5),否则执行步骤(3)。
(3)以当前的结点凸包为基础生成高层结点,找出高层结点中所包含当前结点的最大数目N,若M/2≤NM,则执行步骤(4);若 N < M / 2 ,则t值过小,令 s = t , t = t + ( t - t 0 ) 2 , t 0 = s ,重新执行步骤(3);若 N > M ,则t值过大,令 t = ( t + t 0 ) 2 ,重新执行步骤(3)。
(4)以 t 为阈值对当前结点综合区内的建筑进行综合,由高层结点所有子结点中综合后的对象生成该结点的综合区子树,令结点 Thres = t ,以高层结点作为当前结点,若当前结点的个数为1,则执行步骤(5);否则令 t 0 = t , t = t 0 + 1 ,执行步骤(3)。
(5)如果存在约束,则以河流、道路等级为基础,将各综合R树的根结点作为中间结点构成覆盖全部区域的综合R树,GAMR树构建完成。
综合区生成过程中,采用自底而上的方式依次生成所有结点的综合区子树。对于只需要特定层次结点建筑对象的应用,自上而下地搜索其各层次子结点,将具有子树的结点进行综合生成该结点综合区子树。GAMR树是一种集成了三维建筑LOD模型生成和管理方法的索引树,LOD模型由根结点到叶结点逐步精细,其结构如图2所示。
Fig. 2 Structure of GAMR tree

图2 GAMR树的结构

5 GAMR树的查询与显示

单尺度查询的检索结果具有唯一性,即区域内包含了固定的对象。GAMR树的查询属于多尺度查询,查询结果随着尺度的不同而变化,因此,将所有尺度中位于目标地理区域内的对象全部检索出来更具有普遍意义。以矩形区域查询为例,GAMR树多尺度查询的实现步骤为:
(1)初始化GAMR树为当前树,设搜索矩形在地理空间中的区域为S;
(2)从当前树的根节点T开始依次判断其子结点Index项与S之间的关系,若S包含Index或二者相交,则执行步骤(3);当不存在满足此空间关系的Index时,执行步骤(4);
(3)对该结点所对应的PointToGA项进行判断,若PointToGA不为空,则记录该单元在GAMR树中的深度i,以S为基础,按照文献[14]中的R树区域查询算法,对该子树进行搜索;若建筑位于搜索区域S内,记录该对象,将当前结点单元中查询到的所有建筑记为( T H i , B i 1 , B i 2 , B i 3 , …),其中, T H i 为当前节点所对应的阈值;以当前结点为根节点,其子树为当前树,执行步骤(2);
(4)将查询所得建筑对象以组的形式存储,合并 T H i 值相同的对象组,查询完成。
无论是建筑对象本身还是建筑的内部特征,可辨识性是实现其可视化的基本要求。三维场景中,观察对象时大多采用透视中心投影,这种投影方式下,物体大小随着视距和方向的改变而改变,因此三维环境下对象的辨识具有视点相关性。建筑的可辨识性可分为3个层次:建筑特征、建筑自身和建筑之间。其中,建筑特征及建筑自身的可辨识性是指建筑特征和建筑自身轮廓能为用户所识别,当其尺寸小于一定阈值,难被用户所察觉时,需进行综合处理;建筑之间的可辨识性是指两相邻建筑之间必须保持一定的距离,当视觉上难以对二者进行区分时,需将其合并。
GAMR树中对不同等级建筑模型的综合力度及综合区之间的最短距离作了统一规定,建筑的多尺度显示转化为根据可辨识度的不同,从树中选择相应结点进行显示的问题。计算机可视化表达中,投影到屏幕的尺寸大小决定了对象特征能否为人眼所识别,考虑到人眼的视觉误差,通常认为投影尺寸长度小于2个像元时,该特征不能被识别。通过视点与综合区之间的关系能计算出人眼可辨识的最小尺寸,根据该尺寸选择显示相应的结点。视线方向的不同会导致相同长度的屏幕投影有所差别(图3),难以采用统一的标准进行度量。从保证对象正面特征的可辨识性出发,以线段与视线垂直时的尺寸为计算基础,则保持可辨识性的最小尺寸 L t 可由式(1)求得。
L t = 2 d × cosθ × P l d 0 (1)
式中, d 为视点到综合区边界的最短距离; d 0 为视点到屏幕的垂直距离; P l 为屏幕单位像素的大小; θ 为距离最近点与视线正前方的角度。
Fig. 3 Variations of projected length caused by different sight directions

图3 视线方向对投影长度的影响

以最小尺寸为基础实现GAMR树多尺度显示的具体方法:由树的根结点开始依次遍历其子结点,计算结点Index可辨识的最小尺寸 minS ,若 minS > L t ,则显示该结点综合区子树中的建筑对象,终止遍历以此结点为根的子树;若当前结点为叶结点,显示该结点综合区子树中的建筑。

6 结论

GAMR树已应用于三维建筑综合实验系统以实现模型的组织和管理。图4为基于GAMR树管理的某区域三维建筑模型的可视化结果;图5为以综合区为基础,对某一尺度建筑对象进行查询的结果,查询效率较高,能满足实时性的要求。实验证明,GAMR树能很好地应用于三维建筑多尺度模型的组织与管理,尤其对于三维建筑几何模型自动综合的实现具有重要意义。
Fig. 4 3D building models organized by GAMR tree

图4 GAMR树管理的三维建筑模型

Fig. 5 The querying result of a building that displayed at a certain scale

图5 某尺度下建筑对象的查询结果

The authors have declared that no competing interests exist.

[1]
Forberg A.Simplification of 3D building data[C]. ICA Workshop on Generalization and Multiple Representation, Leicester, UK, 2004.

[2]
Thiemann F, Sester M.Segmentation of buildings for 3D-Generalisation[C]. ICA Workshop on Generalization and Multiple Representation, Leicester, UK, 2004.

[3]
Kada M.3D building generalization based on half-space modeling[C]. Proceedings of the ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data, Hannover, Germany, 2006.

[4]
Kada M.3D building generalisation by roof simplification and typification[C]. XXIII International Cartographical Conference, Moscow, 2007.

[5]
Forberg A.Generalization of 3D building data based on a scale-space approach[J]. SPRS Journal of Photogrammetry and Remote Sensing, 2007,62:104-111.

[6]
Peter M, Haala N, Fritsch D.Preserving ground plan and facade lines for 3D building generalization[C]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Beijing, 2008.

[7]
Fan H C, Meng L Q.A three-step approach of simplifying 3D buildings modeled by CityGML[J]. International Journal of Geographical Information Science, 2012,26(6):1091-1107.

[8]
Guercke R, Gözelmann T, Brenner C, et al.Aggregation of LoD 1 building models as an optimization problem[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2011,66:209-222.

[9]
Xie J H, Zhang L Q, Li J, et al.Automatic simplification and visualization of 3D urban building models[J]. International Journal of Applied Earth Observation and Geoinformation, 2012,18:222-231.

[10]
Mao B, Ban Y F.A multiple representation data structure of 3D building textures[C]. 19th International Conference on Geoinformatics, 2011.

[11]
Chan E P F, Chow K K W. On multi-scale display of geometric objects[J]. Data & Knowledge Engineering, 2002,40:91-119.

[12]
Kwon J H, Yoon Y I.An access method for integrating multi-scale geometric data[J]. Lecture Notes in Computer Science, 2002,2435:204-217.

[13]
邓红艳,武芳,翟仁健,等.一种用于空间数据多尺度表达的R树索引结构[J].计算机学报,2009,32(1):177-184.

[14]
Guttman A.R-tree: A dynamic index structure for spatial search[C].Proceedings of the ACM SIGMOD International Conference on Management of Data,1984:47-57.

[15]
葛磊,武芳,钱海忠.一种面向综合的3维建筑模型重构方法[J]. 测绘科学技术学报,2012,29(6):454-458.

[16]
周艳,朱庆,黄铎.三维城市模型中建筑物LOD模型研究[J].测绘科学,2006,20(9):74-77.

[17]
Gerhard Gröger, Thomas H.Kolbe, Angela Czerwinski, etc. OpenGIS® City Geography Markup Language (CityGML) Encoding Standard[M]. Open Geospatial Consortium Inc, 2008.

[18]
王国庆,朱庆,艾廷华.建筑物三维表面模型简化算法探讨[J].测绘科学,2006,32(2):84-86.

[19]
朱庆,龚俊,杜志强,等.三维城市模型的多细节层次描述方法[J].武汉大学学报·信息科学版,2005,20(11):965-969.

[20]
吕金建,文贡坚,李德仁,等.一种新的基于空间关系的特征匹配方法[J].测绘学报,2008,37(3):367-373.

[21]
Raheja J L.Recognition of 3D settlement structure for generalization[D]. Munich: University of Munich, 2005.

Outlines

/