空间体对象间三维拓扑构建研究

根据三维拓扑的研究现状以及特定应用领域对三维拓扑的需求,分析了这些特定应用领域的拓扑关系,提出了两种三维拓扑构建方法。这两种方法在兼顾内拓扑的同时主要构建体之间的外拓扑关系。第一种方法是在体单独构建完毕后建立体之间的拓扑关系;第二种方法考虑到当前成熟三维建模软件或CAD软件中的数据大多以离散面方式组织,设计了自动寻体算法,同时构建体之间的外拓扑关系。利用深圳典型地籍数据和建筑设计图生成的三维数据进行实验,验证了此算法的可行性。     

顾及外拓扑的异构建筑三维拓扑重建

分析了异构建筑在三维拓扑重建中的问题,依据拓扑数据模型的需求,提出了基于顶图、底图和结构图的自动拓扑重建算法,该算法能够有效地对异构建筑进行整体三维拓扑重建,不仅保留了建筑内每一实体单元的内拓扑,同时也兼顾了实体间的外拓扑。基于该方法,设计并开发了三维地籍管理系统中的数据生成模块,以深圳市某小区为实验区,验证了算法的可行性及有效性。     

简单面目标与带孔洞面目标间拓扑关系的层次表达方法

带孔洞的面目标是现实中较为常见的一类复杂目标,它们之间的拓扑关系要比简单面目标复杂得多.本文基于空间划分和目标分解的思想,利用点集(拓扑学)理论中的邻域概念详细分析和描述带孔洞面目标的点集拓扑分量,这种描述方法实质上是简单面目标点集拓扑分量描述的一种自然延展.进而,对简单面目标间拓扑关系的描述和区分方法进行了扩展,层次地分析和区分简单面目标与带孔洞面目标间的拓扑关系.相比于Egenhofer等人提出的代数描述和间接表达方法,本文提出的方法是一种直接描述和层次表达的方法,并且与简单面目标间拓扑关系的表达方法是相统一的.     

Reconstructing facade semantic models using hierarchical topological graphs

Semantic information in 3D building models is of vital importance for various applications in terms of smart cities. To infer the semantic information and localize the components on building facades, this article proposes a novel approach to model facades with semantics by constructing hierarchical topological graphs. This method utilizes the topological characteristics of building facades. In the first‐layer layout graph, the algorithm takes the nearest cluster as the vertex and the distance between components as the edge. Thus, a topology graph is generated for the facade. The proposed algorithm is divided into three steps. First, the topology graph is obtained by calculating the spacing between the components. It is reasonable to calculate the topological graph by encoding the topological edges. If this calculation is not effective, the topology is justified by adjusting the spacing between components. Finally, the vertices in the graph are used to repair the occluded parts of the facade. In the second‐layer graph, a grid is constructed according to the first‐layer graph. Then, the attributes of the nodes are used to reconstruct the facade. The experimental results show that this method has a high accuracy of 90% and that the average time consumption is 6 s.     

A Topology‐Inferred Graph‐Based Heuristic Algorithm for Map Simplification

In this article we present a heuristic map simplification algorithm based on a novel topology‐inferred graph model. Compared with the existing algorithms, which only focus either on geometry simplification or on topological consistency, our algorithm simplifies the map composed of series of polylines and constraint points while maintaining the topological relationships in the map, maximizing the number of removal points, and minimizing error distance efficiently. Unlike some traditional geometry simplification algorithms, such as Douglas and Peucker's, which add points incrementally, we remove points sequentially based on a priority determined by heuristic functions. In the first stage, we build a graph to model the topology of points in the map from which we determine whether a point is removable or not. As map generalization is needed in different applications with different requirements, we present two heuristic functions to determine the priority of points removal for two different purposes: to save storage space and to reduce computation time. The time complexity of our algorithm is which is efficient enough to be considered for real‐time applications. Experiments on real maps were conducted and the results indicate that our algorithm produces high quality results; one heuristic function results in higher removal points saving storage space and the other improves the time performance significantly.     

基于庞卡莱代数的TEN三维GIS模型研究

不规则四面体网具有结构简单、易于扩展的特性。借助于庞卡莱代数,应用边界表示理论重新描述了TEN模型。与传统几何结构模型相比,这种模型具有表达简单、易于计算的特点。同时,提出基于庞卡莱代数的TEN合并和删除运算以及拓扑一致性检查。在VC++环境下,对TEN模型的合并和删除运算进行编程与实现。实验表明,基于庞卡莱代数的TEN模型可以有效建立动态实体模型,能够实时建立拓扑关系,适合于表达不规则矿体等动态变化的三维实体。     

GIS图上地理区域空间不确定性的分析

区域是GIS空间分析的基本单元。它是环境科学、土壤科学等领域中广泛存在的一类地理实体。这类实体抽象概括为GIS中空间目标时不可避免地带有模糊性。利用模糊集这个强有力的数学工具，首先基于场模型提出了表达GIS中模糊区域目标的方法，分析了其空间不确定性。继而，建立了模糊区域的形态描述模式，即模糊区域边界、内部和外部，并指出了Cohn给出的定义中的不足。在此基础上，对Egenhofer提出的九元组进行了扩展，构建了适合于描述确定和模糊区域目标间拓扑空间关系的模型。     

