Bit late on this one but a faster solution would be to sort (quicksort, bubblesort etc) three lists, one for each axis, using the minimum and maximum extents of each box in that given axis. When sorted you iterate through each list calculating the interval/distance between each box - the largest in each axis representing the largest free 'slot' in that dimension.
Then you take the largest from all three axis and using the minimum/maximum extents of the two boxes / area edge either side of the gap for X,Y and Z - that's your biggest possible, non intersecting box.
Add the box to the set and then repeat the process until no interval (gap) exists. If you require a minimum gap between boxes, add that border to the box sizes before the sorting stage - for minimum sizes of boxes, just ignore any interval (gap) below a certain value.
For cubes you just make sure that the largest from all three sets is bigger than the length of one side, or you could just find the first in X that is bigger, then the first in Y, etc to find your first available spot - the direction you start searching each sorted list lets you fill the smallest or the biggest spaces first etc
---
In 2D you can use a similar technique to create texture atlases or in 1D of course it's a good start for a defragmentation algorithm.
Reply With Quote
Bookmarks