Implementation And Improvement Of A Quadrilateral Mesh Simplification Algorithm

Computer has become a key instrument in areas of movie production, CG animation, medical imaging processing and artistic creation, thanks to the rapid advancement of computer graphics in recent years. Mesh model is widely used for blanking, shading and rendering due to its convenience. Structured quad meshes provide a better surface approximation for curved surfaces which gained a lot of attention lately. In the pursuit of enhanced depth and sense of reality, people often result to high precision sampling or utilizing complex and detailed mesh during modeling when describing multiple features. In this approach, face count in the mesh becomes enormous, creating extensive loads during calculation, manipulation, storage, operation processes that exceeds capability of current hardware. Many algorithms of mesh model simplification have been proposed in order to reduce the vertex number while maintaining model quality.In this thesis, we studied development and application of quad mesh simplification algorithms. Definition and significance of mesh simplification is discussed. Mesh simplification algorithms are presented in four categories, vertex clustering, vertex collapse, edge collapse and face collapse. Typical algorithms are evaluated in terms of efficiency and effectiveness. Ideology of edge collapse method algorithms based on QEM is also evaluated.Definition and characteristics of quad mesh dual structure is discussed. Basic operations in dual structure chord are explained in detail by showing its effect on quad mesh face numbers.In this thesis, we designed an algorithm with targeted edge collapse operation considering the connectivity of quad meshes. Model quality is ensured by a set of effective simplification priority strategy control. Priority measurements include three parts, i) maintaining model geometry with QEM calculation; ii) calculating maximum length of collapsed edge; iii) calculating the changes of vertex valence in order to preserve geometry of quad meshes. Algorithm can rebuild triangle or triangle/quad mixed meshes into pure quad meshes. This algorithm can generate high quality mesh simplification with good simplification efficiency and is suitable for all types of grid meshes.Drawbacks in this algorithm are discussed and presented with various solutions. Future works on grid mesh algorithm are also mentioned.