Study On The Extraction Of Quadric Surfaces From 3D Mesh

With the continuous progress of technologies in computer software and hardware, 3D scan and modeling technologies in graphics field also have made great advances. In the fields requiring precise 3D models, such as reverse engineering, image animation and computer games, digitize 3D graphs are emerging in multitude and widely applied. For the model submitted to computer processing, the solid model is firstly scanned by scanner to obtain messy point cloud swarm, based on which complex mesh polyhedrons are then generated. Finally, extraction of quadric surfaces from these polyhedrons is performed to reconstruct solid model computer. Surface extraction technology has great impact on the quality of reconstructed model. Therefore, extraction of quadric surfaces from mesh polyhedron is always the key technology in graphics and hot research subject.Firstly, this thesis reviewed the background knowledge, progress and application of recovering quadrics in 3D meshes. The principles of each typical algorithms were illustrated, the realization methods and performances were also explained.Secondly, this thesis developed a quadrics extraction algorithm based on hierarchical clustering. After the model surface was divided into small regions with designated features, the algorithm hierarchically clustered the given shape into connected regions, which can be approximated by basic quadrics ascribing to the given set. Different from the bottom-up local greed strategy in region increase, our hierarchical clustering extracting algorithm employed global greed strategy. In addition, the core of this algorithm was set in selecting optimal clusters for combination operation, instead of primitive cluster extension.Thirdly, a fast algorithm for the extraction of quadric surfaces was proposed to approximate the given 3D mesh model by a group of overlapped ellipsoids. This algorithm can solve these two problems: computing the optimized fitting ellipsoid inside the given 3D mesh; selecting the most important (minimum repetition) subset from substantive candidate ellipsoids.Finally, the research work in this thesis was summarized and the future research direction was prospected.