2.3 KiB
Voxel engine in Godot 3 with Rust
2022-05-05
I made a voxel engine in rust to learn rust and godot-rust as well as explore voxel systems. It has (practically) infinite terrain generation, lets you place and remove voxels and supports transparent voxel types. The main point was to develop an optimised meshing algorithm.
Demo of fast terrain generation Optimised mesh visualisation
Optimised/greedy mesh algorithm
editor's note: This writeup was never finished :D
The algorithm I'm using is one I made myself, inspired by a few others. I could not find an easy to understand explanation of how to do it but this artice and this article gave me somewhere to start.
In this explanation I will assume basic knowledge of how meshes work and how to do the simplest form of culling for voxel meshes.
fig. 1: example set of voxels, with the simplest form of mesh generation applied.
To start off, we can break down the problem to 2 dimensions by recognising that each direction along the axis as well as each layer along those directions is independent. We then only have to process a single 2D slice of the voxel domain at once.
fig. 2: The algorithm only needs to consider one layer and direction at a time, highlighted in green
The first step is to generate "strips", essentially create long quads that cover connected voxels. We can loop through the plane and keep track of at most one active strip. The active strip is the last one started and we grow it as more voxels under it are traversed. In the inner loop we check the voxel at that position as well as the one above. With this we can determine if we need to stop the current strip, start a new one or do nothing. If there is not currently an active strip, a new one should be created when the voxel below is filled and the one above is empty (an exposed surface).
fig.3: Long strips of adjacent voxels can be merged into fewer, long quads.
.
this was incomprehensible, take me home