“Generalized cylinder decomposition” by Zhou, Yin, Huang, Zhang, Gong, et al. …
Conference:
Type(s):
Title:
- Generalized cylinder decomposition
Session/Category Title: Geometry Processing
Presenter(s)/Author(s):
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 cylindricity-driven 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.
References:
1. Asafi, S., Goren, A., and Cohen-Or, D. 2013. Weak convex decomposition by lines-of-sight. Computer Graphics Forum (Proc. of SGP) 32, 5, 23–31.
2. Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. The Visual Computer 22, 3, 181–193.
3. Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., and Lee, T.-Y. 2008. Skeleton extraction by mesh contraction. ACM Trans. on Graphics (Proc. of SIGGRAPH) 27, 3, 44:1–44:10.
4. Baerentzen, J. A., Abdrashitov, R., and Singh, K. 2014. Interactive shape modeling using a skeleton-mesh co-representation. ACM Trans. on Graphics (Proc. of SIGGRAPH) 33, 4, 132:1–132:10.
5. Biasotti, S., Giorgi, D., Spagnuolo, M., and Falcidieno, B. 2008. Reeb graphs for shape analysis and applications. Theoretical Computer Science 392, 1–3, 5–22.
6. Chazelle, B. 1987. Approximation and decomposition of shapes. In Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, Lawrence Erlbaum Associates, 145–185.
7. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. on Graphics (Proc. of SIGGRAPH) 28, 3, 73:1–73:12.
8. Chen, T., Zhu, Z., Shamir, A., Hu, S.-M., and Cohen-Or, D. 2013. 3-sweep: extracting editable objects from a single photo. ACM Trans. on Graphics (Proc. of SIGGRAPH Asia) 32, 6, 195:1–195:10.
9. Chvatal, V. 1979. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4, 3, 233–235.
10. Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. In Proc. of SIGGRAPH, ACM, SIGGRAPH ’04, 905–914.
11. Douglas, D. H., and Peucker, T. K. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Int. J. Geographic Information and Geovisualization 10, 2, 112–122.
12. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. of SIGGRAPH, 209–216.
13. Golovinskiy, A., and Funkhouser, T. 2008. Randomized cuts for 3D mesh analysis. ACM Trans. on Graphics (Proc. of SIGGRAPH Asia) 27, 5, 145:1–145:12.
14. Goyal, M., Murugappan, S., Piya, C., Benjamin, W., Fang, Y., Liu, M., and Ramani, K. 2012. Towards locally and globally shape-aware reverse 3d modeling. Computer-Aided Design 44, 6, 537–553.
15. Grunwald, P. D. 2007. The Minimum Description Length Principle. Adaptive Computation and Machine Learning series. The MIT press.
16. Hoffman, D. D., and Richards, W. A. 1984. Parts of recognition. Cognition, 65–96.
17. Hu, R., Li, H., Zhang, H., and Cohen-Or, D. 2014. Approximate pyramidal shape decomposition. ACM Trans. on Graphics (Proc. of SIGGRAPH Asia) 33, 6, 213:1–213:12.
18. Jacobson, A., Deng, Z., Kavan, L., and Lewis, J. P. 2014. Skinning: Real-time shape deformation. In ACM SIGGRAPH Courses.
19. Jalba, A., Sobiecki, A., and Telea, A. 2015. An unified multiscale framework for planar, surface, and curve skeletonization. IEEE Trans. Pattern Analysis & Machine Intelligence.
20. Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3d mesh segmentation and labeling. ACM Trans. on Graphics (Proc. of SIGGRAPH) 29, 4, 102:1–102:12.
21. Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. In Proc. of SIGGRAPH, ACM, SIGGRAPH ’03, 954–961.
22. Knuth, D. 2000. Dancing links. Millenial Perspectives in Computer Science, 159–187.
23. Li, X., Toon, T., Tan, T., and Huang, Z. 2001. Decomposing polygon meshes for interactive applications. In Proc. of Symp. on Interactive 3D Graphics, 35–42.
24. Li, G., Liu, L., Zheng, H., and Mitra, N. J. 2010. Analysis, reconstruction and manipulation using arterial snakes. ACM Trans. on Graphics (Proc. of SIGGRAPH Asia) 29, 6, 152:1–152:10.
25. Li, Y., Wu, X., Chrysathou, Y., Sharf, A., Cohen-Or, D., and Mitra, N. J. 2011. Globfit: Consistently fitting primitives by discovering global relations. ACM Trans. on Graphics (Proc. of SIGGRAPH) 30, 4, 52:1–52:12.
26. Lien, J. M., and Amato, N. M. 2004. Approximate convex decomposition of polygons. In Proc. of ACM Symp. on Computat. Geom., 17–26.
27. Mangan, A. P., and Whitaker, R. T. 1999. Partitioning 3D surface meshes using watershed segmentation. IEEE Trans. Visualization & Computer Graphics 5, 4, 308–321.
28. Miklos, B., Giesen, J., and Pauly, M. 2010. Discrete scale axis representations for 3d geometry. ACM Trans. on Graphics (Proc. of SIGGRAPH) 29, 4, 101:1–101:10.
29. Mortara, M., Patané, G., Spagnuolo, M., Falcidieno, B., and Rossignac, J. 2004. Plumber: a method for a multi-scale decomposition of 3d shapes into tubular primitives and bodies. In Proc. of Shape Modeling International, 339–344.
30. Raab, R., Gotsman, C., and Sheffer, A. 2004. Virtual woodwork: Making toys from geometric models. International Journal of Shape Modeling 10, 1, 1–30.
31. Ren, Z., Yuan, J., Li, C., and Liu, W. 2011. Minimum nearconvex decomposition for robust shape representation. In Proc. Int. Conf. on Computer Vision, 303–310.
32. Reniers, D., van Wijk, J. J., and Telea, A. 2008. Computing multiscale curve and surface skeletons of genus-0 shapes using a global importance measure. IEEE Trans. Visualization & Computer Graphics 14, 2, 355–368.
33. Sander, P. V., Wood, Z. J., Gortler, S. J., Snyder, J., and Hoppe, H. 2003. Multi-chart geometry images. In Proc. Eurographics Symp. on Geometry Processing, 146–155.
34. Shamir, A., Shapira, L., and Cohen-Or, D. 2006. Mesh analysis using geodesic mean-shift. The Visual Computer 22, 2, 99–108.
35. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539–1556.
36. Shapira, L., Shamir, A., and Cohen-Or, D. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 24, 4, 249–259.
37. Simari, P. D., and Singh, K. 2005. Extraction and remeshing of ellipsoidal representations from mesh data. In Proc. of Graphics Interface, 161–168.
38. Solomon, J., Ben-Chen, M., Butscher, A., and Guibas, L. 2011. Discovery of intrinsic primitives on triangle meshes. Computer Graphics Forum (Proc. of Eurographics) 30, 2, 365–374.
39. Tagliasacchi, A., Zhang, H., and Cohen-Or, D. 2009. Curve skeleton extraction from incomplete point cloud. ACM Trans. on Graphics (Proc. of SIGGRAPH) 28, 3, 71:1–71:9.
40. Tagliasacchi, A., Alhashim, I., Olson, M., and Zhang, H. 2012. Mean curvature skeletons. Computer Graphics Forum (Proc. of SGP) 31, 5, 1735–1744.
41. Thiery, J.-M., Guy, E., and Boubekeur, T. 2013. Sphere-meshes: Shape approximation using spherical quadric error metrics. ACM Trans. on Graphics (Proc. of SIGGRAPH) 32, 6, 178:1–178:12.
42. van Kaick, O., Fish, N., Kleiman, Y., Asafi, S., and Cohen-OR, D. 2014. Shape segmentation by approximate convexity analysis. ACM Trans. on Graphics 34, 1, 4:1–4:11.
43. Vazirani, V. V. 2001. Approximation Algorithms. Springer.
44. Yin, K., Huang, H., Zhang, H., Gong, M., Cohen-Or, D., and Chen, B. 2014. Morfit: Interactive surface reconstruction from incomplete point clouds with curve-driven topology and geometry control. ACM Trans. on Graphics (Proc. of SIGGRAPH Asia) 33, 6, 41:1–41:12.
45. Zheng, Y., Fu, H., Cohen-Or, D., Au, O. K.-C., and Tai, C.-L. 2011. Component-wise controllers for structure-preserving shape manipulation. Computer Graphics Forum (Proc. of Eurographics) 30, 2, 563–572.
46. Zunic, J., and Rosin, P. L. 2004. A new convexity measure for polygons. IEEE Trans. Pattern Analysis & Machine Intelligence 26, 7, 923–934.
47. Zunic, J., Hirota, K., and Rosin, P. L. 2010. A Hu moment invariant as a shape circularity measure. Pattern Recognition 43, 1, 47–57.
