A new computational method facilitates the dense placement of objects inside a rigid container.
People often find it difficult to pack in a uniform way 3D objects of varied sizes and shapes. This problem, in fact, is classified as NP-hard, which means it cannot be solved exactly — or even approximately, to a high degree of precision — without requiring absurdly long computational times that could take years or decades – not to mention the number of pieces that need to be fit into a confined space.
A team of researchers from MIT and Inkbit (an MIT spinout company based in Medford, Massachusetts) are working on a new computational methodology that could simplify this task.
The technique called “dense, interlocking-free and Scalable Spectral Packing,” or SSP consists in three main steps:
- The first step in SSP is to work out an ordering of solid 3D objects for filling a fixed container. One possible approach, for example, is start with the largest objects and end with the smallest. The next step is to place each object into the container. To facilitate this process, the container is “voxelized,” meaning that it is represented by a 3D grid composed of tiny cubes or voxels, each of which may be just a cubic millimeter in size. The grid shows which parts of the container — or which voxels — are already filled and which are vacant.
- The next step is to sift through all the possible placements and determine the best available position to put the object. For this task, the researchers compute another metric at each voxel, which is designed to locally maximize the packing density. This metric measures the gaps between the object and the container wall — or between the object that’s being moved and those objects already situated within the container. If the object is placed in the very center, for example, the metric would likely assign a high value. The goal, however, is to minimize gaps between objects, and that can be achieved by putting the object where the metric value is the lowest. “It’s kind of like the game Tetris,” Matusik explains. “You want to leave as little empty space as possible.”
- The last step of the SSP algorithm is to ensure that, for a seemingly desirable arrangement, every object can actually get into its assigned site, or equivalently, that every object can be separated from the other objects when the container is being unpacked. Which is to say that the packing must be “interlocking-free” — a condition for avoiding configurations such as interlocked rings.
Figuring out the best placements for each and every object as the container fills up obviously requires a lot of calculations. But the team employed a mathematical technique, the fast Fourier transform (FFT), which had never been applied to the packing problem before. By using FFT, the problems of minimizing voxel overlap and minimizing gaps for all voxels in the container can be solved through a relatively limited set of calculations, such as simple multiplications, as opposed to the impractical alternative of testing out all possible locations for the objects to be positioned inside. And that makes packing faster by several orders of magnitude.
What does it have to do with 3D printing, you might ask?
The approach can, of course, be useful for warehouse and shipping companies where various objects are routinely packed into boxes of different sizes. However, the research team is especially interested in applications in 3D printing, also called additive manufacturing. Parts are normally manufactured in batches and placed on trays. However, current approaches “have very limited utilization of the [container] volume” — typically around 20 percent. “If we can increase the packing density, we can increase the overall efficiency of the printing process, thus reducing the overall cost of manufactured parts,” the lead researcher explains.
While this research offers new and improved procedures for 3D printing, as well as for packing rigid objects, the problem of how best to arrange deformable objects or articulated objects — the latter consisting of more than one rigid part connected by joints — is still open, and may be addressed in future work. In the meantime, if people ever find themselves with just two hours to fit more than 6,000 objects into a storage bin, there is no need to despair. Help may be just an algorithm away.
Remember, you can post job opportunities in the AM Industry on 3D ADEPT Media free of charge or look for a job via our job board. Make sure to follow us on our social networks and subscribe to our weekly newsletter : Facebook, Twitter, LinkedIn & Instagram ! If you want to be featured in the next issue of our digital magazine or if you hear a story that needs to be heard, make sure to send it to contact@3dadept.com