Spectral mesh segmentation

Polygonal meshes are ubiquitous in geometric modeling. They are widely used in many applications, such as computer games, computer-aided design, animation, and visualization. One of the important problems in mesh processing and analysis is segmentation, where the goal is to partition a mesh into segments to suit the particular application at hand. In this thesis we study structural-level mesh segmentation, which seeks to decompose a given 3D shape into parts according to human intuition. We take the spectral approach to mesh segmentation. In essence, we encode the domain knowledge of our problems into appropriately-defined matrices and use their eigen-structures to derive optimal low-dimensional Euclidean embeddings to facilitate geometric analysis. In order to build the domain knowledge suitable for structural-level segmentation, we develop a surface metric which captures part information through a volumetric consideration. With such a part-aware metric, we design a spectral clustering algorithm to extract the parts of a mesh, essentially solving a global optimization problem approximately. The inherent complexity of this approach is reduced through sub-sampling, where the sampling scheme we employ is based on the part-aware metric and a practical sampling quality measure. Finally, we introduce a segmentability measure and a salience-driven line search to compute shape parts recursively. Such a combination further improves the autonomy and quality of our mesh segmentation algorithm.