Editing Perlin noise

{{short description|Type of gradient noise in computer graphics}}
[[File:Perlin noise example.png|thumb|Two-dimensional slice through 3D Perlin noise at {{math|''z'' {{=}} 0}}]]

'''Perlin noise''' is a type of [[gradient noise]] developed by [[Ken Perlin]] in 1983. It has many uses, including but not limited to: [[Scenery generator|procedurally generating terrain]], applying [[pseudo-random]] changes to a variable, and assisting in the creation of [[image texture]]s. It is most commonly implemented in two, three, or four [[Dimension|dimensions]], but can be defined for any number of dimensions.

==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.<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=ACM SIGGRAPH Computer Graphics |date=July 1985 |volume= 19| issue= 97–8930 |pages= 287–296|doi=10.1145/325165.325247| ref=perlin_noise_siggraph_paper}}</ref> He developed it after working on [[Disney]]'s [[computer animated]] [[sci-fi]] motion picture ''[[Tron]]'' (1982) for the animation company [[Mathematical Applications Group]] (MAGI).<ref>{{Cite web |last=Perlin |first=Ken |title=In the beginning: The Pixel Stream Editor |url=https://www.csee.umbc.edu/~olano/s2002c36/ch04.pdf |access-date=May 31, 2022}}</ref> In 1997, Perlin was awarded an [[Academy Award for Technical Achievement]] for creating the algorithm, the citation for which read:<ref>{{Cite magazine |last=Tanner |first=Mike |title=Oscar is FX Wizard's Reward |language=en-US |magazine=Wired |url=https://www.wired.com/1997/01/oscar-is-fx-wizards-reward/ |access-date=2022-05-31 |issn=1059-1028}}</ref><ref name="kens_aa">[http://mrl.nyu.edu/~perlin/doc/oscar.html#noise Original source code]</ref><ref>{{Cite web |url=http://mrl.nyu.edu/~perlin/doc/oscar.html |title=Ken's Academy Award |access-date=2011-05-29 |archive-date=2018-05-01 |archive-url=https://web.archive.org/web/20180501200154/http://mrl.nyu.edu/~perlin/doc/oscar.html |url-status=bot: unknown }} of Ken Perlin's 'coherent noise function'</ref><ref name="gustavson">{{cite web |last1=Gustavson |first1=Stefan |title=Simplex noise demystified |url=http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf |accessdate=24 April 2019 |archive-date=21 March 2023 |archive-url=https://web.archive.org/web/20230321011148/http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf |url-status=dead }}</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 |assign1=Kenneth Perlin  |assign2=Wsou Investments LLC}}</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]].<ref name=Hart2001>{{Cite book |last=Hart |first=John C. |chapter=Perlin noise pixel shaders |date=2001-08-01 |title=Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware |chapter-url=https://dl.acm.org/doi/abs/10.1145/383507.383531 |series=HWWS '01 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=87–94 |doi=10.1145/383507.383531 |isbn=978-1-58113-407-0}}</ref> The function has a [[pseudo-random]] appearance, yet all of its visual details are the same size.{{cn|date=March 2025}} 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.<ref name=Hart2001/>

[[File:Pink red liquid using perlin noise + bump + coloring (2415197699).png|thumb|A virtual 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]].<ref name=LagaeEtAl2010>{{Cite journal |last1=Lagae |first1=A. |last2=Lefebvre |first2=S. |last3=Cook |first3=R. |last4=DeRose |first4=T. |last5=Drettakis |first5=G. |last6=Ebert |first6=D.s. |last7=Lewis |first7=J.p. |last8=Perlin |first8=K. |last9=Zwicker |first9=M. |date=2010 |title=A Survey of Procedural Noise Functions |url=https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8659.2010.01827.x |journal=Computer Graphics Forum |language=en |volume=29 |issue=8 |pages=2579–2600 |doi=10.1111/j.1467-8659.2010.01827.x |issn=1467-8659}}</ref>  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-real-time procedural textures in all kinds of computer graphics.

It is frequently used in video games to make [[procedurally generated terrain]] that looks natural.  The success is in part due to the hierarchical structuring of Perlin noise that mimics naturally occurring hierarchical structures, and therefore also has found to be useful in environmental science applications.<ref>{{Cite journal |last=Etherington |first=Thomas R. |date=2022 |title=Perlin noise as a hierarchical neutral landscape model |url=https://we.copernicus.org/articles/22/1/2022/ |journal=Web Ecology |language=en |volume=22 |issue=1 |pages=1–6 |doi=10.5194/we-22-1-2022 |doi-access=free|bibcode=2022WEco...22....1E }}</ref>

==Algorithm detail==
[[File:Perlin animation 6 octaves.gif|thumb|Perlin noise rescaled and added into itself to create fractal noise. At each step, noise frequency is doubled and amplitude is halved.]]
[[File:Perlin noise with contour.svg|thumb|2-D Perlin noise with a contour line at zero, showing that the noise is zero at the gradient mesh intersections]]

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

===Grid definition===
[[File:PerlinNoiseGradientGrid.svg|alt=|none|thumb|256x256px|A two-dimensional grid of gradient vectors]]
Define an {{mvar|n}}-dimensional grid where each grid intersection has associated with it a fixed random {{mvar|n}}-dimensional unit-length gradient vector, except in the one dimensional case where the gradients are random scalars between −1 and 1.

===Dot product===
[[File:PerlinNoiseDotProducts.svg|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.]]

For working out the value of any candidate point, first find the unique grid cell in which the point lies. Then, identify the {{math|2<sup>''n''</sup>}} corners of that cell and their associated gradient vectors. Next, for each corner, calculate an offset vector. An offset vector is a displacement vector from that corner to the candidate point.

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 four offset vectors and dot products, while in three dimensions it will require eight offset vectors and eight dot products. In general, the algorithm has {{math|''O''(2<sup>''n''</sup>)}} [[Big O notation|complexity]] in {{mvar|n}} dimensions.

===Interpolation===
[[File:PerlinNoiseInterpolated.svg|alt=|none|thumb|256x256px|The final interpolated result]]
The final step is interpolation between the {{math|2<sup>''n''</sup>}} dot products. Interpolation is performed using a function that has zero first [[derivative]] (and possibly also second derivative) at the {{math|2<sup>''n''</sup>}} 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 0 at every node, giving Perlin noise its characteristic look.

If {{math|''n'' {{=}} 1}}, an example of a function that interpolates between value {{math|''a''<sub>0</sub>}} at grid node 0 and value {{math|''a''<sub>1</sub>}} at grid node 1 is

:<math>f(x) = a_0 + \operatorname{smoothstep}(x)\cdot(a_1-a_0) \quad \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 {{closed-closed|–1.0, 1.0}} and can be scaled accordingly.

==Gradient permutation==
In Ken Perlin's original implementation he used a simple hashing scheme to determine what gradient vector is associated with each grid intersection.<ref>{{cite web |last1=Perlin |first1=Ken |title=Perlin noise |url=https://mrl.nyu.edu/~perlin/noise/ |accessdate=26 August 2020}}</ref> A pre-computed permutation table is used to turn a given grid coordinate into a random number. The original implementation worked on a 256 node grid and so included the following permutation table:

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

This specific permutation is not absolutely required, though it does require a randomized array of the integers 0 to 255. If creating a new permutation table, care should be taken to ensure uniform distribution of the values.<ref>{{cite web |title=Perlin Noise: Part 2 |url=https://www.scratchapixel.com/lessons/procedural-generation-virtual-worlds/perlin-noise-part-2 |accessdate=26 August 2020 |archive-date=17 February 2023 |archive-url=https://web.archive.org/web/20230217040756/https://www.scratchapixel.com/lessons/procedural-generation-virtual-worlds/perlin-noise-part-2 |url-status=dead }}</ref>

To get a gradient vector using the permutation table the coordinates of a grid point are looked up sequentially in the permutation table adding the value of each coordinate to the permutation of the previous coordinate. So for example the original implementation did this in 3D as follows:

<syntaxhighlight lang="c">
// Values above 255 were handled by repeating the permutation table twice.
static final int p[] = new int[512];
static { for (int i=0; i < 256 ; i++) p[256+i] = p[i] = permutation[i]; }

int hash = p[p[p[X] + Y] + Z];
</syntaxhighlight>

The algorithm then looks at the bottom 4 bits of the hash output to pick 1 of 12 gradient vectors for that grid point.

==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 [[Big O notation|{{math|''O''(2<sup>''n''</sup>)}}]] for {{mvar|n}} dimensions.<ref>{{Citation |last1=Blatz |first1=Michael |title=A Very Short History of Dynamic and Procedural Content Generation |date=2017 |work=Game Dynamics: Best Practices in Procedural and Dynamic Game Content Generation |pages=1–13 |editor-last=Korn |editor-first=Oliver |url=https://link.springer.com/chapter/10.1007/978-3-319-53088-8_1 |access-date=2025-03-17 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-319-53088-8_1 |isbn=978-3-319-53088-8 |last2=Korn |first2=Oliver |editor2-last=Lee |editor2-first=Newton|url-access=subscription }}</ref>  Alternatives to Perlin noise producing similar results with improved complexity scaling include [[simplex noise]] and [[OpenSimplex noise]].

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

== References ==
{{reflist}}

==External links==
{{commons}}
* [https://web.archive.org/web/20170201233641/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/ PHP Implementation] (GitHub)
* [https://web.archive.org/web/20180616011332/http://www.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]
*[https://cees-gitlab.stanford.edu/sfarris/pynoise Python package to create Perlin noise]
*[https://glusoft.com/sdl2-tutorials/random-terrain-perlin-noise-sdl Random terrain generation and perlin noise with SDL]
{{Procedural noise |state=expanded}}
{{Noise}}

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