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
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.
Mykei Johnson
2024-08-28 23:20:51 +0000 UTCAhh 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.
Vercidium
2024-08-28 23:14:25 +0000 UTCYeah 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
Mykei Johnson
2024-08-28 04:25:54 +0000 UTCAh 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
Vercidium
2024-08-28 04:17:20 +0000 UTCThis 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
2024-08-27 16:08:04 +0000 UTCI 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
2024-08-26 16:03:48 +0000 UTCOh 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.
Mykei Johnson
2024-08-25 13:30:36 +0000 UTCIt 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
Vercidium
2024-08-25 11:35:54 +0000 UTCI'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"
Mykei Johnson
2024-08-25 11:28:35 +0000 UTCIt does, for example when a 5x5 region of voxels is removed, all adjacent voxels will be checked to figure out if they're floating
Vercidium
2024-08-25 07:56:14 +0000 UTCDoes 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
2024-08-25 01:54:54 +0000 UTCFantastic, 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!
Mykei Johnson
2024-08-25 00:05:39 +0000 UTCTurns 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
Vercidium
2024-08-25 00:01:41 +0000 UTCThis 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
Mykei Johnson
2024-08-24 23:37:24 +0000 UTCThe 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
Vercidium
2024-08-24 23:21:04 +0000 UTCThank you, there's not as much research on this publicly compared to greedy meshing and it's just as important!
Mykei Johnson
2024-08-20 04:21:11 +0000 UTCNot yet as I’m currently overseas. I’ll resume work on it when I’m back
Vercidium
2024-08-20 04:15:22 +0000 UTCHas the floating voxel code been put on github yet?
Mykei Johnson
2024-08-19 23:52:46 +0000 UTC
