{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T17:02:44Z","timestamp":1791478964728,"version":"4.3.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"973 Program","doi-asserted-by":"crossref","award":["2014CB360503"],"award-info":[{"award-number":["2014CB360503"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61522213, 61379090"],"award-info":[{"award-number":["61522213, 61379090"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012245","name":"Guangdong Science and Technology Program","doi-asserted-by":"crossref","award":["2015A030312015, 2014B050502009, 2014TX01X033"],"award-info":[{"award-number":["2015A030312015, 2014B050502009, 2014TX01X033"]}],"id":[{"id":"10.13039\/501100012245","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shenzhen VisuCA Key Lab","award":["CXB201104220029A"],"award-info":[{"award-number":["CXB201104220029A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2015,11,4]]},"abstract":"<jats:p>\n            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\n            <jats:italic>generalized cylinders<\/jats:italic>\n            , which are ubiquitous in both organic forms and man-made artifacts. We introduce a quantitative measure of\n            <jats:italic>cylindricity<\/jats:italic>\n            for a shape part and develop a cylindricity-driven optimization algorithm, with a global objective function, for\n            <jats:italic>generalized cylinder decomposition.<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/2816795.2818074","type":"journal-article","created":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T12:36:39Z","timestamp":1445949399000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["Generalized cylinder decomposition"],"prefix":"10.1145","volume":"34","author":[{"given":"Yang","family":"Zhou","sequence":"first","affiliation":[{"name":"Shenzhen VisuCA Key Lab \/ SIAT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kangxue","family":"Yin","sequence":"additional","affiliation":[{"name":"Shenzhen VisuCA Key Lab \/ SIAT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hui","family":"Huang","sequence":"additional","affiliation":[{"name":"Shenzhen VisuCA Key Lab \/ SIAT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minglun","family":"Gong","sequence":"additional","affiliation":[{"name":"Memorial University of Newfoundland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Cohen-Or","sequence":"additional","affiliation":[{"name":"Tel-Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12169"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0375-x"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360643"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601226"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.10.018"},{"key":"e_1_2_2_6_1","volume-title":"Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics","author":"Chazelle B.","unstructured":"Chazelle , B. 1987. Approximation and decomposition of shapes . In Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics , Lawrence Erlbaum Associates , 145--185. Chazelle, B. 1987. Approximation and decomposition of shapes. In Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, Lawrence Erlbaum Associates, 145--185."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531379"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508378"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015817"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258849"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409098"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.12.004"},{"key":"e_1_2_2_15_1","series-title":"Adaptive Computation and Machine Learning series","volume-title":"The Minimum Description Length Principle","author":"Grunwald P. D.","unstructured":"Grunwald , P. D. 2007. The Minimum Description Length Principle . Adaptive Computation and Machine Learning series . The MIT press . Grunwald, P. D. 2007. The Minimum Description Length Principle. Adaptive Computation and Machine Learning series. The MIT press."},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Hoffman D. D. and Richards W. A. 1984. Parts of recognition. Cognition 65--96.  Hoffman D. D. and Richards W. A. 1984. Parts of recognition. Cognition 65--96.","DOI":"10.1016\/0010-0277(84)90022-2"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661244"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2659467.2675048"},{"key":"e_1_2_2_19_1","article-title":"An unified multiscale framework for planar, surface, and curve skeletonization","author":"Jalba A.","year":"2015","unstructured":"Jalba , A. , Sobiecki , A. , and Telea , A. 2015 . An unified multiscale framework for planar, surface, and curve skeletonization . IEEE Trans. Pattern Analysis & Machine Intelligence. Jalba, A., Sobiecki, A., and Telea, A. 2015. An unified multiscale framework for planar, surface, and curve skeletonization. IEEE Trans. Pattern Analysis & Machine Intelligence.","journal-title":"IEEE Trans. Pattern Analysis & Machine Intelligence."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778839"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1201775.882369"},{"key":"e_1_2_2_22_1","unstructured":"Knuth D. 2000. Dancing links. Millenial Perspectives in Computer Science 159--187.  Knuth D. 2000. Dancing links. Millenial Perspectives in Computer Science 159--187."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/364338.364343"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866178"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964947"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997823"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.817348"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778838"},{"key":"e_1_2_2_29_1","volume-title":"Proc. of Shape Modeling International, 339--344","author":"Mortara M.","unstructured":"Mortara , M. , Patan\u00e9 , 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 . Mortara, M., Patan\u00e9, 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."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218654304000584"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2011.6126256"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.23"},{"key":"e_1_2_2_33_1","volume-title":"Proc. Eurographics Symp. on Geometry Processing, 146--155","author":"Sander P. V.","unstructured":"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 . 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."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0370-2"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01103.x"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-007-0197-5"},{"key":"e_1_2_2_37_1","volume-title":"Proc. of Graphics Interface, 161--168","author":"Simari P. D.","unstructured":"Simari , P. D. , and Singh , K . 2005. Extraction and remeshing of ellipsoidal representations from mesh data . In Proc. of Graphics Interface, 161--168 . Simari, P. D., and Singh, K. 2005. Extraction and remeshing of ellipsoidal representations from mesh data. In Proc. of Graphics Interface, 161--168."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01867.x"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531377"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03178.x"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508384"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611811"},{"key":"e_1_2_2_43_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer . Vazirani, V. V. 2001. Approximation Algorithms. Springer."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661241"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01880.x"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.19"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2009.06.017"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816795.2818074","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2816795.2818074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:18Z","timestamp":1750225698000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816795.2818074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,11,4]]}},"alternative-id":["10.1145\/2816795.2818074"],"URL":"https:\/\/doi.org\/10.1145\/2816795.2818074","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}