{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T15:56:51Z","timestamp":1778601411680,"version":"3.51.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"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":[[2023,8]]},"abstract":"<jats:p>\n            Packing 3D objects into a known container is a very common task in many industries such as packaging, transportation, and manufacturing. This important problem is known to be NP-hard and even approximate solutions are challenging. This is due to the difficulty of handling interactions between objects with arbitrary 3D geometries and a vast combinatorial search space. Moreover, the packing must be\n            <jats:italic>interlocking-free<\/jats:italic>\n            for real-world applications. In this work, we first introduce a novel packing algorithm to search for placement locations given an object. Our method leverages a discrete voxel representation. We formulate collisions between objects as correlations of functions computed efficiently using Fast Fourier Transform (FFT). To determine the best placements, we utilize a novel cost function, which is also computed efficiently using FFT. Finally, we show how interlocking detection and correction can be addressed in the same framework resulting in interlocking-free packing. We propose a challenging benchmark with thousands of 3D objects to evaluate our algorithm. Our method demonstrates state-of-the-art performance on the benchmark when compared to existing methods in both density and speed.\n          <\/jats:p>","DOI":"10.1145\/3592126","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T15:47:45Z","timestamp":1690386465000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects"],"prefix":"10.1145","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-5183-6548","authenticated-orcid":false,"given":"Qiaodong","family":"Cui","sequence":"first","affiliation":[{"name":"Inkbit, Medford, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4663-9435","authenticated-orcid":false,"given":"Victor","family":"Rong","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology (MIT), Cambridge, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3357-1665","authenticated-orcid":false,"given":"Desai","family":"Chen","sequence":"additional","affiliation":[{"name":"Inkbit, Medford, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0212-5643","authenticated-orcid":false,"given":"Wojciech","family":"Matusik","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology (MIT), Cambridge, United States of America"},{"name":"Inkbit, Cambridge, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207543.2018.1534016"},{"key":"e_1_2_2_3_1","volume-title":"Release","author":"Netfabb Autodesk","year":"2023","unstructured":"Autodesk. 2023. Autodesk Netfabb. https:\/\/www.autodesk.com\/products\/netfabb\/ Build: 47, Release: 2023.1."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.03.011"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115952.3115993"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3528223.3530071","article-title":"Computational design of high-level interlocking puzzles","volume":"41","author":"Chen Rulin","year":"2022","unstructured":"Rulin Chen, Ziqi Wang, Peng Song, and Bernd Bickel. 2022. Computational design of high-level interlocking puzzles. ACM Trans. Graph. 41, 4 (2022), 1--15.","journal-title":"ACM Trans. Graph."},{"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":"publisher","DOI":"10.1016\/j.comgeo.2009.12.003"},{"key":"e_1_2_2_9_1","unstructured":"Erwin Coumans and Yunfei Bai. 2016--2021. PyBullet a Python module for physics simulation for games robotics and machine learning. http:\/\/pybullet.org."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.01.048"},{"key":"e_1_2_2_11_1","volume-title":"Real-time collision detection","author":"Ericson Christer","unstructured":"Christer Ericson. 2004. Real-time collision detection. Crc Press."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3502802"},{"key":"e_1_2_2_13_1","unstructured":"Michael Fogleman. 2019. Pack3d. https:\/\/github.com\/fogleman\/pack3d"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258849"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.506981"},{"key":"e_1_2_2_16_1","volume-title":"PackIt: A Virtual Environment for Geometric Planning. In International Conference on Machine Learning.","author":"Goyal Ankit","year":"2020","unstructured":"Ankit Goyal and Jia Deng. 2020. PackIt: A Virtual Environment for Geometric Planning. In International Conference on Machine Learning."},{"key":"e_1_2_2_17_1","first-page":"11","article-title":"TetGen, a Delaunay-based quality tetrahedral mesh generator","volume":"41","author":"Hang Si","year":"2015","unstructured":"Si Hang. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw 41, 2 (2015), 11.","journal-title":"ACM Trans. Math. Softw"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417764"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele 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_20_1","volume-title":"Near-optimal bin packing algorithms. Ph. D. Dissertation","author":"Johnson David S","unstructured":"David S Johnson. 1973. Near-optimal bin packing algorithms. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.89.6.2195"},{"key":"e_1_2_2_22_1","volume-title":"Voxel-Based Solution Approaches to the Three-Dimensional Irregular Packing Problem. Operations Research","author":"Lamas-Fernandez Carlos","year":"2022","unstructured":"Carlos Lamas-Fernandez, Julia A Bennell, and Antonio Martinez-Sykora. 2022. Voxel-Based Solution Approaches to the Three-Dimensional Irregular Packing Problem. Operations Research (2022)."},{"key":"e_1_2_2_23_1","volume-title":"Affine body dynamics: Fast, stable & intersection-free simulation of stiff materials. arXiv preprint arXiv:2201.10022","author":"Lan Lei","year":"2022","unstructured":"Lei Lan, Danny M Kaufman, Minchen Li, Chenfanfu Jiang, and Yin Yang. 2022. Affine body dynamics: Fast, stable & intersection-free simulation of stiff materials. arXiv preprint arXiv:2201.10022 (2022)."},{"key":"e_1_2_2_24_1","volume-title":"Planning algorithms","author":"LaValle Steven M","unstructured":"Steven M LaValle. 2006. Planning algorithms. Cambridge university press."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.04.045"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1631\/FITEE.1400421"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13490"},{"key":"e_1_2_2_28_1","volume-title":"The three-dimensional bin packing problem. Operations research 48, 2","author":"Martello Silvano","year":"2000","unstructured":"Silvano Martello, David Pisinger, and Daniele Vigo. 2000. The three-dimensional bin packing problem. Operations research 48, 2 (2000), 256--267."},{"key":"e_1_2_2_29_1","unstructured":"NVIDIA. 2022a. CUDA release: 12.0. https:\/\/developer.nvidia.com\/cuda-toolkit"},{"key":"e_1_2_2_30_1","unstructured":"NVIDIA. 2022b. CUDA release: 12.0. https:\/\/developer.nvidia.com\/cufft"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1603929113"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.3390\/math8071130"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508409"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0134(20000501)39:2<178::AID-PROT8>3.0.CO;2-6"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq444"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.01.025"},{"key":"e_1_2_2_37_1","volume-title":"Fast parallel surface and solid voxelization on GPUs. ACM transactions on graphics (TOG) 29, 6","author":"Schwarz Michael","year":"2010","unstructured":"Michael Schwarz and Hans-Peter Seidel. 2010. Fast parallel surface and solid voxelization on GPUs. ACM transactions on graphics (TOG) 29, 6 (2010), 1--10."},{"key":"e_1_2_2_38_1","unstructured":"Sculpteo. 2023. Sculpteo Fabpilot. https:\/\/www.fabpilot.com\/."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766962"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366147"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-015-0331-2"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555525"},{"key":"e_1_2_2_43_1","unstructured":"UnionTech. 2018. Polydevs. https:\/\/polydevs3d.com\/ Version 2.2.5.33."},{"key":"e_1_2_2_44_1","volume-title":"Bedrich Benes, R M\u011bch, N Carr, Ondrej Stava, and GS Miller.","author":"Vanek Juraj","year":"2014","unstructured":"Juraj Vanek, JA Garcia Galicia, Bedrich Benes, R M\u011bch, N Carr, Ondrej Stava, and GS Miller. 2014. Packmerger: A 3d print volume optimizer. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 322--332."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8794049"},{"key":"e_1_2_2_46_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--14.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_47_1","volume-title":"State of the Art on Computational Design of Assemblies with Rigid Parts. Eurographics 2021 STAR 40","author":"Wang Ziqi","year":"2021","unstructured":"Ziqi Wang, Peng Song, and Mark Pauly. 2021. State of the Art on Computational Design of Assemblies with Rigid Parts. Eurographics 2021 STAR 40 (2021)."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90048-5"},{"key":"e_1_2_2_49_1","volume-title":"PackerBot: Variable-Sized Product Packing with Heuristic Deep Reinforcement Learning. In 2021 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 5002--5008","author":"Yang Zifei","year":"2021","unstructured":"Zifei Yang, Shuo Yang, Shuai Song, Wei Zhang, Ran Song, Jiyu Cheng, and Yibin Li. 2021. PackerBot: Variable-Sized Product Packing with Heuristic Deep Reinforcement Learning. In 2021 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 5002--5008."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818064"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2001.958278"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392468"},{"key":"e_1_2_2_53_1","volume-title":"A fast sweeping method for eikonal equations. Mathematics of computation 74, 250","author":"Zhao Hongkai","year":"2005","unstructured":"Hongkai Zhao. 2005. A fast sweeping method for eikonal equations. Mathematics of computation 74, 250 (2005), 603--627."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i1.16155"},{"key":"e_1_2_2_55_1","volume-title":"Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797","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)."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592126","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:46Z","timestamp":1750178266000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1145\/3592126"],"URL":"https:\/\/doi.org\/10.1145\/3592126","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,26]]},"assertion":[{"value":"2023-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}