Tuesday, October 01, 2013 Eric Richards

Generating Random Terrains using Perlin Noise

Terrain DirectX 11 Perlin Noise SlimDX C# Procedural Terrain

Perlin Noise

The Perlin Noise function defines a continuous curve or surface which contains both large and small scale features.  To generate Perlin Noise, we add together noise functions of different frequencies and amplitudes, where the frequency is the number of samples on the noise curve and amplitude is the range of values, which gives us the final noise curve or surface.  We call each constituent noise curve of the final noise function an octave, since, for each successive octave, the frequency doubles.  We will control the amplitude of each curve with a value we’ll call persistence.  The relationship between amplitude and persistence is: amplitude = persistence^octave. 

To generate reliable Perlin noise, we need a pseudo-random noise function which has the property that it returns the same value for a given seed value.  The .NET Random class is not really suited for this, so we will create our own noise function.  The following function will be added to our MathF utility class, and is adapted from Mr. Granberg’s code (which appears to be adapted from Hugo Elias’s implementation):

public static float Noise(int x) {
    x = (x << 13) ^ x;
    return (1.0f - ((x * (x * x * 15731) + 1376312589) & 0x7fffffff) / 1073741824.0f);
}

The finer details of the implementation are beyond me, but this seems to be a commonly-accepted random number generation algorithm; for our purposes, just know that this function returns a random value based on the input parameter in the range [-1,1].

To produce a continuous curve from the sampled points on a noise curve, we need to interpolate between the nearest samples.  We could use linear interpolation as a very cheap method of interpolating between samples, but that would produce a very blocky noise curve function.  Instead, for a smoother curve, we can use cosine interpolation, which is still relatively cheap to compute, in comparison to other more exact methods, like cubic interpolation.  Cosine interpolation is not provided out-of-the-box in .NET, so we will add a CosInterpolate() function to our MathF utility class as well.

public static float CosInterpolate(float v1, float v2, float a) {
    var angle = a * PI;
    var prc = (1.0f - LookupCos(angle)) * 0.5f;
    return v1 * (1.0f - prc) + v2 * prc;
}

When I first implemented this, I used the standard .NET Math.Cos() function, but found that it was unacceptably slow.  Instead, I wrote a simple command-line program to calculate the cosine of every angle between 0 and 2*PI and output these cosines as a C# array that I could add to my MathF class.  I then added the LookupCos function to index into this lookup table.  The resolution on the angles is only accurate to the thousandth’s place, but for this application, that seems to be good enough, and the array lookup is significantly cheaper than using Math.Cos().

public static float LookupCos(float a) {
    var a1 = (int)(a * 1000);
    return CosLookup[a1];
}

private static readonly float[] CosLookup = new[]{ 
    1f,
    0.9999995f,
    0.999998f,
    // 6000-odd more entries...
    1.0f
};

With our noise function and our interpolation function defined, we can implement our 2D Perlin Noise function.  This function takes a seed value, which will be constant for the entire heightmap, the persistence value for the noise function, the octave number of the noise curve we are generating, and the x and y coordinates of the desired position.

public static float PerlinNoise2D(int seed, float persistence, int octave, float x, float y) {
    var freq = (float)Math.Pow(2.0f, octave);
    var amp = (float)Math.Pow(persistence, octave);
    var tx = x * freq;
    var ty = y * freq;
    var txi = (int)tx;
    var tyi = (int)ty;
    var fracX = tx - txi;
    var fracY = ty - tyi;

    var v1 = Noise(txi + tyi * 57 + seed);
    var v2 = Noise(txi + 1 + tyi * 57 + seed);
    var v3 = Noise(txi + (tyi + 1) * 57 + seed);
    var v4 = Noise(txi + 1 + (tyi + 1) * 57 + seed);

    var i1 = CosInterpolate(v1, v2, fracX);
    var i2 = CosInterpolate(v3, v4, fracX);
    var f = CosInterpolate(i1, i2, fracY) * amp;
    return f;
}

First, we calculate the frequency and amplitude of the noise, according to the persistence and octave parameters.  Next, we determine the position on the noise surface that we wish to sample (tx, ty), along with the closest integral sample points (txi, tyi).  Our interpolation factors will be the distance of the computed sample points from the integral sample points (fracX, fracY).  We sample the noise function at the four integral points defining the quad that our sample point lies on.  Multiplying by 57 adds some extra randomness to the samples, and we add the seed value as an offset.  Finally, we do a bi-cosine interpolation, using the x and y interpolation factors previously computed, and multiply the resulting value by the octave amplitude.

