Finding break in voxel grid (3D array)

Question

I am working at dynamic voxel engine in Unity (something like Space Engineers) where player can create object from voxels, push them, damage and split in to other object.

I store all data in 3D array, 1 mean voxel, 0 mean empty node.

So I looking for solution to break object (array). For example when I remove enough voxels object should split in to two.

00000000            00000    0000
01110110   ====>    01110    0110
01110110            01110    0110
00000000            00000    0000

In 2D example it should split like that.

I try to use BFS search but it not fast enough ;(. It works fine for small grids like 5x5x5, when I creat 5x5x50 grid it works few seconds before break arrays.

My algorithm: 1) First find empty node 2) When you find empty node start BFS from that node, collect all not empty nodes, when you cant find not empty node finish.

If break exist it will collect only one part of array so it find break, if there is no break it will return whole array.

The problem is speed of it ;/ How to make it faster?

Answer 1

When you remove a node, take any solid nodes attached to it and do a connectivity test between each pair. If any of the solid nodes that were once connected to the solid node you just removed are no longer connected, then removing that node has just created two separate objects.

This algorithm isn't affected by the size of the grid, but rather the size of the objects. There are additional optimizations you can do for connectivity for large objects. (See this answer for some optimizations you can implement there). However, most of your searches are going to be very quick, because objects will still be connected with short paths.

I'll use a 2D example here for simplicity:

1. Our single object
2. We remove the red node and do connectivity checks between every green node with every other green node. We find they're all still connected.
3. We remove the red node and do connectivity checks between every green node with every other green node. We find that these nodes are no longer connected.
4. We have two separate objects. You can define these objects by taking the green nodes that were not connected and doing a BFS on each to determine the bounds of each completed object.