View Full Version : fill area with cubes

Colin

02-04-2016, 12:40 AM

Hi there,

I've been working non-stop on a project and have burned myself out... quite literally... and now I am having a problem that I no longer can get my head around. I'm hoping someone can help.

Anyways the issue is.

Imagine I have an area in 3d space

x: 300 - 500

y: 300 - 500

z: 300 - 500

inside of this area is some small floating boxes ( i have positions/scales, and total volume when added together) - What i need to do is calculate positions/offsets/sizes of new boxes to surround the existing ones.

It is similar to the "truck" filling problem, except that the boxes are not necessarily stacked on top of each other, and we do not have pre-defined boxe scales to put inside, we need to create new ones to best fit/fill the space.

Can anyone help me with this?

Super Vegeta

02-04-2016, 01:09 PM

If you're not taking rotation into account, then I think this would be quite easily solvable using an Octree (https://en.wikipedia.org/wiki/Octree). Using the tree, you can detect the edges of the polyhedron(s) formed by existing cubes, and then calculate new boxes to wrap it.

Colin

02-04-2016, 05:29 PM

Yes I am not concerned about direction, I have built a list of edges of the cubes, but exactly the problem is how to place new cubes around them, in 2d this seems relatively simple, but as soon as you add a 3rd dimension, it becomes a whole new set of problems :( and I am just totally lost as to where to go now.

My original thought is to order the list of cubes/xyz into lowers->highest, then run through them building new cubes to the left of, but then the issue is not all cubes are touching, so there would be gaps left between multiple cubes, it must also take into consideration the positions of other cubes on that directional plane.

SilverWarior

03-04-2016, 01:58 PM

This is the logic that I would use for such problem. It probably isn't the fastest one but it should finish the job.

1. I would divide the 3D space you have into a grid whose density would be suitable so that every existing box fits into the grid perfectly.

2. I would give every existing box a unique ID and then assign that ID to the gird cells that are being occupied by that box. This would give me information about which grid cells are occupied and which not.

3. I would try to find first empty grid cell and place a new box in it (just 1,1,1 box for now). It is preferable if this starting cell is in a corner. And don't forget to give it a unique ID

4. Then I would start expanding the size of this box while maintaining its aspect ratio (2,2,2 then 3,3,3, then 4,4,4 etc.) until the size can no longer be expanded.

//Only used for rectangular cuboids

5. After that if you don't need for the boxes to have all sizes equal you can try and start extruding (expanding) a single face of this new box.

6. Later you can try extruding some other face of the box. If your initial box was placed in corner you would have to do this only for two box faces max.

7. After you fully expanded your first box you find the next free grid cell and repeat the process from 3. step

8. Finally you simply get dimensions of your new boxes with the help of having unique ID's stored in grid cells

This approach should fill all the spaces and also try to use as biggest boxes as possible to do so.

Colin

04-04-2016, 10:36 PM

Some interesting ideas, thanks. I will post my solution when I put everything together.

phibermon

25-09-2016, 01:01 AM

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.

Powered by vBulletin® Version 4.2.5 Copyright © 2020 vBulletin Solutions Inc. All rights reserved.