# How to find the largest bounding boxes in 3D array to cover all cells?

I'm trying to generate colliders automatically from a 3D array where each cell represents a constant-sized piece in a world (like a voxel). I'm trying to optimize the number of colliders, so I want to traverse the 3D array and create as few colliders as possible to cover all cells.

I know that for a single axis (1D array), I could do something like this:

// Let's say 0 = empty and 1 = wall
int[] array = {0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1};
boolean creating = false; // Was start index found?
int startIndex = 0; // Where the box started?
int endIndex = 0; // Where the box ended?

for (int i = 0; i < array.length; ++i) {
if (!creating) {
if (array[i] == 1) {
creating = true;
startIndex = i;
endIndex = i;
}
}else{
if (array[i] == 1) {
// The line of blocks continues, increment the end index
endIndex = i;
}else{
// Empty cell found, create a collider
createBox(startIndex, endIndex);
creating = false;
}
}
}

// Result would be four colliders sized 2, 1, 3 and 1


However, I can't figure out how to expand this to two and three dimensions. For instance, take this 2D array:

{{ 1, 1, 1, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 1, 0, 0 },
{ 1, 1, 1, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 1, 1, 1, 1, 0, 0, 0 }}


This should result in three colliders: the first from (0, 0) to (2, 2), the second from (3, 1) to (3, 5) and the third from (0, 4) to (3, 4). However, simply looping the two dimensions wouldn't work.

Any ideas how to tackle this?

I'm not really sure whether or not the process you describe guarantees the least amount of bounding boxes, but it surely is a good way to approach the problem, as it definitely reduces the amount of bounding boxes that you need to check collisions against. I use this approach myself.

Basically, I just do this one dimension at a time. First, I process the level horizontally, so row by row, and place in temporary bounding boxes. You seem to already know how to do this, so I won't bother with pseudo code here.

After you have the boxes connected in one dimension, you just need to do a pass on all the boxes in the other dimension. Either do a full coordinate loop, or simply iterate over the boxes you created previously. You just need to look for a box directly underneath the box you're trying to connect, and make sure its width matches. So something like:

void processVertical()
{
for (Box box : HorizontalBoxes)
{
// Ignores invalid (already processed) boxes, see the comment below.
if (box.width == 0) continue;

// Check if we can merge with the box below us.
Box below = findBoxDirectlyBelow(box.x, box.y)
if (below && below.width == box.width)
{
box.height += below.height;  // Expands.

// Makes the box below unusable, so that we don't end up processing it.
below.width = 0
}
}
}

Box findBoxDirectlyBelow(int x, int y)
{
for (Box box : HorizontalBoxes)
{
if (box.x == x && box.y == y + 1) return box;
}
return null;
}


For a third dimension, you would just repeat the process but compare the width and height of the created boxes with the boxes close to each other in the Z-direction.