2. Marching Cubes

Introduction

Now once I got the "Advanced Perlin Noise" working, I started to implement the "Marching Cubes" algorithm to give shape to the values the Perlin Noise class is providing. By the way, there are many alternatives to this algorithm that are solving pesky discontinuities and topological issues, like "Marching Tetrahedra" or "Surface Nets". But since "Marching Cubes" offers more extensive sources, I still went for it.

Small note aside

I will go through the individual points that make up this algorithm showing it in code, but bear in mind that I will cut a little shorter on the theory since there many great sources that explain all of this in a much greater detail way beyond what I am capable of here. You can also just go to the sources page and use the same sources I used, they are all great!

---

Implementation

"Marching Cubes" use as the name might imply, cubes. So the first part is pretty straightforward: I use a volume vector which sets the dimensions for my shape, then iterate through this space to obtain the Perlin Noise values for all 8 vertices per cube and save them together with the vertices themselves in a struct to use that information later on. The struct is really simple:

Now I iterate through (x, y, z), create a new cube struct, and get the values by inputting the coordinates into the Perlin Noise function. Here I made several adjustments that you will probably not see in the usual implementations. First of all, I check whether my coordinate lies on the outermost part of my shape and if so, consider it to be in the shape. That way I "close off" my shape to make it look better since the Perlin Noise is not a closed-off volume meaning that you could look "inside" the shape, but more importantly this avoids pesky lighting artifacts.

Now while implementing this, I was wondering why my algorithm would not work. After debugging the code for some time, I noticed one thing: well, actually there are several parts working hand in hand to create this issue. Perlin Noise uses the point within the unit cube to interpolate the values from all 8 points to one final scalar value. In my use case, I am using integer values only as points in space, this means the point within the unit cube is always (0,0,0). This causes the interpolation to only use the value of the first dot product. Furthermore, the first dot product takes that inner point as parameters and thus the dot product will be 0, and since this value is the only one used all values will result in 0. I use two steps to tackle this issue.

1. I scale the vectors to 1/5th of their inherent size. This way the values lie in between two integers and return valid noise values.

2. There is still one issue remaining: even though I downscale the values they can still all give an integer value and that means that all points with that condition would be considered within the shape. I interpolate between noise values of the points diagonal to the actual point and use this as the value.

In addition to the things mentioned above, I also added a height heuristic. This takes the height of the current point in space into account and thus creates a walkable surface, which of course is handy-dandy when you want a terrain.

So once I've got all the cubes with their values I can start assembling the mesh.

First off, I calculate a "cube index". This index basically saves which vertices of the cubes lie within the shape, by setting the individual bits:

I then put the values in an edge table. This table takes the cube index and returns a 12-bit number, where each bit belongs to one edge of the cube, and describes whether that edge is being cut by the shape or not, according to the cube index. If that value is 0, it means that this cube is either completely inside or outside the shape and we can disregard it.

Now having this information I iterate through all 12 edges of the cube, checking whether they are being cut by the shape. Should they be cut, I calculate that exact point by interpolation between the two vertices that make up the edge by the noise values of the two vertices and save that point in a list.

Lastly, I put the "cube index" into the triangle table, the table then returns the configurations for the triangles to create the actual shape. I then create a mesh, assign vertices and triangles, recalculate the normals and assign it to a MeshFilter component.