三维地籍空间拓扑数据模型研究与实现

本文提出了一种适于表达三维地籍的空间拓扑数据模型,并分别在概念层次和实现层次给出了概念模型和逻辑模型。概念模型分为3层:要素层、几何层和拓扑层。要素层用于表述地籍管理对象,几何层用于描述实体的几何形态,拓扑层用于表达实体间的拓扑关系。在概念模型基础上,给出了对应的逻辑模型。实验结果表明:所提出的模型有效、可行。     

三维GIS场景与多路视频融合的对象快速确定法

虚实融合技术是视频增强三维虚拟地理场景的关键环节之一,对提高真实沉浸式视觉体验具有重要作用。现有基于视频投影的虚实融合方法,在三维场景动态更新时,通常需要对用户视角下新场景内所有渲染对象进行遍历,来筛选出摄像头范围内需融合的对象,导致融合过程耗时长、效率不高。本文提出一种顾及拓扑关系的多路视频与三维GIS场景融合的对象快速确定方法。首先对三维场景视锥体内视频对象集渲染对象动态建立拓扑网络模型;然后基于拓扑网络模型建立视频与渲染对象的拓扑关系,完成融合对象的快速确定及融合渲染;最后利用滕州市三维场景进行了验证。试验结果表明,本文提出的方法在视频与三维GIS场景融合时,整体耗时少、效率高,极大地降低了融合的计算代价,具有良好的可行性及稳健性。     

Modelling and analysing 3D buildings with a primal/dual data structure

While CityGML permits us to represent 3D city models, its use for applications where spatial analysis and/or real-time modifications are required is limited since at this moment the possibility to store topological relationships between the elements is rather limited and often not exploited. We present in this paper a new topological data structure, the dual half-edge (DHE), which permits us to represent the topology of 3D buildings (including their interiors) and of the surrounding terrain. It is based on the idea of simultaneously storing a graph in 3D space and its dual graph, and to link the two. We propose Euler-type operators for incrementally constructing 3D models (for adding individual edges, faces and volumes to the model while updating the dual structure simultaneously), and we also propose navigation operators to move from a given point to all the connected planes or polyhedra for example. The DHE also permits us to store attributes to any element. We have implemented the DHE and have tested it with different CityGML models. Our technique allows us to handle important query types, for example finding the nearest exterior exit to a given room, as in disaster management planning. As the structure is locally modifiable the model may be adapted whenever a particular pathway is no longer available. The proposed DHE structure adds significant analytic value to the increasingly popular CityGML model.     

基于OpenMP的矢量空间数据并行拓扑算法设计与实现

高性能并行GIS逐渐成为GIS发展的新方向。矢量数据的复杂性使得一些并行GIS算法难以实现,从而无法满足并行GIS的发展要求。文中针对GIS算法中的拓扑算法,借助OpenMP编程模型,通过消除并行拓扑处理过程中的数据依赖,在单机多核的环境下设计并实现了矢量空间数据并行拓扑算法。通过实验对比串行拓扑算法和并行拓扑算法的处理时间和结果,验证了并行拓扑算法的正确性,同时证明并行拓扑算法能够在一定程度上提升拓扑处理的效率。     

数字地形建模的真三维TIN算法研究(英文)

The problem of taking an unorganized point cloud in 3D space and fitting a polyhedral surface to those points is both important and difficult. Aiming at increasing applications of full three dimensional digital terrain surface modeling, a new algorithm for the automatic generation of three dimensional triangulated irregular network from a point cloud is proposed. Based on the local topological consistency test, a combined algorithm of constrained 3D Delaunay triangulation and region-growing is extended to ensure topologically correct reconstruction. This paper also introduced an efficient neighboring triangle location method by making full use of the surface normal information. Experimental results prove that this algorithm can efficiently obtain the most reasonable reconstructed mesh surface with arbitrary topology, wherein the automatically reconstructed surface has only small topological difference from the true surface. This algorithm has potential applications to virtual environments, computer vision, and so on.     

Construction of 3D Volumetric Objects for a 3D Cadastral System

This article presents a new method to illustrate the feasibility of 3D topology creation. We base the 3D construction process on testing real cases of implementation of 3D parcels construction in a 3D cadastral system. With the utilization and development of dense urban space, true 3D geometric volume primitives are needed to represent 3D parcels with the adjacency and incidence relationship. We present an effective straightforward approach to identifying and constructing the valid volumetric cadastral object from the given faces, and build the topological relationships among 3D cadastral objects on‐the‐fly, based on input consisting of loose boundary 3D faces made by surveyors. This is drastically different from most existing methods, which focus on the validation of single volumetric objects after the assumption of the object's creation. Existing methods do not support the needed types of geometry/topology (e.g. non 2‐manifold, singularities) and how to create and maintain valid 3D parcels is still a challenge in practice. We will show that the method does not change the faces themselves and faces in a given input are independently specified. Various volumetric objects, including non‐manifold 3D cadastral objects (legal spaces), can be constructed correctly by this method, as will be shown from the results.     

