Study Of Multi-Resolution Modeling Key Technologies For Large-Scale Terrain Dataset

Terrain model has been widely used in many fields such as 3D games, flight training, environmental simulation for the battlefield, geological information system (GIS), virtual reality (VR), and so on. At present, the study about terrain model has been applied into other fields which include aeronautics, airborne system, navigation system in 3D terrain,forecast for geological disaster and so on. Recently, with the rapid development of the digital measuring techniques, terrain model can represent more detailed features and then terrain scene turns to be more complicated. Accordingly, rendering large scale or super large scale terrain scene has to be supported by external memory. However, the obvious velocity difference between external memory and RAM has been a bottleneck in dealing with large scale data. Therefore, it is extremely meaningful for studying external memory management in terrain model, which is the basic for rendering terrain scene with large data and also becomes one of the focuses studied by the domestic and overseas scholars.Simplifying terrain model is not only the key technique of rendering terrain scene with large data, but also increasingly draws attention from fields such as 3D model retrieval, terrain navigation, simulation of water flow and so on. It is difficult for most model simplifying algorithms to consider both the efficiency of algorithms and the quality of the approximations. Therefore, researchers usually focus on one side according to the above different demands. The goal of the former is to improve the algorithm efficiency, and then meet the requirement of the graphic hardware. In scientific visualization field, the quality of approximations is more important, that is to say, the approximations should be of high accurate even with higher simplification ratio. With the development of scientific visualization, however, applications of many researching fields also have included rendering the dynamic scene. Therefore, it is extremely significant to develop an effective method for rapidly producing high-quality multi-resolution approximations of the original model.In view of this, we have deeply studied on these aspects including data organization based on large-scale terrain data set, multi-resolution modeling methods and their key techniques etc. The main work and contributions in this paper are just as followed.(1) The research advances about out-of-core data organization, multi-resolution modeling methods and their key techniques have been introduced in details.The classical methods and latest developments proposed by domestic and overseas scholars in multi-resolution modeling field have been classified and described. The key problems are also analyzed and summarized. There are mainly the following several aspects:①Out-of-core technique for large data set;②data fitting of approximations and simplification method of terrain model;③error metric for the simplification model;④cracks stitching of multi-resolution models and synthesis of multi-textures of terrain model.(2) The terrain out-of-core model has been studied for the terrain model with large-scale data set. Based on the physical model and logical model, the data organization method and its scheduling strategy have been proposed.By analyzing traditional multi-resolution external memory model, which takes image pyramid technique, the problem of redundant resolution storage was identified. We proposed the terrain data organization method and the data scheduling strategy, including five steps: data reorganization of the original terrain, multi-resolution logic model for external memory, clustering analysis on multi-resolution terrain, coding of nodes in a cluster, and incremental data scheduling.Detailed works are just as follows:①Division of physical data blocks for the various data sources has been completed, which considers both the constraint conditions of the logical model and the expansibility of physical model.②Logical multi-resolution model was created in terms of terrain fluctuant features. There are no adding physical storages of multi-detailed layers in such model, but building a multi-resolution logical model index on the basic of changeless physical model. Therefore, under the situation of no adding redundant physical storage, the data loaded into the RAM will be radically reduced.③Clustering analysis for the logical model has been done, according to the principle that static errors are similar. All the data blocks in each clustering can constitute a closed terrain area. So, once a certain clustering is determined by needs of RAM, we can lessen searching scope, directly carrying such data into RAM without losing the data block.④Building multi-resolution filled curves, we can arrange sequence and code for data block in every clustering. By this method we can intercept continuous data block by needs of RAM according to local features of filled curves.⑤Incremental data scheduling has been adopted to further reduce data carried into RAM, which can improve the responding speed of I/O operations.According to five steps above, multi-resolution external memory organization has been performed, which data carried into RAM has been reduced sharply. By clustering analysis and incremental data scheduling, efficiency of carrying data into RAM has been improved obviously. (3) The terrain model simplification method has been proposed based on terrain features, using the idea of discrete particle swarm algorithm.After analyzing the existed problem in classical hierarchical model, we put forward the method that combine the hierarchical model simplification with the swarm intelligence algorithm. What is new in this method is that the particle has been redefined as a set of feature bits, and a new evaluation function has been proposed. It is better to measure the surface of an approximation model. Based on it, an optimal particle can be produced and has been taken as the heuristic information to accelerate the simplification. As a result, the simplification across layers has been performed. Therefore, the efficiency of our method and the quality of approximations are improved greatly.The main works are following:①A RAM data structure was proposed, which suitable for external memory data loading, namely connotative hierarchical structure (CHS). After proving the properties of connotative hierarchy theoretically, we explained the relation between the layer information of a node and its position, and the index equations between father nodes and their child nodes each other.②In order to put all the detailed features of terrain into the consideration of error function, the concept of simplification field was presented.③A new divergence function has been put forward based on simplification areas and its equations have also presented. In virtue of this function, the simplification model is of quite high accuracy even as the higher simplification ratio, due to the entire characters and local characters in model are both considered.④Redefining particle structure as a state of simplification model and carrying out particle compressing storage by use of CHS.⑤Setting up particle evaluating metric based on the divergence function and simplification ratio of the model, we can keep the convergence of the algorithm, and accelerate the process of the optimal multi-resolution terrain model.(4) These methods have been studied in this paper on confirming adaptively the multi-threshold of error metrics in the simplification model.Analyzing the disadvantages in traditional algorithm using the unified error threshold calculating method, we proposed the multi-threshold error strategy according to the higher quality demands of the scientific fields. By this strategy, we resolved the problem how to improve the model accuracy. Firstly, the base of our work is an algorithm for selecting the feature points of terrain model presented by CHS. And then we proposed the corresponding strategies to deal with three various terrain features.①Aiming at the terrain that combines canyon with plateau, we put forward the method of bisection threshold based on grain calculation, because of their clear division features of terrains. After rough division for terrain, we respectively take the different error calculating and threshold to improve the accuracy of the simplification model.②Aiming at the rugged terrain without obvious division, we put forward self-adaptability model simplification method based on merging feature areas. After merging the areas with the similar matching degree, we neglect the nodes that meet error tolerance, and then made a further division for some complicated terrains. The advantage is that it can produce the accurate simplification models and improve efficiency of the algorithm.③Aiming at the flat terrain without division features, we made a mend on the basic of the second method and put forward the strategy of terrain fluctuant degree. We focus on resolving the problems how to unite multi-resolution feature fields and divide irregular simplification areas, then enlarging the grain of merging the feature areas. Thus, it took short time to combine the feature areas and divide the various simplification areas. Compared with method of②, the model accuracy of model and the efficiency of the algorithm are both slightly improved.The above three methods are all tested on real data, and the results showed they can achieve the good balance between the quality of approximations and the efficiency of the algorithms.(5) This paper has studied the continuity of multi-resolution models and the multi-texture synthesis of terrain modelsThe continuity of multi-resolution mesh models has always been a difficult problem that has to be considered and resolved. Many algorithms produced a lot of redundant triangles due to cracks stitching, which led to debase the efficiency of good algorithm in some extent, and thus the self-adaptability of simplification models is also been declined. In this paper, we sum up all the cracks stitching methods before and then put forward a cracks stitching method combining our CHS with terrain features. The redundant triangles have been deceased greatly in virtue of ignoring the invisible cracks in those flat areas, and accordingly improved the whole performance of algorithm. The experimental results showed that our seamless model is of the three characteristics:①mesh continuity;②changeless accuracy of multi-resolution model;③changeless terrain curving surface.Texture plays an indispensable role on the terrain scene, but the data quantity of texture model usually exceeds the geometrical model of the terrains. For this problem, we put forward two kinds of resolving methods. One is to implement the multi-resolution texture storage and scheduling by use of our external memory model; the other is to meet the demands of terrain roaming by synthesis of the real-time texture according to the small block texture data and the terrain geometrical features. The experiments showed that the texture model and the geometrical model have been integrated tightly.On the whole, certain other algorithms are faster or generate higher quality approximations than ours, but they typically do not meet the capability of our algorithm in both areas. In our whole framework, there are many key technologies, including terrain out-of-core model, data scheduling, model simplification, cracks stitching, multi-texture synthesis and so forth. The results in this paper are theoretical significant and of application value in the aspect of multi-resolution modeling of terrains, and in the application fields of considering the both requirements of rendering and scientific computation.