基于多分辨率半边的全球多尺度地形无缝建模

发布时间：2018-10-15 15:47

【摘要】：随着空间数据采集技术的飞速发展和全球经济一体化的不断深入,许多应用领域越来越频繁地使用大范围(甚至全球)高分辨率地形数据进行分析决策。但是,由于受当前的计算机硬件限制,为了提高显示效率并实现DEM数据的无缝绘制和渲染,就需要在保证地形精度的前提下进行DEM格网简化,即构建多分辨率DEM表达模型。以传统四叉树结构或二叉树结构作为多分辨率格网的剖分结构,不可避免在相邻不同分辨率DEM格网之间产生裂缝,而目前的裂缝消除方法大都属于“后期处理”,且这些方法会带来新问题,如地形失真、计算量大、破坏细分准则、地形简化算法复杂化、数据管理复杂等等。多分辨率半边结构以多分辨率组合映射为基础模型,是半边结构在多分辨率表达方面的扩展。该理论将格网抽象为dart集合,几何实体的构建和拓扑关系表达均由dart的复合运算实现。该结构在实现格网多分辨率剖分时,直接对边管理,可以实现边、面同步剖分。为此,本文引入多分辨率组合映射理论,提出一种基于多分辨率半边结构的多分辨率DEM无缝表达方法,有望从前期的格网剖分结构层面消除地形多分辨率表达中的裂缝问题。多分辨率半边结构在多分辨率格网的无缝表达方面具有优势,但基于该结构的研究仍处于初级阶段,为了实现大规模甚至全球地形多分辨率建模,本文对其在全球多分辨率地形无缝建模的部分关键技术、操作算法和应用进行较为深入探讨,主要工作及成果总结如下:1)梳理基础理论及总结现有研究成果多分辨率组合映射是多分辨率半边的理论模型,本文以多分辨率组合映射为核心,厘清了相关理论间的关系,包括半边结构、组合映射、超映射、多分辨率半边结构;而后将该理论用于GIS中基本实体和空间关系的表达,为该理论应用于多分辨率DEM无缝表达奠定基础;分析了空间复杂度和邻近搜索时间复杂了,并对该结构的优缺点进行了分析和总结。在此基础上,从多分辨率组合映射的基本理论、相关技术和算法等方面,扼要而全面的叙述了近年来国内外的研究成果。研究发现,在基本理论方面,多分辨率组合映射的理论较为完善,但并非尽善尽美,且缺乏应用;在表面格网多分辨率表达方面,相关研究仅限于细分原理和存储方法,未对关键技术和建模算法进行研究;当该理论应用到本文,处理大规模或全球地形数据时,还会涉及四分体间裂缝、块间裂缝、数据组织等方面的问题。在以上问题的基础上,引出本文的研究内容和思路,并提出研究方案和技术路线。2)构建了基于多分辨率半边的多尺度DEM无缝表达算法树结构只对格网面细分,未对格网边管理,不可避免在不同层次相邻格网边界处产生裂缝问题。因此,引入多分辨率组合映射理论,提出一种基于多分辨率半边结构的多尺度dem无缝建模方法。首先,给出规则格网的多分辨率半边剖分原理和存储机制;然后,提出局部地形规则格网的多尺度dem的无缝建模算法。该算法从前期的格网剖分结构上解决了多分辨率dem表达中的裂缝问题,不需要限制相邻格网的剖分层差,数据无冗余,地形无失真,可实现完全依据地形起伏的简化,能够自适应的管理简化后的多边形格网。3)设计与实现了全球多分辨率地形无缝表达全球离散格网是全球地形表达的有效模型,全球多分辨率dem的裂缝不仅出现在单个四分体内部,还见于四分体之间,尽管目前的裂缝消除方法有很多种,但大都属于“后期处理”,且存在诸多限制。因此,本文将基于多分辨率半边的局部地形多尺度dem无缝建模算法扩展到全球范围。首先,给出基于多分辨率半边的多种全球离散格网统一表达原理;然后,以球面菱形格网为例,提出了菱形格网的多分辨率半边剖分、编码、编码坐标与经纬度坐标之间的转化和全球菱形格网点高程值获取等方法;最后,基于以上方法,设计并实现了全球多分辨率dem无缝建模算法。4)实现了全球多分辨率地形的动态lod管理模拟与可视化为了实现全球高分辨率地形的无缝模拟和可视化,提出基于多分辨率半边和菱形块的全球多分辨率地形动态lod管理模拟和可视化方法。首先,提出了块间裂缝的消除方法,包括块边界结点、极点结点和块顶点处结点;然后,对全球地形数据进行分块组织,基于块构建多分辨率半边结构,并应用动态调度方法,实现了全球多分辨率地形的动态lod无缝表达。多分辨率半边结构可以保证块内无缝细分,块间裂缝的消除比传统方法简单;块内简化依据地形起伏,不存在数据冗余;不涉及块间高程点的调整,地形无失真。5)设计并开发了实验原型系统以c++语言和directx为工具,应用全球gtopo30及局部地形高程数据,应用本文提出的算法,设计和开发相应的实验系统,验证本文算法的正确性、可行性和有效性。该系统的主要功能包括:本文所提算法的实现,包括局部地形无缝建模算法、全球多分辨率dem无缝建模算法和基于块的动态lod建模算法;算法运行结果的数据统计分析,包括存储元素、渲染三角形个数和四边形个数等;可视化互操作,包括图形的放大、缩小、旋转等操作;地形数据文件的读取和输出。局部区域地形格网自适应无缝建模实验结果表明:本文方法能够实现多尺度dem无缝建模,且与“限定四叉树”法相比,随剖分层次的增加,格网数量和渲染数据量的降低率逐渐增大,当剖分层次为7时,以上两个指标分别为13.9%和12.2%,优于“限定四叉树”法。该研究为多分辨率组合映射理论应用于全球多分辨率dem无缝表达奠定了基础。全球多分辨率DEM无缝建模实验结果表明:以多分辨率半边结构为基础,通过边界和极点处结点细分准则的特殊处理,四分体内部、边界和极点处均不会产生裂缝;通过调整细分阈值ε、最大剖分层次Lmax、最小剖分层次Lmin等三个参数,可分别实现陆地和海洋格网不同程度的简化;当剖分层次为10,阈值为500米时,“限定四叉树”结构比多分辨率半边多渲染三角形91922个,比例为15.11%。实现了全球多分辨率DEM的无缝可视化表达,基本满足了全球多分辨DEM建模对绘制速度和逼真度的要求。基于菱形块的全球地形动态LOD无缝建模实验表明:多分辨率半边结构可以保证块内无裂缝,块间通过边界结点细分方法的限制,菱形块边界处相邻结点同时剖分,对称分布,块间无裂缝;与传统方法相比,本文方法的简化效率更高,地形无失真,计算量小。
[Abstract]:With the rapid development of spatial data acquisition technology and the deepening of global economic integration, many fields of application increasingly use large-scale (even global) high-resolution terrain data for analysis and decision-making. However, due to the current computer hardware limitation, in order to improve the display efficiency and realize the seamless rendering and rendering of DEM data, it is necessary to simplify the DEM grid on the premise of ensuring the terrain precision, that is to construct a multi-resolution DEM expression model. As a cross-sectional structure of multi-resolution grid, the traditional four-fork tree structure or binary tree structure inevitably causes cracks between adjacent different resolution DEM grids, and the current crack elimination methods mostly belong to "Post-processing" and the method can bring new problems, such as terrain distortion, large calculation amount, breaking subdivision criterion, complicated terrain simplification algorithm, complex data management and the like. Multi-resolution half-side structure is based on multi-resolution combination mapping and is an extension of half structure in multi-resolution expression. According to the theory, the grid is abstracted into a dart set, and the construction of the geometric entity and the expression of the topological relation are all realized by the composite operation of the art. According to the structure, when the grid multi-resolution section is realized, the edge and the surface synchronization section can be realized directly on the edge management. To this end, the multi-resolution combined mapping theory is introduced in this paper, and a multi-resolution DEM seamless expression method based on multi-resolution half structure is proposed. The multi-resolution half-side structure has advantages in the seamless expression of multi-resolution grid, but the research on this structure is still in the primary stage. In order to realize multi-resolution modeling of large-scale and even global terrain, this paper is a key technology of seamless modeling of multi-resolution terrain in the world. The operation algorithms and applications are discussed in depth, the main work and results are summarized as follows: 1) The basic theory and summary of the existing multi-resolution combination mapping is the theoretical model of multi-resolution half, which is based on multi-resolution combination mapping. The relationship between the relevant theories is clarified, including the half structure, the combination mapping, the super-mapping and the multi-resolution half-half structure, and then the theory is applied to the expression of the basic entity and the space relation in the GIS, thus laying a foundation for the theory to be applied to the seamless expression of the multi-resolution DEM; The complexity of space complexity and adjacent search time is analyzed, and the advantages and disadvantages of the structure are analyzed and summarized. On this basis, from the aspects of the basic theory, correlation technique and algorithm of multi-resolution combination mapping, the research achievements at home and abroad in recent years are briefly described. It is found that in the basic theory, the theory of multi-resolution combination mapping is perfect, but not perfect and lacks the application; in the aspect of multi-resolution expression of the surface mesh, the relevant research is limited to the subdivision principle and the storage method, and the key technology and the modeling algorithm are not researched; When the theory is applied to this paper, when dealing with large-scale or global terrain data, it also concerns the problems of interquartic cracks, inter-block cracks, data organization and so on. On the basis of the above problems, this paper draws out the research content and thought of this paper, and puts forward the research scheme and the technical route. 2) The multi-scale DEM seamless expression algorithm tree structure based on multi-resolution half is constructed, the mesh surface subdivision is only subdivided, and the grid edge management is not carried out. crack problems are inevitably generated at adjacent grid boundaries at different levels. Therefore, the multi-resolution combined mapping theory is introduced, and a multi-scale dem seamless modeling method based on multi-resolution half structure is proposed. First, a multi-resolution half-section principle and storage mechanism of regular grid are given, then a seamless modeling algorithm of multi-scale dem of local terrain regular grid is proposed. The algorithm solves the crack problem in the multi-resolution dem expression from the prior grid section structure, does not need to limit the cross section difference of the adjacent grid, has no redundancy and no distortion of the terrain, and can realize the simplification of the topographic relief completely, the global discrete grid is the effective model for global terrain expression, and the crack of the global multi-resolution dem is not only found in the inner part of a single tetrad, but also between the four quadrants, Although there are many methods of crack elimination at present, most of them belong to "Post-processing" and there are a number of limitations. Therefore, this paper extends the local terrain multi-scale dem seamless modeling algorithm based on multi-resolution half to the global scope. Firstly, a multi-resolution half of the global discrete grid expression principle is given, and then a multi-resolution half section of a diamond grid is proposed based on the spherical diamond grid, and the coding is carried out. and finally, based on the above method, the global multi-resolution dem seamless modeling algorithm is designed and realized. 4) the dynamic lod management simulation and visualization of the global multi-resolution terrain are realized, so that seamless simulation and visualization of the global high-resolution terrain are realized, A global multi-resolution terrain dynamic lod management simulation and visualization method based on multi-resolution half and diamond block is proposed. firstly, a method for eliminating inter-block cracks is proposed, which comprises a block boundary node, a pole node and a node at the vertex of the block; then, the global terrain data is segmented, the multi-resolution half structure is constructed based on the block, and a dynamic scheduling method is applied, and the dynamic lod seamless expression of the global multi-resolution terrain is realized. The multi-resolution half-side structure can ensure the seamless subdivision in the block, the elimination of the inter-block cracks is simpler than the traditional method, the simplification of the block according to the topographic relief does not exist, the data redundancy does not exist, and the adjustment of the elevation points between the blocks is not involved, In this paper, we design and develop the experimental prototype system based on the cpr language and the direct tx as the tool, apply the global gtopo 30 and local terrain elevation data, apply the algorithm proposed in this paper, design and develop the corresponding experimental system, and verify the correctness, feasibility and validity of the algorithm. The main functions of the system include the realization of the proposed algorithm, including the local terrain seamless modeling algorithm, the global multi-resolution dem seamless modeling algorithm and the block-based dynamic lod modeling algorithm, the data statistical analysis of the algorithm operation result, including the storage element, the number of the rendered triangles and the number of quads, etc.; visual interoperability, including operations such as enlargement, reduction, rotation, etc. of graphics; and the reading and output of the terrain data file. The results of self-adaptive seamless modeling of local terrain mesh show that the method can realize the seamless modeling of multi-scale dem and "defining a four-prong tree" Compared with the method, the decreasing rate of the grid quantity and the rendered data volume gradually increases with the increase of the cross section level. When the split layer is 7, the above two indexes are 13. 9% and 12. 2%, respectively. "defining a four-prong tree" Law. This study laid the foundation for the application of multi-resolution combined mapping theory to the seamless expression of multi-resolution dem. The results of global multi-resolution DEM seamless modeling show that, on the basis of multi-resolution half structure, crack is not generated at the inner, boundary and pole of the tetrad through special treatment of node subdivision criterion at the boundary and the pole; by adjusting the subdivision threshold value, the maximum split level Lmax, three parameters such as the minimum split layer Lmin and the like can realize the simplification of different degrees of the land and the ocean grid respectively; when the split sub-level is 10, the threshold value is 500 meters, "defining a four-prong tree" The structure is more than half-resolution half-rendering triangle 91922, with a ratio of 15. 11%. the seamless visual representation of the global multi-resolution DEM is realized, and the requirements of global multi-resolution DEM modeling on drawing speed and fidelity are basically met. The global terrain dynamic LOD seamless modeling experiment based on diamond block shows that the multi-resolution half-side structure can ensure no crack in the block, the block passes through the limit of the boundary node subdivision method, the adjacent nodes at the diamond block boundary are simultaneously split, symmetrically distributed and no cracks exist between the blocks; compared with the traditional method, The simplified efficiency of the method is higher, the terrain is free of distortion, and the calculation amount is small.
【学位授予单位】：中国矿业大学(北京)
【学位级别】：博士
【学位授予年份】：2015
【分类号】：P208

【参考文献】