KNAPSAK

This repository contains a simple Python implementation of a solution procedure for variants of (what is sometimes referred to as) the Orthogonal Minimum Container Packing problem [1]. We utilize VTK data structures and methods, and the simulated (dual) annealing optimization algorithm in SciPy. The implementation captured here is intended to form a basis for study of cutting-stock, knapsack, and bin packing problems, with more sophisticated and/or specialized optimization algorithms.

Setup

We require Python 3 with NumPy, SciPy, and VTK packages installed.

A virtual environment may be convenient for this. On a Linux system, create a virtual environment env and install the required packages with the following commands:

$ python3 -m venv ./env
$ source env/bin/activate
$ pip install -r requirements.txt

Or on a Windows system, using Powershell:

> python3 -m venv .\env
> .\env\Sctripts\Activate.ps1
> pip install -r .\requirements.txt

Usage

Pack n copies of each mesh into an axis-aligned bounding box with a minimized volume:

python main.py opt_str vis_flg n1 mesh1.stl n2 mesh2.stl ...

opt_str specifies the variant of the problem, and may take the following values:

• boxsix : axis-aligned bounding box collisions with 6 rotations.
• soxsix : axis-aligned bounding box collisions with 6 rotations and scaling along each coordinate axis.
• obj24r : decimated STL mesh collisions with 24 rotations; all those rotations which map a cube unto itself.
• objall : decimated STL mesh collisions with all rotations.

vis_flg : switches on (1) or off (0) rendering the latest minimum during the optimization process.

Note:

• A decimation procedure, which reduces the number of triangles in each mesh to 1000, is applied internally.
• Meshes are increased in size by 1% in the STL-mesh-based collision detection.
• The simulated (dual) annealing algorithm is set to terminate after 1 million function evaluations in the case of STL mesh collision detection, and 10 million evaluations in the case of axis-aligned bounding box based collisions.

Examples

Figure 1: Example STL meshes (Armadillo, Stanford Bunny, 3DBenchy, Dragon, and a big cone).

Example 1

python main.py obj24r 1 1 stl/Bunny.stl 2 stl/Armadillo.stl 3 stl/3DBenchy.stl 4 stl/Dragon.stl 1 stl/Cone.stl

Figure 2: Packing one bunny, two armadillos, three benchy boats, four dragons, and one big cone, with 24 rotations permitted and collisions detected on decimated STL meshes.

Example 2

python main.py objall 1 1 stl/Bunny.stl 2 stl/Armadillo.stl 3 stl/3DBenchy.stl 4 stl/Dragon.stl 1 stl/Cone.stl

Figure 3: Packing one bunny, two armadillos, three benchy boats, four dragons, and one big cone, with all rotations permitted and collisions detected on decimated STL meshes.

References

[1] Alt, H., & Scharf, N. (2018). Approximating smallest containers for packing three-dimensional convex objects. International Journal of Computational Geometry & Applications, 28(02), 111-128.