Researchers from MIT and Inkbit have developed a new packing algorithm called “dense, interlocking-free and Scalable Spectral Packing” (SSP) that optimizes the packing of 3D objects with varied sizes and shapes. While the general problem of object packing remains unsolved, SSP represents a significant leap forward in making the task more manageable.
Voxelized
The algorithm’s approach involves voxelizing both the container and the objects to be packed, representing them as grids of tiny cubes. By calculating collision metrics at each voxel, the algorithm determines the available space for an object, considering overlaps and collisions. Then, it computes a metric to maximize the packing density by minimizing gaps between objects and the container walls.
To achieve these results, the researchers employed the fast Fourier transform (FFT), a mathematical technique never used for packing problems before (as far as they know). This allowed them to solve voxel overlap and gap minimization with a limited set of calculations, significantly reducing computational time.
In tests, the algorithm efficiently placed 670 objects with a density of 36% in just 40 seconds. It took two hours to arrange 6,596 objects with a density of 37.30%. These densities and speeds outperformed traditional packing algorithms.
Tetris-like
The implications of this research extend beyond traditional packing scenarios, with potential applications in areas such as robotics, manufacturing, warehousing, and shipping.
And naturally, the algorithm offers promise in the field of 3D printing, where increased packing density can enhance the efficiency and reduce costs in the additive manufacturing process.
While the algorithm provides solutions for rigid objects and 3D printing, challenges remain in arranging deformable and articulated objects. Future research may address these complexities.
Come and let us know your thoughts on our Facebook, Twitter, and LinkedIn pages, and don’t forget to sign up for our weekly additive manufacturing newsletter to get all the latest stories delivered right to your inbox.