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

3dalgorithmsoptimization

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.

Best Answer

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.

Related Topic