View source for Perlin noise

[[Image:Perlin noise.jpg|frame|Two-dimensional slice through 3D Perlin noise at z=0]]

'''Perlin noise''' is a type of [[gradient noise]] developed by [[Ken Perlin]] in 1983 as a result of his frustration with the "machine-like" look of [[computer-generated imagery]] (CGI) at the time.<ref name="ken_powerpoint">{{cite web| url= http://www.noisemachine.com/talk1/| title= Making Noise| first= Ken| last= Perlin | archiveurl= https://web.archive.org/web/20071008162042/http://www.noisemachine.com/talk1/| url-status= dead | archive-date= October 8, 2007| website= noisemachine.com| publisher= Ken Perlin}}</ref> He formally described his findings in a [[SIGGRAPH]] paper in 1985 called ''An image Synthesizer''.<ref name="Perlin:1985:IS:325165.325247">{{cite journal|last1=Perlin|first1=Ken|title=An Image Synthesizer|journal=SIGGRAPH Comput. Graph.|date=July 1985 |volume= 19| issue= 97–8930 |pages= 287–296|doi=10.1145/325165.325247| ref=perlin_noise_siggraph_paper}}</ref> In 1997, Perlin was awarded an [[Academy Award for Technical Achievement]] for creating the algorithm:<ref name="kens_aa">[http://mrl.nyu.edu/~perlin/doc/oscar.html#noise Original source code] of Ken Perlin's 'coherent noise function'</ref><ref>{{cite web |last1=Gustavson |first1=Stefan |title=Simplex noise demystified |url=http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf |accessdate=24 April 2019}}</ref>
{{quote|To Ken Perlin for the development of Perlin Noise, a technique used to produce natural appearing [[texture mapping|texture]]s 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.<ref>{{cite patent |country=US |number=6867776 |status=patent |title=Standard for perlin noise |pubdate= |gdate=2005-03-15 |fdate=2001-01-10 |pridate=2001-01-10 |inventor= Kenneth Perlin |invent1= |invent2= |assign1=Kenneth Perlin  |assign2=Wsou Investments LLC |class=G06T11/001  |url=}}</ref>

==Uses==
[[File:Fractal terrain texture.jpg|thumb|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{{snd}}such as object surfaces, fire, smoke, or clouds{{snd}}appear more natural, by imitating the controlled random appearance of textures in nature.

[[File:Pink red liquid using perlin noise + bump + coloring (2415197699).png|thumb|An organic surface generated with Perlin noise]]
It is also frequently used to generate textures when memory is extremely limited, such as in [[Demo (computer programming)|demos]].  Its successors, such as [[fractal noise]] and [[simplex noise]], have become nearly ubiquitous in [[graphics processing unit]]s both for [[Real-time computer graphics|real-time graphics]] and for non-realtime procedural textures in all kinds of computer graphics.

==Development==
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.<ref>Kerman, Phillip. ''Macromedia Flash 8 @work: Projects and Techniques to Get the Job Done.'' Sams Publishing. 2006. {{ISBN|9780672328282}}.</ref>

==Algorithm detail==
[[Image:Perlin.png|thumb|128px|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 (mathematics)|function]], but can be defined for any number of dimensions.  An implementation typically involves three steps: grid definition with random gradient vectors, computation of the [[dot product]] between the distance-gradient vectors and interpolation between these values. <ref>{{cite web |last1=Gustavson |first1=Stefan |title=Simplex noise demystified |url=http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf |accessdate=24 April 2019}}</ref>

===Grid definition===
[[File:PerlinNoiseGradientGrid.png|alt=|none|thumb|256x256px|A 2-dimensional grid of gradient vectors]]
Define an ''n''-dimensional grid where each point has a random ''n''-dimensional unit-length gradient vector, except in the one dimensional case where the gradients are random scalars between -1 and 1.

Assigning the random gradients in one and two dimensions is trivial using a [[random number generator]].  For higher dimensions a Monte Carlo approach can be used<ref name="ken_powerpoint"/> where random Cartesian coordinates are chosen in a unit cube, points falling outside the unit ball are discarded, and the remaining points are normalized to lie on the unit sphere. The process is continued until the required number of random gradients are obtained.

In order to negate the expensive process of computing new gradients for each grid node, some implementations use a [[Hash table|hash and lookup table]] for a finite number of precomputed gradient vectors.<ref name="libnoise">[http://libnoise.sourceforge.net/index.html libnoise]</ref>  The use of a hash also permits the inclusion of a random seed where multiple instances of Perlin noise are required.

===Dot product===
[[File:PerlinNoiseDotProducts.png|alt=|none|thumb|256x256px|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.]]
Given an ''n''-dimensional gradient value at each grid node, the next step in the algorithm is to determine into which grid cell the given point falls{{clarify|reason="Which given point?"|date=October 2019}}.  For each corner node of that cell, the distance vector between the point and the node is determined.  The [[dot product]] between the gradient vector at the node and the distance vector is then computed. This function has a value of 0 at the node and a [[gradient]] equal to the precomputed node gradient.

For a point in a two-dimensional grid, this will require the computation of 4 distance vectors and dot products, while in three dimensions 8 distance vectors and 8 dot products are needed.  This leads to the <math>O(2^n)</math> complexity scaling.

===Interpolation===
[[File:PerlinNoiseInterpolated.png|alt=|none|thumb|256x256px|The final interpolated result]]
The final step is interpolation between the <math>2^n</math> dot products computed at the nodes of the cell containing the argument point. Interpolation is performed using a function that has zero first [[derivative]] (and possibly also second derivative) at the  <math>2^n</math> grid nodes. Therefore, at points close to the grid nodes the output will approximate the dot product from earlier. This means that the noise function will pass through zero at every node and have a [[gradient]] equal to the precomputed grid node gradient. These properties give Perlin noise its characteristic spatial scale.

If <math>n=1</math>, an example of a function that interpolates between value <math>a_0</math> at grid node 0 and value <math>a_1</math> at grid node 1 is

:<math>f(x) = a_0 + \operatorname{smoothstep}(x)\cdot(a_1-a_0) \ \ \text{for }0\leq x\leq 1</math>

where the [[smoothstep]] function was used.

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.<ref name="libnoise"/>

==Implementation==

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

<syntaxhighlight lang="c">
/* Function to linearly interpolate between a0 and a1
 * Weight w should be in the range [0.0, 1.0]
 *
 * as an alternative, this slightly faster equivalent function (macro) can be used:
 * #define lerp(a0, a1, w) ((a0) + (w)*((a1) - (a0))) 
 */
float lerp(float a0, float a1, float w) {
    return (1.0f - w)*a0 + w*a1;
}

// Computes the dot product of the distance and gradient vectors.
float dotGridGradient(int ix, int iy, float x, float y) {

    // Precomputed (or otherwise) gradient vectors at each grid node
    extern float Gradient[IYMAX][IXMAX][2];

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

    // Compute the dot-product
    return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]);
}

// 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 = 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;
}
</syntaxhighlight>

==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 <math>O(2^n)</math> for <math>n</math> dimensions.  Alternatives to Perlin noise producing similar results with improved complexity scaling include [[simplex noise]] and [[OpenSimplex noise]].

==See also==
* [[Value noise]]
* [[Simulation noise]]

== References ==
{{reflist}}

==External links==
* [https://mzucker.github.io/html/perlin-noise-math-faq.html Matt Zucker's Perlin noise math FAQ ]
* [http://www.ddj.com/architect/222600097?pgno=4 Rob Farber's tutorial demonstrating Perlin noise generation and visualization on CUDA-enabled graphics processors]
* [http://libnoise.sourceforge.net/ Jason Bevins's extensive C++ library for generating complex, coherent noise values]
* [https://github.com/A1essandro/perlin-noise-generator/ Realization] on PHP (github)
* [http://scratchapixel.com/lessons/procedural-generation-virtual-worlds%20/perlin-noise-part-2 Perlin Noise Explained in Depth (with C++ source code)]
* [https://thebookofshaders.com/11/ The Book of Shaders by Patricio Gonzalez Vivo & Jen Lowe]
*[http://perlin.mydevelops.com Perlin noise online generator]
{{Procedural noise |state=expanded}}
{{Noise}}

[[Category:Noise (graphics)]]
[[Category:Special effects]]
[[Category:Fractals]]
[[Category:Computer graphics]]
[[Category:Articles with example C code]]