Bottom-up 3D Shape Segmentation

3D shape segmentation is a fundamental research topic in computer graphics. On one hand, segmentation assists texture mapping, geometry-image creatio, remeshing, simplification and lots of other applications. Recently, an apparent trend in computer graphics research has seen growing interests in high-level analysis and process of geometry data, focusing more on shape structures than geometric details, and segmentation of a 3D shape into semantic parts is a fundamental task in high-level shape analysis and processing. In recent years, co-segmentation of a set of 3D shapes, i.e., segmentation of the shapes as a whole into consistent semantic parts with correspondences, has received increased attention. It has been demonstrated that more knowledge can be inferred from multiple shapes rather than an individual shape and co-analysis of the set produces better segmentations than the single-shape algorithms. However, extraction of appropriate knowledge inherent to multiple shapes for consistent segmentation remains challenging.On the other hand, decomposing a complex shape into simpler primitives is also one of the most fundamental geometry problems. The main motivation is that most computation and manip-ulation tasks can be more efficiently executed when the shapes are simple. We are interested in a shape decomposition problem where the simple primitives sought are pyramidal. A shape is pyra-midal if it has a flat base with the remaining boundary forming a height function over the base. The simplicity of pyramidality mainly owes to its functional nature, since processing of pyramidal shapes is confined to 2.5D. The application which originally motivated our study of pyramidality is 3D printing via Fusion Decomposition Modeling (FDM). FDM is one of the dominant technologies for 3D fabrication. Its layer-based additive printing scheme requires support material to be injected (and later removed) to produce overhangs in a fabricated shape. If the shape is pyramidal, then no support material is needed, leading to savings in both material and print time.In this dissertation, we focus on the study of 3D shape segmentation aiming at different appli-cations. The main contributions of this dissertation include:1. We present a novel bottom-up algorithm for automatically co-segmenting a set of shapes from a common family into consistent parts. Starting from over-segmentations of shapes, our approach generates the segmentations by grouping the primitive patches of the shapes directly and obtains their correspondences simultaneously. The key idea here is to define multiple features on those over-segmented patches so that those semantically corresponding patches will lie in the same subspace of each feature space. In this way, we turn our clustering problem into a subspace clustering problem. Experimental results have shown how our algorithm jointly extracts consistent parts across the collection in a good manner.2. When combining information from different feature spaces, the traditional way is to concate-nate the different features into one larger feature descriptor and then cluster directly in this larger feature space. However, we propose a new formulation of optimization with a consis-tent penalty, which facilitates both the identification of most similar patches and selection of master features for two similar patches. Therefore the affinity matrices for various features are sparsity-consistent and the similarity between a pair of patches may be determined by part of (instead of all) features. Usually multiple features will be used during shape analysis and geomatry processing, so we think that our new way of combining information from different feature spaces will be useful for other applications as well.3. We introduce a bottom-up algorithm for approximate pyramidal shape decomposition. The general exact pyramidal decomposition problem is NP-hard. We turn this problem into an NP-complete problem which admits a practical solution. Specifically, we link pyramidal decomposition to the Exact Cover Problem (ECP). Given an input shape S, we develop clus-tering schemes to derive a set of building blocks for approximate pyramidal parts of S. The building blocks are then combined to yield a set of candidate pyramidal parts. Finally, we employ Knuth’s Algorithm X over the candidate parts to obtain solutions to ECP as pyramidal shape decompositions. Our solution is equally applicable to 2D or 3D shapes, and to shapes with polygonal or smooth boundaries, with or without holes. We demonstrate our algorithm on numerous shapes and evaluate its performance.4. Pyramidality is a relatively new and unexplored shape property. Pyramidal shapes are optimal for molding, casting, and layered 3D printing. Here we make a preliminary attempt and introduce the first construction algorithm for approximate pyramidal decomposition. We hope that our work can inspire more works for exploring this nice shape property. Moreover, the key to convert the shape segmentation problem to the exact cover problem is to construct the set of candidate parts fulfilling some desired property. In our case, the desired property is pyramidality, but it could be any other shape property like convexy. We believe that this key insight could be useful and provide a new way of solving other shape segmentation problems.