Replaceable Substructures for Efficient Part-Based Modeling

1KAUST     2INRIA Grenoble     3Universiteit Utrecht    4University College London    

Eurographics 2015


A popular mode of shape synthesis involves mixing and matching parts from different objects to form a coherent whole. The key challenge is to efficiently synthesize shape variations that are plausible, both locally and globally. A major obstacle is to assemble the objects with local consistency, i.e., all the connections between parts are valid with no dangling open connections. The combinatorial complexity of this problem limits existing methods in geometric and/or topological variations of the synthesized models. In this work, we introduce replaceable substructures as arrangements of parts that can be interchanged while ensuring boundary consistency. The consistency information is extracted from part labels and connections in the original source models. We present a polynomial time algorithm that discovers such substructures by working on a dual of the original shape graph that encodes inter-part connectivity. We demonstrate the algorithm on a range of test examples producing plausible shape variations, both from a geometric and from a topological viewpoint.


Figure 1: From a shape M with annotated part types (indicated by color) we construct a shape graph G where each part becomes a node and each part-connection an edge. This yields parts of different types and rules for connecting them, visualized as a compatibility matrix (c). The dual graph G* encodes how a set of parts can be removed to extract a subgraph. In this example (bottom-left), the cut is formed by removing five nodes from the dual graph G*.


Figure 2: In-model synthesis. For models with partial repetitive structures like playgrounds, racetracks, and ball tracks, replaceable subgraphs can be explored in just a single model. Hence, we progressively replace substructures from a source model.

Figure 3: In-group model synthesis. Matching subgraphs can also be discovered and swapped between different models. Starting from only 3 bike models, with 13, 15, and 16 parts, respectively, we obtain a variety of plausible models with varied topologies as well as geometries that are inserted as new inputs for further variation. The synthesized results of toy tractors were created from 4 input models.


We are grateful to the anonymous reviewers for their comments, suggestions, and additional references. We would like to thank Alexander Berner, Martin Bokeloh, Oliver Burghard, Javor Kalojanov and Youyi Zheng for discussions. The project was supported in part by the Marie Curie Career Integration Grant 303541, the ERC Starting Grant SmartGeometry (StG-2013- 335373), the ERC Advanced Grant Expressive (ADG-2011 291184), and gifts from Adobe.

  AUTHOR = "Han Liu and Ulysse Vimont and Michael Wand and Marie-Paule Cani and Stefanie Hahmann and 
            Damien Rohmer and Niloy J. Mitra",
  TITLE = "Replaceable Substructures for Efficient Part-Based Modeling",
  JOURNAL = "Computer Graphics Forum (Special issue of Eurographics 2015)",
  YEAR = "2015", 
  numpages = {11},

Paper (20MB)

Code / Data (50MB)