Marching Cubes Part 2: Generating a mesh with marching cubes
In the first part we went over how the marching cubes algorithm creates a mesh given a 3D grid. In this part we will learn how to translate that understanding of the algorithm to an actual mesh in Unity. For constructing the actual mesh, we will use compute shaders as they speed up the process of calculating the configuration for each cube significantly. You can read more about compute shaders in this tutorial.
Before we start with generating a mesh, we first have to fill our grid with values. These values are responsable for telling us if the point is either underground or above ground.
Let’s start by creating a new Unity project. In this project, we wan’t to begin by creating a new static class called “GridMetrics”, this class will be used to store values that will be used all over the project, such as chunk size, number of threads per workgroup (for the compute shader), etc.
We will start with a very small chunk size for testing purposes, by the end of this guide, we will increase it.
In this tutorial series I will assume that each chunk size in our terrain will always be a multiple of 8, this makes sure that we will not have to spawn many threads on the GPU that are unused because of the arbitrary grid sizes.
To setup our grid, create a new C# script called “NoiseGenerator” (Right Click > Create > C# Script). Attach the script to a new object in the hierarchy.
In this script, define a new compute buffer, this buffer is responsable for communicating the noise values generated by the GPU compute shader back to the CPU C# script.
To initialize our compute buffer, we need to know the size of our 3D noise grid, which we stored in our GridMetrics. We also need to know the size of a single element. Since we just want a single noise value for each point in our grid, we will fill our noise grid with floats. Create a function to create the buffer and another function to release it.
Next, create a function that generates an array of floats (this is a 1D array, as our compute shader will return a 1D array), which we will use to generate noise values for single chunk. Initialize the array with the size of our grid.
To execute our noise generation we first have to have a reference to the compute shader that will take care of generating the noise values. Create a new compute shader called “NoiseCompute” (Right Click > Create > Shader > Compute Shader) and add a variable field for it in the NoiseGenerator.
Now that we have our shader, we still need to set the buffer to be able to communicate between GPU and CPU.
Now, we dispatch the shader. We will only have single kernel in this shader, so use kernel id 0. We also need to tell the shader the size of our chunk/mesh and how many workgroups to create. Our chunk size is 8. Our number of threads per workgroup is 8. Therefore we have to have 1 workgroups for each dimension to create a grid of 8 by 8 by 8.
Lastly, after dispatching and executing the compute shader, we expect to find the generated noise values on the buffer. Transfer the data on the buffer back to our noiseValues array.
Now that we have executed noise generation, we also want to display the values on the screen. Let’s create a new script C# “NoiseVisual” to show us our output.
Attach this new scipt to a new object in the hierarchy.
In this script, we want to have a reference to our noise generator and call the generate noise function on start.
To display the weights, loop through them in the OnDrawGizmos function which allows us to draw shapes to the screen in editor.
As our noise array is a 1D array, but we want to display a 3D array, we need to convert the 3D index (xyz) to a 1D index with the following formula:
Before drawing our grid, make sure it actually contains values. Let’s also color our weights in such a way that if the noise value is 1, the point will be displayed as white, and when the value is 0, it will be black. We lerp between the colors with our noise value to get some gray colors too.
To make sure this works, let’s quickly populate our _weights with random values.
Running the game in editor should now give us a 8x8x8 grid. Don’t forget to turn on Gizmos!
1.2 Sampling Noise
While we can display noise values, we obviously don’t want them to be completely random. We want to make noise that somewhat reflects real terrain. For this we will use pseudo random noise (structured noise). This series is not a tutorial on how to generate noise from scratch though, so we will be using a noise library. I will be using a library called FastNoiseLite. Download the HLSL file and put it inside your project. I used the following file structure:
In the previous section we already created a compute shader called “NoiseCompute”. Open this shader and clear it of its boilerplate code, we won’t be needing it. In this compute script, we want to create a 3D array consisting of noise values. Since we use a library, let’s include this library file in our NoiseCompute. Don’t forget to use the right file extension! You may be using FastNoiseLite.hlsl instead of .compute.
I also went ahead and changed our kernel from “CSMAIN” to “GenerateNoise”.
All of our numthreads will be the same, for clarity sake, let’s create a constant int for this nonetheless. These numthreads should always equal the defined numthreads in our static “GridMetrics” class.
To store the values of our points in the grid, we need a RWStructuredBuffer, this however is a 1D array so we need to make sure when adding to it we use the 1D index, and not the 3D one. Let’s create a helper function for this.
To go from a 3D position (which is stored in our id of the thread within the workgroup of the compute shader) we require the size of our terrain chunk.
Now we can actually start to generate some noise. As with almost all noise, we want to have some control over how this noise is generated. We might want some control over what the base height is of our ground, how high the mountains reach, etc.
The noise scale tells us how stretched out the noise will be. – Note (update 2023): this variable is not needed! The same effect can be achieved by only using frequency, I therefore recommend to not include this variable (or to set it to 1 at all times) as it could be an unnecessary added complexity –
The amplitude determines how high our terrain will reach, high amplitude means high mountains.
Frequency tells us where to sample noise, when we have a high frequency, we will sample the noise further away from eachother. This can give us quite chaotic noise as the sampling will be less coherent.
Octaves gives us details, when the noise is generated for a point, we will essentially regenerate it but at a smaller sample size and this for the amount of octaves.
Finally, the ground percent just tells us where along the height of the chunk we want to be above ground.
If what these variables exactly do isn’t all that clear, they will become a lot clearer once you can start playing with the variables of the terrain mesh by the end of this tutorial.
Next, we have to tell the noise library about our settings. I opted to use simplex noise with the ridged fractal type. The ridgid noise gives the noise a bit more of a natural feeling.
To sample and create the noise in such a way that it feels like a terrain, we first have to take into account the position to sample at.
Once we have that, let’s define the height of our ground. This is done by taking the negative of our y position and adding some value to it (our base ground).
Finally, sample the noise, add the ground and raise all of it with the amplitude.
Let’s also not forget to actually put the noise in to our weights array.
That should be it for our noise. Return to the NoiseGenerator and let’s set the noise paramaters on the shader, initialize them with some default values.
In case you haven’t already, return to the NoiseVisual and uncomment our GetNoise().
In case your computer can handle it, you can also set the PointsPerChunk to 16 (or higher).
Now, run the game.
1. Marching cubes mesh
Since I have already explained before how the marching cubes algorithm works in the previous part, I won’t go over it again in detail.
Why didn't you include this part in the previous one?This question has two anwers:
- Otherwise the guide would become quite long
- Some people are more interested in an explanation of the algorithm, rather than a full tutorial on how to make meshes with it. The previous part was also not specific to Unity.
To start, we will rename our NoiseVisual to something more fitting. Since we will be creating terrain and terrains have many chunks, rename “NoiseVisual” to “Chunk”.
In here we need to call our marching cubes compute.
As mentioned in the previous part, we can use custom structs to pass data on the computeBuffer. We want to pass Triangles. A single triangle exists out of 3 vertices. Every triangle is therefore the size of 3 times 3 floats (xyz * 3).
Just as with our NoiseGenerator we will need buffers to transfer data between the CPU and the GPU. For marching cubes, we will need 3 buffers.
The triangles buffer holds all of our triangle objects that will be generated by marching cubes
Since we can’t know how many triangles will be generated, we have to keep track of them
Our weights buffer contains the noise values generated in the first part of this tutorial
Just like before, create functions to create and release the buffers.
Going over the CreateBuffers function.
Since we have to tell the buffers the maximum amount of elements it can contain, we need to initialize the trianglesBuffer with 5 * the total grid size. 5 is derived from the fact that there can at most be 5 triangles per cube configuration.
We already defined the size of a single triangle which is the stride of the buffer. We also have to make our buffer of type append. Just as a regular buffer is similar to an array, the append buffer is similar to a list. Instead of having to use an index to add to the list, we can simply call list.Append(myElement)
The triangles count buffer will simply contain a single integer.
The weightsBuffer, just like the weightsBuffer in the NoiseGenerator, contains a single float value per point in the 3D grid.
Create a function ConstructMesh. In this function we want to first set our buffers.
Then, set some of the parameters like isoLevel, noise values, etc. used by marching cubes. Also set our trianglesBuffer counter to 0. So that we know for sure that the trianglesBuffer contains 0 elements.
Dispatch our marching cubes.
Let’s now focus on the marching cubes compute shader. Create a MarchingCubesCompute compute shader (Create > Shader > Compute Shader).
Download the marching cubes lookup tables (HLSL). Put the lookup tables in the Assets/Scripts/Compute/Includes project folder.
Open the MarchingCubesCompute. Here we will rely on the code of the previous part. Start by including the lookup tables and renaming the kernel to “March”. Also add our const numThreads.
Add the parameters needed for the algorithm.
To start, in our March function we need to first check whether we are inside of our grid. Since we are using cubes, we need to stop one before the end of our points per chunk, so that we won’t go out of bounds.
In the image above, we are using 5 points on our x axis, as you can see, even though we have 5 points, we need to use 4 squares to fill up the grid. The same applies to our 3D grid.
Next, get the noise values at the corners of our cubes. Again, like our NoiseCompute, for this we need to know the index of the noise values. Create a new compute shader called “MetricsCompute”, put it into the Includes folder.
In this helperCompute, we will keep track of some shared functions and variables. Like so:
Inside of our NoiseCompute, remove the numThreads, chunkSize and indexFromCoord. Include the MetricsCompute.
Let’s return to our Marching Cubes shader and get the noise values of the corners of the cube.
The following should be familiar from the previous part.
Get the cube configuration.
Get the triangle indexes.
Loop through them to find the edges.
Interpolate between the points on the edge to find the exact position for the vertices of the triangles.
Finally, add our triangle to the list.
Why don't we just add the three vertices to the triangles list?When working with compute shaders, we can never be sure in which order elements are added to our list. This is because threads work in parallel, so many threads could be adding vertices at the same time causing the list to not be in the right order.
Great, that’s it for the compute shader.
Head over to our Chunk.cs.
Inside our Chunk.cs, let’s create a function to get the number of triangles we generated. Call it “ReadTriangleCount”. To do this, we have to create an array of ints, this array will simply contain a single element, our triangles count. We have to copy the count of triangles from the triangles buffer to the triangles count buffer.
In case you are wondering why we can’t just use _trianglesBuffer.count (which is an existing function), the .count gives us the max capacity of the buffer, not the actual length of the appendBuffer.
In the constructMesh, initialize an array with the count we just read from the buffer and transfer the triangles from the triangles buffer to our array.
We have to now translate these triangles to actual mesh data, create a new function for this.
Initialize the vertices and triangles list (this is for our mesh data). Every triangle contains 3 vertices so we will need triangles.Length * 3 as size of our vertices and triangles array.
Loop through all triangles generated by marching cubes, and add them to our verts and tris.
Create the mesh and return it.
Also return it in our ConstructMesh() function.
Add a reference to a meshFilter. MeshFilters are responsible for showing the actual mesh.
Inside the start method, call contruct mesh and assign the mesh to the meshFilter.
In Unity, make sure that there is a chunk object in the hierarchy, add a meshFilter and meshRenderer to it, also a new material.
The chunk also needs its references to the marching cubes shader, the mesh filter, and ofcourse the noise generator.
We are finally ready to see our algorithm in action.
Don’t forget to disable the Gizmos, they slow down your game by quite a lot.
Also, like mentioned in the beginning, you can now increase the size of your chunk (make sure Gizmos is off or removed entirely!)
In the next part we will make our small, static terrain a bit more exciting by allowing us to terraform.