3D Container Packing - Optimierungen für AutoPacking

AutoPacking is a software which packs arbitrary 3D-objects into a 3D-container. The goal of this thesis was to improve the runtime and packing quality of the program. In addition to this the packing density on the container boundary should be improved.

Description

Most packing problems are NP-hard and therefore no efficient algorithm to solve them is known. The most timeconsuming part of AutoPacking the collisions detection betweent the objects and the container. AutoPacking uses InnerSphereTrees (ISTs) to represent its objects and the container. One potential problem is that the representation of the container with a bounding volume hierarchy always contains the whole packing space of the container. Therefore the collision detection algorithm needs to traverse a lot of the hierarchy.

A solution to this was to split the hierarchy into parts so that each part only contains a fraction of the container. Another solution was to use the GPU to look for collisions between the container and the objects. The GPU approach does not use the hierarchy of the container and instead checks each sphere of the container against the hierarchy of the objects.

Another problem was that some of the packed objects would overlap very strong with the container. This was solved by using DOP-Trees to represent the container and the objects when checking for collisions between the objects and the container.

To improve the packing density on the container boundary a new algorithm was implemented. This algorithm uses the sampling points of AutoPacking to create a more dense sampling at the boundary.

Results

This thesis uses the GrowingSeedsAlgorithm from AutoPacking for the evaluation as this was the best tested candidate.

As you can see for the szenario vase with hearts all developed variants run faster than the original version.

For the szenario hand with fruits on the other hand the runtime of the version with only on DOP-Tree representing the container is slower than the original version.

The GPU versions are only faster if you use only one IST for the container. If you divide the container then these get slower than the CPU version. The packing quaility improves when you use more than one IST or the DOP-Tree.

The newly developed improvement heuristic is gets better results if the settings for the sampling of the container are equal for the inital packing and the improvement. When the container is sampled with a higher resolution for the improvement then the CavitiyFillingGrowingAlgorithm produces equal results.

Files

Full version of the Master Thesis (German only)

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.