Studies On Mesh Segmentation Algorithms And Techniques

Under the development of computer technology and measuring techniques, reverse engineering has attracted research attention in the field of CAD/CAM recently. Reverse engineering uses technology of CAD/CAM and advanced manufacturing to transform the products into CAD models. Firstly, point cloud data are obtained from the entities. The triangulation of point cloud is carried out then to have another form of digital data, namely triangular meshes. Triangular meshes reserve the geometry of point cloud and deduce the topology from the triangulation. The process of point cloud and triangular meshes is the research area focus of Digital Geometry Process, Computer Graphics, Maths and Computer Science etc. Thus it has both the theoretical and practical value.The dissertation reviews the history of reverse engineering and the techniques of measurement at the beginning. Then we focus our attention on mesh segmentation. The forms, characteristics and effects of segmentation are discussed. The related algorithms and techniques are the interest of the dissertaion, so they are illustrated and analyzed intensively. As the core function of reverse engineering software, surfacing is the aim of our mesh segmentation algorithms. According to the characteristics of surfacing and surface identification in reverse engineering, the identification of salient region and automatic seamless segmentation are adopted as the form for mesh segmentation. The conesponding algorithms of mesh segmentation and related issues in implementation are studied from the view of software developers.In the form of salient region identification, the dissertation proposes a mesh segmentation algorithm based on the principals of watershed. The algorithm discerns the salient region on mesh precisely and segments the mesh into regions where curvature changes mildly. The segments can satisfy the requirements for quadric surface identification and NURBS approximation in Reverse Engineering. Moreover, the dissertation analyzes the calculation of discrete curvature when noise corrupts meshes. Various algorithms for mesh smooth and calculation of discrete curvature are discussed and lay a foundation for raising a noise robust mesh segmentation algorithm. The algorithm remains to be simple and practical.Compared with previous techniques (such as mesh smooth) to deal with mesh noise, the noise robust mesh segmentation proposed in the dissertation has the advantages in several ways. Namely, our algorithm doesn't have to specify certain parameters and doesn't involve the user input to judge the existence of mesh noise. In comparison with "Normal Vector Voting", noise robust calculation of discrete curvature, our algorithm also has the advantages in simplicity of calculation and absence of parameters set by users. The novel way to segment the noisy mesh is realized in RE software.In the form of seamless mesh segmentation, the dissertation illustrates the work below: a) On the foundation of mesh parameterization which uses simplified mesh as the parameter domain, the dissertation proposes a novel algorithm which applies edge-collapse to construct the parameter domain. b) The globally smooth parameterization raises edge classification in order to achieve a global smoothness of parameterization. Inspired by the algorithm, the dissertation proposes a direct way to set up the results of edge classification. c) Based on the new algorithms, the dissertation makes use of the results of edge classification to insert new vertices into the edges of original mesh and re-triangulate the mesh. The new algorithms and results are applied to automatic surfacing in RE. Previous mesh parameterizations which base on simplified mesh always simplify mesh by removing vertices and re-triangulating the left hole. Adversely, the dissertation adopts edge-collapse, the mainstream technique of mesh simplification. The usage of edge-collapse can construct the base domain that has triangles in better shape. This can significantly improve the effect of parameterization. Compared with GSP (Globally Smooth Parameterization), the results of edge-classification are set up directly from the results of parameterization in the dissertation. Thus the algorithm is simple and quick. The results of edge-classification are used to set up linear equations of parameterization in GSP. However, the dissertation raises new algorithms that insert new vertices, re-triangulate the mesh, map the collapsed vertices into original mesh and segment the original mesh seamlessly. The segmenting patches are isomorphic to triangles of the simplified mesh. The pair-wise combination of triangles is conducted on simplified mesh and quad-rangulates the original mesh. Our algorithm not only avoids solving linear systems of equations, but also avoids calculation for mapping parameterization results from base domain to the original mesh. These complex operations are quite common in previous algorithms.