GSoC Update: Understanding Simplex Noise

Before diving into the concept of Simplex Noise, we need to understand what noise is and what are the applications of it. Here I will be giving an overview about different type of noises and why and how they were developed.


Background

So it all started back in 1980s when Ken Perlin was working on the CGI for the animated movie Tron. The graphics were not realistic at that time and have a machine like appearance which made them look artificial. So Perlin developed a gradient noise which was pseudo random in nature to create natural looking textures. After that, people started using noise extensively all over the world.

Source: GPU Gems 2

The picture above is an example of procedural bump mapping using pseudo random noise. I have written pseudo random and not just random because we need to have a predictable texture, making it completely random might cause problems. For more noise related example, you can have a look at my previous blog.


About Perlin Noise

Perlin noise is a gradient noise, which means that we put pseudo random gradient points at fixed interval of time and then interpolate them into a smooth function as shown in the figure below. 

For 1D noise, we assign a gradient values to integer coordinates and then interpolate between the points keeping the value of function zero at coordinate points.

A gradient function in 1D

For 2D noise, the method is more or less similar. Here we have a two dimensional square grid and at any point on surface, the function value is calculated by taking contribution from the four corners of the grid cell. The value from each corner is extrapolation of the linear ramp with assigned gradient.

There are few disadvantages of using Perlin noise, First of all the complexity of the algorithm is O(N^2) and secondly there are directional artifacts which is not desirable. 


Terminologies used in Noise

Earlier we talked about different wave like functions that were created by interpolating gradient points. Now we have a understanding that noise is like a wave and in fact a fifth degree polynomial blending function is used by Perlin noise for interpolation. So noise is also represented with similar terminologies as that of a regular wave i.e. sine or cosine wave.

Amplitude: It's the difference between maximum and minimum value of the function.

Wavelength: It's the distance between two gradient points on the function.

Frequency: It is inverse of wavelength.

Octave: Just like musical octaves, each successive noise function have a frequency double than the previous one.

Persistence: For simplicity, we can think of it as a factor with value between 0 and 1. It is multiplied with amplitude in successive octaves.


Simplex Noise

In Simplex noise, we try to fill the space with simplices (geometrically compact shapes) having the minimum number of corners. For example, in one dimension we use straight line, in two dimension we use equilateral triangle( three corners), in three dimension we use tetrahedron(4 corners) and so on.

Here I am going to talk about its implementation in mainly 2D textures for generating heightmaps for terrains. So as I mentioned, for 2D space a simplex grid is made up of equilateral triangles.

A 2D Simplex Grid

So similar to Perlin Noise, the value on the surface is calculated by summation of contribution from each corner of simplex grid. Note that Perlin noise had four corners corresponding to a two dimensional grid, but here we have only three.

  The most important part of calculation of noise value at surface is to find the simplex in which we are currently present. In 2D grid we can skew the equilateral triangles to form a grid of right angled isosceles triangles such that two such triangles form a square with side of length one. 

Now by looking and comparing the values of the transformed coordinates (x,y) , we can easily find out about the position of the point in the grid.

Due to lesser computational complexity of O(N) and due to the ease of implementation, Simplex Noise is preferred over Perlin noise.

Adding octaves to the noise function

Multiple octaves of noise can be added by summing multiple passes of noise. The contribution of each succeeding octave is determined by the persistence. The larger the persistence, the more of each octave is included in the total.Here is an example where six octaves of noise is added up and the final result is shown.

Different Octaves of Noise

Final noise pattern after multiple passes of noise function

This might not be the best explanation of Simplex Noise but I have written it to make my own understanding clear about the noise algorithm. You can find a detailed and simplified explanation of Simplex Noise in the article by Stefan Gustavsan. Other references include Perlin Noise explanation by Hugo Elias and a talk by Ken Perlin himself.

Leave a comment if you find anything out of place.