Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects

ACM Transactions on Graphics (SIGGRAPH 2023)

Qiaodong Cui, Inkbit | Victor Rong, MIT | Desai Chen, Inkbit | Wojciech Matusik, MIT and Inkbit

 

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 interlocking-free for real-world applications.

Left: We select over 6000 objects from Thingi10K as our benchmark, which consists of many challenging geometries. Middle: We densely pack the benchmark into a cuboid with a packing density of 35.77%. The packing is free of interlocking. Right: An in-focused view highlighting densely packed objects.

 

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.

 

ADDITIONAL RESOURCES
Paper

PDF

Video

MP4

Slides

PDF

Datasets

ZIP

SUPPLEMENTAL VIDEOS

This work was conducted at Inkbit LLC and is part of Inkbit’s patented and patent pending commercial 3d printing solutions.

 

    

Ready to Learn More?