Marching Cubes
Marching cubes are a mesh generation algorithm that at it's core that takes a complicated structure and breaks it down into cubes to be processed individually. The way the algorithm accomplishes this is by sampling the vertices of several cubes strewn across space and determining which vertices sample values above or below a set threshold.
When contemplating a cube, each of the vertices as well as the edges can be given an index. These indices can be used to generate facets.
In the example shown above, vertex 3 was across the threshold and therefor a facet using edges 2, 3, and 11 was formed. Every combination of vertices will yield one or more triangles.
There exist only 15 unique cases
Each of the possible combinations of vertices will only ever yield either one of these 15 cases or some reflection or rotation of one of the cases. Because each of these cases are known ahead of time, they can be stored in a lookup table. Because a cube has exactly 8 vertices, we can elegantly use a single byte, which holds exactly 8 zeros, as a way to refer to the specific combination of vertices a given cube has across the threshold. By sequentially going through a given space, you can build up enough cubes to generate more complex shapes.
Simplex noise was applied to the world space and then the marching cubes algorithm was performed across a 16 x 16 chunk. By modulating the threshold value, the noise's pattern in space can be seen. This is why this algorithm was originally developed for medical scans. Once the ability to generate entire chunks at a time was complete, next comes connecting several chunks in space to create larger surfaces.
When putting our terrain generation algorithm to the test, we were able to generate the following results.
Canyon Bend
Natural Amphitheater
Rolling Hills
Arches
This algorithm has also been the focus of several academic and research inquiries.
"Sureal Looking Terrain"
- Nvidea
"Smoothed Visible Human"
-Ben Anderson
"Brush Tool"
-Sebastian Lague
"SmoothedSurfaces"
-Evgeni Chernyaev
Deep Rock Galactic
No Man's Sky
Both of the above titles use the marching cubes algorithms for their core gameplay. It is a relatively low impact algorithm that can be used for mining or other mesh manipulation tasks.
Eira: Echos of Adventure
This Champlain Game Studio 2020 game was another example of a game that heavily used marching cubes to accompany it's gameplay.