【作者】 张慧杰；

【导师】 孙吉贵；

【作者基本信息】 吉林大学 ， 计算机软件与理论， 2009， 博士

【摘要】 多分辨率地形简化模型不仅在户外场景绘制领域有着广泛的应用,而且在科学计算可视化研究领域也越来越受到关注。由此可见,兼顾两种领域双重需求的多分辨率建模技术有着重要的研究意义和应用前景。本文的主要研究内容包括:①建立了面向大数据集的地形外存物理模型和逻辑模型。分析了传统多分辨率外存模型通过采用影像金字塔技术,对相同地形以不同分辨率冗余存储的问题,提出了不增加物理存储的多分辨率外存框架,使载入内存的数据量大大减少。②根据静态几何误差相近、地形空间封闭的原则,在逻辑模型基础上进行了聚类分析。提出了基于多分辨率的空间填充曲线自动生成算法,实现了基于聚类的局部数据检索、更新和增量调度,使数据载入内存的效率显著提高。③构造了一种新的隐式层次结构,给出了节点位置与层次之间、父子节点之间相互索引的计算公式和理论证明。分析了经典的逐层简化算法存在的问题,提出了层次模型简化技术与群智能算法相结合的模型简化方法。该方法在保证简化模型的自适应性和精度要求的同时大大提高了简化算法的效率。④分析了传统算法中采用统一误差计算方法和阈值的缺点,结合科学计算领域对高质量简化模型的需求,我们提出了自适应确定误差阈值的方法,使多分辨率模型在简化比例较高的情况下,仍然保持较高的模型精度。⑤针对大部分算法在修补多分辨率模型裂缝时产生许多冗余三角形的问题,提出了结合裂缝可见性的多分辨率模型裂缝修补算法。研究了多分辨率纹理数据的外存组织与调度以及多纹理合成技术,其合成的纹理模型与三维几何模型具有良好的结合性。更多还原

【Abstract】 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.更多还原