Research On An Algorithm For Mesh Segmentation Based On Singularities And Feature Edges

Mesh models are widely utilized in the fields of computer graphics, computer vision, reverse engineering and so on. Mesh segmentation technology plays a vital role in digital geometry processing, such as mesh parameterization, mesh simplification, shape matching, geometry deformation and texture mapping. In this paper, an algorithm for mesh segmentation is studied based on topological structure and geometrical characteristics of mesh models.Mesh segmentation is realized by adopting the singularity-based algorithm. Singularities are extracted based on the topology structure of the mesh model. A particle is placed on each edge which is incident to singularities, and then begins moving along the edge from the singularities simultaneously. When a particle reaches an ordinary vertex, it moves to the opposite edge at that vertex. When a particle reaches a singularity, boundary vertex, vertex on the trajectory of the other particle, or conforms to the right hand rule, it stops. After all particles stop, their trajectories form the boundaries of the partitions. Experimental results show that structured partitions can be realized by using the algorithm.An algorithm for feature extraction of mesh models based on feature edges is studied. The weight of an edge is determined by the angle between the two normal vectors of its adjacent quadrangles, after which an edge weight histogram is plotted. For different types of mesh models, threshold values of the edge weight are calculated adaptively according to the edge weight histograms using different methods. Median filtering is employed to reduce noise in the edge weight. All edges whose weight is greater than the weight threshold are considered as feature edges and collected. These features edges are sorted by weight in descending order, so that feature curves are grown from them in this order. If a feature edge is on an already grown feature curve, it will not grow. When the growing stops, feature curves are discarded whose proportion of feature edges is less than a given threshold. Experimental results show that obvious features can be extracted by using this algorithm.Convex decomposition of mesh models is achieved based on the point-to-point visibility. Patches are obtained on the basis of parting lines which are formed by using the algorithm based on singularities and feature edges. Convexity degree between adjacent patches is measured using the portion of mutually visible pairs of points out of the total number of pairs. And then the two patches with maximum convexity degree are sought and fused. In course of seeking the pair of patches with maximum convexity degree, one with a longer common boundary will be selected if they have the same convexity degree. After patch fusion, the adjacent information of the generated patch and its adjacent patches is updated, and the convexity degree of these pairs of patches is recalculated. The above procedure of patch fusion and convexity degree recalculation will be repeated, until the maximum is less than a setting threshold. Experimental results show that the decomposition coincides with the concave-convex quality of surfaces without over-decomposition.Segmentation, rendering, rotation and scaling of mesh model are achieved in the environment of MFC and OpenGL.