MIT has just developed a new computational method that can figure out how to arrange a dense placement of objects inside a rigid container – while also guaranteeing that the objects are separable/interlock free (can be taken out again without getting stuck on each other).

The optimal way of positioning 3D objects of varied sizes and shapes in a container is still considered an unsolved problem. In fact, it is classified as NP-hard, which means it cannot be solved exactly — or even approximately, to a high degree of precision — without gargantuan computational times that could take years or decades depending on the number of pieces that need to be fit into a confined space.

Researchers from MIT and Inkbit (an MIT spinout company in Medford, Massachusetts), headed by Wojciech Matusik, an MIT professor and Inkbit co-founder, is presenting this technique, which they call “Dense, interlocking-free and Scalable Spectral Packing,” or SSP, this August at SIGGRAPH 2023

The method leverages a discrete voxel representation and formulates collisions between objects as correlations of functions computed efficiently using a novel cost function that can be efficiently solved with a Fast Fourier Transform (FFT).

Definitely worth checking out.