Editing Perlin noise (section)

==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.