四维宗地建模及其核心操作算法

传统地籍是基于某一时刻的土地二维剖分，不支持立体产权管理和时空权属查询，需要探索四维（三维空间+时间）地籍。四维宗地是四维地籍的登记客体，是宗地在四维空间的扩展，其创建、分割、合并与注销等操作是四维地籍最常用、最基本的功能。结合城市发展现状和地籍管理需求，分析时态产权特征，用UML建模四维宗地数据模型和基于拓扑数据模型的四维宗地操作算法。研究内容包括:①提出四维宗地数据模型；②提出基于"拉伸"的四维宗地创建算法以及基于分段时间的共享拓扑基元处理方法；③提出四维宗地的分割、合并算法。研究结果表明:四维宗地的构建为追踪产权的时空变化提供了理论借鉴和技术支持，也使得地籍管理向四维地籍迈进了一步。     

基于航空立体影像对的复杂房屋三维拓扑重建

对利用航空影像对重建复杂房屋三维模型进行了研究，提出了拓扑链、外拓扑和内拓扑的概念，分析了复杂房屋的内拓扑和外拓扑的三维重建，构造了复杂房屋的三维拓扑数据模型。基于此模型设计了双向搜索算法，用于自动构建复杂房屋的三维拓扑面，从而实现了复杂房屋的自动三维拓扑重建。实验证明，本文提出的双向搜索算法是很稳健、高效的。     

Morse理论支持下的建筑物点云特征提取

针对传统特征提取算法的结果存在交叉紊乱、不连续、缺少拓扑关系等问题，本文提出了基于Morse理论的建筑物点云特征提取算法。首先定义三维表面模型上顶点的Morse函数指标；然后采用邻点比较法自动提取特征点；最后针对Morse-Smale复形的对偶性在建筑物拓扑特征中已无实际意义的问题，提出了单复形拓扑模型的提取与简化算法。试验结果表明，该算法能够获得清晰、连续、完整的建筑物特征线，实现对建筑物模型表面的完全分割；简化算法在保证建筑物特征线拓扑一致性的前提下，可以获取不同层次的建筑物拓扑特征，为建筑物模型的重建与可视化提供了保障。     

The Phoenix Algorithm for Three Dimensional Data Capture

The graphical representation and interactive manipulation of accurate three dimensional (3D) models of reality is rapidly becoming an inescapable necessity for many applications of geographical information systems (GIS). There are many problems and difficulties that must be overcome in order to facilitate such 3D models. Can accurate measurements, at sufficient resolution and using affordable resources, be obtained? Will application software usefully process, in all aspects, models of the real world, held in full 3D? Can a topology of containment, adjacency and contiguity in 3D be integrated into the conventional procedural and recording functionality of two dimensional (2D) GIS and still provide workable spatial analysis tools? A 3D GIS applied to an urban environment should maintain a model that would typically consist of solid representations of individual buildings, roads and utilities, providing both external and internal detail, all assigned to a suitable digital terrain model (DTM). The particular 3D application considered here addresses the need for accurate reconstruction of historical urban buildings. The creation, manipulation and exploration of such models is often referred to as “virtual heritage”. Much of this paper describes an effective methodology, called the Phoenix algorithm, requiring only a single image of an urban object, for the construction of 3D models of buildings at high resolution. The development of this algorithm is discussed and the results obtained from it are compared with those obtained using traditional 3D capture techniques. An outline of further potential GIS applications is presented.     

Buildings and terrain unified – multidimensional dual data structure for GIS

3D city models are widely used in many disciplines and applications, such as urban planning, disaster management, and environmental simulation. Usually, the terrain and embedded objects like buildings are taken into consideration. A consistent model integrating these elements is vital for GIS analysis, especially if the geometry is accompanied by the topological relations between neighboring objects. Such a model allows for more efficient and errorless analysis. The memory consumption is another crucial aspect when the wide area of a city is considered – light models are highly desirable. Three methods of the terrain representation using the geometrical–topological data structure – the dual half-edge – are proposed in this article. The integration of buildings and other structures like bridges with the terrain is also presented.     

顾及上下文的线状目标实体派生方法

针对制图自动综合中发现的线面数据存在的没有构建空间实体拓扑问题，本文提出一种顾及上下文的线状目标实体派生方法。首先，对围墙线、附属设施和建筑物建立空间拓扑邻近关系，对直接邻近群组进行聚类，然后，将其划分为3种模式，即两个围墙之间的拓扑连接、围墙与建筑物之间的拓扑连接及建筑物邻近的悬挂围墙线与建筑物之间的拓扑连接；最后，对这3种模式分别采用各自对应的最短路径、外轮廓线以及最近点的拓扑连接方法进行连接。以福建省数据为例进行试验，本文方法能够有效构建空间实体拓扑连接，有助于提高地图自动综合，同时能够满足生产实践的要求，具有很高的实用性。