Quadric Error Metric Edge Collapse Algorithm Based On Vertex Degree

Mesh model representation method is a valuable 3D objects representation method and it is widely used in many computer graphics systems such as computer graphics, virtual reality, geographic information system and medical image system. With the development of science and technology, 3D mesh models constructed and used in those fields are more precise and more complex. However, such complex models are not always required because they are difficult to store, transmit, and render. It is useful to have simpler versions of complex models in many cases. Model simplification is to provide approximate models of complex models by reducing triangles, edges and vertices and the simpler models keep the basic geometrical shape of the originals.These years, the technique of model simplification has become a hot topic and many efficient model simplification techniques have been provided. But mesh model simplification is a NP problem and the conflict between the simplification speed and the simplification precision always exists and there isn't a simplification algorithm that can reach optimal balance between speed and precision. A good simplification algorithm can only reach sub-optimal balance between speed and precision.After some error evaluating methods and some existing model simplification algorithms are surveyed, a new algorithm is presented, which is named quadric error metric edge collapse algorithm based on vertex degree. The new algorithm is based on weighted quadric error metric and edge collapse algorithm. Quadric error metric and edge collapse algorithm needs much computation on high-degree vertices, and contracting the edges adjacent to this kind of vertices often makes some key points to move so as to lose some important features. The new algorithm overcomes the drawbacks by assuming the topology of the model and using vertex degree in controlling the simplification procedure. The new algorithm will overcome these problems. Moreover, the new algorithm can prevent long triangles and optimizes the quality of meshes. Compared with Garland algorithm, the new algorithm speeds up the model simplification procedure and improves the quality of model simplification.This thesis is dedicated to a high efficiency method on simplifying triangle mesh models. Firstly, some basic concepts about triangular mesh models and error evaluating methods are introduced, and then some existed model simplification algorithms are surveyed; Secondly, quadric error metric edge collapse algorithm based on vertex degree is described in details; Lastly, the new algorithm is implemented with Visual C++ and OpenGL and a few mesh models are simplified using this system to prove the validity of the new algorithm.