Algorithm to place 3D objects within a defined space

user_12449182 0
Viewed 43

I am currently trying to solve a problem to place boxes of various sizes (all cubes or rectangular prisms) within a defined volume.

In the application I am working on, a user defines a length, width, and height of a volume, as well as the length, width, and height of n boxes to place within the volume. The output will be a 3D visualization of all the boxes in space within the volume. The placement of these objects does not need to be optimal, nor do I care if boxes are touching or not, just as long as they exist in the space without overlapping.

My original approach to solve this problem was as follows:

for every box
{
    place box at (0,0,0);
    while True;
    {
        for every box that has already been placed
        {
            if the boxes overlap
            {
                create a vector pointing in the opposite direction of the other box;
                move the box along the vector some dist. X, unless at the border of the available volume;
            }
        }
        if the box didn't overlap with any other box
        {
            break out of while loop and continue to the next box;
        }
    }
}

This mostly worked. The main issue with this approach is time. When running this, the first 3 boxes take about 10 seconds, the following 3 get placed after 1:30, and the next 3 take over 10 minutes to finish. For larger assemblies, this is completely unusable. Additionally, this approach has a major flaw in that a box can get stuck between other boxes and the sides of the volume because the resulting vector will point outside of the space.

Are there any other more efficient approaches to solve similar problems that I could adapt to this situation? Again, the goal of this is not to find a perfect space optimization or to fill the entire space.

I am working with CAD, so the information available to me is anything I can access with the API, such as the global coordinates of the vertices of all of the boxes and the coordinates of the vertices of the available volume.

bin-packing language-agnostic algorithm
1 Answers

What you are trying to do is called a "packing problem", and the specific flavor is trying to pack cubes into another cube. Wikipedia is strangely pithy on this topic, but there's a more detailed article here. I know answering with links is discouraged on SO, but I think it's better than the alternative of writing a lengthy treatise on cuboid packing here :)

Your algorithm has complexity O(n2) (two loops) which would explain why it's slow. In fact, depending on how you move the boxes, it might be even worse than O(n2). I actually am not sure if it even terminates, because I can't tell where the algorithm would realize it if there were too many boxes and they couldn't fit in the space.

Since you say you correctness or optimality is not critical, a fast algorithm would be a greedy strategy:

pack boxes:
    x1, y1, z1 = 0
    x2, y2, z2 = 0
    repeat until no boxes left:
        box = take largest box
        if box can go at x1, y1, z1:
            place it there
            x1 = x1 + box length along x

            update y2, z2
        else:
            if box can go to at 0, y2, z1:
                place it there
                x1 = box length along x
                y1 = y2 + box length along y
                
                update y2, z2
            else:
                if box can go at 0, 0, z2:
                    place it there
                    x1 = box length along x
                    y1 = box length along y
                    z1 = z2 + box length along z

                    update y2, z2
                else:
                    give up (too many/too big boxes)

update y2, z2:
    y2 = max(y2, y2 + box length along y)
    z2 = max(z2, z2 + box length along z)

This is horribly inefficient, but it will run in O(n) and should be easy to implement. We are basically starting with the biggest box at origin, and stacking them along x. When we hit the wall, we do a "carriage return" by moving down y and stacking a new column. When we hit the wall along y, we instead go down z and repeat for a new plane.

When selecting the biggest box, you can use a heuristic such as volume, sum of dimensions, average dimension or even sort by width, length, height. This algorithm fails badly if your boxes are inconsistently shaped (for example, if it has to put a very tall box after a very long box), so you should pick a heuristic that mitigates this.

Some optimizations could be:

  • Sorting the boxes into several classes like tall-fat-long and stack simultaneously from different corners -- you can use clustering here
  • Use a zig-zag pattern and always push each box flush with the previous column
  • Stack in a spiral pattern
  • Start by rotating all boxes so that their longest edge is on x, next on y, next on z

However a lot of the faster/more optimal methods will involve maintaining an efficient data structure of the growing box pile "surface", so you don't have to do NxN collision checking.

user_194385770
Related