My algorithm that extracts the largest box that can be made from smaller boxes, is too slow

Question

Imagine a cube based world (such as Minecraft, Trove, or Cube World) where everything is made up of identically sized cubes and all the cubes are of the same kind.

The goal is to represent the world with the fewest number of rectangular boxes (by merging cubes but retaining convex shape (aka, a rectangular box shape)). My algorithm succeeds at this, but its performance is too slow for its intended purpose. Are there faster algorithms?

The pseudo-C#-code for my algorithm is basically:

struct Coordinate { int x,y,z; }; //<-- integer based grid
HashSet<Coordinate> world; // <-- contains all the cubes

//width, height, and length represent how many cubes it spans
struct RectangularBox { Coordinate coord; int width,height,length; }

void Begin()
{
    List<RectangularBox> fewestBoxes = new List<RectangularBox>();
    while(world.Count > 0)
    {
         RectangularBox currentLargest = ExtractLargest();
         fewestBoxes.Add(currentLargest);
         world.RemoveRange(currentLargest.ContainedCubes());
    }
    //done; `fewestBoxes` contains the fewest rectangular boxes needed.
}

private RectangularBox ExtractLargest()
{
    RectangularBox largestBox = new RectangularBox();
    foreach (Coordinate origin in world)
    {
        RectangularBox box = FindMaximumSpan(origin);
        if (box.CalculateVolume() >= largestBox.CalculateVolume())
            largestBox = box;
    }
    return largestBox;
}

private RectangularBox FindMaximumSpan(Coordinate origin)
{
    int maxX, maxY,maxZ;
    while (world.Contains(origin.Offset(maxX, 0, 0))) maxX++;
    while (world.Contains(origin.Offset(0, maxY, 0))) maxY++;
    while (world.Contains(origin.Offset(0, 0, maxZ))) maxZ++;

    RectangularBox largestBox;
    for (int extentX = 0; extentX <= maxX; extentX++)
        for (int extentY = 0; extentY <= maxY; extentY++)
            for (int extentZ = 0; extentZ <= maxZ; extentZ++)
            {
                int lengthX = extentX + 1;
                int lengthY = extentY + 1;
                int lengthZ = extentZ + 1;
                if (BoxIsFilledWithCubes(origin, lengthX, lengthY, lengthZ))
                {
                    int totalVolume = lengthX * lengthY * lengthZ;
                    if (totalVolume >= largestBox.ComputeVolume())
                        largestBox = new RectangularBox(origin, lengthX, lengthY, lengthZ);
                }
                else
                    break;
            }
    return largestBox;
}

private bool BoxIsFilledWithCubes(Coordinate coord, 
    int lengthX, int lengthY, int lengthZ)
{
    for (int gX = 0; gX < lengthX; gX++)
        for (int gY = 0; gY < lengthY; gY++)
            for (int gZ = 0; gZ < lengthZ; gZ++)
                if (!world.Contains(coord.Offset(gX, gY, gZ)))
                    return false;
    return true;
}

Essentially, for every block in the world, it first finds how many contigious blocks there are in each of the three positive dimensions (+X, +Y, +Z). And then it kinda flood-fills that volume and checks which is the largest filling that isn't missing any blocks.

Update: Since I seemed to have implied this was for a game's rendering engine, I just want to clarify, this isn't for a game's rendering engine; it's for a file-converter; no GUI.

@Rotem Perhaps, but I'm actually looking for alternative algorithms rather than a review of my code. I've provided my code just as a force of habit. — Mr. Smith, Jul 21 '15 at 09:28
Algorithm questions are more suited to SE sites like computer science... — Bakuriu, Jul 21 '15 at 12:35
It also depends on how often you call the method. If you call it every frame or only when a block changes. These games usually have chunks (specific sized rectangle ex: 64x64x32 blocks), cache values as much as possible and calculate only per chunk. And only calculate these values on the visible blocks. — the_lotus, Jul 21 '15 at 12:58
“Imagine a cube based world (such as Minecraft)” What is this Minecraft of which you speak. — Paul D. Waite, Jul 21 '15 at 13:07

