The chore of packing just got faster and easier

packing-algorithmsfftoptimization3d-printingcomputational-geometry

Abstraction: MIT SSP algorithm uses FFT to solve 3D object packing at large scale

Key points:

MIT and Inkbit researchers developed "dense, interlocking-free and Scalable Spectral Packing" (SSP), presented at SIGGRAPH 2023
The 3D bin-packing problem is NP-hard; SSP addresses it via voxelization and a fast Fourier transform (FFT)-based collision and gap metric — a novel application of FFT to packing
Packed 670 objects in 40 seconds (36% density) and 6,596 objects in 2 hours (37.3% density) — "several orders of magnitude" faster than prior methods
Algorithm ensures interlocking-free arrangements: every object can be placed and removed without collision, important for unpacking
Primary application is 3D printing / additive manufacturing, where current tray utilization is ~20%; SSP targets significantly higher utilization
Also applicable to warehouse and shipping logistics

Connections: Mit · Inkbit · Combinatorial Optimization · Algorithms · 3d Printing