{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:21:13Z","timestamp":1764969673420,"version":"3.46.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2024YFB3309500"],"award-info":[{"award-number":["2024YFB3309500"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U23A20312","62472257","62472258"],"award-info":[{"award-number":["U23A20312","62472257","62472258"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021171","name":"Guangdong Basic and Applied Basic Research Foundation","doi-asserted-by":"crossref","award":["2023B1515120026"],"award-info":[{"award-number":["2023B1515120026"]}],"id":[{"id":"10.13039\/501100021171","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>Tightly cutting raw materials into a set of carvable objects, known as the stock cutting problem, is a necessary step in subtractive manufacturing. This problem can be framed as a 3D irregular object packing task, aiming to fit as many objects as possible within a predefined container. While previous packing algorithms can generate dense, non-overlapping, and even disassemblable configurations, they cannot satisfy carvable constraints.<\/jats:p>\n                  <jats:p>\n                    This paper introduces the\n                    <jats:italic toggle=\"yes\">carvable hull-and-pack<\/jats:italic>\n                    problem, which integrates irregular object packing with subtractive manufacturing. This problem is more challenging than general 3D packing, as it requires ensuring the carvability of each object and generate the disassembly sequence. To address this, we first define a novel geometric hull, called\n                    <jats:italic toggle=\"yes\">carving hull<\/jats:italic>\n                    , which accounts for both the object's shape and the cutter accessibility, constrained by the real-time distribution of surrounding objects. Then we present\n                    <jats:italic toggle=\"yes\">Chapper<\/jats:italic>\n                    , an effective solution to co-optimize carving hull packing and the planning of disassembly sequence to maximize space utilization while preserving the carvable constraints. Given a raw material and a list of generic 3D objects, our algorithm starts with densely packing each object into the material with a pre-computed placement order, while simultaneously maintaining a valid disassembly sequence. We solve the complex object-to-object and cutter-to-object collisions by leveraging a discrete voxel representation. The carvability of each object is also guaranteed in the packing process, where we define a novel carvable metric to determine whether each object is carvable or not. Based on the packing result and the disassembly sequence, we propose a clipped Voronoi-based volume decomposition method to generate the actual carving hull for each object and finally create feasible cutting tool paths on the carving hulls. Our approach effectively packs CAD and freeform datasets, exhibiting a unique space utilization rate performance compared to the alternative baseline.\n                  <\/jats:p>","DOI":"10.1145\/3763314","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Chapper: Carvable Hull-and-Pack for Subtractive Manufacturing"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-1906-4752","authenticated-orcid":false,"given":"Zhenmin","family":"Zhang","sequence":"first","affiliation":[{"name":"Shandong University, Qingdao, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2793-2690","authenticated-orcid":false,"given":"Shuai","family":"Feng","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7057-5386","authenticated-orcid":false,"given":"Hao","family":"Xu","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5558-2210","authenticated-orcid":false,"given":"Lujiaoyang","family":"Fu","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5881-892X","authenticated-orcid":false,"given":"Lin","family":"Lu","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3376-1725","authenticated-orcid":false,"given":"Jianwei","family":"Guo","sequence":"additional","affiliation":[{"name":"Beijing Normal University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6389-1045","authenticated-orcid":false,"given":"Haisen","family":"Zhao","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480555"},{"key":"e_1_2_1_2_1","volume-title":"libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/. (2018)","author":"Alec Jacobson Daniele Panozzo","year":"2018","unstructured":"Daniele Panozzo Alec Jacobson. 2018. libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/. (2018). 2018."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92267-6_76"},{"key":"e_1_2_1_4_1","volume-title":"Surface2Volume: Surface segmentation conforming assemblable volumetric partition. arXiv preprint arXiv:1904.10213","author":"Ara\u00fajo Chrystiano","year":"2019","unstructured":"Chrystiano Ara\u00fajo, Daniela Cabiddu, Marco Attene, Marco Livesu, Nicholas Vining, and Alla Sheffer. 2019a. Surface2Volume: Surface segmentation conforming assemblable volumetric partition. arXiv preprint arXiv:1904.10213 (2019)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207543.2018.1534016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207543.2018.1534016"},{"volume-title":"Computer Graphics Forum","author":"Attene Marco","key":"e_1_2_1_7_1","unstructured":"Marco Attene. 2015. Shapes in a box: Disassembling 3D objects for efficient packing and fabrication. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 64\u201376."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459837"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(00)00021-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2021.01.003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530071"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818087"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-5273(94)00045-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592126"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.03.011"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2012.05.025"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.29.6.1092"},{"volume-title":"KI 2015: Advances in Artificial Intelligence, Steffen H\u00f6lldobler, Rafael Pe\u00f1aloza","author":"Edelkamp Stefan","key":"e_1_2_1_18_1","unstructured":"Stefan Edelkamp and Paul Wichern. 2015. Packing Irregular-Shaped Objects for 3D Printing. In KI 2015: Advances in Artificial Intelligence, Steffen H\u00f6lldobler, Rafael Pe\u00f1aloza, and Sebastian Rudolph (Eds.). Springer International Publishing, Cham, 45\u201358."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.3390\/math11041028"},{"key":"e_1_2_1_20_1","volume-title":"Mayron C\u00e9sar Oliveira Moreira, and Marina Andretta","author":"Ferreira Augusto Sebastiao","year":"2020","unstructured":"Augusto Sebastiao Ferreira, Mayron C\u00e9sar Oliveira Moreira, and Marina Andretta. 2020. Nesting problems with continuous rotations: a survey. Anais (2020)."},{"key":"e_1_2_1_21_1","volume-title":"A 3D Convex Hull Algorithm for Graphics Hardware. Accessed: Mar 6","author":"Gao Mingcen","year":"2024","unstructured":"Mingcen Gao, Thanh-Tung Cao, Tiow-Seng Tan, and Zhiyong Huang. 2024. A 3D Convex Hull Algorithm for Graphics Hardware. Accessed: Mar 6 (2024)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3687755"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.3389\/fmech.2022.966691"},{"key":"e_1_2_1_24_1","volume-title":"Illustrating the disassembly of 3D models. Computers & graphics 37, 6","author":"Guo Jianwei","year":"2013","unstructured":"Jianwei Guo, Dong-Ming Yan, Er Li, Weiming Dong, Peter Wonka, and Xiaopeng Zhang. 2013. Illustrating the disassembly of 3D models. Computers & graphics 37, 6 (2013), 574\u2013581."},{"key":"e_1_2_1_25_1","volume-title":"Robust Coarse Cage Construction With Small Approximation Errors","author":"Guo Jia-Peng","year":"2023","unstructured":"Jia-Peng Guo, Wen-Xiang Zhang, Chunyang Ye, and Xiao-Ming Fu. 2023. Robust Coarse Cage Construction With Small Approximation Errors. IEEE Transactions on Visualization and Computer Graphics (2023)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2024.3460409"},{"key":"e_1_2_1_27_1","unstructured":"David S Johnson. 1973. Near-optimal bin packing algorithms. Ph.D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_1_28_1","volume-title":"Operations Research Proceedings 2019: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR)","author":"Klimova Katerina","year":"2019","unstructured":"Katerina Klimova and Una Benlic. 2020. Heuristic Search for a Real-World 3D Stock Cutting Problem. In Operations Research Proceedings 2019: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Dresden, Germany, September 4\u20136, 2019. Springer, 63\u201369."},{"key":"e_1_2_1_29_1","volume-title":"ABC: A Big CAD Model Dataset For Geometric Deep Learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).","author":"Koch Sebastian","year":"2019","unstructured":"Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo. 2019. ABC: A Big CAD Model Dataset For Geometric Deep Learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3687965"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.273735"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1177\/1687814016652080"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201328"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1631\/FITEE.1400421"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366148"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13490"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417772"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.114257"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2019.03.003"},{"key":"e_1_2_1_40_1","volume-title":"Riccardo Scateni, et al.","author":"Muntoni Alessandro","year":"2019","unstructured":"Alessandro Muntoni, Lucio Davide Spano, Riccardo Scateni, et al. 2019b. Split and Mill: User Assisted Height-field Block Decomposition for Fabrication.. In STAG. 61\u201370."},{"key":"e_1_2_1_41_1","unstructured":"NVIDIA. 2022a. CUDA Toolkit Documentation Release: 12.6. NVIDIA. https:\/\/developer.nvidia.com\/cuda-toolkit"},{"key":"e_1_2_1_42_1","unstructured":"NVIDIA. 2022b. cuFFT Library Documentation Release: 12.6. NVIDIA. https:\/\/developer.nvidia.com\/cufft"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2024.3385612"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.3390\/math8071130"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.3390\/logistics8030069"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2017.11.010"},{"volume-title":"Integrated Computer Technologies in Mechanical Engineering: Synergetic Engineering","author":"Plankovskyy Sergiy","key":"e_1_2_1_47_1","unstructured":"Sergiy Plankovskyy, Yevgen Tsegelnyk, Olga Shypul, Alexander Pankratov, and Tatiana Romanova. 2020. Cutting irregular objects from the rectangular metal sheet. In Integrated Computer Technologies in Mechanical Engineering: Synergetic Engineering. Springer, 150\u2013157."},{"key":"e_1_2_1_48_1","article-title":"Manufacturing automation: metal cutting mechanics, machine tool vibrations, and CNC design","volume":"31","author":"Rigelsford Jon","year":"2004","unstructured":"Jon Rigelsford. 2004. Manufacturing automation: metal cutting mechanics, machine tool vibrations, and CNC design. Industrial Robot: An International Journal 31, 1 (2004).","journal-title":"Industrial Robot: An International Journal"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.01.025"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206863"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366147"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130803"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3272127.3275034","article-title":"DESIA: A general framework for designing interlocking assemblies","volume":"37","author":"Wang Ziqi","year":"2018","unstructured":"Ziqi Wang, Peng Song, and Mark Pauly. 2018. DESIA: A general framework for designing interlocking assemblies. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1\u201314.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3450626.3459680","article-title":"MOCCA: modeling and optimizing cone-joints for complex assemblies","volume":"40","author":"Wang Ziqi","year":"2021","unstructured":"Ziqi Wang, Peng Song, and Mark Pauly. 2021. MOCCA: modeling and optimizing cone-joints for complex assemblies. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1\u201314.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.advengsoft.2011.04.009"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356518"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618354"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1155\/2016\/8703782"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3610548.3618235"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.09.004"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417810"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618348"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818064"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603544"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3508499"},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3197517.3201338","article-title":"DSCarver: decompose-and-spiral-carve for subtractive manufacturing","volume":"37","author":"Zhao Haisen","year":"2018","unstructured":"Haisen Zhao, Hao Zhang, Shiqing Xin, Yuanmin Deng, Changhe Tu, Wenping Wang, Daniel Cohen-Or, and Baoquan Chen. 2018. DSCarver: decompose-and-spiral-carve for subtractive manufacturing. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1\u201314.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_1_67_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).","journal-title":"A Dataset of"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2024.103996"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:17:15Z","timestamp":1764969435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":68,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3763314"],"URL":"https:\/\/doi.org\/10.1145\/3763314","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-05-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}