Procedural generation: Perlin noise

84

Read previous parts:

Next part:

First thing which comes to mind to most of those who aren't familiar with underlying math of Perlin noise is something like this:

Fractal noise

The curious thing is that this is NOT a Perlin noise. This is fractal noise applied to the Perlin noise. We will talk about fractal noise in the next article, but now let's see what's Perlin noise really is.

Many articles on Perlin noise are overwhelmed with math details and look too verbose. I love math, however I believe that the best way to teach a software depeloper something new lies through demonstation of ideas and principles, but not through the diving into the ocean of math formulas and equations. So I'll try to do my best to keep things short and simple.

Perlin noise in a nutshell

A short 1D introduction. Assume we have XY axes. Let's put random numbers on X axis at integer coordinates. Let those numbers be from (-1; 1) interval. Also assume those numbers are values of tangent of an angle. (-1; 1) interval of tangent values mean (-45°, 45°) interval of angles. In other words, we have a 1D regular grid of random tangents:

Tangents

Now having these tangent values assume we found some algorithm that gives us a nice and smooth function which equals to zero at integer values of X axis and has the same tangent angle (or a value of the derivative of this function) as our random numbers:

Tangents and curve

This function is Perlin noise, so simple! The big part of the subject is how do you build such a function so it could match all of the requirements. However this part is implementation details which you can dive into if you're obsessed with math or you could just omit them and find some ready-to-use solution if you just need a code that works.

Simplest algorithm

Anyway, let's review at least one (and the simplest) possible solution. So, we have tangent values in the grid nodes and we need a smooth function which has no breaks and its derivative also doesn't break.

Let's start from a single line which goes through the point \(x_n = n\). The equation of this line is:

$$y_n(x) = k_n (x - x_n),$$

where \(k_n\) is tangent value at the point \(x_n\).

We can build a function as a chain of segments which are described by the corresponding line equation above. This function will go through zeros at integer X and have proper tangent values. However a derivative of such function won't be smooth.

To make it smooth we'll try to interpolate line equation between two neighbor points:

$$f_n(x) = \operatorname{lerp}(y_n(n), y_{n+1}(x), x - x_n),$$

where lerp is a linear interpolation:

$$\operatorname{lerp}(a, b, t) = a(1 - t) + b t$$

So at \(x = x_n\) it's equal to \(y_n\) and then it flows to \(y_{n+1}\) when \(x\) approaches to \(x_{n+1}\). However there is a surprise: such linear interpolation will give you correct function values, but incorrect tangent values (in general):

