Perlin noise

Perlin noise is a type of gradient noise developed by Ken Perlin.

Two-dimensional slice through 3D Perlin noise at z=0

History

Ken Perlin developed perlin noise in 1983 as a result of his frustration with the "machine-like" look of computer-generated imagery (CGI) at the time.[1] He formally described his findings in a SIGGRAPH paper in 1985 called An image Synthesizer.[2] He developed it at Mathematical Applications Group, Inc. (MAGI) for Disney's computer animated sci-fi motion picture Tron (1982). In 1997, Perlin was awarded an Academy Award for Technical Achievement for creating the algorithm.[3] 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] [5][6]

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.

Perlin did not apply for any patents on the algorithm, but in 2001 he was granted a patent for the use of 3D+ implementations of simplex noise for texture synthesis. Simplex noise has the same purpose, but uses a simpler space-filling grid. Simplex noise alleviates some of the problems with Perlin's "classic noise", among them computational complexity and visually-significant directional artifacts.[7]

Uses
A virtual landscape generated using Perlin 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. 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 object surfaces, fire, smoke, or clouds – appear more natural, by imitating the controlled random appearance of textures in nature.

An organic surface generated with Perlin noise

It is also frequently used to generate textures when memory is extremely limited, such as in demos. Its successors, such as fractal noise and simplex noise, have become nearly ubiquitous in graphics processing units both for real-time graphics and for non-realtime procedural textures in all kinds of computer graphics.

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

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: defining a grid of random gradient vectors, computing the dot product between the gradient vectors and their offsets, and interpolation between these values. [8]

Grid definition
A 2-dimensional grid of gradient vectors

Define an n-dimensional grid where each grid intersection has associated with it a fixed random n-dimensional unit-length gradient vector, except in the one dimensional case where the gradients are random scalars between -1 and 1.

Dot product
The dot product of each point with its nearest grid node gradient value. The dot product with the other three nodes in the cell is not shown.

For working out the value of any candidate point, first find the unique grid cell in which the point lies. Then the corners of that cell, and their associated gradient vectors, are identified. Next, for each corner, an offset vector is calculated, being the displacement vector from the candidate point to that corner.

For each corner, we take the dot product between its gradient vector and the offset vector to the candidate point. This dot product will be zero if the candidate point is exactly at the grid corner.

For a point in a two-dimensional grid, this will require the computation of 4 offset vectors and dot products, while in three dimensions it will require 8 offset vectors and 8 dot products. In general, the algorithm has an complexity scaling.

Interpolation
The final interpolated result

The final step is interpolation between the dot products. Interpolation is performed using a function that has zero first derivative (and possibly also second derivative) at the grid nodes. Therefore, at points close to the grid nodes, the output will approximate the dot product of the gradient vector of the node and the offset vector to the node. This means that the noise function will pass through zero at every node, giving Perlin noise its characteristic look.

If , an example of a function that interpolates between value at grid node 0 and value at grid node 1 is

where the smoothstep function was used.

Noise functions for use in computer graphics typically produce values in the range [-1.0,1.0] and can be scaled accordingly.

Implementation

The following is a two-dimensional implementation of Classical Perlin Noise, written in C.

The original reference implementation by Perlin was written in Java, with major differences:

  • it is using a three dimensional approach by interpolating between 8 corners of a cube instead of the 4 corners of a square below.
  • the random gradient direction shuffles bits of the integer coordinates of corners, which is much faster than shuffling using the interference at high frequency of rotations of the integer coordinates of corners, merged and rotated again at high frequency by a product: the rotations are not uniformly distributed.
  • Perlin's method split the integer space into 256x256x256 cubes and then uses a random permutation of these cubes to shuffle them, and then each cube position corners is assigned one of twelve directions to the neighbouring non-permuted cubes in a 4x4x4 paving space: this requires only integer operations but maintains a uniform distribution of directions.
  • the interpolation function (named fade) is the smoother 4-degree Smootherstep (with the first three derivatives equal to zero on the clamping boundaries) and not the basic linear step. This avoids visible artefacts, notably along vertices or diagonals joining the sampling corners, where the result would visibly be anisotropic (tainting the desired white noise into pink noise; if the noise was used to generate a solid crystal, it would not be entirely black and opaque to the light, but partly transparent and colored in some discrete directions of observation).

So the code below is very basic a for illustration only, will be slow, and not usable in applications.

#include <math.h>

