MIT and Inkbit present Spectral Packing method for packing 3D objects

In a paper that will be featured at the upcoming SIGGRAPH 2023 conference, MIT CSAIL researchers, in collaboration with Inkbit, presented Spectral Packing, a new computational methodology that could revolutionize the way AM users pack 3D objects in stackable 3D printing technologies, with implications ranging from shipping to serial AM production. This comes as a solution to a centuries-old problem that has baffled mathematicians and scientists alike.

In the collaboration between MIT and Inkbit, the team of researchers, led by Wojciech Matusik, CTO at Inkbit and professor of electrical engineering and of computer science at MIT, developed the novel computational method to maximize the throughput of 3D printers by packing objects as densely as possible and accounting for interlocking-avoidance (between many parts with different shapes and sizes) and scalability.

Spectral Packing is like playing Tetris in 3D. Imagine breaking a box and toys into tiny LEGO-like blocks called voxels. The algorithm smartly checks if toys fit without overlapping and tries to use space efficiently. Using a math shortcut called Fast Fourier Transform, it does these calculations super fast. Essentially, it’s a speedy, brainy way to pack 3D objects tightly in a box.

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 (In computational complexity theory, NP-hardness, or non-deterministic polynomial-time hardness, is the defining property of a class of problems that are informally “at least as hard as the hardest problems in NP). Even approximate solutions are challenging. This is due to the difficulty of handling interactions between objects with arbitrary 3D geometries and vast combinatorial search space. Moreover, the packing must be interlocking-free for real-world applications.

In this work, the researchers first introduce a novel packing algorithm to search for placement locations given an object. This method leverages a discrete voxel representation. The researchers then formulate collisions between objects as correlations of functions computed efficiently using Fast Fourier Transform (FFT). To determine the best placements, they utilize a novel cost function, which is also computed efficiently using FFT.

Finally, the researchers show how interlocking detection and correction can be addressed in the same framework resulting in interlocking-free packing. They thus propose a challenging benchmark with thousands of 3D objects to evaluate the algorithm.

The team demonstrated the efficiency of the new algorithm by placing 670 objects in just 40 seconds, achieving a packing density of about 36 percent – significantly better than traditional algorithms. This breakthrough holds immense potential, especially in 3D printing, where increasing packing density directly translates into reducing the cost of manufactured parts. It’s also invaluable for shipping and warehouse companies.

Overall, this method demonstrates state-of-the-art performance on the benchmark when compared to existing methods in both density and speed.

Videos are available here.

Download the full paper here.