Generating a Random Heightmap

With our Perlin Noise generation encapsulated into utility functions in MathF, the algorithm for creating a random heightmap is very simple.  We will simply loop over each cell in our heightmap, sum the octaves of Perlin Noise for each cell, shift the noise into the [0,1] range, and normalize the heightmap values by the HeightMap’s MaxHeight value.  Since each heightmap value is independent, we can use the Task Parallel Library (TPL) introduced in .NET 4.0 to calculate the heightmap values in parallel.  We will add the CreateRandomHeightMapParallel() function to our HeightMap class.  This function will take as parameters a seed value, a noiseSize parameter that modifies the noise samples for each cell, the noise function persistence value and the number of octaves of noise to use.  We will add an additional optional parameter to control whether we display the progression of the heightmap generation algorithm using our ProgressUpdate class.

public void CreateRandomHeightMapParallel(int seed, float noiseSize, float persistence, int octaves, bool drawProgress = false) {

    for (var y = 0; y < HeightMapHeight; y++) {
        var tasks = new List<Action>();
        int y1 = y;

        for (var x = 0; x < HeightMapWidth; x++) {
            int x1 = x;
            tasks.Add(() => {
                var xf = (x1 / (float)HeightMapWidth) * noiseSize;
                var yf = (y1 / (float)HeightMapHeight) * noiseSize;

                var total = 0.0f;
                for (var i = 0; i < octaves; i++) {
                    var f = MathF.PerlinNoise2D(seed, persistence, i, xf, yf);
                    total += f;
                }
                var b = (int)(128 + total * 128.0f);
                if (b < 0) b = 0;
                if (b > 255) b = 255;

                _heightMap[x1 + y1 * HeightMapHeight] = (b / 255.0f) * MaxHeight;
            });
        }
        if (drawProgress) {
            D3DApp.GD3DApp.ProgressUpdate.Draw(0.1f + 0.40f * ((float)y / HeightMapHeight), "Generating random terrain");
        }
        Parallel.Invoke(tasks.ToArray());
    }
}

Using the TPL, you may need to fine-tune which loops of the above algorithm are assigned to an Action.  If there is too little processing in a loop to offset the overhead of creating the Action, the above code may run slower than even the straight single-threaded version of the same algorithm.

Multiplying HeightMaps

One final thing to note before we move on from generating heightmaps is that often we can produce more natural looking terrain heightmaps by multiplying two or more heightmaps together.  One approach would be to use one heightmap with a large noise size and large persistence to define the large-scale features of the terrain, and another heightmap with small noise size and persistence to add small-scale irregularities.  To multiply two heightmaps, we will overload the * (multiplication) operator.  We will then perform a component-wise multiplication of the two heightmaps, normalizing the heightmap values by dividing the values by their respective heightmap’s MaxHeight before multiplying them, and then scaling the resulting heightmap value back into the left-hand heightmap’s MaxValue range.

public static HeightMap operator *(HeightMap lhs, HeightMap rhs) {
    var hm = new HeightMap(lhs.HeightMapWidth, lhs.HeightMapHeight, lhs.MaxHeight);
    for (int y = 0; y < lhs.HeightMapHeight; y++) {
        for (int x = 0; x < lhs.HeightMapWidth; x++) {
            var a = lhs[y, x] / lhs.MaxHeight;
            var b = 1.0f;
            if (rhs.InBounds(y, x)) {
                b = rhs[y, x] / rhs.MaxHeight;
            }
            hm[y, x] = a * b * hm.MaxHeight;
        }
    }
    return hm;
}

Generating Random Terrains

With the code in place to generate a random heightmap, we can implement our random terrain generation code.  We will need to modify our Terrain.Init() function to support random terrains.  Before, we were loading the terrain heightmap image passed in as the InitInfo.HeightMapFilename member.  Now, we will add code to detect if the supplied filename is null or empty, and if so, generate a random heightmap instead.  We will perform a similar check on the InitInfo.BlendMapFilename member, to determine if we should load the blend map from file or generate it at runtime.

public void Init(Device device, DeviceContext dc, InitInfo info) {
    D3DApp.GD3DApp.ProgressUpdate.Draw(0, "Initializing terrain");
    
    // other init code...

    _heightMap = new HeightMap(Info.HeightMapWidth, Info.HeightMapHeight, Info.HeightScale);
    if (!string.IsNullOrEmpty(Info.HeightMapFilename)) {
        D3DApp.GD3DApp.ProgressUpdate.Draw(0.1f, "Loading terrain from file");
        _heightMap.LoadHeightmap(Info.HeightMapFilename);

    } else {
        D3DApp.GD3DApp.ProgressUpdate.Draw(0.1f, "Generating random terrain");
        GenerateRandomTerrain();
    }

    // other init code...

    if (!string.IsNullOrEmpty(Info.BlendMapFilename)) {
        D3DApp.GD3DApp.ProgressUpdate.Draw(0.95f, "Loading blendmap from file");
        _blendMapSRV = ShaderResourceView.FromFile(device, Info.BlendMapFilename);
    } else {
        _blendMapSRV = CreateBlendMap(_heightMap, device);
    }
    D3DApp.GD3DApp.ProgressUpdate.Draw(1.0f, "Terrain initialized");
}

To support generating random terrain, we will extend our InitInfo structure to contain the seed, noiseSize, persistence and number of octaves for up to two heightmaps.

public struct InitInfo {
    // RAW heightmap image file or null for random terrain
    public string HeightMapFilename;
    // Heightmap maximum height
    public float HeightScale;
    // Heightmap dimensions
    public int HeightMapWidth;
    public int HeightMapHeight;
    // terrain diffuse textures
    public string LayerMapFilename0;
    public string LayerMapFilename1;
    public string LayerMapFilename2;
    public string LayerMapFilename3;
    public string LayerMapFilename4;
    // Blend map which indicates which diffuse map is
    // applied to which portions of the terrain
    // null if the blendmap should be generated
    public string BlendMapFilename;
    // The distance between vertices in the generated mesh
    public float CellSpacing;
    public Material? Material;
    // Random heightmap parameters
    public float NoiseSize1;
    public float NoiseSize2;
    public float Persistence1;
    public float Persistence2;
    public int Octaves1;
    public int Octaves2;
    public int Seed;
}

Our GenerateRandomTerrain function is relatively straightforward. We generate two heightmaps using the supplied heightmap parameters, then multiply them together to get the final heightmap. The Cap function here subtracts its parameter from each heightmap entry, clamping the value above 0, and recalculates the MaxHeight of the resulting heightmap.

private void GenerateRandomTerrain() {
    var hm2 = new HeightMap(Info.HeightMapWidth, Info.HeightMapHeight, 2.0f);
    _heightMap.CreateRandomHeightMapParallel(Info.Seed, Info.NoiseSize1, Info.Persistence1, Info.Octaves1, true);
    hm2.CreateRandomHeightMapParallel(Info.Seed, Info.NoiseSize2, Info.Persistence2, Info.Octaves2, true);
    hm2.Cap(hm2.MaxHeight * 0.4f);
    _heightMap *= hm2;
}

Creating the Blendmap

When we are generating a random terrain, it makes sense to create a blend map that matches the elevations of the random heightmap.  Here, we will use a relatively simple algorithm that assigns the terrain diffuse texture based on the height value of the heightmap.  Remember that we store the influence of each texture to the final terrain color in a separate channel of the blend map.  I have added some noise to the elevation thresholds and channel values for each texture, which makes the transitions between textures a little more irregular and natural looking.  After we have computed the blend map according to the heightmap, we apply two passes of smoothing using a box filter; creating the blend map without smoothing results in a very unnatural blocky texturing, with abrupt transitions between textures.  Once we have smoothed the blendmap, we will create a Direct3D texture, which we then use to create the ShaderResourceView which we will upload to the GPU with our TerrainEffect.

private ShaderResourceView CreateBlendMap(HeightMap hm, Device device) {
            
    var colors = new List<Color4>();
    for (int y = 0; y < _heightMap.HeightMapHeight; y++) {
        for (int x = 0; x < _heightMap.HeightMapWidth; x++) {
            var elev = _heightMap[y, x];
            var color = new Color4(0);
            if (elev > hm.MaxHeight * (0.05f + MathF.Rand(-0.05f, 0.05f))) {
                // dark green grass texture
                color.Red = elev / (hm.MaxHeight) + MathF.Rand(-0.05f, 0.05f);
            }
            if (elev > hm.MaxHeight * (0.4f + MathF.Rand(-0.15f, 0.15f))) {
                // stone texture
                color.Green = elev / hm.MaxHeight + MathF.Rand(-0.05f, 0.05f);
            }
            if (elev > hm.MaxHeight * (0.75f + MathF.Rand(-0.1f, 0.1f))) {
                // snow texture
                color.Alpha = elev / hm.MaxHeight + MathF.Rand(-0.05f, 0.05f);
            }
            colors.Add(color);

        }
        D3DApp.GD3DApp.ProgressUpdate.Draw(0.95f + 0.05f * ((float)y / _heightMap.HeightMapHeight), "Generating blendmap");
    }
    SmoothBlendMap(hm, colors);
    SmoothBlendMap(hm, colors);
    var texDec = new Texture2DDescription {
        ArraySize = 1,
        BindFlags = BindFlags.ShaderResource,
        CpuAccessFlags = CpuAccessFlags.None,
        Format = Format.R32G32B32A32_Float,
        SampleDescription = new SampleDescription(1, 0),
        Height = _heightMap.HeightMapHeight,
        Width = _heightMap.HeightMapWidth,
        MipLevels = 1,
        OptionFlags = ResourceOptionFlags.None,
        Usage = ResourceUsage.Default
    };
    var blendTex = new Texture2D(
        device,
        texDec,
        new DataRectangle(
            _heightMap.HeightMapWidth * Marshal.SizeOf(typeof(Color4)),
            new DataStream(colors.ToArray(), false, false)
        )
    );
    var srvDesc = new ShaderResourceViewDescription {
        Format = texDec.Format,
        Dimension = ShaderResourceViewDimension.Texture2D,
        MostDetailedMip = 0,
        MipLevels = -1
    };

    var srv = new ShaderResourceView(device, blendTex, srvDesc);
            
    Util.ReleaseCom(ref blendTex);
    return srv;
}

private void SmoothBlendMap(HeightMap hm, List<Color4> colors) {
    for (int y = 0; y < _heightMap.HeightMapHeight; y++) {
        for (int x = 0; x < _heightMap.HeightMapWidth; x++) {
            var sum = colors[x + y * hm.HeightMapHeight];
            var num = 0;
            for (int y1 = y - 1; y1 < y + 2; y1++) {
                for (int x1 = x - 1; x1 < x + 1; x1++) {
                    if (hm.InBounds(y1, x1)) {
                        sum += colors[x1 + y1 * hm.HeightMapHeight];
                        num++;
                    }
                }
            }
            colors[x + y * hm.HeightMapHeight] = new Color4(sum.Alpha / num, sum.Red / num, sum.Green / num, sum.Blue / num);
        }
    }
}

Adding UI Elements to our Application Window

One of the advantages of building our D3DApp class using Windows Forms, which we have not taken advantage of until now, is that we can add normal WinForms UI elements to our application.  These may not be the prettiest, but they work seamlessly and require none of the additional work that would be required to implement our own UI controls.  You can see these controls added to our RandomTerrainDemo example application.  Since most of the control initialization is standard WinForms boilerplate, I will not reproduce it all here; I will demonstrate how we add the FlowLayoutPanel that houses our controls and the button which generates a new random terrain from the other parameter controls and leave the rest up to you to look over. 

In our application Init() function, after we have called the base D3DApp Init() function, we will add a new helper function, AddUIElements().  For convenience, we will stuff all of the Winforms boilerplate and event handlers for our UI controls in here.  Our first step is to create the UI elements, initializing any necessary layout and behavior properties.  Next, we will add our UI elements to our FlowLayoutPanel, relying on it to appropriately position its child controls.  Lastly, we add the FlowLayoutPanel to the Controls collection of our application Window.  Because we use the DockStyle.Top flag and AutoSize=true, our FlowLayout will extend across the top of our window, with its height calculated based on its child controls.

private void AddUIElements() {
    _panel = new FlowLayoutPanel {
        Dock = DockStyle.Top,
        AutoSize = true,
        FlowDirection = FlowDirection.LeftToRight
    };

    _generateButton = new Button {
        Text = "Generate Terrain",
        AutoSize = true
    };
    // create other controls...
    _panel.Controls.Add(_generateButton);
    // add other controls
    Window.Controls.Add(_panel);
}

The final piece of the puzzle is adding a click handler to our _generateButton to create the random terrain based on our input control values. To do this, we need to fill out an InitInfo structure, and then re-initialize the terrain with the new parameters.  As part of our UI, we have a PictureBox which displays the generated random heightmap as a gray-scale bitmap, which we will access through another new property on our Terrain class, HeightMapImg.

_generateButton.Click += (sender, args) => {
    Window.Cursor = Cursors.WaitCursor;
    Util.ReleaseCom(ref _terrain);
    _terrain = new Terrain();
    var tii = new InitInfo {
        HeightMapFilename = null,
        LayerMapFilename0 = "textures/grass.dds",
        LayerMapFilename1 = "textures/darkdirt.dds",
        LayerMapFilename2 = "textures/stone.dds",
        LayerMapFilename3 = "Textures/lightdirt.dds",
        LayerMapFilename4 = "textures/snow.dds",
        BlendMapFilename = null,
        HeightScale = 50.0f,
        HeightMapWidth = 2049,
        HeightMapHeight = 2049,
        CellSpacing = 0.5f,

        Seed = (int)_txtSeed.Value,
        NoiseSize1 = (float) _txtNoise1.Value,
        Persistence1 =(float) _txtPersistence1.Value,
        Octaves1 = (int) _txtOctaves1.Value,
        NoiseSize2 = (float) _txtNoise2.Value,
        Persistence2 = (float) _txtPersistence2.Value,
        Octaves2 = (int) _txtOctaves2.Value
    };
    _terrain.Init(Device, ImmediateContext, tii);
    _camera.Height = _terrain.Height;
    _hmImg.Image = _terrain.HeightMapImg;
    Window.Cursor = Cursors.Default;
};

Generating the Heightmap Image

The PictureBox control that we will use to display the heightmap in the UI cannot accept a DirectX texture as its image data.  Instead, we need to transform the heightmap data into a Windows Forms Bitmap, which the PictureBox can use.  We will create a helper function, called from our HeightMap.BuildHeightmapSRV() function to create this Bitmap.

private void BuildHeightMapThumb() {
    var userBuffer = _heightMap.Select(h => (byte)((h / MaxHeight) * 255)).ToArray();
    _bitmap = new Bitmap(HeightMapWidth - 1, HeightMapHeight - 1, PixelFormat.Format24bppRgb);
    var data = _bitmap.LockBits(
        new Rectangle(0, 0, _bitmap.Width, _bitmap.Height), 
        ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    var ptr = data.Scan0;
    var bytes = data.Stride * _bitmap.Height;
    var values = new byte[bytes];

    Marshal.Copy(ptr, values, 0, bytes);

    for (var i = 0; i < values.Length; i++) {
        values[i] = userBuffer[i / 3];
    }
    Marshal.Copy(values, 0, ptr, bytes);

    _bitmap.UnlockBits(data);
}

The first thing that we need to do is convert each heightmap value to a byte, by dividing the heightmap value by the MaxHeight property of the HeightMap, to scale the value into the [0,1] range, then multiplying by 255 to get the corresponding byte value.  Next, we create the Bitmap, using the full size dimensions of the HeightMap (be careful to avoid fence-post problem errors by subtracting one from the HeighMapWidth and HeightMapHeight), and a 24bpp image format without alpha.  We then lock the Bitmap, so that we can access the Bitmap’s pixel data, and marshal the pixel data into a managed array that we can update.  Each pixel in the Bitmap is then represented by three byte entries in the values array, so we loop over the pixel data and set each color channel of the pixel to the byte representation of the heightmap elevation data, which will result in the proper gray-scale image.  Finally, we marshal the modified pixel data back to the Bitmap’s data pointer, and unlock the Bitmap.

The Result

Running the RandomTerrainDemo application, you can experiment with different terrain creation parameters and see the terrains that result.  You should see that, for a given initial seed, you will generate terrains with the same basic topology.  Increasing or decreasing the NoiseSize parameters will alter the size of the generated terrain features, while modifying the persistence value will result in more or less hilly terrains.  Using more octaves will result in more fine details, though it will take longer to generate the terrain.  Five to nine octaves seems to give the best results, in my experience.

Next Time…

We will move on from terrain generation for a while, although I will probably circle back and add more features later.  There is a ton more we can do with random terrain generation; I have found some interesting articles on carving rivers, and I would like to look at some more interesting techniques for constructing the blend map, based on modeling weather and climate.  I will also want to circle back and add support for mouse picking to the terrain, for centering the camera or ordering units about on the terrain.  Pathfinding is also an entire other can of worms that we will want to integrate into our terrain, and eventually we will want to add some other details to our generated terrain, like tree models and billboards, or grass.  The possibilities are nearly endless…

But for now, we will move on to loading 3D models.  Previously, we have only supported loading models from a very simple, text-based model format.  Now, we will extend our code to support loading a plethora of commercial 3D formats, using the open-source Assimp model loading library.  As well as simple static meshes, we will also look at implementing a model class with support for skeletal animation.