Voxtric – Update 3: Integrity Splitting

This post and the video above are short due to the single change that took place in Voxtric for this post to be made, but the change itself is a big one. After a fairly large amount of work I managed to get algorithm for checking for and splitting off of disconnected collections of voxel data.

Method (Has since been far and away improved)

It works by storing a series of points around each block that is removed at once (6 for each block removed), and then checking each point for a solid block at that positing, throwing the point away if there is no solid block at the position. Doing it this way means that large areas of blocks are able to be removed at once and the rest of the algorithm as is about to be explained will still work.

A DataSplitFinder is then created at each point which stores a std::vector of positions found, an std::map of the positions found in the most recent round of checks (explained in a moment), and a std::vector of the positions found in the previous round of checks. It also stores the total number of positions found.

Each DataSplitFinder then performs a breadth first search for the other finders around it. When one is encountered, they are merged together and the process continues. If a finder cannot continue its breadth first search as there is nowhere else for it to search, it means that this finder has detected a collection of voxel data that is no long connected to the main body of voxel data. A new RegionCollection is then created and the voxel data that has been identified as not connected is copied over to the new RegionCollection. This process continues until there is only one finder left as all active finders will have been merged together of removed when copying data.

As it is faster to copy the least data possible from a large voxel data collection, the DataSplitFinder with the least voxel positions found is the one that performs each round of its search more often than the others. This is because, in the case that a split has occurred, in places where the finders can reach each other they will quickly merge into one finder and each round will spread over a much larger area. The smaller section though will have the constraints of being on a boundary of voxel data and will have merged with fewer if any finders.

As this smaller section is the bit we want to copy out, it is the one we perform the breadth first search operation on until it is either confirmed to show a split in the voxel data, it finally meets up with the other finders, or the number of positions it holds becomes more than that of any one of the other active finders. In the latter case, the exact same process is repeated, just with whatever finder now has the least voxel data positions stored.