Determining if removal of a voxel will break up a group

Question

I have the following situation: I have a 3d grid of voxels (on/off, the max size is probably 128x128x128). I know in advance that inside the grid, all the voxels that are turned on are interconnected, forming a single group.

Now I need to determine: when I remove a voxel (turn it off), will it break up the group?

My initial idea was to look at neighbors of the voxel that is removed and determine if they are still interconnected trough other voxels (see my other question: Algorithm to see if two voxels are interconnected). But there might be better/other ways to do this.

So what would be a good way to determine if removal of a voxel will break up the group it was part of?

Answer 1

I covered this somewhat in my other comment, but I think here you're thinking about external / internal classification. By removing a voxel, you are changing the voxels around it into 'edge' voxels (if they weren't already). This should boil down into 3 actual cases (symmetry gets you the rest of them) - in the example below the numbers are the group IDs, the - is the voxel being removed

11      2    
1-     1-     1-2

• The first case is trivial - it's a corner, but the voxels above and to the left remain fully connected through the other voxel.

• The second case: it's a corner and the removed voxel has disconnected the above and left voxels that were previously connected

• The third case: it's a line, and the removed voxel has disconnected the left and right voxels previously connected.

If you identify that the 2nd or 3rd cases have happened, you need to do some path-finding to see if 1 and 2 are still connected through their other adjacent voxels.

You can get some efficiency here though. If a voxel is entirely internal to a group (i.e. all 8 of its neighbours are part of the same group), then it can be discounted. Why? It's a topology thing. Imagine the 2D case - there are only two possibilities. Either there is a single edge which, regardless of how it twists and turns, still forms a ring of voxels. Or, there are two rings, one containing one voxel, and one containing the other. E.g.:

 xxx xxx
 x x-x x
 xxx xxx

or

 xxxxxxx
 x     x
 xxx xxx
   x-x 
 xxx xxx

That should extend to 3D as well, except instead of a boundary ring, you'd have a boundary surface. So when you are trying to determine whether the two recently disconnected voxels are still connected, you can exclude all the internal voxels from your traversal, because by definition if a voxel is connected to any one of the boundary voxels of a group, it is also connected to all the internal voxels in that group.

It's sort of the reverse effect of the hub voxels I talked about in my answer to the other question - you don't have to find your way from every voxel to every other voxel, you only have to find your way to the interesting voxels.

Answer 2

If you're using A*, you can utilize it here.

Starting with a list of the voxels that were connected to the removed voxel. Begin with the first in the list, use A* to find a path to the second in the list. If a path exists, find a path from the second to the third, third to fourth and so on.

Most of those searches will be very fast, because the voxels will be right next to each other. If there's any path that fails, it means a discontinuity has been created.

This should be pretty easy to implement if you already have the A* functionality implemented.