score 6 · Answer 1 · edited Apr 12 '17 at 07:31

You can make use of the fact that when

 BoxIsFilledWithCubes(c,x,y,z)

returns true, then it is not necessary to check in BoxIsFilledWithCubes(c,x+1,y,z) all those cubes in the coordinate range "(c,x,y,z)" again. You need only to check those cubes with the new x-coordinate c.x + (x+1). (Same is true for y+1, or z+1). More generally, by splitting up a box into two smaller boxes (for which you might already know if they are both filled with cubes, or not both filled), you can apply a divide-and-conquer technique here, which becomes faster than your original approach when you cache the intermediate results.

To accomplish this, you start implementing BoxIsFilledWithCubes(c,x,y,z) recursively, for example:

 bool BoxIsFilledWithCubes(coord,lx,ly,lz)
 {
     if(lx==0|| ly==0 || lz==0)
        return true;
     if(lx==1 && ly==1 && lz==1)
          return world.Contains(coord);
     if(lx>=ly && lx>=lz)  // if lx is the maximum of lx,ly,lz ....
         return BoxIsFilledWithCubes(coord,lx/2,ly,lz) 
             && BoxIsFilledWithCubes(coord.Offset(lx/2,0,0), lx-lx/2, ly, lz);
     else if(ly>=lz && ly>=lx)  
         // ... analogously when ly or lz is the maximum

 }

and then use memoization (like it is discussed here) to avoid any repeated calls to BoxIsFilledWithCubes with the same parameters. Note you will have to clear the memoization cache when you apply a change to your world container, like by world.RemoveRange. Nevertheless I guess this will make your program faster.

score 5 · Answer 2 · answered Jul 21 '15 at 10:00

5

Build up an octree with a leaf node aabb size of the size of your box. While traversing the octree you can cheaply merge nodes. Completely filled nodes are trivial to merge (new box = parent aabb), while for partially filled nodes, you can use a variant of your current algorithm to check merge-ability.

answered Jul 21 '15 at 10:00

Wilbert

1,703
1
12
16

That two nodes are completely filled doesn't imply that they should be merged; it's not a step towards finding the largest box; if you merge them, you'll likely have to split them again at a later point once the largest box is found. I don't see how an octree helps in this scenario. – Mr. Smith Jul 21 '15 at 14:10
Full nodes can be merged in the sense that all 8 children can become part of a single larger box. This larger box will not have to be split later on, but it might be merged. The hierarchy allows you to quickly merge lots of boxes, completely filled nodes allow you to jump up a level without further testing. – Wilbert Jul 21 '15 at 14:44

score 1 · Answer 3 · answered Jul 21 '15 at 12:51

You seem to be at least O(n^2) (see big O notation) as you loop over all boxes in the world in “Begin()”, then for each box, you loop over all boxes in the world in ExtractLargest(). So a world with 10 unrelated boxes will take 4 times longer than a world with 5 unrelated boxes.

You therefore need to limit the number of boxes that ExtractLargest() has to look at, to do that you need to use some type of spatial search, as you are working in 3d, you may need a 3d spatial search. However first start by understanding 2d spatial search.

Then consider if you will ever have many boxes over the top of each other, if not then a 2d spatial search that just covers x,y may be enough to cut down your looping.

Octree/quadtree are one option, but there are many other options for space partitioning,

But you may be able to just use a 2 dimensional array of lists (Grid spatial index), where all boxes that cover the point (a, b) are in array[a,b].list. But most lickly that would lead to too large an array, so what about array[mod(a,100),mob(b,100)].list? This all depends on what your data is like.

(I have seen the grid solution work very well in real life.)

Or do what Wilbert says with an octree with a leaf node aabb size of the size of your box, but later on you are likely to have to find the box that the user’s mouse is pointing at etc, once again a case of spatial search.

(You must decide if you are just trying to get this software to work, or if you are trying to understand how to be a better programmer and hence are more interested in the learning then a quick solution.)

My algorithm that extracts the largest box that can be made from smaller boxes, is too slow

3 Answers3