Nearly convex segmentation of polyhedra through convex ridge separation

• Published in: Computer aided design 2016-09, Vol.78, p.137-146
• Main Authors: Liu, Guilin, Xi, Zhonghua, Lien, Jyh-Ming
• Format: Article
• Language: English
• Subjects: Convexity; Segmentation; Shape approximation
• ISSN: 0010-4485; 1879-2685
• DOI: 10.1016/j.cad.2016.05.015

Decomposing a 3D model into approximately convex components has gained more attention recently due to its ability to efficiently generate small decompositions with controllable concavity bounds. However, current methods are computationally expensive and require many user parameters. These parameters are usually unintuitive thus adding unnecessary obstacles in processing a large number of meshes with various types and shapes or meshes that are generated online within applications such as video games. In this paper, we investigate an approach that decomposes a mesh P based on the identification of convex ridges. Intuitively, convex ridges are the protruding parts of the mesh P. Our method, called CoRiSe, extracts nearly convex components of P by separating each convex ridge from all the other convex ridges through the new concept of residual concavity. CoRiSe  takes a single user parameter: concavity tolerance which controls the maximum concavity of the final components, as input, along with other two fixed parameters for encoding the smoothness term of graph cut. We show that our method can generate comparable (sometimes noticeably better) segmentations in significant shorter time than the current state-of-art methods. Finally, we demonstrate applications of CoRiSe, including physically-based simulation, cage generation, model repair and mesh unfolding. •A segmentation method produces meshes with bounded concavity.•The method detects and separates protruding parts called convex ridges.•The proposed method requires very few user parameters.•The segmentation can be done faster than the existing approaches.•Applications in simulation, deformation, mesh repair and unfolding are shown.