{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T19:39:16Z","timestamp":1791661156549,"version":"4.3.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T00:00:00Z","timestamp":1606435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            We introduce\n            <jats:italic>carvable volume decomposition<\/jats:italic>\n            for efficient 3-axis CNC machining of 3D freeform objects, where our goal is to develop a fully automatic method to jointly optimize setup and path planning. We formulate our joint optimization as a volume decomposition problem which prioritizes minimizing the number of setup directions while striving for a minimum number of\n            <jats:italic>continuously carvable<\/jats:italic>\n            volumes, where a 3D volume is continuously carvable, or simply carvable, if it can be carved with the machine cutter traversing a\n            <jats:italic>single continuous<\/jats:italic>\n            path. Geometrically, carvability combines visibility and monotonicity and presents a new shape property which had not been studied before. Given a target 3D shape and the initial material block, our algorithm first finds the minimum number of carving directions by solving a\n            <jats:italic>set cover<\/jats:italic>\n            problem. Specifically, we analyze cutter accessibility and select the carving directions based on an assessment of how likely they would lead to a small carvable volume decomposition. Next, to obtain a minimum decomposition based on the selected carving directions efficiently, we narrow down the solution search by focusing on a special kind of points in the residual volume,\n            <jats:italic>single access<\/jats:italic>\n            or SA points, which are points that can be accessed from\n            <jats:italic>one and only one<\/jats:italic>\n            of the selected carving directions. Candidate carvable volumes are\n            <jats:italic>grown<\/jats:italic>\n            starting from the SA points. Finally, we devise an energy term to evaluate the carvable volumes and their combinations, leading to the final decomposition. We demonstrate the performance of our decomposition algorithm on a variety of 2D and 3D examples and evaluate it against the ground truth, where possible, and solutions provided by human experts. Physically machined models are produced where each carvable volume is continuously carved following a connected Fermat spiral toolpath.\n          <\/jats:p>","DOI":"10.1145\/3414685.3417772","type":"journal-article","created":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T21:51:05Z","timestamp":1606513865000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["VDAC"],"prefix":"10.1145","volume":"39","author":[{"given":"Ali","family":"Mahdavi-Amiri","sequence":"first","affiliation":[{"name":"Simon Fraser University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fenggen","family":"Yu","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haisen","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Washington and Shandong University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adriana","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,27]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"1","article-title":"2018. A survey on smart automated computer-aided process planning (ACAPP) techniques","volume":"97","author":"M.","year":"2018","unstructured":"M. Al-wswasi, A. Ivanov , and H. Makatsoris . 2018. A survey on smart automated computer-aided process planning (ACAPP) techniques . The International Journal of Advanced Manufacturing Technology 97 , 1 ( 2018 ), 809--832. M. Al-wswasi, A. Ivanov, and H. Makatsoris. 2018. A survey on smart automated computer-aided process planning (ACAPP) techniques. The International Journal of Advanced Manufacturing Technology 97, 1 (2018), 809--832.","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"T. Alderighi L. Malomo D. Giorgi B. Bickel P. Cignoni and N. Pietroni. 2019. Volume-Aware Design of Composite Molds. ACM Trans. Graph. 38 4 Article 110:1--110:12 (2019).  T. Alderighi L. Malomo D. Giorgi B. Bickel P. Cignoni and N. Pietroni. 2019. Volume-Aware Design of Composite Molds. ACM Trans. Graph. 38 4 Article 110:1--110:12 (2019).","DOI":"10.1145\/3306346.3322981"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201381"},{"key":"e_1_2_2_4_1","volume-title":"Interlocking Pieces for Printing Tangible Cultural Heritage Replicas. In Eurographics Workshop on Graphics and Cultural Heritage, Reinhard Klein and Pedro Santos (Eds.). The Eurographics Association.","author":"Alemanno G.","unstructured":"G. Alemanno , P. Cignoni , N. Pietroni , F. Ponchio , and R. Scopigno . 2014 . Interlocking Pieces for Printing Tangible Cultural Heritage Replicas. In Eurographics Workshop on Graphics and Cultural Heritage, Reinhard Klein and Pedro Santos (Eds.). The Eurographics Association. G. Alemanno, P. Cignoni, N. Pietroni, F. Ponchio, and R. Scopigno. 2014. Interlocking Pieces for Printing Tangible Cultural Heritage Replicas. In Eurographics Workshop on Graphics and Cultural Heritage, Reinhard Klein and Pedro Santos (Eds.). The Eurographics Association."},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"C. Ara\u00fajo D. Cabiddu M. Attene M. Livesu N. Vining and A. Sheffer. 2019. Surface2Volume: Surface Segmentation Conforming Assemblable Volumetric Partition. ACM Trans. Graph. 38 4 (2019) 80:1--80:16.  C. Ara\u00fajo D. Cabiddu M. Attene M. Livesu N. Vining and A. Sheffer. 2019. Surface2Volume: Surface Segmentation Conforming Assemblable Volumetric Partition. ACM Trans. Graph. 38 4 (2019) 80:1--80:16.","DOI":"10.1145\/3306346.3323004"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001877"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818087"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"B. Choi and R. Jerrard. 1998. Sculptured Surface Machining: Theory and Applications. Kluwer Academic Publishers.  B. Choi and R. Jerrard. 1998. Sculptured Surface Machining: Theory and Applications. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-5283-3"},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"D. Ding Z. S. Pan D. Cuiuri and H. Li. 2014. A tool-path generation strategy for wire and arc additive manufacturing. The international journal of advanced manufacturing technology 73 1--4 (2014) 173--183.  D. Ding Z. S. Pan D. Cuiuri and H. Li. 2014. A tool-path generation strategy for wire and arc additive manufacturing. The international journal of advanced manufacturing technology 73 1--4 (2014) 173--183.","DOI":"10.1007\/s00170-014-5808-5"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000687"},{"key":"e_1_2_2_11_1","unstructured":"M. R. Garey and D. S. Johnson. 1983. Computers and Intractability. A Guide to the Theory of NP-Completeness. (1983).  M. R. Garey and D. S. Johnson. 1983. Computers and Intractability. A Guide to the Theory of NP-Completeness. (1983)."},{"key":"e_1_2_2_12_1","volume-title":"ACM Symp. Computational Fabrication.","author":"Hattab A.","unstructured":"A. Hattab and G. Taubin . 2019. Rough Carving of 3D Models with Spatial Augmented Reality . In ACM Symp. Computational Fabrication. A. Hattab and G. Taubin. 2019. Rough Carving of 3D Models with Spatial Augmented Reality. In ACM Symp. Computational Fabrication."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00170-010-3004-9"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12556"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661244"},{"key":"e_1_2_2_16_1","volume-title":"Generalized matryoshka: Computational design of nesting objects. Computer Graphics Forum 36, 5","author":"Jacobson A.","year":"2017","unstructured":"A. Jacobson . 2017. Generalized matryoshka: Computational design of nesting objects. Computer Graphics Forum 36, 5 ( 2017 ), 27--35. A. Jacobson. 2017. Generalized matryoshka: Computational design of nesting objects. Computer Graphics Forum 36, 5 (2017), 27--35."},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"A. Jacobson D. Panozzo etal 2018. libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/.  A. Jacobson D. Panozzo et al. 2018. libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_18_1","series-title":"SIAM J. Comput. 14, 4","volume-title":"Decomposing a Polygon into Simpler Components","author":"Keil J. M.","year":"1985","unstructured":"J. M. Keil . 1985. Decomposing a Polygon into Simpler Components . SIAM J. Comput. 14, 4 ( 1985 ), 799--817. J. M. Keil. 1985. Decomposing a Polygon into Simpler Components. SIAM J. Comput. 14, 4 (1985), 799--817."},{"key":"e_1_2_2_19_1","volume-title":"Dancing links. arXiv preprint cs\/0011047","author":"Knuth D. E.","year":"2000","unstructured":"D. E. Knuth . 2000. Dancing links. arXiv preprint cs\/0011047 ( 2000 ). D. E. Knuth. 2000. Dancing links. arXiv preprint cs\/0011047 (2000)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"A. Lasemi D. Xue and P. Gu. 2010. Recent development in CNC machining of freeform surfaces: a state-of-the-art review. Computer-Aided Design 42 7 (2010) 641--654.  A. Lasemi D. Xue and P. Gu. 2010. Recent development in CNC machining of freeform surfaces: a state-of-the-art review. Computer-Aided Design 42 7 (2010) 641--654.","DOI":"10.1016\/j.cad.2010.04.002"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13147"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366148"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982397"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3204458"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185584"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the Eurographics Workshop on Graphics for Digital Fabrication. Eurographics Association, 1--9.","author":"S\u00e1 A.","unstructured":"A. S\u00e1 , K. Rodriguez-Echavarria , N. Pietroni , and P. Cignoni . 2016. State of the art on functional fabrication . In Proceedings of the Eurographics Workshop on Graphics for Digital Fabrication. Eurographics Association, 1--9. A. S\u00e1, K. Rodriguez-Echavarria, N. Pietroni, and P. Cignoni. 2016. State of the art on functional fabrication. In Proceedings of the Eurographics Workshop on Graphics for Digital Fabrication. Eurographics Association, 1--9."},{"key":"e_1_2_2_28_1","unstructured":"Siemens Industry Software Inc. 2020. NX software. www.plm.automation.siemens.com\/global\/en\/products\/nx\/.  Siemens Industry Software Inc. 2020. NX software. www.plm.automation.siemens.com\/global\/en\/products\/nx\/."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2019.03.001"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"G. Toussaint. 1985. Movable separability of sets. Comput. Geom. (1985) 335--375.  G. Toussaint. 1985. Movable separability of sets. Comput. Geom. (1985) 335--375.","DOI":"10.1016\/B978-0-444-87806-9.50018-9"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.06.005"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1108\/13552540210413284"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925958"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201338"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417772","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3414685.3417772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:14Z","timestamp":1750197794000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417772"}},"subtitle":["volume decompose-and-carve for subtractive manufacturing"],"short-title":[],"issued":{"date-parts":[[2020,11,27]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3414685.3417772"],"URL":"https:\/\/doi.org\/10.1145\/3414685.3417772","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,27]]},"assertion":[{"value":"2020-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}