24/7 Space News
The chore of packing just got faster and easier
An MIT-led team developed a novel packing algorithm to search for placement locations within a given object.
The chore of packing just got faster and easier
by Steve Nadis for MIT CSAIL
Boston MA (SPX) Jul 08, 2023

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, 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 open-access paper, written by Qiaodong Cui of Inkbit, MIT graduate student Victor Rong SM '23, Desai Chen PhD '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 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."

That's not the whole story, however, because the foregoing discussion concerns an object that's moved, or "translated," into the container while maintaining a fixed orientation in space. The computer may go through this whole process with many different orientations for the same object until it finds the orientation that best fits the space.

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.

In one demonstration, the new algorithm efficiently placed 670 objects in just 40 seconds, achieving a packing density of about 36 percent. It took two hours to arrange 6,596 objects with a packing density of 37.30 percent. "The densities we're getting, close to 40 percent, are significantly better than those obtained by traditional algorithms," Matusik says, "and they're also faster."

This work represents "a breakthrough solution to a longstanding problem of effectively organizing 3D objects," comments Bedrich Benes, a professor of computer science at Purdue University. "The proposed solution maximizes the packing density and has the potential to find applications in many practical areas, ranging from robotics to manufacturing. Moreover, the no-interlocking solutions are suitable for computer-controlled environments."

The approach can, of course, be useful for warehouse and shipping companies where various objects are routinely packed into boxes of different sizes, according to Matusik. However, he and his colleagues are especially interested in applications in 3D printing, also called additive manufacturing. Parts are normally manufactured in batches and placed on trays. However, current approaches, Matusik says "have very limited utilization of the [container] volume" - typically around 20 percent. "If we can increase the packing density," he adds, "we can increase the overall efficiency of the printing process, thus reducing the overall cost of manufactured parts."

While the SIGGRAPH paper 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.

Research Report:"Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects"

Related Links
Computer Science and Artificial Intelligence Laboratory (CSAIL)
Space Technology News - Applications and Research

Subscribe Free To Our Daily Newsletters

The following news reports may link to other Space Media Network websites.
Mountain of strategic metals stranded in DR Congo begins to shift
Tenke Fungurume, DRC (AFP) July 6, 2023
A mountain of copper and cobalt worth up to $2 billion is piled up in DR Congo, symbolising the wildly volatile market for metals touted as crucial to the green energy revolution. As many as 13,000 tonnes of cobalt powder are thought to be hoarded in the Chinese-owned Tenke Fungurume mine - equivalent to seven percent of the world's production last year. It was stuck for over nine months, alongside an even larger stockpile of copper, due to a dispute over royalties between owners CMOC and the D ... read more

Long history and bright future of space sample deliveries

SpaceX Dragon splashes down carrying 3,600 pounds of samples, experiments

SpaceX Dragon to return to Earth with experiments, samples from ISS

Virgin Galactic's use of the 'Overview Effect' to promote space tourism is a terrible irony

A space rocket hotter than the Sun

Unfavourable weather delays final Ariane 5 launch

ISRO terminates hot test for semi-cryogenic engine midway

Flight software for Artemis II meets testing checkpoint

Ingenuity phones home

Gullies on Mars could have been formed by recent periods of liquid meltwater

Up up up and finally over: Sols 3873-3875

Advanced space technology enabling 2024 ESCAPADE mission to Mars

Tianzhou 5 reconnects with Tiangong space station

China questions whether there is a new moon race afoot

Three Chinese astronauts return safely to Earth

Scientific experimental samples brought back to Earth, delivered to scientists

ESA unveils its comprehensive, high-resolution image library in a revamped platform

AST SpaceMobile and Maritime Launch Services Boost Capital with Stock Offerings

Apex raises $16M in Series A funding

AST SpaceMobile confirms 4G capabilities to everyday smartphones directly from space

Mountain of strategic metals stranded in DR Congo begins to shift

The chore of packing just got faster and easier

China Achieves Milestone in Satellite-to-ground Laser Communications

No additional radiation at cruising altitude off the coast of Brazil

A surprise chemical find by ALMA may help detect and confirm protoplanets

Reconstructing alien astronomers' view of our home galaxy's chemistry

New era of exoplanet discovery begins with images of 'Jupiter's Younger Sibling'

Evidence of the amino acid tryptophan found in space

Unveiling Jupiter's upper atmosphere

ASU study: Jupiter's moon Europa may have had a slow evolution

Juno captures lightning bolts above Jupiter's north pole

Colorful Kuiper Belt puzzle solved by UH researchers

Subscribe Free To Our Daily Newsletters


The content herein, unless otherwise known to be public domain, are Copyright 1995-2023 - Space Media Network. All websites are published in Australia and are solely subject to Australian law and governed by Fair Use principals for news reporting and research purposes. AFP, UPI and IANS news wire stories are copyright Agence France-Presse, United Press International and Indo-Asia News Service. ESA news reports are copyright European Space Agency. All NASA sourced material is public domain. Additional copyrights may apply in whole or part to other bona fide parties. All articles labeled "by Staff Writers" include reports supplied to Space Media Network by industry news wires, PR agencies, corporate press officers and the like. Such articles are individually curated and edited by Space Media Network staff on the basis of the report's information value to our industry and professional readership. Advertising does not imply endorsement, agreement or approval of any opinions, statements or information provided by Space Media Network on any Web page published or hosted by Space Media Network. General Data Protection Regulation (GDPR) Statement Our advertisers use various cookies and the like to deliver the best ad banner available at one time. All network advertising suppliers have GDPR policies (Legitimate Interest) that conform with EU regulations for data collection. By using our websites you consent to cookie based advertising. If you do not agree with this then you must stop using the websites from May 25, 2018. Privacy Statement. Additional information can be found here at About Us.