Basis Functions

At the core of a noise algorithm is the basis function. It provides a mapping between the input vector and the output scalar. This mapping must be deterministic, but as with rand and friends, a 'seed' value may be supplied so we can vary the outputs when needed.

There are two major categories of noise function I see in popular use:

Each basis function comes with efficiency and quality tradeoffs.

Value Noise

The simplest method is to assign one random scalar to each integral coordinate (the red points). Any deterministic method can be used to generate these values.

Evaluation at the fractional coordinates (the blue point) is simple interpolation weighted by the distance to each lattice point.

constexpr float lerp (float a, float b, float t);

float
interpolate (const float values[2][2], vector2f frac)
{
    auto y0 = lerp (v[0][0], v[0][1], frac.x);
    auto y1 = lerp (v[1][0], v[1][1], frac.x);
    return lerp (y0, y1, frac.y);
}

Acquiring Randomness

A tried and true approach is to use a pre-populated array of `random' values with a known distribution and a second pertubation array of offsets. The low-order bits of the lattice coordinate is used to index into the pertubation array, which is used to index into the random values.

I utilise the integer mixing function of a keyed hash (Murmur2 in my implementation). Given a seed, and the lattice coordinates, I can divide the output by the maximum to get a uniform real.

Warning:

If using the mixing function approach pay particular attention to any emergence of directional artefacts arising from your choice and usage of mixing function.

Evaluation

Given that the source of randomness here is truely uniform there is a risk that the generated noise will not have the gradual transitions that coherent noise is known for.

However this approach has high performance, gives direct control over the value distributions, and can often be 'good enough' for many use-cases (especially when used as a basis for fractals).

Perlin Noise

Rather than assigning scalar values to lattice points Perlin noise assigns n-dimensional vectors (the red lines).

Evaluation for a coordinate is by computing the difference of the input coordinate and the lattice coordinate, then the dot-product of this difference with the lattice point’s vector. Interpolation of these values is performed as per value noise.

Randomness can be generated in much the same way as value noise. Simple extensions include: * listing n-d values in the value array * repeated perbutation indexing for each dimension * repeated integer mixing for each dimension

The algorithm gives a far more gradual change than value noise, at the cost of increased computational complexity.

The cost of scaling Perlin noise to higher dimensions becomes prohibitive quite rapidly, with complexity of O(pow(2,n)). Simplex noise was developed partially to counter this issue.

Worley/Voronoi Noise

Stepping away from lattice noise, Worley noise is derived from a distribution of points in n-dimensional space.

The value for each query is the distance from the query to the nearest point.

Interpolation

Value and Perlin noise make extensive use of interpolation across the pow(2,n) points.

Most commonly cubic and quintic polynomials are used (given their specification in the two Perlin papers).

Simple linear interpolation is sufficient for some purposes and gives some amount of evaluation speedup, but tends to display obvious axis aligned artefacts. The extreme of truncated 'interpolation' is all but useless because of it’s obvious grid structure.

Cosine interpolation allows a smooth transition and has interesting gradient properties, but can incur a far higher runtime cost.

While interpolation functions are an interesting (and excessive) parameter, they don’t appear to increase performance greatly, while potentially introducing significant grid artefacts.

Fractals

The basis functions above could be useful sucessfully by themselves for many simple operations, but their power is greatly increased by combining success evaluations as a fractal. The concept is to provide both high frequency (detail) and low frequency (structure) by summing successive iterations with increasing frequency and decreasing scaling.

I will also reference parameters named 'frequency' (the initial lacunarity) and 'amplitude' (the initial gain) for implementation flexibility.

float
fbm::eval (point2f p) const
{
    float total = 0;
    float scale = m_amplitude;

    p *= m_frequency;

    for (unsigned i = 0; i < m_octaves; ++i) {
        total += m_basis (p) * scale;

        p *= m_lacunarity;
        scale *= m_gain;
    }

    return total;
}

Evaluation

A well defined grid from the initial octave is quite obvious for the first 4 octaves. After which the higher frequency layers soften, but never quite eliminate, the grid artefacts.

This isn’t necessarily a negative for some applications, but can be exceedingly difficult to remove in post-processing.

The base layer is much smoother than value noise, and the structure does not alter significantly after perhaps 2 octaves. Indeed, Perline noise can appear quite homogenous when compared to value noise at similar scales.

Worley noise appears vastly different to other lattice noise.

Additional visual detail is greatly diminshed after 4 octaves. I tend to select at least 2 octaves less Worley noise than Value or Perlin.

Evaluating Worley noise can be quite expensive, depending on your implementation. Particularly if using higher arity variants (eg, f2-f1, f4).

Musgrave’s Models

There are a number of common fractal noise algorithms, specifically designed for terrain, written by Ken Musgrave.

Ridged Multifractal, Hybrid Multifractal, and Heterogenous terrain are the typical examples that can found scattered around the internet. These are all described in detail in the book `Texture and Modelling: A Procedural Approach'.

Turblence

Offset terbulence is a simple extension to any noise function where the queried position is randomly perturbed; commonly by a secondary coherent noise function.

float
turblence::eval (point2f p) const
{
    vector2f offset {
        m_perturb[0] (p),
        m_perturb[1] (p)
    };

    return m_data.eval (p + offset * m_scale);
}

The simplest method is to instantiate an additional basis function for each dimension and offset the query using these values.

Experimenting with parameters can prove interesting, with values well above 100% displaying an unexpected effect.

Postprocess

Coherent noise routines don’t stop here. Many applications, such as terrain generation, greatly benefit from post-processing.

Normalising the output to unit values can simplify display and further processing.

Conclusions

Implementing your own coherent noise routines can be an interesting exercise.

While it is as important as ever to carefully evaluate the problem you are attempting to solve, a simple Perlin FBM implementation will get you a long way.