/* Function to linearly interpolate between a0 and a1
 * Weight w should be in the range [0.0, 1.0]
 */
float interpolate(float a0, float a1, float w) {
    /* // You may want clamping by inserting:
     * if (0.0 > w) return a0;
     * if (1.0 < w) return a1;
     */
    return (a1 - a0) * w + a0;
    /* // Use this cubic interpolation [[Smoothstep]] instead, for a smooth appearance:
     * return (a1 - a0) * (3.0 - w * 2.0) * w * w + a0;
     *
     * // Use [[Smootherstep]] for an even smoother result with a second derivative equal to zero on boundaries:
     * return (a1 - a0) * ((w * (w * 6.0 - 15.0) + 10.0) * w * w * w) + a0;
     */
}

typedef struct {
    float x, y;
} vector2;

/* Create random direction vector
 */
vector2 randomGradient(int ix, int iy) {
    // Random float. No precomputed gradients mean this works for any number of grid coordinates
    float random = 2920.f * sin(ix * 21942.f + iy * 171324.f + 8912.f) * cos(ix * 23157.f * iy * 217832.f + 9758.f);
    return (vector2) { .x = cos(random), .y = sin(random) };
}

// Computes the dot product of the distance and gradient vectors.
float dotGridGradient(int ix, int iy, float x, float y) {
    // Get gradient from integer coordinates
    vector2 gradient = randomGradient(ix, iy);

    // Compute the distance vector
    float dx = x - (float)ix;
    float dy = y - (float)iy;

    // Compute the dot-product
    return (dx*gradient.x + dy*gradient.y);
}

// Compute Perlin noise at coordinates x, y
float perlin(float x, float y) {
    // Determine grid cell coordinates
    int x0 = (int)x;
    int x1 = x0 + 1;
    int y0 = (int)y;
    int y1 = y0 + 1;

    // Determine interpolation weights
    // Could also use higher order polynomial/s-curve here
    float sx = x - (float)x0;
    float sy = y - (float)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 = interpolate(n0, n1, sx);

    n0 = dotGridGradient(x0, y1, x, y);
    n1 = dotGridGradient(x1, y1, x, y);
    ix1 = interpolate(n0, n1, sx);

    value = interpolate(ix0, ix1, sy);
    return value;
}

Permutation

Many implementations of Perlin noise use the same permutation set that Ken Perlin used in his original implementation.[9] That implementation is as follows:

int permutation[] = { 151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 
                      103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 
                      26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237, 149, 56, 
                      87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134, 139, 48, 27, 166, 
                      77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220, 105, 92, 41, 55, 
                      46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 
                      187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 
                      198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118, 126, 
                      255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 223, 183, 
                      170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 
                      172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232, 178, 185, 112, 
                      104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 
                      241, 81, 51, 145, 235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 
                      157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205, 
                      93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180 };

This specific permutation is not absolutely required, though it does require a randomized array of the values [0–255] (inclusive). If creating a new permutation table, care should be taken to ensure uniform distribution of the values.[10]

Complexity

For each evaluation of the noise function, the dot product of the position and gradient vectors must be evaluated at each node of the containing grid cell. Perlin noise therefore scales with complexity for dimensions. Alternatives to Perlin noise producing similar results with improved complexity scaling include simplex noise and OpenSimplex noise.

See also

References
  1. Perlin, Ken. "Making Noise". noisemachine.com. Ken Perlin. Archived from the original on October 8, 2007.
  2. Perlin, Ken (July 1985). "An Image Synthesizer". SIGGRAPH Comput. Graph. 19 (97–8930): 287–296. doi:10.1145/325165.325247.
  3. Original source code
  4. Kerman, Phillip. Macromedia Flash 8 @work: Projects and Techniques to Get the Job Done. Sams Publishing. 2006. ISBN 9780672328282.
  5. Archived 2018-05-01 at the Wayback Machine of Ken Perlin's 'coherent noise function'
  6. Gustavson, Stefan. "Simplex noise demystified" (PDF). Retrieved 24 April 2019.
  7. US patent 6867776, Kenneth Perlin, "Standard for perlin noise", issued 2005-03-15, assigned to Kenneth Perlin and Wsou Investments LLC
  8. Gustavson, Stefan. "Simplex noise demystified" (PDF). Retrieved 24 April 2019.
  9. Perlin, Ken. "Perlin noise". Retrieved 26 August 2020.
  10. "Perlin Noise: Part 2". Retrieved 26 August 2020.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.