I have a voxel game, where in 3d space, voxels can be added or removed.

Because these voxels can be moved as a whole, I keep connected voxels in an assembly structure.

My issue comes when I delete a voxel, essentially splitting an assembly into two separate assemblies.

I need a way to determine if any of the adjacent voxels to the one deleted, are still in the same assembly, or if a new assembly needs to be created.

I am using only 6 directions, forward, back, left, right, up, down.

This is the original assembly, the voxel highlighted in red is the one I plan to delete

Once the voxel is removed, the void is surrounded by 3 voxels that could potentially be a new assembly, A B and C

Logically we can see that voxel A and B will still be part of the original assembly, but voxel C, and the ones connected to it, will need to be part of a new assembly.

At first I thought of making a list of new assembly contenders (A,B and C) then doing a 3d flood fill starting with A, and checking to see if that flood fill would eventually land on the spot of B or C, if it did, remove it from the list of contenders for a new assembly, then repeat for all remaining voxels on the list of contenders.

Then, I though… maybe there is a faster way, by instead using a path finding algorithm, to see if there is a valid path between the points of A, B and C, sort of like the flood fill method, I get a list of contenders, and starting with the first in the list A, try to find a path to B, then C, if any path is found, remove that voxel from the list.

So… I ask, which method would be less expensive, as I would like to do this in real time, with rather large assemblies.

and where would I even find good algorithms to do this.

I tried to look up 3d flood fill, but didn't really find any good results.

I also looked up some path finding algorithms, but again, they all seem to be for 2D implementations, and not really any luck finding things for 3d.

Thanks in advance for any help.

I'd recommend to use a disjoint set data structure to cluster adjacent voxels into distinct connected sets. You would initialize the set (an array) to contain one entry for each voxel, with each voxel having itself as its parent index (i.e. not connected to anything else). Then, iterate over all adjacent pairs of voxels, and merge together their sets (pick one of the two to merge the other into). This is done by determining the root index for each voxel in a pair (follow the indices to find the voxel that has itself as the set index), and then picking one to assign the other voxel to. Whichever set index is chosen is assigned as the parent of all voxels (i.e. if merging set B into set A, you assign the root voxel of the B to have A as its parent, to make everything in B a child of A). At the end, you should have for every voxel the index of the parent voxel which it is associated with, which defines an implicit tree, with the root of each tree representing a distinct cluster. For each voxel, determine the root voxel index to get a unique identifier for the cluster. There will be one cluster index for each disjoint set of voxels.

Because these voxels can be moved as a whole, I keep connected voxels in an assembly structure.

You don't have to compute disjoint and connected component as Aressera explained whenever you delete or add a voxel in your “assemblies”: you can keep the assemblies and reorganize assemblies according to the connected components with an explicit command (or two separate ones, one for splitting and one for merging).

This way the potentially heavy and sometimes undesirable computation would run on demand without needless recalculation during editing operations.

I am still trying to work through what Aressera said, if I am able to get it working, I will post my solution here.

It can use a 1-to-6 linked-list structure to store the voxels. When a voxel gets removed, do traversing on all the adjacent voxels. Set a distinct route number (RN) for each traversing route of the adjacent voxels, up to six traversing routes (do multi-threading on them), all voxels in a traversing route will be assigned the same RN. If a traversed voxel is already assigned another RN, which means that the current traversing route connects to the other, stop and remove the current traversing route. After all traversings end, survived traversing route contains the voxels that belong to a same assembly distinct to others.

The 1-to-6 linked-list can be optimized for large assemblies.

Find the voxels around the deleted voxel. For each pair of “around” voxels try to find a path between them without crossing an assembly boundary. If that works both ends are in the same assembly, otherwise they are not.

In this way you get groups of “around” voxels that can reach each other. Each group belongs to one assembly.

Seems like a recursive fill pattern cycle in paint, but in 3d. If parts of the voxels are not being ,,recolored'' then you can disconnect those.