Generic Bootstrap Blog

Over the past week or so I’ve been trying to implement a gradient noise function, a task that has been a particularly frustrating experience. There are many pages that describe Perlin noise and friends, but as someone with minimal formal training in mathematics I found most of them to be scarcely better than gibberish. I’m about to try to give the explanation I wish I had a week ago, but if you still don’t get it there will be some public domain code later on which you’re free to copy as desired.

Initially I was going to attempt an introduction to coherent and gradient noise so this page was as gentle as possible, but there’s plenty already out there on this topic and I’m unlikely to best any of them. Check out any of the following links if you need a refresher:

• http://libnoise.sourceforge.net/noisegen/index.html
• http://chaoscultgames.com/products/CN/CoherentNoiseManual.pdf
• https://en.wikipedia.org/wiki/Gradient_noise

Please note that my expertise in this field is non-existent. There seems to be a lot of confusion around what does and doesn’t qualify as Perlin noise, so whilst the algorithm I’ll describe borrows heavily from Ken Perlin’s writing I will be referring to it as “gradient noise” for the rest of this post.

Here’s the code, adapted from Ken Perlin’s implementation of Perlin noise in C:

// To the extent possible under law, the person who associated CC0 with this
// work has waived all copyright and related or neighboring rights to this work.
// http://creativecommons.org/publicdomain/zero/1.0/
class GradientNoise {
    const int N_GRADIENTS = 256;
    double[] gradients = new double[N_GRADIENTS];

    public double sample (double point) {
        var left_gradient_index = (int) point % N_GRADIENTS;
        var right_gradient_index = (left_gradient_index + 1) % N_GRADIENTS;

        var left_grad_offset = point - (int) point;
        var right_grad_offset = left_grad_offset - 1;

        var prod_left = left_grad_offset * gradients[left_gradient_index],
            prod_right = right_grad_offset * gradients[right_gradient_index];

        // S-curve weighting from revised Perlin noise
        var sx = 6 * Math.pow (left_grad_offset, 5)
            - 15 * Math.pow (left_grad_offset, 4)
            + 10 * Math.pow (left_grad_offset, 3);

        //      linear interpolation                       scale to range 0-1
        return (prod_left + sx * (prod_right - prod_left)) / 2 + 0.5;
    }

    public GradientNoise () {
        for (var i = 0; i < gradients.length; i++)
            gradients[i] = Random.double_range (-1, 1);
    }
}

In our GradientNoise class, we create an array of unit-length gradients. Each index in the array represents an integer point on our number line. The value of N_GRADIENTS was selected arbitrarily.

The sample() function is where the magic happens. Here’s the breakdown:

• left_gradient_index represents the integer point immediately left of point on our number line. We modulo against N_GRADIENTS so we don’t read past the end of our gradient array. Similarly, right_gradient_index represents the integer point immediately to the right of point.

• left_grad_offset is the distance between left_gradient_index and point, and is less than 1. right_grad_offset is the same, except this value is negative; we do this so that multiplying by a negative gradient (ie, a gradient sloping towards point) yields a positive value.
  These variables are called ‘offset’ instead of ‘distance’ because the right offset doesn’t strictly refer to a distance as a distance cannot be negative, whereas I thought they could conceptually be considered as an offset from point (albeit a backwards one).

• prod_left and prod_right determine how much influence the two gradients either side of point have on our final value. The prod suffix is short for ‘product’, as in the dot product of our one-length vectors.

• Our final result will be a weighted average: we’ll be averaging the numbers prod_left and prod_right, weighted by point‘s position between our two gradients (ie left_grad_offset). We won’t be using left_grad_offset directly, however; if we did, we wouldn’t get the nice roll-off between points we’re after. Instead, we’ll smooth it using the S-curve presented in Ken Perlin’s paper on updated Perlin noise:

$$6t^5 - 15t^4 + 10t^3$$

• Finally, we perform the weighted average via linear interpolation. Our result will be between -1 and 1, so we also divide by 2 and add \(1/2\) to get a value between 0 and 1.

And that’s it! I’m a long way from able to give any guarantees with respect to desirable properties, so be warned that this variant may well be both slower and poorer in its output. All I can say is that it looks like continuous noise, and that’ll do for me.

Please feel free to leave a comment noting corrections, suggestions, thoughts. Thanks for reading!