vercidium
patreon
Voxel Tech: Floating Voxel Algorithms
🕑 Added 2024-05-18 00:40:05 +0000 UTCThe core feature in Sector's Edge is its destruction. When a building is no longer connected to the ground, it should come crashing down.
Buildings could be composed of hundreds of thousands of voxels, so we need an incredibly quick way of checking if a building is floating or not. I call these Floating Voxel Checks (FVC).
I was still in university when I was working on this back in 2020, so I killed 2 birds with 1 stone and did my computer science major project on FVCs.
I've attached the full 30-page report to this post, which covers the 7 different FVC algorithms I created. They use all sorts of fancy optimisations, and one of them optimises itself over time!
In the end I combined a few algorithms together to achieve up to 2133x faster FVCs.
I'm still searching for the code for this. I'll upload it to the paid GitHub repository when I find it.
Comments
Mykei Johnson
Yup this has been my dilemma for several years. It's trivial to flood fill and find each separate region but to do it fast like this FVC is another story. I'm sure it's solvable because games like teardown wouldn't exist otherwise.
Vercidium
Ahh yes I get what you mean. You could calculate the total amount of voxels in the model, and then track the amount of voxels visited in each floating voxel check. If it's less than the total amount of voxels, then it must be separate. This would be incredibly slow for large objects as it'll need to visit every voxel in the model. If you break off a tiny part of a large model, it might see the large portion of the model as the 'floating' part and try to copy that into another object, rather than the tiny part.
Mykei Johnson
Yeah I have all of that working. The algorithm just doesn't support splitting when still connected to the bottom. Imagine a cube that you slice in half along the X axis, the two sections aren't connected but they're still technically connected to the ground in this algorithm. So this works for maps where there's a "ground" but not for physical voxel objects that technically don't have a ground
Vercidium
Ah rather than removing the floating voxels, you want to copy them to another separate voxel object, and then be able to interact with that voxel object? For Sector's Edge I copied them to another voxel object, which was then affected by gravity and falls down and crashes into the rest of the map. But it didn't support breaking a falling object into multiple voxel objects. Rather than having one 'Map' class, you'd need a list of them. When voxels are floating, a new Map would be initialized and the floating voxels copied over to it. That way each Map only contains 1 connected group of voxels
Mykei Johnson
This didn't turn out well, because it would detect the whole thing as floating too, causing it to be remade. I think splitting apart a voxel object would have to be a different algorithm to a floating voxel check
Mykei Johnson
I just realised I can get around this issue by leaving a 1 voxel wide gap on the bottom of the unconnected region, the models will then split apart as you would expect!
Mykei Johnson
Oh right, yeah that makes sense! Thanks. I'm hoping I can modify the algorithm to check when a unconnected voxel object is broken apart. So you can break apart voxel physics objects once they're broken off the main map.
Vercidium
It works for multiple floating regions, I’ll record a video tomorrow from Sector’s Edge where multiple physics bodies are created from one large explosion fvcData contains all the voxels that have been visited in the current check (there are multiple checks per batch). Once the check completes, it either removes these voxels or sets them all back to unvisited and unconnected So when a remove causes multiple floating regions, the fvcData array will be populated once, then those voxels are removed and the array resets. Then the process repeats for each other floating region
Mykei Johnson
I'm thinking of the case where a remove causes multiple floating regions, these regions need to be identified so they can create seperate physics bodies. I see that the chunk has a single fvcData array which I assume would contain all the floating voxels even if there's clusters that are not touching. There's also the case where you might want to break apart the detached floating clusters into smaller ones once they've been turned into rigid bodies. I believe this may be a seperate algorithm though, google suggests it's "connected component labeling"
Vercidium
It does, for example when a 5x5 region of voxels is removed, all adjacent voxels will be checked to figure out if they're floating
Mykei Johnson
Does this also handle detecting clusters of floating voxels? As in removing a batch of voxels could result in clusters of floating voxels not connected to each other
Mykei Johnson
Fantastic, thank you for all your work. The pdf was a great help at getting it working, now I can see how it's properly done!
Vercidium
Turns out I can only grant sponsors access to 1 repository on GitHub :( I've now uploaded the FVC code to the fvc folder in the ve repo
Mykei Johnson
This is great news! I can't wait to mess around with it. It is still private for me though, maybe needs an invite. I can see the private "ve" repo though
Vercidium
The code is now available at https://github.com/vercidium-patreon/fvc It also contains a newer, faster FVC method (called fvc2024 in the code) that I created after working on this university project. I'm working on a renderer so you can interact with a voxel model and see each algorithm in real time
Mykei Johnson
Thank you, there's not as much research on this publicly compared to greedy meshing and it's just as important!
Vercidium
Not yet as I’m currently overseas. I’ll resume work on it when I’m back
Mykei Johnson
Has the floating voxel code been put on github yet?
