Procedural Terrain Generation: Making a TerrainSquare

I've made a few posts about procedural terrain, and now I'm going to get into some of the code. For this post, I'm just going to go over the class that generates a single square. The entire file is provided at the bottom of the post, but you can't go dropping it into an existing project, as there are certain dependencies you won't have. However, it'll most certainly show exactly how it works and the concepts are universal. I'm sure it can be cleaned up and improved in places, and any insights are appreciated.

Before going into it, I should point out that there are two "oddities" with this code. One is that it's meant to be run on separate threads from Unity's main thread of execution. This is required in order to ensure smooth generation and actually using the computing power available in modern CPUs. However, Unity does not play nice with threading. As such, calls to the Unity API must be held off until the very end when the data gets returned to the main thread. So in this class, we number crunch as much as possible, then signal when we're done so that the TerrainManager can instantiate the GameObject in the main thread. The second oddity is that Unity is pretty dumb about garbage collection, owing to using an outdated version of Mono. Because speed is critical here, aggressive object pooling is used to prevent allocation of new resources (and the TerrainSquare objects themselves are reused by the TerrainManager).

So let's get into it.

This should be pretty straight forward. The FastMesh object is what all the mesh data is being loaded into. One is grabbed from the MeshPool already initialized with the proper arrays that we can populate with mesh data. The 2D array of floats stores our height map. This is only actually used to create the TerrainCollider Unity object so that we're not attempting to use giant MeshColliders where they're not needed. The WorldData static object contains the functions that generate the terrain data, and has already been primed with a seed.

From there you have our static pools. One for the quads we generate, the meshes, biome data, and height maps. If you're just making one square, Unity gets updated with a proper garbage collector, or you're using a different engine that doesn't have to use pooling, then you don't need these.

This is the function where the magic happens. The name ThreadedFunction derives from the base class that sets up the structure for large threaded jobs, and is called when Start() is executed. First we pull from the WorldData some information on how to build the square: the number of quads on the side of a terrain square, and how large those quads are going to be. The total number of quads per square is WorldData.QUAD_NUMBER ^ 2 with 2 triangles per quad. We're going for the flat shaded look here, and want it to be widely supported without having to use geometry shaders (also when it was written I had no idea where to even begin on shaders), so no vertices are shared between triangles. As such, each tri gets its own 3 vertices and does not share them with neighbors. It also makes index calculation super easy.

Finally, we go ahead and pull the objects we'll be storing data in from the buffers.

Now things get fun. The quads for our mesh are currently stored in a 1D array. I'm honestly not sure if 1D is really any faster than 2D or jagged in this case, it was simply one of the little things I did when trying to eak out as much speed as I could (it was the first time I've really had to squeeze performances out of a program, and Unity is pretty unhelpful in profiling functions not on the main thread). So a little bit of math is required to get the current quad from the iteration variables. We simply loop through x and z and perform the following operations for each square.

Next, we calculate where in "noise space" we currently are. This is defined by the terrain square's set location combined with which quad we're on. It seems pretty weird at first glance that the location is divided by the quad length. This goes into some noise location vs world space location conversions that are done to enable greater or smaller sampling resolution of the noise while still keeping the same overall shape of terrain. If you don't intend to play with just how large the terrain resolution is or don't care about maintaining the same overall pattern (without stretching or squishing it) then you can ignore this little complication.

That being said, the NoiseLoc variable corresponds to the lower left vertex. We then create 3 new locations based on it for the next steps along the x and z axes.

Now it's finally time to start pulling some height values. The simplest way to do this would be to just plug in the location for each quarter into the the WorldData.GetHeight() function and be done with it, but it's inefficient. Most of the time you're not creating a new row or column, and the height of a vertex can be pulled from the leading edge of the previous row or column. The only height you are guaranteed to have to calculate is the upper right corner, so first we do that. Note that the x and z values provided to the vertex are in object space, while the height (y value) is taken from the WorldData's height function using the value that we converted to "noise space". Here vertex 0, 2, and 3 correspond to the first, lower left triangle, and vertex 1, 4, and 5 are the upper right triangle. This convention holds for the normals, colors, etc.

Next we check our x and z values to see if we're creating a new row or column. If they're both zero, then this is our first quad and need to bootstrap the whole thing. Note the doubling up of vertices for flat shading.

Continuing on, check to see if it's a new row or column and generate the require vertex values appropriately, pulling from previous quads where you can. Most of the time will be spent in the else section which can just copy the values already generated.

Populate the height map with the values we already crunched for the vertices. Since Unity height maps are stored in a range from 0 to 1, we need to convert from full scale down to the proper range.

Unity has a nice RecalculateNormals() function for meshes that works pretty well, however it will only run on the main thread. Because of the overall desire to interrupt that thread as little as possible, they're calculated by hand here. I honestly can't elaborate on the math, this is from researching the vector calculations needed for flat shading each triangle and adapting it here. Totally works though.

Now that we've constructed location and lighting, it's time for some color.

Color is handled per-triangle, so we need to switch to that sort of math instead of per-vertex. We still need positioning data though, so we average the 3 vertices together for both triangles in the quad to get their center. In order to color them, the first thing we need to do is pull their biome information. Biomes are climate zones defined by temperature and moisture levels. Hot dry areas are deserts, hot wet areas are jungle, etc. These two values can give you most of the climate zones on Earth. The use of continuous noise should ensure that deserts don't end up adjacent to snow fields. In addition, the height of the triangle is needed in the calculation to reduce the heat value of the triangle, so it's also provided to the biome data function.

Once we've gotten our biome data, it's time to initialize the colors. For this generator, there are 3 colors associated with each biome: ground, rock, and beach. Ground is the default color, rock is for triangles that have a large slope, and beach is self explanatory. These colors are blended in 2 ways: transition between type (ground/rock/beach) and transition between biome.

The biome data we got previously gives us the overall data for each biome and how closely the triangle resembles that biome. This is defined by a float value that measures distances along an x,y graph that maps temperature and moisture. Lower values are closer matches, higher values are farther matches.

First, the distance value is squared to reduce the influence of far flung biomes. We're mainly interested in the nearby ones so that the colors smoothly transition from one biome to the next. The 3 color types are then generated by adding up each biome's color, divided by that squared distance. This ensures that the close biomes has a far greater say on color than farther ones. The total divisor keeps track of how much we ultimately need to divide by in order to get the average color, and gets applied to the final 3 colors get the true values. Using this divisor (instead of dividing by the total number of biomes that you typically would for the mean) biases the colors even more toward the closest biome.

For beaches, we still want a gradual transition, but it needs to be quick. We're looking for this effect:

So with that in mind, everything below the sea level (y = 0) gets colored for beach. Beyond that, we calculate the color difference between ground and beach and transition between them based on height.

For exposed rock we do a similar transition effect, but based upon slope instead of height. This is done be figuring out the maximum height difference between any 2 vertex pair for each triangle.

This concludes the vertex color data and most of the heavy lifting. The only thing left are the UVs and indices, which are easy enough (thank you flat shading). UVs are simply repeated per quad, and indices are just the number of quads generated times the vertex count per quad (6) +1 for each vertex. Then populate the FastMesh object so that it's ready to go. It might look crazy to have so many calls to the FastMesh functions when I could have added versions that took arrays or params, but once again I'm trying to cut down on memory allocation and I've already got a ton of pools.

Indices get passed to the FashMesh, close out the loop, mark the square as finished, and release the quad array back to the pool.

The rest of the code in this particular file are self explanatory, and deal with object creation and reset, as well as the quad structure used to keep track of things. I hope someone gets something out of this, and if you have any questions or comments feel free to post!

The full source file is as follows:

//#define BENCHMARK
//#define DEBUG

using Smooth.Algebraics;
using Smooth.Pools;
using System;
using System.Collections.Generic;
using UnityEngine;

public class TerrainSquare : ThreadedJob
{
    public Vector3 Location;
    FastMesh FM;
    float[,] HM;
    public static WorldData WD;

    //Remove [] next to FastMesh.  Had to get steemit to stop complaining
    static Pool<Quad[]> QuadPool = new Pool<Quad[]>(CreateQs, ResetQs);
    static Pool<FastMesh[]> MeshPool = new Pool<FastMesh[]>(CreateFM, ResetFM);
    static Pool<Tuple<Biome, float>[]> BiomeDataPool = new Pool<Tuple<Biome, float>[]>(CreateBD, ResetBD);
    static Pool<float[,]> HeightPool = new Pool<float[,]>(CreateHM, ResetHM);

    public FastMesh Mesh
    {
        get
        {
            if(IsDone) return FM;
            else return null;
        }
    }

    public float[,] HeightMap
    {
        get
        {
            if(IsDone) return HM;
            else return null;
        }
    }

    protected override void OnStart()
    {
        if(WD == null)
        {
            throw new InvalidOperationException("TerrainSquare has not been provided with WorldData.");
        }
    }

    protected override void ThreadFunction(object obj)
    {
        // Number of quads per side of the square
        int SLength = WorldData.QUAD_NUMBER;

        // The size of each quad side
        float QLength = WorldData.QUAD_LENGTH;

        FM = MeshPool.Borrow();
        HM = HeightPool.Borrow();
        Quad[] Quads = QuadPool.Borrow();

        for(int x = 0; x < SLength; x++)
        {
            for(int z = 0; z < SLength; z++)
            {
                int n = x * SLength + z;
                Quads[n] = new Quad();

                Vector3 NoiseLoc = new Vector3(x + (Location.x / QLength), 0, z + (Location.z / QLength));

                Vector3 NoiseLocZ = NoiseLoc + new Vector3(0, 0, 1);
                Vector3 NoiseLocX = NoiseLoc + new Vector3(1, 0, 0);
                Vector3 NoiseLocXZ = NoiseLoc + new Vector3(1, 0, 1);

                Quads[n].Ver3 =
                Quads[n].Ver4 =
                    new Vector3(
                        (x + 1) * QLength,
                        WD.GetHeight(NoiseLocXZ),
                        (z + 1) * QLength);

                // First row, first column
                if(x == 0 && z == 0)
                {
                    Quads[n].Ver0 =
                    Quads[n].Ver1 =
                        new Vector3(
                            x * QLength,
                            WD.GetHeight(NoiseLoc),
                            z * QLength);

                    Quads[n].Ver2 =
                        new Vector3(
                            x * QLength,
                            WD.GetHeight(NoiseLocZ),
                            (z + 1) * QLength);

                    Quads[n].Ver5 =
                        new Vector3(
                            (x + 1) * QLength,
                            WD.GetHeight(NoiseLocX),
                            z * QLength);
                }
                else if(x == 0)
                {
                    Quads[n].Ver0 =
                    Quads[n].Ver1 =
                        Quads[n - 1].Ver2;

                    Quads[n].Ver2 =
                        new Vector3(
                            x * QLength,
                            WD.GetHeight(NoiseLocZ),
                            (z + 1) * QLength);

                    Quads[n].Ver5 =
                        Quads[n - 1].Ver3;
                }
                else if(z == 0)
                {
                    Quads[n].Ver0 =
                    Quads[n].Ver1 =
                        Quads[n - SLength].Ver5;

                    Quads[n].Ver2 =
                        Quads[n - SLength].Ver3;

                    Quads[n].Ver5 =
                        new Vector3(
                            (x + 1) * QLength,
                            WD.GetHeight(NoiseLocX),
                            z * QLength);
                }
                else
                {
                    Quads[n].Ver0 =
                    Quads[n].Ver1 =
                        Quads[n - SLength].Ver5;

                    Quads[n].Ver2 =
                        Quads[n - SLength].Ver3;

                    Quads[n].Ver5 =
                       Quads[n - 1].Ver3;
                }

                //Heightmap (for collisions)
                HM[z, x] = (Quads[n].Ver0.y) / WorldData.MAX_HEIGHT;
                if(x == SLength - 1) HM[z, x + 1] = (Quads[n].Ver5.y) / WorldData.MAX_HEIGHT;
                if(z == SLength - 1) HM[z + 1, x] = (Quads[n].Ver2.y) / WorldData.MAX_HEIGHT;
                if(x == SLength - 1 && z == SLength - 1) HM[z + 1, x + 1] = (Quads[n].Ver3.y) / WorldData.MAX_HEIGHT;

                //Normals
                Vector3 V, W, N;
                V = Quads[n].Ver2 - Quads[n].Ver0;
                W = Quads[n].Ver3 - Quads[n].Ver0;
                N.x = (V.y * W.z) - (V.z * W.y);
                N.y = (V.z * W.x) - (V.x * W.z);
                N.z = (V.x * W.y) - (V.y * W.x);
                Quads[n].Nor0 = Quads[n].Nor2 = Quads[n].Nor3 = N.normalized;

                V = Quads[n].Ver4 - Quads[n].Ver1;
                W = Quads[n].Ver5 - Quads[n].Ver1;
                N.x = (V.y * W.z) - (V.z * W.y);
                N.y = (V.z * W.x) - (V.x * W.z);
                N.z = (V.x * W.y) - (V.y * W.x);
                Quads[n].Nor1 = Quads[n].Nor4 = Quads[n].Nor5 = N.normalized;

                Vector3 Tri1A = (NoiseLoc + NoiseLocXZ + NoiseLocZ) / 3;
                Vector3 Tri2A = (NoiseLoc + NoiseLocXZ + NoiseLocX) / 3;
                float Tri1H = (Quads[n].Ver0.y + Quads[n].Ver2.y + Quads[n].Ver3.y) / 3;
                float Tri2H = (Quads[n].Ver1.y + Quads[n].Ver5.y + Quads[n].Ver4.y) / 3;

                Tuple<Biome, float>[] BiomeData1 = BiomeDataPool.Borrow();
                Tuple<Biome, float>[] BiomeData2 = BiomeDataPool.Borrow();

                WD.GetBiome(Tri1A, Tri1H, BiomeData1);
                WD.GetBiome(Tri2A, Tri2H, BiomeData2);
                Color Ground1, Ground2, Beach1, Beach2, Rock1, Rock2;
                Ground1 = Ground2 = Beach1 = Beach2 = Rock1 = Rock2 = new Color();
                float Divisor1 = 0, Divisor2 = 0;

                for(int i = 0; i < BiomeData1.Length; i++)
                {
                    float Div = (float)Math.Pow(BiomeData1[i]._2, 2);
                    Ground1 += BiomeData1[i]._1.Ground / Div;
                    Beach1 += BiomeData1[i]._1.Beach / Div;
                    Rock1 += BiomeData1[i]._1.Rock / Div;
                    Divisor1 += 1 / Div;
                }
                Ground1 /= Divisor1;
                Beach1 /= Divisor1;
                Rock1 /= Divisor1;
                Quads[n].C0 = Quads[n].C2 = Quads[n].C3 = Ground1; 

                for(int i = 0; i < BiomeData2.Length; i++)
                {
                    float Div = (float)Math.Pow(BiomeData2[i]._2, 2);
                    Ground2 += BiomeData2[i]._1.Ground / Div;
                    Beach2 += BiomeData2[i]._1.Beach / Div;
                    Rock2 += BiomeData2[i]._1.Rock / Div;
                    Divisor2 += 1 / Div;
                }
                Ground2 /= Divisor2;
                Beach2 /= Divisor2;
                Rock2 /= Divisor2;
                Quads[n].C1 = Quads[n].C4 = Quads[n].C5 = Ground2;

                float BeachLine = WorldData.BeachLine;
                if((Quads[n].Ver0.y + Quads[n].Ver2.y + Quads[n].Ver3.y) / 3 < 0) Quads[n].C0 = Quads[n].C2 = Quads[n].C3 = Beach1;
                else if((Quads[n].Ver0.y + Quads[n].Ver2.y + Quads[n].Ver3.y) / 3 < BeachLine * 2)
                {
                    Color bdiff = Ground1 - Beach1;
                    float scale = (Quads[n].Ver0.y + Quads[n].Ver2.y + Quads[n].Ver3.y) / 3 / (BeachLine * 2);
                    Quads[n].C0 = Quads[n].C2 = Quads[n].C3 = Beach1 + (bdiff * (float)Math.Pow(scale, 2));
                }

                if((Quads[n].Ver1.y + Quads[n].Ver4.y + Quads[n].Ver5.y) / 3 < 0) Quads[n].C1 = Quads[n].C4 = Quads[n].C5 = Beach2;
                else if((Quads[n].Ver1.y + Quads[n].Ver4.y + Quads[n].Ver5.y) / 3 < BeachLine * 2)
                {
                    Color bdiff = Ground2 - Beach2;
                    float scale = (Quads[n].Ver1.y + Quads[n].Ver4.y + Quads[n].Ver5.y) / 3 / (BeachLine * 2);
                    Quads[n].C1 = Quads[n].C4 = Quads[n].C5 = Beach2 + (bdiff * (float)Math.Pow(scale, 2));
                }

                float RockThreshold = WorldData.RockThreshold;
                float Slope1 = Mathf.Max(Mathf.Abs(Quads[n].Ver2.y - Quads[n].Ver0.y), Mathf.Abs(Quads[n].Ver2.y - Quads[n].Ver3.y), Mathf.Abs(Quads[n].Ver0.y - Quads[n].Ver3.y));
                if(Slope1 > RockThreshold)
                {
                    Color rdiff = Rock1 - Quads[n].C0;
                    Slope1 -= RockThreshold;
                    float scale = Slope1 / RockThreshold;
                    if(scale > 1) scale = 1;
                    Quads[n].C0 = Quads[n].C2 = Quads[n].C3 = Quads[n].C0 + (rdiff * scale);
                }
                float Slope2 = Mathf.Max(Mathf.Abs(Quads[n].Ver1.y - Quads[n].Ver4.y), Mathf.Abs(Quads[n].Ver1.y - Quads[n].Ver5.y), Mathf.Abs(Quads[n].Ver4.y - Quads[n].Ver5.y));
                if(Slope2 > RockThreshold)
                {
                    Color rdiff = Rock2 - Quads[n].C1;
                    Slope2 -= RockThreshold;
                    float scale = Slope2 / RockThreshold;
                    if(scale > 1) scale = 1;
                    Quads[n].C1 = Quads[n].C4 = Quads[n].C5 = Quads[n].C1 + (rdiff * scale);
                }

                BiomeDataPool.Release(BiomeData1);
                BiomeDataPool.Release(BiomeData2);
                
                Quads[n].UV0 = new Vector2(0, 0);
                Quads[n].UV2 = new Vector2(0, 1);
                Quads[n].UV3 = new Vector2(1, 1);

                Quads[n].UV1 = new Vector2(1, 1);
                Quads[n].UV4 = new Vector2(1, 0);
                Quads[n].UV5 = new Vector2(0, 0);

                Quads[n].Ind0 = 0 + (n * 6);
                Quads[n].Ind1 = 2 + (n * 6);
                Quads[n].Ind2 = 3 + (n * 6);

                Quads[n].Ind3 = 1 + (n * 6);
                Quads[n].Ind4 = 4 + (n * 6);
                Quads[n].Ind5 = 5 + (n * 6);

                FM.AddVertex(Quads[n].Ver0); FM.AddVertex(Quads[n].Ver1); FM.AddVertex(Quads[n].Ver2); FM.AddVertex(Quads[n].Ver3); FM.AddVertex(Quads[n].Ver4); FM.AddVertex(Quads[n].Ver5);
                FM.AddNormal(Quads[n].Nor0); FM.AddNormal(Quads[n].Nor1); FM.AddNormal(Quads[n].Nor2); FM.AddNormal(Quads[n].Nor3); FM.AddNormal(Quads[n].Nor4); FM.AddNormal(Quads[n].Nor5);
                FM.AddColors(Quads[n].C0); FM.AddColors(Quads[n].C1); FM.AddColors(Quads[n].C2); FM.AddColors(Quads[n].C3); FM.AddColors(Quads[n].C4); FM.AddColors(Quads[n].C5);
                FM.AddUV(Quads[n].UV0); FM.AddUV(Quads[n].UV1); FM.AddUV(Quads[n].UV2); FM.AddUV(Quads[n].UV3); FM.AddUV(Quads[n].UV4); FM.AddUV(Quads[n].UV5);
                FM.AddTri(Quads[n].Ind0, Quads[n].Ind1, Quads[n].Ind2);
                FM.AddTri(Quads[n].Ind3, Quads[n].Ind4, Quads[n].Ind5);
            }
        }

        IsDone = true;
        QuadPool.Release(Quads);
    }

