My face reduction algorithm for cubic voxel terrain
Added 2022-06-02 22:03:01 +0000 UTCI plan on getting back to Nibbles shortly! Wanted to post a little something else in the meantime. I spend the past few days working on a voxel engine in Godot 4, cubic like Minecraft this time unlike the marching cubes one which is more complex than I know what to do with. The basics were super simple but it took some time to figure out how to code a proper face reduction algorithm for maximum optimization. Some thoughts on that adventure for other game devs and software engineers:
The best approach was to start with a virtual face then scan all existing faces against it before committing it: If a match is found the new face is discarded and the match is repositioned and rescaled to occupy both spaces, only if no match is found a new face is added to the list. Two scans are preformed for both directions, in the X and Y scales of the face: Faces that have the same scale and position in X and are touching each other in Y (then vice versa) become one face. To reduce the number of necessary loops faces are stored in slices representing the virtual sheet and direction each is standing on, only neighbors on the same slice are scanned.
In practice, both using and not using the face reduction system results in roughly the same chunk generation speed, it takes the same estimate number of seconds for all chunks to be generated after a game starts and the player lands. However a much lesser number of faces is produced, resulting in slightly improved rendering performance and a lot less memory being used.
I attached two screenshots for comparison, one with and one without the face reduction system. The difference can be observed rather clearly. You can see my code in the super early project which is now up on Github:
https://github.com/MirceaKitsune/godot_cubedot/blob/main/scripts/voxel.gd
