A tetris to pack the largest number of objects in a container

July 7 () –

An MIT-led team has developed a novel algorithm to find locations to objects within a container. and achieve faster and easier packaging.

In 1611, Johannes Kepler, known for his laws of planetary motion, offered a solution to the question of the densest possible way to arrange spheres of the same size. The famous astronomer addressed this problem when asked how to stack cannonballs so that they take up the least amount of space. Kepler concluded that the best configuration is the so-called face-centered cubic lattice, an approach commonly used in grocery stores to display oranges: each cannonball should rest in the cavity left by the four cannonballs. cannon (lined up in a tight two-by-two square) that lie directly below it. However, this was merely a conjecture that was not proven until nearly 400 years later by a mathematician at the University of Michigan..

While that solved the problem of evenly packing the spheres, the more general problem, related to the optimal way to position 3D objects of various sizes and shapes, remains unresolved. This problem, in fact, is classified as NP-hard, which means that it cannot be solved exactly, or even approximately, with a high degree of precision, without requiring absurdly long computation times that could take years or decades, depending on the number of pieces that must fit in a confined space.

However, there has been great progress, not in the form of a mathematical proof, but through a new computational methodology that makes this previously unwieldy task more manageable.

A team of researchers from MIT and Inkbit (an MIT spin-off company based in Medford, Massachusetts), led by Wojciech Matusik, an MIT professor and co-founder of Inkbit, presents this technique, which they call “dense, interlocking-free and Scalable Spectral Packing” or SSP, at SIGGRAPH 2023, the world’s largest conference on computer graphics and interactive techniques. A paper will be published next month in the ACM Transactions on Graphics magazine.

The first step in SSP is to build an order for solid 3D objects to fill a fixed container. One possible approach, for example, is to start with the largest objects and end with the smallest. The next step is to place each object in the container. To facilitate this process, the container is “voxelized,” meaning that it is represented by a 3D grid made up of tiny cubes, or voxels, each of which can be only one cubic millimeter in size. The grid shows which parts of the container, or which voxels, are already filled and which are empty.

The object to be packaged is also voxelized, again represented by an agglomeration of cubes that are the same size as those of the container. To calculate the space available for this object, the algorithm calculates a quantity called a collision metric at each voxel. It works by placing the center of the object in each voxel of the container, and then counting the number of occupied voxels that the object overlaps or “bumps into”. The object can only be placed at locations where the overlap is zero; in other words, where there are no collisions.

The next step is to analyze all the possible locations and determine the best available position to place the object. For this task, the researchers calculate 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 being moved and objects already inside the container. If the object is placed in the center, for example, the metric would probably assign a high value.

However, the goal is to minimize the gaps between the objects, and that can be achieved by placing the object where the metric value is lowest. “It’s like the game Tetris,” Matusik explains. it’s a statement. “You want to leave as little empty space as possible.”