Efficiently filling empty cells in 3D matrix

Question

I have a 3D "cubical" matrix, with some cells filled and others empty. A closed region enclosed by filled cells represents a hollow shape. For example, the matrix could have cells filled in such a way that together they form the surface of a hollow sphere. Now, I want an efficient way to fill the interior of this sphere: if a cell C0 is surrounded in all directions by filled cells (filled cell in any direction need not be an immediate neighbor of C0), then fill C0.

A naive way would be the following :-

For each cell, scan in the +X, -X, +Y, -Y, +Z, -Z direction, and see if you encounter a filled cell in each and every direction.

If a filled cell is encountered in each and every direction, then fill this cell (as it is part of the interior of some shape).

If you reach the end of grid even in one direction without encountering any filled cell, then the cell under consideration is not interior to any shape, and should remain unfilled.

The complexity of above approach is O(n^4), where dimension of 3D grid is n*n*n.

An optimization could be to as follows :-

If for an unfilled cell C[x][y][z], we encountered one filled cell each in all the 6 directions, then not only C[x][y][z] needs to be filled, it is also guaranteed that all the cells which we scanned just now (i.e. {in +X direction, all cells C[x][y][z], C[x+1][y][z], C[x+2][y][z], ..., till the first filled cell}, similarly for -X, +Y, -Y, +Z, -Z direction) must be part of the interior of some shape, and hence must be filled.

Another could be as follows :-

If for an unfilled cell C[x][y][z], we DO NOT encounter any filled cell in, say, +X direction, then not only will C[x][y][z] remain unfilled, it is also guaranteed that all the cells which we scanned just now (i.e. in +X direction, all cells C[x][y][z], C[x+1][y][z], C[x+2][y][z], ..., till the end of grid) must be part of the exterior and hence, must remain unfilled.

Can someone suggest a more efficient approach to this problem? Even simple optimizations like above, which might not reduce the order of time complexity, are welcome.

Answer 1

You are dealing with 3D Flood Fill. See detailed Wikipedia article http://en.m.wikipedia.org/wiki/Flood_fill

Answer 2

Just for completeness, two more. YMMV depending on a lot of factors.

1. Find the surface

If you are dealing with a large number of voxels, one optimisation possibility would be to find the border surface of the hollow. This can be done as in Pham Trung's answer but only accepting cells which have at least one of their 6 neighbours filled.

After the border surface has been determined, it can be filled line-by-line using 1D fills, as the directions "inside" and "outside" are known.

This method keeps the set size much smaller if you have a large number of voxels (scales as n^2 instead of n^3). Set lookups are usually very fast, but if the set does not fit into RAM, they slow down a lot.

2. Slice to 2D

Another possibility would be to slice the shape into 2D slices and connect the resulting cavities layer-by-layer. Then only two slices need to be kept in memory at the same time.

The principal idea is to give every separate connected 2D region an own identifier and then find its connections to the already known regions in the neighbouring layer. After handling all layers, connected 3D regions remain.

The challenging part is to find the best algorithm to connect the 2D regions in neighbouring layers. It seems that this method is fast with simple shapes (few disconnected regions in the 2D slices) but slow with complex shapes ("wormholes in tree"). Also, a quick algorithm to find a single common point in two sets is needed. (I.e. no full set intersection is required, just the information whether the sets have at least one common point or not.)

Again, if your sets are of reasonable size, the trivial algorithm described by Pham Trung is probably the best choice.

Answer 3

For each cell, scan in the +X, -X, +Y, -Y, +Z, -Z direction, and see if you encounter a filled cell in each and every direction.

If a filled cell is encountered in each and every direction, then fill this cell (as it is part of the interior of some shape).

The above statement is incorrect unless you are only dealing with convex hulls. The image below shows that the point in question is not enclosed in the blue shape but it will still intersect in all (x,y,z) directions.

Instead, to handle the general case of finding hollowed shapes, you can add all cells to a Set. Then start at a boundary cell. The cell at the boundary is part of a hollowed shape if it is filled, otherwise it is part of a background (non-filled) shape.

Then, similar to @Pham Trung's answer, you can traverse outward in all directions until you have traversed all cells that are within the shape, ignoring the colored cells at the boundaries. Choose another cell at the boundary of the previous shape and start the process over until all cells are traversed.

In the end you will have each cell labeled as either part of a hollow shape or the background.

Answer 4

Ok, as this is a closed hollow shapes, we can simply use a BFS or DFS to solve the problem.

BFS:

Starting with an empty queue, add to the queue any cell that lies inside the hollow shape. From the top of the queue, pop out one cell, fill this cell and check 6 other neighbors of this cell, if this neighbor is not filled, add it to the queue, else just ignore this cell. Continue this process until the queue is empty.

The remaining problem is to find a cell that located inside the hollow shape, one trick is the you need to find the cell located at the corner of the shape, which has at least three filled neighbors.

Time complexity is O(number of needed to filled cell * 6 direction need to check)

Tip to move to 6 direction:

int[] x = {0,0,0,0,1,-1};
int[] y = {0,0,1,-1,0,0};
int[] z = {1,-1,0,0,0,0};

Point p = // point in space with three dimension x,y,z

for(int i = 0; i < 6; i++){
     int a = p.x + x[i];
     int b = p.y + y[i];
     int c = p.z + z[i];
}