{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T23:50:19Z","timestamp":1771977019126,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T00:00:00Z","timestamp":1540252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Adobe and NTopology"},{"name":"NSF CAREER","award":["IIS-1652515"],"award-info":[{"award-number":["IIS-1652515"]}]},{"name":"Italian DSURF PRIN 2015","award":["2015B8TRFM"],"award-info":[{"award-number":["2015B8TRFM"]}]},{"name":"European Union's Horizon 2020 research and innovation programme","award":["680448 (CAxMan)"],"award-info":[{"award-number":["680448 (CAxMan)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            We propose a novel algorithm for decomposing general three-dimensional geometries into a small set of overlap-free\n            <jats:italic>height-field blocks<\/jats:italic>\n            , volumes enclosed by a flat base and a height-field surface defined with respect to this base. This decomposition is useful for fabrication methodologies such as 3-axis CNC milling, where a single milling pass can only carve a single height-field surface defined with respect to the machine tray but can also benefit other fabrication settings. Computing our desired decomposition requires solving a highly constrained discrete optimization problem, variants of which are known to be NP-hard. We effectively compute a high-quality decomposition by using a two-step process that leverages the unique characteristics of our setup. Specifically, we notice that if the height-field directions are constrained to the major axes, then we can always produce a valid decomposition starting from a suitable surface segmentation. Our method first produces a compact set of large, possibly overlapping, height-field blocks that jointly cover the model surface by recasting this discrete constrained optimization problem as an unconstrained optimization of a continuous function, which allows for an efficient solution. We then cast the computation of an overlap-free, final decomposition as an ordering problem on a graph and solve it via a combination of cycle elimination and topological sorting. The combined algorithm produces a compact set of height-field blocks that jointly describe the input model within a user given tolerance. We demonstrate our method on a range of inputs and showcase a number of real life models manufactured using our technique.\n          <\/jats:p>","DOI":"10.1145\/3204458","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T12:16:16Z","timestamp":1540296976000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Axis-Aligned Height-Field Block Decomposition of 3D Shapes"],"prefix":"10.1145","volume":"37","author":[{"given":"Alessandro","family":"Muntoni","sequence":"first","affiliation":[{"name":"University of Cagliari and New York University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4688-7060","authenticated-orcid":false,"given":"Marco","family":"Livesu","sequence":"additional","affiliation":[{"name":"CNR IMATI"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0950-7372","authenticated-orcid":false,"given":"Riccardo","family":"Scateni","sequence":"additional","affiliation":[{"name":"University of Cagliari"}]},{"given":"Alla","family":"Sheffer","sequence":"additional","affiliation":[{"name":"University of British Columbia"}]},{"given":"Daniele","family":"Panozzo","sequence":"additional","affiliation":[{"name":"New York University"}]}],"member":"320","published-online":{"date-parts":[[2018,10,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Eurographics Workshop on Graphics and Cultural Heritage, Reinhard Klein and Pedro Santos (Eds.). Eurographics Association, 145--154","author":"Alemanno Giuseppe","year":"2014","unstructured":"Giuseppe Alemanno , Paolo Cignoni , Nico Pietroni , Federico Ponchio , and Roberto Scopigno . 2014 . Interlocking pieces for printing tangible cultural heritage replicas . In Proceedings of the Eurographics Workshop on Graphics and Cultural Heritage, Reinhard Klein and Pedro Santos (Eds.). Eurographics Association, 145--154 . Giuseppe Alemanno, Paolo Cignoni, Nico Pietroni, Federico Ponchio, and Roberto Scopigno. 2014. Interlocking pieces for printing tangible cultural heritage replicas. In Proceedings of the Eurographics Workshop on Graphics and Cultural Heritage, Reinhard Klein and Pedro Santos (Eds.). Eurographics Association, 145--154."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12608"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1731309.1731311"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601157"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213031"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2537852"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00236"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/964965.808602"},{"key":"e_1_2_1_9_1","volume-title":"Leiserson","author":"Cormen Thomas H.","year":"2001","unstructured":"Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , and Charles E . Leiserson . 2001 . Introduction to Algorithms (2nd ed.). McGraw--Hill Higher Education . Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001. Introduction to Algorithms (2nd ed.). McGraw--Hill Higher Education."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661266"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/346876.348220"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000687"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807442.2807476"},{"key":"e_1_2_1_14_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob and others. 2010. Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org.  Ga\u00ebl Guennebaud Beno\u00eet Jacob and others. 2010. Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1108\/13552541111113862"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12556"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03037.x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2013.05.011"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661244"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo and others. 2016. libigl: A simple C++ geometry processing library. Retrieved from http:\/\/libigl.github.io\/libigl\/.  Alec Jacobson Daniele Panozzo and others. 2016. libigl: A simple C++ geometry processing library. Retrieved from http:\/\/libigl.github.io\/libigl\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/368996.369025"},{"key":"e_1_2_1_22_1","first-page":"15","article-title":"Shuffler: Modeling with interchangeable parts","volume":"13","author":"Kraevoy V.","year":"2007","unstructured":"V. Kraevoy , D. Julius , and A. Sheffer . 2007 . Shuffler: Modeling with interchangeable parts . The Visual Computer 13 (2007), 15 . V. Kraevoy, D. Julius, and A. Sheffer. 2007. Shuffler: Modeling with interchangeable parts. The Visual Computer 13 (2007), 15.","journal-title":"The Visual Computer"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236246.1236265"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3128975.3129024"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1661412.1618503"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366148"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3059592.3059593"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.2753162"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766955"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925886"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461957"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12179"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12051"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01103.x"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818128"},{"key":"e_1_2_1_36_1","volume-title":"CNC Programming Handbook: A Comprehensive Guide to Practical CNC Programming","author":"Smid Peter","unstructured":"Peter Smid . 2003. CNC Programming Handbook: A Comprehensive Guide to Practical CNC Programming . Industrial Press Inc . Peter Smid. 2003. CNC Programming Handbook: A Comprehensive Guide to Practical CNC Programming. Industrial Press Inc."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925876"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366147"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2015.03.020"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2006.00999.x"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/839277.840029"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/357346.357348"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12353"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12810"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12811"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925966"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964992"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818064"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2001.958278"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818121"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858036.2858362"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925901"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461967"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3204458","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3204458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:13Z","timestamp":1750282873000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3204458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,23]]},"references-count":53,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3204458"],"URL":"https:\/\/doi.org\/10.1145\/3204458","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,23]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}