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

SUPPLEMENTAL VIDEOS