$$ \left\{ \begin{array}{l} f_n(x_n) = y_n \\ f_{n+1}(x_{n+1}) = y_{n+1} \end{array} \right. $$

however in general

$$ \left\{ \begin{array}{l} f_n'(x_n) \ne y_n \\ f_{n+1}'(x_{n+1}) \ne y_{n+1} \end{array} \right. $$

Assume \(k_0 = 1\) and \(k_1 = -1\). Interpolating between them linearly we'll see this:

Lerp

Correct values, incorrect tangents. To fix that we need to do the last step. We'll interpolate line functions with smoothstep function in combination with lerp:

$$f_n(x) = \operatorname{lerp}(y_n(x), y_{n+1}(x), \operatorname{smoothstep}(x - x_n)),$$

where

$$\operatorname{smoothstep}(t) = t^2(3 - 2t)$$

Now, putting all together, we'll see this:

Smoothstep

Now both function values and tangent values are correct.

So, once again, what did we do. We created a regular 1D grid and filled it with random numbers from (-1; 1) interval. We assumed that those numbers are tangent values of some function which should go through zeros at grid nodes and have derivatives equal to those random numbers. We demanded that both function and its derivative should be smooth. We found a simple algorithm how to build such a function. This function is 1D Perlin noise.

Perlin noise for 2D grid

The basic idea for two dimensions is the same:

  1. Create 2D grid;
  2. Generate random values for grid nodes;
  3. Build a function which interpolates values between grid nodes.

The main difference for 2D case is that random values aren't tangents but random unit vectors:

Unit vectors

So, we need to build a 2D function which returns Perlin noise value for a given pair of coordinates. As always, for integer coordinates (i.e. at grid nodes) this function should return zero. For other coordinates it should do some interpolation.

Let's take a point somewhere between grid nodes and draw vectors from nearby grid nodes to this point:

2D point

What we need to interpolate this time are dot products of node's random vector (green ones) and its corresponding vector that points to the target point (blue ones).

How do we interpolate values in 2D? In tree steps:

  1. Interpolate between dot products 1 and 2 by x;
  2. Interpolate between dot products 3 and 4 by x;
  3. Interpolate between two previous steps by y.

Let's take a source code from the previous article and continue our work there. First, we'll need math functions:

// Dot product of vectors
function dot(a, b)
{
    return a.x * b.x + a.y * b.y;
}

// Linear interpolation between a and b
function lerp(a, b, t)
{
    return a + (b - a) * t;
}

// Smoothstep value
function smoothstep(t)
{
    return t * t * (3 - 2 * t);
}

// Random unit vector generator
function unitVector()
{
    const phi = 2 * Math.PI * Math.random();
    return {x : Math.cos(phi), y : Math.sin(phi)};
}

Second — let's implement Perlin noise generator class. It looks almost like Grid class. However it stores random unit vectors, not scalar values.

class Perlin
{
    // Scale is a distance between grid nodes
    constructor(width, height, scale)
    {
        this.scale = scale;
        this.resize(width, height);
    }

    // Array index of unit vector at (x, y) integer coordinates
    indexOf(x, y)
    {
        x = x >= 0 ? (x % this.width) : (this.width + (x % this.width));
        y = y >= 0 ? (y % this.height) : (this.height + (y % this.height));
        return y * this.width + x;
    }

    // Unit vector at (x, y) integer coordinates
    value(x, y)
    {
        return this.values[this.indexOf(x, y)];
    }

    // Perlin noise value at (x, y) real coordinates
    get(x, y)
    {
        // Rescale x and y according to the grid scale
        x /= this.scale;
        y /= this.scale;

        // Integer coordinates of the requested point
        const floor = {x : Math.floor(x), y : Math.floor(y)};

        // Unit vectors of the nearest grid nodes
        const v1 = this.value(floor.x,     floor.y);
        const v2 = this.value(floor.x + 1, floor.y);
        const v3 = this.value(floor.x,     floor.y + 1);
        const v4 = this.value(floor.x + 1, floor.y + 1);

        // Local coordinates of the requested point
        const local = {x : x - floor.x, y : y - floor.y};

        // Vectors that point to the requested point
        const p1 = {x : local.x,     y : local.y};
        const p2 = {x : local.x - 1, y : local.y};
        const p3 = {x : local.x,     y : local.y - 1};
        const p4 = {x : local.x - 1, y : local.y - 1};

        // Dot products of grid unit vectors and pointing vectors
        const d1 = dot(v1, p1);
        const d2 = dot(v2, p2);
        const d3 = dot(v3, p3);
        const d4 = dot(v4, p4);

        // Interpolate between dot products 1 and 2 by smoothstep(x)
        const ix1 = lerp(d1, d2, smoothstep(local.x));

        // Interpolate between dot products 3 and 4 by smoothstep(x)
        const ix2 = lerp(d3, d4, smoothstep(local.x));

        // Interpolate between two previous results by smoothstep(y)
        return lerp(ix1, ix2, smoothstep(local.y));
    }

    // Resize the grid and fill it with random unit vectors
    resize(width, height)
    {
        this.width = width;
        this.height = height;
        this.values = new Array(width * height);

        for(let n = 0; n < this.values.length; ++n)
        {
            this.values[n] = unitVector();
        }
    }
}

And the third — our Grid class needs additional member function generate which we will use to fill the grid with values provided by the given generator:

generate(generator)
{
    for(let y = 0; y < this.height; ++y)
    {
        for(let x = 0; x < this.width; ++x)
        {
            this.values[this.indexOf(x, y)] = generator.get(x, y);
        }
    }
}

Now let's update our HTML page:

<!DOCTYPE html>
<html>
    <head>
        <link rel="stylesheet" type="text/css" href="style.css" />
    </head>
    <body>
        <canvas id="canvas" width="1200" height="800"></canvas>
        <script src="math.js"></script>
        <script src="grid.js"></script>
        <script src="perlin.js"></script>
        <script>
            const grid = new Grid(1200, 800);
            const perlin = new Perlin(48, 32, 25);
            grid.generate(perlin);
            grid.normalize();
            grid.draw(document.getElementById("canvas"));
        </script>
    </body>
</html>

And see the results. Green for positive values, red for negative ones:

Perlin noise colored

Yep, that's Perlin noise. We could remap noise values to monochrome colors and see a more familiar visualization:

Perlin noise monochrome

Looking at the monochrome visualisation you may notice that the noise isn't really smooth, a tiny artifacts are noticeable. To fix that we can use a quintic function instead of smoothstep. More about Quintic function on Wikipedia.

function quintic(t)
{
    return t * t * t * (t * (t * 6 - 15) + 10);
}

Perlin noise quintic interpolation

Ah, much better!

So a Perlin noise function consists of a regular grid filled with random unit vectors and a function which calculates dot products and interpolate the results. Just like that.

Full source code for this article: source.zip. Unzip the archive and open page.html in your web browser.

Read previous parts:

Next part:

Share this page: