Github Repository
Terrain generation is the process of generating a 3D mesh from a set of (usually randomized) 3D data to look like natural terrain. This project presents an implementation of the Cubical Marching Squares algorithm originally proposed by Chien-Chang Ho et al. and sampled from a dynamic Octree data structure.
The Lingo
There are many different types of 3D meshing algorithms with Marching Cubes/Marching Squares and Dual Contouring being the two most popular ones. The input to these algorithms is some kind of 3D data set. The type of data I use for my project is called Hermite Data. Each point in a Hermite Data set contains the density and normal vector at that point in space, and for those unfamiliar with 3D graphics, a normal vector is a vector that ‘points away’ from and is perpendicular to the surface. The data in my Hermite Data set is randomly using layered 3D perlin noise, which is type of smooth random noise, to mimic the look of terrain. That data is then used to generate an Octree data structure. An Octree is a recursive data structure that gets smaller depending on the amount of detail and data it needs to hold, so with areas of less detail on the surface, the Octree holds ‘less data’ and vice versa which helps with optimizations.
It’s Octree’in Time
To generate an Octree, I decided to generate it in parallel on a GPU using whats called a Compute Shader, which is a special shader specifically designed for computations rather than rendering. Now, the recursive nature of an Octree makes it particularly difficult to compute in a parallel environment. To fully utilize the power of computing in parallel, you want your instances of your algorithm to be as independent from each other as possible because otherwise there could be what are called race conditions. Race conditions are when there are two or more instances of an algorithm trying to read and/or write data at the same point at the ‘same time’. Since data cannot be read or written at the same place literally at the same time, there is a race to which instance goes first and there is no guarantee as to who will come first leading to possible inconsistent and unpredictable behavior. So, to generate an Octree in parallel, I tackled the problem in reverse by starting out with every node at a maximum subdivision level and working backgrounds through un-subdivision. To achieve the un-subdivisions, I had to split the process into two steps. The first step was to create a list of custom structs containing information about the parent node of each node at each subdivision level. To collect this information, I went in reverse and utilized consecutive parallel merges to properly calculate the necessary information using local memory on the GPU and taking advantage of the GPU architecture. With the custom structs calculated, the generation of the Octree is completed easily using the information gathered to determine whether a particular node needs to be un-subdivided. One disadvantage to completing this process in parallel is it means the algorithm starts out at maximum efficiency but each un-subdivision makies it less and less efficient as the more nodes remaining gets less and less.
The Second Part
The Cubical Marching Squares (CMS) algorithm is a clever deconstruction of the Marching Cubes algorithm. The Marching Cubes works from splitting the 3D data set into a grid of nodes or cubes which it then meshes each cube individually forming a bigger more complex mesh in the process. CMS works by taking the inherit 3D problem of Marching Cubes and deconstructing it into smaller easier to solve 2D problems. So, instead of meshing one cube, that cube is split into is 6 faces and meshed using the 2D equivalent of Marching Cubes, Marching Squares.The 6 faces are then traced to form the mesh of the cube. By modifying the Marching Cubes algorithm in this manner, it allows the resolving of a lot of the weaknesses of Marching Cubes. One advantage is it allows the preservation of sharp features within a mesh so any sharp corners that may be present. The biggest advantage, however, is the possible compatibility with a variable level of detail system which is something that was very difficult to achieve with Marching Cubes. Therefore, implementing the CMS algorithm, I was able to integrate it with Octree data structure discussed previously. The most difficult part about this process is resolving the transition faces, which means two neighboring faces that are of different subdivision levels. These transition faces create holes in the mesh making it a non-manifold mesh. The current solution I created for this problem is most likely not the best as some issues still remain. Upon the first generation of a mesh, it successfully creates a manifold or air tight mesh with varying LODs. However, strangely, upon regenerating a given mesh, holes start to appear at the transition faces making a non-manifold meshes. Some more work needs to be done to figure out a complete solution to this issue.
The Road Ahead
There is a lot of work that remains to get this project to where I want it to go. The first task is to fix the current bugs found within the project. From there, there are many avenues I want to explore for this project. A big aspect is expanding the scale of the terrain generation to a possible planet-wide scale. This will require a more robust implementation of an LOD system that spans across multiple chunks of different terrains. Another big part of that goal is the amount of data required for a planet and the streaming of that data between the CPU and GPU. Another big area I would like to explore is the noise generation for the terrain. I wish to explore using various types of noise with different layers to achieve all types of terrains from mountains, caves, oceans, rivers, etc. Lastly, another area of potential exploration is the integration of a voxel-based water physics system of the likes of 7 Days to Die, Minecraft, and Terraria.