Click here to Skip to main content
Click here to Skip to main content

A generic lattice noise algorithm, an evolution of Perlin noise.

, 20 Nov 2014 MIT
Rate this:
Please Sign up or sign in to vote.
Development of a new generic lattice noise algorithm that advances beyond perlin noise and expands the possibilities of textural noise creation.

Introduction

Perlin noise is right now the most important algorithm when it comes to textural noise generation. It has been for more than 20 years. Newer and better algorithms have been designed since then, but they can't beat the high ratio quality vs performance that perlin noise offers.

This article will develop a generic noise algorithm for which perlin noise remains as a particular case, but what radically expands the variety of procedural noises that can be created. Here are some examples.

 

Source code from a small app that uses the algorithm to create textures is supplied at the top of the article. Be aware that the code as it's written is intended to be easy to adapt and modify, not to be performance optimized. There's a huge margin to improve performance (for example, generation times around 50-500 ms for a 2048x2048 array in a middle range laptop are not difficult to obtain).

 

Lattice noise overview

Lattice noises are a type of algorithm intended to procedural noise generation. The common element in lattice noises is a lattice or grid which subdivides the area in smaller sections (usually squares, though not necessarily). The algorithm travels the grid generating the noise function inside each square. This noise usually looks "blurry", so the process is repeated several times using smaller grids that layer over the previous ones in order to improve to improve the definition. Each layer has a narrow-band frequency range proportional to the size of the square. As we add new smaller grid layers, we increase the high frequencies in the noise, improving its definition.

Each of those layers is going to be called an «octave».

The main (and almost the only) commonly used lattice noise algorithms are the perlin noise one and its derivatives (as the simplex algorithm).

Generating the noise function inside a grid square

Let's consider an individual square inside the grid whose size is λ. Traditional perlin noise function is generated interpolating a gradient field inside the square. The noise value of each point inside the cell in a point defined by (u,v) will be interpolated using the values of the gradient au+bv where (a,b) corresponds to the values of the gradient field in every corner of the cell.

This is how traditionally perlin noise is defined. Now, let's change the approach.

Without changing the underlying logic algorithm, we are going to try a different point of view in order to make the algorithm easier to understand.

Instead of considering that the noise function is interpolated inside each cell, let’s consider that the noise function is determined in the neighborhood of each grid point by a function defined in this point. From a mathematical point of view, we will define the noise function in the neighborhood of a point (xi, yi) as the product of two different functions: a proximity function that depends on the field values fk(xi, yi) and a fade function that will fade to zero as we walk away from the point (xi, yi).

n(xi+u,yi+v) = fprox(u, v, λ, fk(xi, yi)) * ffade(u, v, λ)

This will be easily understood with an example: let’s define fprox as a constant value defined by a PRN (pseudo-random number) calculated using (xi, yi) (this can be easily done using a pseudo-random hash function or a white noise).

As a fade function let’s use the following one, for example:

fhermite(uλ, vλ) = (1 – 3uλ2 + 2uλ3) (1 – 3vλ2 + 2vλ3)

where uλ = u / λ, and vλ = v / λ. This function is the classic cubic Hermite interpolation function.

What we obtain multiplying those two functions is the following outcome.

The top of the “hill” corresponds to the grid point (xi, yi), which fades off and reach zero at the near grid points. This function will be added in the nearby of every grid point, creating a smooth noise function like the following one (be aware the gridded texture in the image is just a reference to better visualize the shape, it has no relation with the grid points).

Now we can add a second octave with a half-size grid. This is what we obtain.

We can keep adding more and more octaves with smaller and smaller sizes. That would be the final result.

What we have obtained, indeed, is a procedurally generated noise scalar function (which we can represent as a texture or as a landscape or in any other way) which, for those particular functions, corresponds with a lattice noise algorithm called Midpoint Displacement. The original Midpoint Displacement algorithm uses linear interpolation, but the final result, after the smaller octave possible has been added, would be the same.

Now let’s imagine we use as proximity function the following one:

fprox(u, v) = fa(xi, yi) * u + fb(xi, yi) * v

Does that sound familiar? On the one hand, that seems similar to one Perlin noise step (which is not casual). On the other hand, that will remind you to the Taylor series. Indeed, we could consider the previous proximity function as a zero order term in a 2-dimensional Taylor series, as much as this one could be considered the first order term.

Multiplying it by the fade function (the same one as before) this is what we obtain.

Notice that the center, which corresponds to the grid point (xi, yi), has z=0. What we are doing here is creating a plain “slope” in the grid point that smoothly fades off  as we reach the adjacent grid points. If we repeat it all along the grid this is what we obtain.

After several octaves: