Perlin noise

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Two-dimensional slice through 3D Perlin noise.
10 octave Perlin noise

Problems playing this file? See media help.

Perlin noise, a type of Gradient noise, was developed by Ken Perlin in 1983 as a result of his frustration with the machine-like look of computer graphics at the time. [1] In 1997, Ken Perlin was awarded an Academy Award for Technical Achievement for discovering the algorithm, the award: [2]

To Ken Perlin for the development of Perlin Noise, a technique used to produce natural appearing textures on computer generated surfaces for motion picture visual effects. The development of Perlin Noise has allowed computer graphics artists to better represent the complexity of natural phenomena in visual effects for the motion picture industry.

Ken Perlin didn't patent the algorithm, however in 2001 he was granted the patent for simplex noise, which is similar but uses a simpler space-filling grid, alleviating some problems with Perlin's "classic noise", among them, computational complexity. [3]

Uses[edit]

Perlin noise rescaled and added into itself to create fractal noise.

Perlin noise is a procedural texture primitive, a type of gradient noise used by visual effects artists to increase the appearance of realism in computer graphics. The function has a pseudo-random appearance, yet all of its visual details are the same size (see image). This property allows it to be readily controllable; multiple scaled copies of Perlin noise can be inserted into mathematical expressions to create a great variety of procedural textures. Synthetic textures using Perlin noise are often used in CGI to make computer-generated visual elements – such as fire, smoke, or clouds – appear more natural, by imitating the controlled random appearance of textures of nature.

It is also frequently used to generate textures when memory is extremely limited, such as in demos, and is increasingly finding use in graphics processing units for real-time graphics in computer games.

Development[edit]

Perlin noise resulted from the work of Ken Perlin, who developed it at Mathematical Applications Group, Inc. (MAGI) for Disney's computer animated sci-fi motion picture Tron (1982). In 1997, he won an Academy Award for Technical Achievement from the Academy of Motion Picture Arts and Sciences for this contribution to CGI.[4]

Algorithm detail[edit]

Perlin noise is most commonly implemented as a two-, three- or four-dimensional function, but can be defined for any number of dimensions. An implementation typically involves three steps: grid definition, computation of the dot product between the distance-gradient vectors and interpolation between these values.

Grid definition[edit]

Define an n-dimensional grid. At each grid coordinate assign a gradient vector of unit length in n dimensions. For a one-dimensional grid each coordinate will be assigned either +1 or -1, for a two-dimensional grid each coordinate will be assigned a random vector on the unit circle, and so forth for higher dimensions.

Computation of the random gradients in one and two dimensions is trivial. For higher dimensions a Monte Carlo approach is proposed in [1] where random Cartesian coordinates are chosen in a unit cube, points falling outside the unit sphere are discarded. The process is continued until the required number of random gradients are obtained. Acquired gradient are then renormalized.

In order to negate the expensive process of computing new gradients for each grid coordinate, some implementations use a hash and lookup table for a finite number of precomputed gradient vectors. [5] The use of a hash also permits the inclusion of a random seed where multiple instances of Perlin noise are required.

Dot product[edit]

The second step in the algorithm is to determine which grid cell a particular point falls. For each grid node/coordinate a distance vector between the particular point and the node coordinate is determined. The dot product between the gradient vector and the distance vector is then computed for each node.

For a point in a two-dimensional grid, this will require the computation of 4 dot products and in three-dimensions 8 dot products. This leads to the O(2^n) complexity scaling.

Interpolation[edit]

The final step is interpolation between the dot product values computed at each node. Interpolation is preformed using a function that has zero first derivative (and possibly also second derivative) at both endpoints.[hmm..., reference?] A linear function, for endpoints at 0 and 1 with values a0 and a1, would be: [5]

f(x) = a_0 (1 - x) + a_1 x

Noise functions for use in computer graphics typically produce values in the range [-1.0,1.0]. In order to produce Perlin noise in this range, the interpolated value may need to be scaled by some scaling factor. [5]

Pseudocode[edit]

The following is pseudocode for a two-dimensional implementation of Classical Perlin Noise.

 // Function to linearly interpolate between a0 and a1
 // Weight w should be in the range [0.0, 1.0]
 function lerp(float a0, float a1, float w) {
     return (1.0 - w)*a0 + w*a1;
 }
 
 // Computes the dot product of the distance and gradient vectors.
 function dotGridGradient(int ix, int iy, float x, float y) {
 
     // Precomputed (or otherwise) gradient vectors at each grid point X,Y
     extern float Gradient[Y][X][2];
 
     // Compute the distance vector
     float dx = x - (double)ix;
     float dy = y - (double)iy;
 
     // Compute the dot-product
     return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]);
 }
 
 // Compute Perlin noise at coordinates x, y
 function perlin(float x, float y) {
 
     // Determine grid cell coordinates
     int x0 = (x > 0.0 ? (int)x : (int)x - 1);
     int x1 = x0 + 1;
     int y0 = (y > 0.0 ? (int)y : (int)y - 1);
     int y1 = y0 + 1;
 
     // Determine interpolation weights
     // Could also use higher order polynomial/s-curve here
     float sx = x - (double)x0;
     float sy = y - (double)y0;
 
     // Interpolate between grid point gradients
     float n0, n1, ix0, ix1, value;
     n0 = dotGridGradient(x0, y0, x, y);
     n1 = dotGridGradient(x1, y0, x, y);
     ix0 = lerp(n0, n1, sx);
     n0 = dotGridGradient(x0, y1, x, y);
     n1 = dotGridGradient(x1, y1, x, y);
     ix1 = lerp(n0, n1, sx);
     value = lerp(ix0, ix1, sy);
 
     return value;
 }

Complexity[edit]

For each function evaluation, the dot product of the position and gradient vectors must be evaluated at each grid point. For each additional dimension, the number of grid points doubles, Perlin noise therefore scales with complexity O(2^n) for n dimensions. Alternatives to Perlin noise producing similar results with improved complexity scaling include simplex noise and OpenSimplex noise.

See also[edit]

References[edit]

  1. ^ a b Making Noise Ken Perlin talk on noise
  2. ^ Original source code of Ken Perlin's 'coherent noise function'
  3. ^ Ken Perlin's 2001 Perlin Noise patent
  4. ^ Kerman, Phillip. Macromedia Flash 8 @work: Projects and Techniques to Get the Job Done. Sams Publishing. 2006. ISBN 9780672328282.
  5. ^ a b c libnoise

External links[edit]