Seamless Modelling Of Global Multi-scale Terrain Based On Multi-resolution Half-edges Structure

With the rapid development of spatial data acquisition technology and the deepening of the global economic integration, many research and application areas apply to a wide range of high-resolution terrain data to analyze and make decisions more and more frequently. However, because of the limitation of current computer hardware and network, grid simplification will need to be done under the condition of guaranteeing the precision of terrain DEM, namely modelling of global multi-resolution DEM, in order to improve the efficiency of display and realize the seamless expression of global DEM data. When performing the multi-resolution DEMs expression based on Quad-tree structure, topological crack generates at the meeting of areas of different resolution levels. Holes appear in the mesh between neighboring faces of different subdivision depths. Although there are many methods of crack elimination, mostly belong to the "post processing", and there are many restrictions, such as terrain distortion, large amount of calculation, destroying subdivision criteria, complicated terrain simplification algorithm, complex data management and so on. The formalization of Multi-resolution half-edges data structure is multi-resolution combinatorial maps, and it is an extension of the half-edge data structure on multi-resolution expression. The theory of multi-resolution combinatorial maps abstracts the terrain as collections of darts, and multi-resolution grids are stored and managed with multi-resolution half-edges data structure, which could realize the synchronous subdivision of faces and edges. So a seamless model of global multi-resolution DEM is proposed, expecting to solve the "cracks" problem from the underlying the data structure of grid subdivision.Though the method based on multi-resolution half-edges structure has the advantage in seamless expression of multi-resolution model, it is still at an early stage. So, in order to achieve large-scale or even global multi-scale terrain modelling, some problems of seamless modelling of global multi-resolution terrain are researched in this article, including key technologies, algorithm, application, and so on. The main works are as follows:1) Organize the basic theory and summary the existing achievements. The model of multi-resolution 2-maps is the formalization of multi-resolution half-edge data structure. Because its theory is so complicated that the summarization is necessary in order to understand it more deeply. The main contents include hypermaps, combinatorial maps, half-edge structure, multi-resolution combinatorial maps, multi-resolution half-edge data structure, and so on. Based on the basic theory, the development and the comprehensive research achievements at home and abroad in recent years are described briefly involving basic theory, key technologies, algorithm based on multi-resolution combinatorial maps, and some questions are summarized. The theory of multi-resolution combinatorial maps is relatively perfect, but it is not perfect, and lack of application. Though the subdivision principle and storage method of adaptive modelling are proposed, the related technologies and algorithm have not yet been studied. If the theory is used in large-scale or global terrain data, it will also involve more complex cracks elimination, data organization and other issues. In the end, the research ideas and content of this dissertation are presented.2) Construct a seamless modelling algorithm of multi-scale DEM based on multi-resolution half-edges. The cause of the cracks is found through some analysis. Quad-tree structure abstracts the terrain as the collections of faces, and the face is the only topological entity operated in the process of subdivision, not involving the edge of the grids. So, the multi-resolution half-edge structure is introduced as the data management structure. Firstly, the theory of multi-resolution half-edges is introduced into the 3D terrain modelling, and the methods suitable for mesh storage and faces extraction are put forward. Then, the adaptive seamless algorithm of 3D terrain is designed and achieved. The method solves the crack problem of multi-resolution DEM expression from the underlying data structure, and it does not need to repeatedly check the level difference between the adjacent nodes, with no data redundancy and terrain distortion, achieving the complete simplification according to the terrain relief. The model lays a solid foundation of applying multi-resolution half-edge into multi-resolution expression of global terrain.3) Design and implement seamless expression of Global multi-resolution terrain based on multi-resolution half-edges. Global discrete grid is an effective model for global terrain expression, and cracks of global multi-resolution DEM not only appear inside of the tetrads, also at the border of these tetrads. Firstly, the unified expression and storage principle of Global discrete grids are studied, and some methods are put forward based on global diamond grid, including encoding, coordinate transformation and faces extraction. Then, seamless expression algorithm is designed and achieved. Finally, seamless expression of the global multi-resolution DEMs can be carried out with a method of making a tiny adjustment of node subdivision.4) Implement simulation and visualization of dynamic LOD of global multi-resolution terrain. In order to realize the seamless modelling and visualization of global high resolution terrain, dynamic LOD based on multi-resolution half-edge structure and diamond block are proposed. Firstly, on the basis of the previous techniques and algorithms, different methods of crack elimination are researched, including internal nodes, boundary nodes and nodes at the pole. Then, organization and scheduling of the terrain data in blocks are researched. Finally, the algorithm of dynamic LOD model is proposed. The model based on multi-resolution half-edge structure can ensure the seamless subdivision of internal node, so the crack elimination between blocks becomes simpler. Because of simplification in the blocks in accordance with the terrain relief, so there is no data redundancy. While simplification between some blocks doesn't involve elevation adjustment, so there is no terrain distortion.5) Design and develop an experimental system. By using C++ language and DirectX tools, an experimental system is developed to verify the validity, feasibility, and effectiveness of the proposed algorithm in this paper, including comparing with restricted quad-tree structure by using GTOPO30 and local terrain data. Its main functions include the implementation of these algorithms, such as seamless algorithm of local terrain, global terrain and dynamic LOD. The statistical analyses of experiment include storage space, the number of rendering triangle, the number of quadrilateral, and so on. It also includes visual interactive operations and the I/O of model files. The first experimental results show that the adaptive seamless modelling of 3D terrain can be realized based on multi-resolution half-edges. Compared with the "restricted quad-tree", this method does not need to repeatedly check the level difference between the adjacent nodes, and with the increase of partition level, reduction rate of the number of grids and rendering data are gradually increasing, reaching 13.9% and 12.2% in 7th level. The second experimental results show that seamless expression of the global multi- resolution DEMs can be carried out with a method of making a tiny adjustment of node subdivision. Compared with the traditional methods, the method in the paper can solve the crack problem from the underlying data structure. By adjusting three parameters, subdivision threshold ?, maximum level Lmax and minimum level Lmin, different simplification results can be achieved in the land and ocean respectively. When ? is 500 meters and the maximum level is ten, the method based on restricted quad-tree structure would render 91922 triangles, 15.11 percent, more than the method based on multi-resolution half-edge structure. In order to realize efficient simulation and seamless visualization of global high-resolution terrain, a seamless modelling of global multi-scale DEMs is discussed based on multi-resolution half-edge structure and diamond block. The third experimental results show that multi-resolution half-edge structure could guarantee no cracks in a block, while the seamless expression between blocks can be realized because of the synchronous subdivision and symmetrical distribution of the nodes in the bounder with the restriction of subdivision. Compared with the traditional method, the method in this paper does not need to repeatedly check the level difference between the adjacent nodes in a block, with no data redundancy, without terrain distortion and small amount of calculation.