Optimizing 3D Object Placement in Confined Spaces

Monday - July 17 2023, 00:50 UTC - 1 year ago

A team of researchers from MIT and Inkbit has presented a new computational methodology, called "dense, interlocking-free and Scalable Spectral Packing", for guiding the optimal placement of 3D objects in confined spaces. The technique uses the voxelization process to create 3D grids representing the container and object to calculate a collision metric for each voxel, and then sorts through these to determine the best position for the object.

In 1611, Johannes Kepler—known for his laws of planetary motion—offered a solution to the question concerning the densest possible way to arrange equal-sized spheres. The famed astronomer took on this problem when asked how to stack cannonballs so as to take up the least amount of space. Kepler concluded that the best configuration is a so-called face-centered cubic lattice—an approach commonly used in grocery stores for displaying oranges: Every cannonball should rest in the cavity left by the four cannonballs (lined up in a tight, two-by-two square) lying directly below it. This was merely a conjecture, however, that was not proven until almost 400 years later by a University of Michigan mathematician.

While that settled the issue of uniform sphere packing, the more general problem, regarding the optimal way of positioning 3D objects of varied sizes and shapes, is still unsolved. 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, depending on the number of pieces that need to be fit into a confined space.

Nevertheless, there has been some major progress, not in the form of a mathematical proof but rather through a new computational methodology that makes this previously unwieldy task more tractable. A team of researchers from MIT and Inkbit (an MIT spinout company based in Medford, Massachusetts), headed by Wojciech Matusik Ph.D. '03, 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 world's largest conference on computer graphics and interactive techniques. An accompanying paper, written by Qiaodong Cui of Inkbit, MIT graduate student Victor Rong SM '23, Desai Chen Ph.D. '17 (also of Inkbit), and Matusik—will be published next month in the journal ACM Transactions on Graphics.

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 object to be packed is also voxelized, again represented by an agglomeration of cubes having the same size as those in the container. To figure out the available space for this object, the algorithm then computes a quantity called the collision metric at each voxel. It works by placing the center of the object at every voxel in the container and then counting the number of occupied voxels the object overlaps, or "collides," with. The object can only be placed in locations where the overlap is zero—in other words, where there are no collisions.

The next step is to sift through all the computed collision metrics to find the one with the least amount of overlap—the location that will accommodate the object with the most efficiency. In this way, the algorithm can systematically determine an optimal placement for each 3D object in a container.