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

• Download source - 7.2 MB
• Download executable - 2 MB

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 (x_i, y_i) as the product of two different functions: a proximity function that depends on the field values f_k(x_i, y_i) and a fade function that will fade to zero as we walk away from the point (x_i, y_i).

n(x_i+u,y_i+v) = f_prox(u, v, λ, f_k(x_i, y_i)) * f_fade(u, v, λ)

This will be easily understood with an example: let’s define f_prox as a constant value defined by a PRN (pseudo-random number) calculated using (x_i, y_i) (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:

f_hermite(u_λ, v_λ) = (1 – 3u_λ² + 2u_λ³) (1 – 3v_λ² + 2v_λ³)

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 (x_i, y_i), 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:

f_prox(u, v) = f_a(x_i, y_i) * u + f_b(x_i, y_i) * 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 (x_i, y_i), 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:

This is the same result that we could obtain using the Perlin noise algorithm. The difference is that here we are not bound by a specific function: if we use a different proximity function, we will obtain a different type of texture.

Indeed, you can see a texture at the left side of the image obtained applying the previous perlin noise-like function. The ones at the right were obtained using different functions.

 

 

Code overview

The source code in this article is a procedural texture generator, with the following files.

- MainWindow.xaml. WPF interface.

- MainWindow.xaml.cs. Main app. Code is quite straight-forward and algorithm code can be found here. The method Redraw( ) executes the procedural texture algorithm. This texture is stored in the jagged array heightmap[ ][ ] (the algorithm was developed to create landscapes, that is another use of lattice noises). The method SetPicture( ) transforms this jagged array in a graphical image using the supplied contrast and luminance values. The method CreatePictureTransparent( ) is only used in case the image is exported and you choose to export a semi-transparent one.

- ProximityFunctions.cs. It contains the proximity function delegates.

- FadeFunctions.cs. It contains the fade function delegates.

- PseudoRandom.cs. PRN generator. The static method float HashRandom(float x, float y, int index) gives a hash based pseudo-random number ranging from -1 to +1. It means that every (x, y) defines a float number. It can be considered random since there's no spatial continuity. Basically, it's a white noise-like function. The integer index allows to choose a different PRN function, it ranges from 0 to 4. To re-initiate the PRN use the method Initiate(int seed).

- Auxiliary.cs. Auxiliary class. It provides some methods to deal with jagged arrays and to load a System.Drawing.Bitmap class into a BitmapSource (which is needed in WPF).

Code details

Proximity Function and Fade Function delegates

Those two delegates are the heart of the algorithm. Changing them will lead to obtain different types of textures. For example: using the TriangularEdgeII delegate won't create a smooth surface as the ones seen before, but this kind of surface:

This other one was created using the Curvature rigged delegate:

And this one was created using the Semirigged gradient one:

The source code provides a nice number of delegates to play with, but they are not the only ones. You can use whatever function you want to try. It's just a matter of creativity.

Both delegates are defined in MainWindow.xaml.cs.

public delegate float FadeFunction(float x, float y);
FadeFunction Fade;
public delegate float ProximityFunction(float x, float y, float lambda, float xHash, float yHash);
ProximityFunction Proximity;

And instantiated in the Redraw( ) method.

FadeFunction Fade = FadeF();
ProximityFunction Proximity = ProximityF();

FadeF( ) and ProximityF( ) functions give back the right delegate according to what you have chosen in the WPF interface.

The Proximity Function delegate

As an example, let's examine the gradient delegate, which would represent the traditional perlin noise.

public static float Gradient(float x, float y, float lambda, float xHash, float yHash)
{
    return (x * PseudoRandom.HashRandom(xHash, yHash, 0) + y * PseudoRandom.HashRandom(xHash, yHash, 1)) / (lambda);
}

This delegate creates a functions in the neighborhood of the point (x_i, y_i). The variables represent:

- x and y. Relative coordinates of the point calculated, considering (x_i, y_i) as the origin of coordinates.

- lambda. Grid square size.

- xHash and yHash. (x_i, y_i) absolute coordinates values.

The delegate gives back a linear function ax + by where a and b are two random values (ranging from -1 to 1) depending on the values (x_i, y_i). The code gets those two values through PseudoRandom.HashRandom(xHash, yHash, 0) and PseudoRandom.HashRandom(xHash, yHash, 1)

The Fade Function Delegate

Fade functions is intended to multiply the proximity function so it makes it "fade off" as we walk away from the grid point. Basically is a continuous function that should value 1 in the origin of coordinates and zero for any value (x,y) where | x | ≥ 1 or | y | ≥ 1.

As an example, let's consider the Hermite Cubic one:

public static float Hermite(float x, float y)
{
    return (1 - (x * x * (3 - 2 * x))) * (1 - (y * y * (3 - 2 * y)));
}

This function returns 1 when (x,y) = (0,0) and returns zero when x ≥ 1 or y ≥ 1 (the function takes zero value when x or y reach 1. It doesn't return zero beyond that, but it won't be calculated beyond those points, so that won't be a concern). Besides that, first derivatives are null both in origin and in x = 1 or y = 1. Second derivatives are not null in those points. Hermite Quintic fits this last condition (what makes it slightly smoother).

The algorithm itself

This is the algorithm.

size = PictureSize();
int numberOfOctaves = Octaves();
int initialStep = InitialStep();
FadeFunction Fade = FadeF();
ProximityFunction Proximity = ProximityF();
PseudoRandom.SetCSharpRandomClasUsed(IsCSRandomUsed());
PseudoRandom.SetScale(1024f / size);

for (int x = 0; x < size + 1; x += 1)
{
    for (int y = 0; y < size + 1; y += 1)
    {
        heightmap[x][y] = 0.5f;
    }
}

for (int octave = 0; octave < numberOfOctaves; octave++)
{
    int sizeGrid;
    float sizeGridF;
    sizeGrid = initialStep / (int)Math.Pow(2.0, octave);
    int init = 0;
    if (rb_G01.IsChecked == true) { init = 0; }
    if (rb_G02.IsChecked == true) { init = - sizeGrid / 2; }
    if (rb_G03.IsChecked == true) { init = - sizeGrid / 4; }

    sizeGridF = (float)sizeGrid;
    float relativeSize = sizeGridF / size;
    float persistence = (float)Math.Pow(relativeSize, 1.0 - Persistence_slider.Value);

    int gridU, gridV;
    float hBase;                          

    if (sizeGrid >= 1)
    {
        for (int x = init; x < size + 1; x += sizeGrid)
        {
            if (x == size - sizeGrid) { gridU = sizeGrid + 1; } else { gridU = sizeGrid; }
            for (int y = init; y < size + 1; y += sizeGrid)
            {
                if (y == size - sizeGrid) { gridV = sizeGrid + 1; } else { gridV = sizeGrid; }

                for (float u = 0; u < gridU; u++)
                {
                    for (float v = 0; v < gridV; v++)
                    {
                        if ((x + (int)u > size - 1 || x + (int)u < 0 || y + (int)v > size -1 || y + (int)v < 0) == false)
                        {
                            float us = u / sizeGridF;
                            float vs = v / sizeGridF;
                            hBase =
                                        Proximity(u, v, sizeGridF, (float)x, (float)y)
                                        * Fade(us, vs)

                                        + Proximity(u - sizeGridF, v, sizeGridF, (float)x + sizeGridF, (float)y)
                                        * Fade(1 - us, vs)

                                        + Proximity(u, v - sizeGridF, sizeGridF, (float)x, (float)y + sizeGridF)
                                        * Fade(us, 1 - vs)

                                        + Proximity(u - sizeGridF, v - sizeGridF, sizeGridF, (float)x + sizeGridF, (float)y + sizeGridF)
                                        * Fade(1 - us, 1 - vs);

                            heightmap[x + (int)u][y + (int)v] += hBase * persistence;
                        }
                    }
                }
            }
        }
    }
}

 

Let's split and go step by step.

size = PictureSize();

This is the texture size. PictureSize( ) just returns the chosen size in the WPF interface. It's recommended to use a power of two number as size. 512, 1024, 2048 or 4096 are good values.

int numberOfOctaves = Octaves();
int initialStep = InitialStep();

More values chosen in the WPF interface. numberOfOctaves controls how many times the whole algorithm is repeated (each cycle being called an "octave"). initialStep is the initial λ, the initial grid square size. For example, if the whole array is 1024 x 1024, this initial value could be 1024, 512, 256, 128 and so on. Change the "initial octave size" option in the app to see the effect.

FadeFunction Fade = FadeF();
ProximityFunction Proximity = ProximityF();

Here are the delegates that we discussed previously.

PseudoRandom.SetCSharpRandomClasUsed(IsCSRandomUsed());

This allows you to use a secondary PRN generator is set to false. Not used by now.

PseudoRandom.SetScale(1024f / size);

This adapt the scale of the hash PRN function. Otherwise, changing the picture size would lead to a different texture (which wouldn't be a good outcome, if you change the size, you'd rather want the same texture with a higher definition, not a new different one).

for (int x = 0; x < size + 1; x += 1)
{
    for (int y = 0; y < size + 1; y += 1)
    {
        heightmap[x][y] = 0.5f;
    }
}

heightmap[ ][ ] is intended to range from 0 to 1 (intended, but not limited to this range). This loops initializes the array in the middle point of this range.

for (int octave = 0; octave < numberOfOctaves; octave++)
{
    int sizeGrid;
    float sizeGridF;
    sizeGrid = initialStep / (int)Math.Pow(2.0, octave);

sizeGrid is the grid square size. Each octave, we'll use a size half the size of the previous one.

int init = 0;
if (rb_G01.IsChecked == true) { init = 0; }
if (rb_G02.IsChecked == true) { init = - sizeGrid / 2; }
if (rb_G03.IsChecked == true) { init = - sizeGrid / 4; }

This establishes the entry point for the array. This is small tweak whose effect you can see in the interface under 'Grid Displacement'. Dismiss it in a first look, it's just a tweak, not really necessary. You can consider init = 0.

sizeGridF = (float)sizeGrid;
float relativeSize = sizeGridF / size;
float persistence = (float)Math.Pow(relativeSize, 1.0 - Persistence_slider.Value);

persistence represents the amplitude of an octave. Higher frequencies need smaller amplitudes in order not to create a chaotic noise. relativeSize is the relation between the grid square size and the whole array size. Using this vale and the slider value we can calculate the persistence value for each octave. Notice that when the slider takes the value zero, the persistence will be directly proportional to the relativeSize value.

int gridU, gridV;
float hBase;

A couple of local values.

if (sizeGrid >= 1)
  {

This avoids the octave to be calculate when the grid square falls under 1 (that would make no sense).

for (int x = init; x < size + 1; x += sizeGrid)
{
    if (x == size - sizeGrid) { gridU = sizeGrid + 1; } else { gridU = sizeGrid; }
    for (int y = init; y < size + 1; y += sizeGrid)
    {
        if (y == size - sizeGrid) { gridV = sizeGrid + 1; } else { gridV = sizeGrid; }

And here we start to travel the grid points in the array. Notice how we step using sizeGrid value: we're moving from grid point to grid point.

Be aware of gridU and gridV. They are intended to allow the right and the bottom boundary of the array to be calculated, since there's not going to be another square beyond it to do so.

for (float u = 0; u < gridU; u++)
{
    for (float v = 0; v < gridV; v++)
    {

Those loops travels the points inside a grid square.

if ((x + (int)u > size - 1 || x + (int)u < 0 || y + (int)v > size -1 || y + (int)v < 0) == false)
{

This condition is related to the init variable and the commented 'Grid Displacement' options. Dismiss it since it's just a tweak and it's not important for the algorithm. In case init = 0, this conditional is not needed and could be deleted.

float us = u / sizeGridF;
float vs = v / sizeGridF;

Relative values. us and vs range from 0 to 1.

hBase =
            Proximity(u, v, sizeGridF, (float)x, (float)y)
            * Fade(us, vs)

            + Proximity(u - sizeGridF, v, sizeGridF, (float)x + sizeGridF, (float)y)
            * Fade(1 - us, vs)

            + Proximity(u, v - sizeGridF, sizeGridF, (float)x, (float)y + sizeGridF)
            * Fade(us, 1 - vs)

            + Proximity(u - sizeGridF, v - sizeGridF, sizeGridF, (float)x + sizeGridF, (float)y + sizeGridF)
            * Fade(1 - us, 1 - vs);

In each point, hBase is calculated adding the values of Proximity( ) * Fade( ) for each and every one of the four corners of the square.

                            heightmap[x + (int)u][y + (int)v] += hBase * persistence;
                        }
                    }
                }
            }
        }
    }
}

And finally the value of hBase is multiplied by the persistence before adding it to the heightmap[ ][ ] array.

Final thoughts

In my opinion, lattice noise algorithms still have many possibilities ahead. I hope this helps to open even more those possibilities.

This is my first article in CodeProject. Any tip, correction or suggestion will be welcome.

 

Update

License has been changed from Codeproject Open License to MIT License, in order to allow the code to be used in Blender and fit the Blender license requirements.