Auto Packing for Arbitrary 3D Objects and Container

In this project, a software named Auto Packing was developed to place arbitrary objects densely inside of a single container in three-dimensional space.

Description

Packing problems occur in many different forms and also in different real-world applications. In this project we consider a variable set of objects and a single arbitrary container in 3D space. The container and objects can have any shape and are allowed to rotate. We have three different optimization criteria: packing density, percentage distribution of object types, and uniform distribution in space for object types. To solve this problem we propose 4 construction heuristics and 2 improvement heuristics. In the final configuration, all objects are placed inside of the container and no overlap exists. To evaluate the developed algorithms, we use different objects and container and also do a rough comparison to related work.




Features

  • Packing arbitrary objects into arbitrary containers in 3D
  • Intial placement of objects
  • Improvement of initial solution
  • Predefined distribution of object types (e.g. 70% apples, 30% bananas)
  • Prevents cluster tendencies (e.g. all bananas stick together) of object types

Results

We created six different problem scenarios to evaluate our algorithms. A rough comparsion was made to similar work. In the example Vase/Hearts, a higher packing density could be achieved with fewer objects. Between the construction heuristics, the GrowingSeeds Algorithm compares very well in different examples for all criteria. In the case of improvement heuristics, the local optimization is recommended, if the reliability is more important than the percentage deviation. We recommend the combination of the GrowingSeeds Algorithm and CavityFilling Algorithm. Further optimization of the collision detection between object and container pairs has big potential for run time since most of the run time is used for it.

Test scenarios with different objects and container. Packing density depends on shape of objects and container, whereas the runtime depends on the number of objects fitting inside of the container.




Packing density increases with the number of sampling points.


Local optimization: Density increases, spatial distribution remains (no clustering before), objects type distribution gets worse.

Files

Full version of the Master Thesis (German only)
Executable Demo: Linux

This video demonstrates algorithms for intial placement of the objects and solution
improvement:

In this video you can see a prototype to manually adjust a generated packing in VR:

License

This original work is copyright by University of Bremen.
Any software of this work is covered by the European Union Public Licence v1.2. To view a copy of this license, visit eur-lex.europa.eu.
The Thesis provided above (as PDF file) is licensed under Attribution-NonCommercial-NoDerivatives 4.0 International.
Any other assets (3D models, movies, documents, etc.) are covered by the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit creativecommons.org.
If you use any of the assets or software to produce a publication, then you must give credit and put a reference in your publication.
If you would like to use our software in proprietary software, you can obtain an exception from the above license (aka. dual licensing). Please contact zach at cs.uni-bremen dot de.