Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects
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 object...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152166 |
| _version_ | 1811095777883193344 |
|---|---|
| author | Cui, Qiaodong Rong, Victor Chen, Desai Matusik, Wojciech |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Cui, Qiaodong Rong, Victor Chen, Desai Matusik, Wojciech |
| author_sort | Cui, Qiaodong |
| collection | MIT |
| description | 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 {\it interlocking-free} 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. |
| first_indexed | 2024-09-23T16:27:34Z |
| format | Article |
| id | mit-1721.1/152166 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:27:34Z |
| publishDate | 2023 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1521662024-01-12T19:32:35Z Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects Cui, Qiaodong Rong, Victor Chen, Desai Matusik, Wojciech Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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 {\it interlocking-free} 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. 2023-09-15T15:37:50Z 2023-09-15T15:37:50Z 2023-08-01 2023-08-01T07:53:49Z Article http://purl.org/eprint/type/JournalArticle 0730-0301 https://hdl.handle.net/1721.1/152166 Cui, Qiaodong, Rong, Victor, Chen, Desai and Matusik, Wojciech. 2023. "Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects." ACM Transactions on Graphics, 42 (4). PUBLISHER_POLICY en https://doi.org/10.1145/3592126 ACM Transactions on Graphics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Cui, Qiaodong Rong, Victor Chen, Desai Matusik, Wojciech Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects |
| title | Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects |
| title_full | Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects |
| title_fullStr | Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects |
| title_full_unstemmed | Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects |
| title_short | Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects |
| title_sort | dense interlocking free and scalable spectral packing of generic 3d objects |
| url | https://hdl.handle.net/1721.1/152166 |
| work_keys_str_mv | AT cuiqiaodong denseinterlockingfreeandscalablespectralpackingofgeneric3dobjects AT rongvictor denseinterlockingfreeandscalablespectralpackingofgeneric3dobjects AT chendesai denseinterlockingfreeandscalablespectralpackingofgeneric3dobjects AT matusikwojciech denseinterlockingfreeandscalablespectralpackingofgeneric3dobjects |