Chinese Journal of Computers   Full Text
Title	A New Simplification Method for Terrain Model Based on Divergence Function
Authors	ZHANG Hui-Jie1),2) SUN Ji-Gui2) LU Ying-Hua1) LU Nan2) WANG Yuan-Zhi3)
Address	1)(College of Computer, Northeast Normal University, Changchun 130117) 2)(College of Computer Science & Technology, Jilin University, Changchun 130012) 3)(Computer Department of Anqing Normal College, Anqing, Anhui 246011)
Year	2009
Issue	No.5(962—973)
Abstract &   Background	Abstract This paper presents a fast simplification method for the terrain model using the discrete particle swarm algorithm based on the quad-tree hierarchical structure. What is new in this paper is that the particle has been redefined as a set of feature points. And then each particle presents a candidate solution of the approximation model. In order to compress those particles, a connotative quad-tree hierarchical structure and its index technology are proposed in this paper. Usually, an error measure is very important to an approximation. Therefore, this paper proposes a new divergence function, which is better to measure the surface of an approximation. Based on it, the evaluation function of particle is defined. Since both the detailed feature and the simplification ratio are also taken into account, the approximation is higher quality. Finally, the optimal particle is taken as the heuristic information to accelerate the simplification, so that these particles can converge rapidly to the optimal approximation. As a result, the method is of higher efficiency. By the experiments on many benchmark terrain models, the efficiency of the proposed method and the quality of approximations are improved greatly, compared with the typical hierarchical simplification algorithms. Keywords quad-tree hierarchy; simplification model; evaluation function; DPSO algorithm; terrain features Background As one of important components of virtual reality, terrain model has been widely applied in numerous fields, such as movies, geographical information system (GIS), cartography, games and 3D models retrieval. However, the major challenge encountered in modeling terrain is that billion of samples are contained in large terrain height map. Thus, many scholars have taken GPU, which can greatly improve the rendering efficiency of the terrain. Even so, this technique can not be competent for rendering interactively the massive data in the terrain model by brute force. Since the previous simplification algorithms adopt a strategy of traversing each level in the hierarchy of model, they can not effectively achieve a trade-off between efficiency of the algorithm and the quality of the approximations. This paper puts forward a fast simplification method for the terrain model. It is new and original to integrate the discrete particle swarm optimization with the hierarchical structure. In detail, each particle is represented as an approximation using the hierarchical structure. By the evaluation function proposed in this paper, the optimal particle can be produced. The error measure strategy considered not only the detailed terrain feature, but also the global contour feature. Therefore, the approximation is of better quality and of higher adaptability. By the experiments conducted on many benchmark terrain models, it is showed that the algorithm is of higher efficiency, compared with other typical simplification methods. This work is supported by National Natural Science Foundation of China under grant number 60773097 and 60603030, and Science Foundation for Young Teachers of Northeast Normal University (20081003). All the research results in this paper have been applied in an actual simulation training system about several different airplanes, and they are running well at present.