How does actual Perlin noise work?

Disclaimer: The reply beneath describes Perlin-fashion gradient noise normally. Just like “It is not champagne until it is produced within the Champagne area of France”, one can argue it isn’t “Perlin” noise until it is utilizing Perlin’s actual unique implementation.

In apply, when recreation builders need “Perlin” noise, we really implement a associated gradient noise, adapting the core concepts to what’s quick and handy on fashionable CPUs/GPUs. I am going to name out a few of these implementation variances as we go alongside.

Firstly, what you are describing is 2D Noise (the inputs are x and y – a two-dimensional parameter area). The truth that you need to visualize the output on a 3rd axis does not make the noise itself three-dimensional. We would name a noise operate 3D if it took x, y, and z as inputs, and produced a fourth quantity as its output.

Second, the algorithm doesn’t “solid rays” from the corners of the grid. It chooses a pseudo-random gradient vector for every nook (every lattice level of the grid). This vector defines how the worth of the noise ought to change within the neighborhood of that nook – which xy path ought to slope “up” in worth.

On this diagram by Matthewslf from the Wikimedia Commonsyou possibly can see these gradients visualized as pink arrows radiating from every nook. The purple-to-green shaded sq. surrounding every nook exhibits how the noise worth varies in line with that nook’s gradient vector (ignoring the opposite corners for now). See how the shaded values are all the time zero (white line) the place they cross the nook, and get more and more constructive (inexperienced) within the path of the gradient arrow:

See Understanding the “gradient” in Perlin Noise for extra on this.

We are able to subtract the coordinates of our pattern level from the coordinates of the nook to get a neighborhood offset from that nook. The dot product of this native offset with the gradient chosen for that nook offers us the output worth in line with that nook.

// Integer x, y coordinate of the bottom-left nook 
// of the cell containing our pattern level.
int2 cell = int2(flooring(samplePosition.xy));

// Offset of the pattern place from this bottom-left nook
// (in vary 0 <= x < 1, 0 <= y < 1).
float2 fraction = frac(samplePosition.xy);

// Noise worth in line with every nook.
float bottomLeft  = dot(getGradient(cell.xy), fraction);
float bottomRight = dot(getGradient(cell.xy + float2(1, 0)), fraction - float2(1, 0));
float topLeft     = dot(getGradient(cell.xy + float2(0, 1)), fraction - float2(0, 1));
float topRight    = dot(getGradient(cell.xy + float2(1, 1)), fraction - float2(1, 1));

To make the noise mix easily between adjoining cells, we have to interpolate between these corners. For 2D noise, that might appear like this:

float2 weight = getInterpolationWeight(fraction);

float high    = lerp(   topLeft,    topRight, weight.x);
float backside = lerp(bottomLeft, bottomRight, weight.x);
float center = lerp(    backside,         high, weight.y);

return center; // Our last, blended noise worth.

We wish the interpolation weight for every nook to be 1 after we’re sampling on the nook itself, and 0 when sampling from the alternative facet of our grid cell. We additionally need the primary and second derivatives of this weight operate to be zero on the edges of every cell, to keep away from a noticeable “crease” or “kink” within the noise worth, the place the floor out of the blue adjustments path or curvature if we visualize it like a heightfield. There are lots of capabilities that may do that:

• Perlin’s unique proposal used a cubic Hermite curve (generally referred to as smoothstep):

  // Given an x, y offset inside a cell, within the vary 0-1 on every axis:
  float2 getCubicInterpolationWeight(float2 xy) {
      return xy * xy * (3.0f - 2.0f * xy);
  }
  

• Trendy implementations generally favor a quintic curve for a extra gradual mix alongside the cell borders, particularly if the cubic model results in artifacts within the given implementation.

  float2 getQuinticInterpolationWeight(float2 xy) {
      return xy * xy * xy * (xy * (xy * 6.0f - 15.0f) + 10.0f);
  }
  

You possibly can see an instance of utilizing these interpolation weights to linearly interpolate between 4 corners on this reply.

As for a way we choose the gradient vectors within the first place, that is additionally as much as the implementation. All that issues is that:

• The choice process takes two integers x and y as inputs and returns a 2D gradient vector.
• The gradient vectors are all of the similar size (conventionally, unit size, so no slope path is persistently steeper than others).
• The gradient vectors are uniformly distributed over the enter area (so there isn’t any bias towards a specific x/y path).
• The number of a gradient vector for a given nook is repeatable (each time you pattern the identical lattice level within the grid, you get the identical gradient for it).
• The number of gradient vectors is not clearly correlated between close by factors (so we do not see repeating patterns). In apply, there shall be some relationship between the factors, since we’re utilizing a pseudo-random algorithm, not a very random supply like cube or radioactive decay; we simply must make the algorithm jumble up the inputs sufficient to obfuscate that reality, so it isn’t visually distracting.

Perlin’s unique scheme used a permutation desk to digest the x and y coordinates of the nook right into a pseudo-random index to make use of in wanting up into an array of gradient vectors. This suited CPUs of the time, however these days (and particularly on GPUs), it typically makes extra sense to only calculate the vector with some math. You need to use any hash operate you want to rework the x and y coordinates of the nook into an index or parameter to search for or generate your gradient vector.

As an illustration, in 2D, we might use one thing like this:

float2 getGradient(int2 nook) {
    // Use any hash operate you want to show x and y coordinates into one quantity:
    float hashed = hash(nook.xy);

    // Return a unit vector, in a path chosen by treating this
    // hashed worth as an angle in radians.
    return float2(cos(hashed), sin(hashed));
}

Placing all of it collectively, you possibly can see (and play with) a pattern implementation in WebGL by Inigo Quilez, right here. His implementation makes use of the “Hugo Elias hash” like so:

float hash(int2 nook) {
   int n = nook.x + nook.y * 11111;

   n = (n << 13) ^ n;
   n = (n * (n * n * 15731 + 789221) + 1376312589) >> 16;

   return float(n);
}