For my R&D Project I was torn between an Ant colony and Procedural planets, going for the harder challenge, I decided to try out procedural planets. I never worked with making meshes, voxels and shader-graph before, so I made an attempt at several ways of making a procedural planet. As inspiration I looked at Space Engineers and No Man’s Sky.
Table of Contents
For a procedural planet like No Man’s Sky and a planet like Space Engineers, you have to make use of voxels to manipulate the terrain. For this, I looked at 3 algorithms. I found these algorithms in the opposite order than displayed here, but it would make more sense in this order.
Marching Cubes makes use of a 3d grid, in this grid we make boxes and define a number to the box. 1 is outside and 0 is inside the mesh. You then ‘March’ through every box in the grid to set their vertices and triangles, this can be done by looking through a lookup table based on the value inside the box.
Images from “Polygonising a scalar field” – Paul Bourke
When I attempted this, I partially followed a tutorial by b3agz. As he was making a terrain and not a planet like I planned on, I had to get it shaped into a sphere.
I did this by looping through the grid and assigning 0 to the cells that were inside a sphere’s radius. This gave me the effect I wanted to have.
Here I started seeing my first problems with Marching Cubes, it’s not as smooth as I wanted it to be. The sphere got more smooth the bigger it gets, but this also means more cubes. More cubes could be solved by an octree, for smoothness I looked at other algorithms.
Surface nets has the same style of grid like Marching Cubes, only does Surface Nets have 1 vertice per cube not 3. The goal is to push the vertice as close as you can to the edge.
Instead of using a grid, I tried to implement an Octree. I first made some drawings on what I wanted to do and since I already knew I wanted a sphere, I was planning to make the Octree push outwards. Only making a box if the box position fits inside the sphere’s radius.
All nodes are saved inside a dictionary, with the key as the nodes position and value as the node script. Every node also saves their position, value(if I ever needed it), size and the starting script so I could add the next nodes to the dictionary.
If my potentional neighbour’s position is inside the circle, we create it. Are we on the outside of the cube and can’t make any more neighbours? We go look if we can make children to get the vertice count up inside a cube. This makes it so there is an LOD system in place.
If we are the last node and don’t have any children, we take a look at where we place the vertice. I do this by calculating the distance from this node towards the middle and subtracting this from the radius, leaving us the distance we still need towards the edge. Then I multiply the direction from the middle to this node by the distance we need to go.
Here is where the struggles began. Making triangles with neighbours/children their vertices. By finding what neighbours are in common, I can find out what vertices I need to connect for a triangle. This gives me too many triangles on the same spot. I did not get to solve this.
Dual Contouring also has 1 vertice per cube like Marching Cubes. For this vertice position, you calculate the intersection between the 2 edges of the cube. This being called the QEF. Being the more difficult version of algorithms, I chose to try out Surface Nets instead.
Image from “QEF Explainer” – Matt Keeter
For the non-voxel planet, I made use of Sebastian Lague’s great ability to teach. Following the Procedural Planet series I got to use ShaderGraph for the first time, learned more clean coding ways that I probably should’ve had before and did never done before editor coding.
There are several ways of making a procedural planet, and a big question is if you want to be able to modify a planets surface. For a modifiable planet, the best algorithm would be Dual Contouring, as it gives the most sharp edges, but the easier option would be Surface Nets. For a normal procedural planet, there are plenty of good tutorials that help you learn a lot of things outside just making procedural planets. For what I have learned in this R&D project, is that I should look more before being demotivated by the most difficult to implement algorithm(Dual Contouring) and look around for all the options that give a similar result. Finding Surface Nets and thinking to myself, “Why wouldn’t I be able to do this?” got me a great boost, but sadly I couldn’t finish it with the troubles I had with triangles.
Paul Bourke, (1994, May) Polygonising a scalar field. http://paulbourke.net/geometry/polygonise/
b3agz, (2020) How to Make 7 Days to Die in Unity – 01 – Marching Cubes. https://www.youtube.com/watch?v=dTdn3CC64sc
Cerbion.net, (2020 April 28th) Understanding Surface Nets. https://cerbion.net/blog/understanding-surface-nets/
Tao Ju, Frank Losasso, Scott Schaefer, Joe Warren
Rice University, (2001) Dual Contouring of Hermite Data. https://cse.wustl.edu/~taoju/research/dualContour.pdf (for Dual Contouring)
Matt Keeter, () QEF Explainer. https://www.mattkeeter.com/projects/qef/
Sebastian Lague, (2019) [Unity] Procedural Planets (E01 the sphere). https://www.youtube.com/watch?v=QN39W020LqU