Generalized Cylinder Decomposition


ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2015)

Yang Zhou1      Kangxue Yin1        Hui Huang1*        Hao Zhang2         Minglun Gong3        Daniel Cohen-Or4

1Shenzen VisuCA Key Lab/SIAT     2Simon Fraser University     3Memorial University of Newfoundland      4Tel-Aviv University 


Figure 1: Generalized cylinder decomposition obtained by our algorithm(right) produces considerably fewer parts compared to approximateconvex decomposition (middle).


Abstract

Decomposing a complex shape into geometrically simple primitives is a fundamental problem in geometry processing. We are interested in a shape decomposition problem where the simple primitives sought are generalized cylinders, which are ubiquitous in both organic forms and man-made artifacts. We introduce a quantitative measure of cylindricity for a shape part and develop a cylindricitydriven optimization algorithm, with a global objective function, for generalized cylinder decomposition. As a measure of geometric simplicity and following the minimum description length principle, cylindricity is defined as the cost of representing a cylinder through skeletal and cross-section profile curves. Our decomposition algorithm progressively builds local to non-local cylinders, which form over-complete covers of the input shape. The over-completeness of the cylinder covers ensures a conservative buildup of the cylindrical parts, leaving the final decision on decomposition to global optimization. We solve the global optimization by finding an exact cover, which optimizes the global objective function. We demonstrate results of our optimal decomposition algorithm on numerous examples and compare with other alternatives.


Source code & demo & data
Welcome to download our source code, executalbe demo and data from below. 

To reference our algorithm, code or data in a publication, please include the bibtex below and a link to this website.


Overview


Figure 2: Our decomposition algorithm overview: given a shape (a), we first compute its local GC set (b), and then merge the local GCs into fewer overlapping non-local GCs (c) that form an over-complete cover for the shape (a). The final decomposition (e) is obtained by solving the exact cover problem from various candidate GC combinations (d) of non-local GCs (b).


Results


 Figure 3: A gallery of decomposition results obtained by our decomposition algorithm, all with the same parameter setting.

Figure 4: A stress test: the 3D monkey model from the teaser was bent and stretched in a variety of ways
to test the robustness of our cylindricity measure and decomposition algorithm.

Figure 5

: Our decomposition returns both inner (right) and outer (left) GC surfaces for container-like objects with inner concavity.


Figure 6: Overlapping covers lead to reduction in part counts.


Applications
 

Figure 7:Curve skeletons derived from our decomposition (GCs are in different colors).

Figure 8: Two dramatic morphing sequences that warp an Aladdin lamp to a genie then to a flamingo. After obtaining the decompositions for the source and target shapes, a cylindricity-based straightforward graph matching results in both part and skeleton correspondence, enabling morphing between corresponding profile curves.

Figure 9: Progressive shape approximation using generalized cylinders from our decomposition algorithm. The pegaso model from [Thiery et al. 2013] is decomposed (leftmost) into 11 parts. A set shape approximations are generated (from left to right) through progressively increasing the number of profile curves and control points (#P, #C) from (25, 100), (50, 300), (75, 600), to (100, 1000). The approximation errors (H, M12, M21), as defined in Table 2, decreases from (6.188, 0.813, 0.683), (2.139, 0.311, 0.32), (1.456, 0.192, 0.198), to (1.456, 0.151, 0.156).

Figure 10 Skeleton+profile approximations obtained from optimal decomposition on the same models.

Video

Youku: 

Youtube: 

Acknowledgments

We thank the reviewers for their valuable feedback. We are grateful to Oliver van Kaick, Oscar Kin-Chung Au, Michela Mortara and Jianwei Guo for sharing their source codes on approximate convex decomposition, Laplacian mesh contraction, Plumber and Poisson disk sampling. We also thank Jean Marc Thiery for providing us the testing data of sphere-meshes and the figures in their paper. This work was supported in part by NSFC (61522213, 61232011,61528208, 61379090), 973 Program (2014CB360503), 863 Program (2015AA016401), Guangdong Science and Technology Program (2015A030312015, 2014B050502009, 2014TX01X033), Shenzhen VisuCA Key Lab (CXB201104220029A), SIAT Innovation Program for Excellent Young Researchers (201305), NSERC (611370 and 293127) and the Israel Science Foundation.


Bibtex
@ARTICLE{gcd15,
    title = {Generalized Cylinder Decomposition},
    author = {Yang Zhou and Kangxue Yin and Hui Huang and Hao Zhang and Minglun Gong and Daniel Cohen-Or},
    journal = {ACM Transactions on Graphics (Proc. of SIGGRAPH Asia 2015)},
    volume = {34},
    number = {6},
    pages = {to appear},
    year = {2015},
}
Copyright © 2016-2018 Visual Computing Research Center