    protected override void OnFinished()
    {
    }

    static FastMesh CreateFM()
    {
        int SLength = WorldData.QUAD_NUMBER;
        return new FastMesh(SLength * SLength * 6, SLength * SLength * 6, true, true, true);
    }

    public static void ResetTS(TerrainSquare TS)
    {
        MeshPool.Release(TS.FM);
        HeightPool.Release(TS.HM);
        TS.Location = Vector3.zero;
        TS.IsDone = false;
    }

    static void ResetFM(FastMesh FM)
    {
        FM.Reset();
    }

    static Tuple<Biome, float>[] CreateBD()
    {
        return new Tuple<Biome, float>[WD.Biomes.Length];
    }

    static void ResetBD(Tuple<Biome, float>[] BD)
    {
    }

    static Quad[] CreateQs()
    {
        return new Quad[WorldData.QUAD_NUMBER * WorldData.QUAD_NUMBER];
    }

    static void ResetQs(Quad[] q)
    {
    }

    static float[,] CreateHM()
    {
        return new float[WorldData.QUAD_NUMBER + 1, WorldData.QUAD_NUMBER + 1];
    }

    static void ResetHM(float[,] HM)
    {

    }
    
    struct Quad
    {
        // No arrays in order to reduce heap allocation
        public Vector3 Ver1, Ver2, Ver3, Ver4, Ver5, Ver0;
        public Vector3 Nor0, Nor1, Nor2, Nor3, Nor4, Nor5;
        public Vector2 UV0, UV1, UV2, UV3, UV4, UV5;
        public int Ind0, Ind1, Ind2, Ind3, Ind4, Ind5;
        public Color32 C0, C1, C2, C3, C4, C5;
    }
}