perspectives for robotics, manufacturing and 3D printing

The question of the densest possible packing of identical spheres was originally answered in 1611 by Johannes Kepler, known for his laws on planetary motion. But the more complex problem of the optimal arrangement of 3D objects of various sizes and shapes still remains unsolved.

However, a group of researchers from MIT and Inkbit, led by Wojciech Matusik, introduced a new computational methodology they call “Dense, Non-Overlapping and Scalable Spectral Packing” (SSP). This technique will be presented at the SIGGRAPH 2023 conference, the largest conference on computer graphics and interactive methods.

The SSP approach involves the process of “voxelizing” a container, represented as a 3D grid of small cubes or voxels. The algorithm then calculates the number of free voxels for each object and determines where the object can be placed without intersecting with other objects. The researchers use another metric that is designed to maximize packing density.

The last step of the SSP algorithm is to ensure that, with the optimal placement, each object can fall into its assigned place, and can also be separated from other objects when unpacked. Using the Fast Fourier Transform (FFT), the team was able to speed up packing by orders of magnitude.

In one demo, the new algorithm efficiently placed 670 objects in just 40 seconds, achieving a packing density of around 36%. He placed 6,596 objects in 2 hours with a packing density of 37.30%. “The densities we’re getting close to 40% are significantly better than those we get with traditional algorithms,” says Matusik, “and they’re also faster.”

“This is a breakthrough solution to the long-standing problem of efficient organization of 3D objects,” comments Bedrich Benes, professor of computer science at Purdue University.

The technique could be useful for warehousing and shipping companies, where different objects are regularly packed in boxes of different sizes, according to Matusik. However, he and his colleagues are particularly interested in 3D printing applications. “If we can increase the packing density,” he adds, “we can increase the overall efficiency of the printing process, thereby reducing the overall cost of the parts produced.”

So far, the problem of the optimal location of deformable objects or articular objects remains open, and it can be solved in future works.