Recently, I wanted to dig into procedurally generated terrain. In the distant past, I explored roguelike map generation techniques starting from the simple Dungeon Generation approach (I have never found a consistent name for this, some call it Tunneling). I say simple because the approach is straight forward. You place several rooms around a map, then attempt to connect them with corridors.
For the past several years, though, I have been working on games in Unreal Engine and wanted to try my hand at 3D terrain. I read some of the popular blog posts and watched some of the popular videos and wanted to try my hands at a Marching Cubes implementation.
So let's dig in!
So what is marching cubes? Let's start with the image you'll see alongside any explanation:
Hope it's all clear, thank you for attending my TED talk. But seriously, I always like to start from the historical context to understand a topic. And back in the 80s, researchers wanted to take 3D medical data from CT and MR machines and create 3d graphics to help doctors understand results. But techniques up to that point had difficulties with resolution and artifacts.
Taking the "assume a frictionless environment in a vacuum" physics approach, let's assume we have evenly distributed 3D data. E.g. we take a data sample every millimeter in a cubic grid showing whether there is something there or empty space (aka Inside or Outside). The idea put forward in their paper on Marching Cubes was that if you take this 3D grid, you can create a cube from 8 adjacent points. Then, since each vertex represents Inside or Outside, you can draw triangles within the cube on the boundaries between Inside vertices and Outside vertices. Since a cube only consists of 8 points, there's a limited number of combinations of points (28 or 256).
The reason you only see 15 cubes in the chart above rather than 256 is because they noticed there are actually only 14 combinations of unique points (and 1 empty cube). If you remove combinations that are simply inversions of existing combinations (you draw a triangle in the same location in those cases) or combinations that are rotations of existing combinations. Knowing this, let's look at the chart again:
- Cube 0: an empty cube. I.e. all the vertices are either Outside (aka open air) or Inside (aka inside a surface).
- Cube 1: a cube with a single vertex Inside (or Outside). So we draw a triangle in that corner on the boundary between this vertex and all adjacent points
- Cube 2: a cube with two vertices next to each other. So we draw a rectangle (two triangles) between these two vertices and all other vertices.
And so on. You then calculate the normal for each triangle (so we know which way the triangle faces for rendering purposes). Once you finish a cube, you then move to a neighboring cube. This is the marching aspect of marching cubes. You're marching along the grid.
While this covers how to create a 3D surface from data, how do we create that data in the first place? We're going to keep things simple and use noise generators. Depending on the type of noise, you can get some interesting terrain!
Simplex Noise vs Value Cubic Noise vs Perlin Noise
Terrain result from these noise types
A popular library for noise generation is FastNoiseLite
To wrap things up, let's take a look at some of the results. For comparisons sake, we'll look at Marching Cubes compared to simply rendering a block at each point for a Minecraft style.
2D Perlin Noise using Marching Cubes
Same 2D Perlin Noise using blocks
We can also generate 3D noise data to create Minecraft style caves or the inside of an asteroid.
3D Perlin Noise using Marching Cubes
3D Perlin Noise using blocks
Now let's compare these to Value Cubic noise.
3D Value Cubic Noise using Marching Cubes
3D Value Cubic Noise using blocks
As we can see, Value Cubic noise produces more open, smooth spaces. This is because the cubic noise approach interpolates between values to create a more smooth transition between regions.