Research On The Key Algorithm Of 3D Real-time Dynamic Multi-solution Display Of Large-scale Terrain

Three-dimensional terrain modeling and visualization of virtual reality have always been important in earth-science research areas, and 3D Real-time Dynamic Display of large-scale terrain is a very challenging subject. For a wide range of topographical features, even in the current rapid developing conditions of hardware, it is still difficult to meet the both requirements of realistic visuals and a higher frame-rate. Therefore, many scholars put forward some effective solutions, but there are a few problems:(1) Use more static LOD methods to realize the accuracy and speed of topographical expression. They can reduce the amount of data and improve the display speed to a certain extent, but have only less levles, and give us a strong sense of jumpping when LOD level switches.(2) Try using continuous or multi-resolution LOD algorithms and achieve good result, but it is difficlut to determine the level of real-time display and hard to apply to large-scale terrain.(3) Owning to the simple rectangular arrangemen of regular grid, the data model used is generally RSG, which is easy to be read and processed by computer, but it contains a large number of data redundancies and is difficult to convey the terrain detail accurately. Irregular sampling points have less redundancy and are convenient to show the physical details, but it is hard to apply to dynamic multi-solution display because of the unregularity of TIN and complexity of topological structure.(4) The reason of overlarge data amount and low display speed is the poor efficitncy of acceleration algorithm, how to combine it with LOD structure to balance the accuracy of judgment and show speed is a problem demanding prompt solution.According to these problems, this paper generates from the model simplification and acceleration algorithms and summarizes the current terminal dynamic-expression problems based on RSG and irregular sampling points, then starts from the Algorithm structure and software-designing under the existing conditions of hardware, and finally builds high-quality and real-time dynamic display of terrain through constructing reasonable data model, combing the scene-blocked, visibility-culling, external storage scheduling with levels of detail algorithms. The research results include:(1) Defining the time-characteristics and importance of virtual reality, indicating that the real-time and real-show are the most important challenges which the current computer graphics is facing, exploring the content, procedures and methods of dynamic display of large-scale terrain and proposing adaptively dynamic building-process and algorithms of multi-resolution LOD through analyzing the respective advantages and disadvantages of RSG and TIN which are DEM's two important forms of expression and summarizing the algorithmic difficulty.(2) Exploring the tree structure and corresponding quadtree and binary level models of regular grid. Considering the algorithmic versatility and speed requirement of large-scale terminal display, paper proposes the pre-treatment strategy which combines top-down level-splitting with down-top parameter-calculating and does lots of work ahead of schedule through establishing efficient data structure of quadtree node. Algorithm judges the level of detail in the stage of real-time dynamic expression according to the conservative screen-error, which can weaken the sense of switching pop to an extreme, and finally gives a method to eliminate the cracks between the different LOD levels by the appendix of splitting-points.(3) Starting from the irregular sampling points and studying the method's shortcomings of local importance judgment. By analogizing the principles of map generalization, paper introduces the 3D Douglas-Peucker algorithm (3D_DP), which has achieved good results, to global importance judgment of sampling points and lays a solid foundation for realistic terrain display.(4) In accordance with the advantages and weaknesses of LOD method of TIN, this paper begins from aspect of sampling points, introduces the Douglas-Peucker algorithm to terrain LOD and proposes a new method of topographical dynamic expression, which combines the 3D_DP, hierarchical quadtree with TIN, through splitting sampling points by hierarchical quadtree structure and constructing TIN inside quadtree nodes. This method classifies the points from the perspective of global importance firstly, constructs quadtree spatial index by isolated split so as to integrate the structural advantages of quadtree on RSG and TIN on sampling points and eliminates the dependency between nodes, then determines the drawing level of quadtree and inserted order and number of sampling points according to the view-distance and simulated error, and finally remove cracks between nodes by adding splitting-points. Anyway, this algorithm ensures not only the frame rate but also the overall accuracy.(5) Aiming at the LOD algorithm of RSG and sampling points which has proposed by this paper, Author also study the data organization and accelerating method of large-scale terrain. It starts from the scene-splitting way and storage structure of sub-block and eliminates the cracks by skirts method, and then casts aside the invisible part between blocks or nodes according to the spatial relationship of node bounding sphere and view-frame. Besides, considering the node-obstructing which is due to the topographical relief, this paper bases on the occlusion culling principle of single point to analyze the sound pre-treatment and simple judge method of ridgeline occlusion and gradually extend to the culling of quadtree nodes. For the sub-block, in order to reduce the real-time dispatch from the internal and external storage, the algorithm divides the memory into two parts, visible and extended areas, and adapts incremental update method and employs multi-thread mechanism based on LOD simplification and data transmission to realize the fast real-time dynamic display of terrain.Based on the research ideas and algorithm theories of this paper, the author designs and develops a corresponding prototyping system to illustrate effectiveness of the algorithm from the experimental point of view, and it should be a reference to LOD simplification and display-speeding for the other related models.