Simplex noise

<h2 id="algorithm-detail">Algorithm detail</h2>
<p>Simplex noise is most commonly implemented as a two-, three-, or four-dimensional <a href="/facts/Function_(mathematics)/CdReEKCh">function</a>, but can be defined for any number of dimensions. An implementation typically involves four steps: coordinate skewing, simplicial subdivision, gradient selection, and kernel summation.
</p>
<h3>Coordinate skewing</h3>
<p>An input coordinate is transformed using the formula
</p>

x
          ′
        
        =
        x
        +
        (
        x
        +
        y
        +
        ⋯
        )
        ⋅
        F
        ,
      
    
    {\displaystyle x'=x+(x+y+\cdots )\cdot F,}

y
          ′
        
        =
        y
        +
        (
        x
        +
        y
        +
        ⋯
        )
        ⋅
        F
        ,
      
    
    {\displaystyle y'=y+(x+y+\cdots )\cdot F,}

⋯
        ,
      
    
    {\displaystyle \cdots ,}

<p>where
</p>

F
        =
        
          
            
              
                
                  n
                  +
                  1
                
              
              −
              1
            
            n
          
        
        .
      
    
    {\displaystyle F={\frac {{\sqrt {n+1}}-1}{n}}.}

<p>This has the effect of placing the coordinate on an <i>A*n</i> lattice, which is essentially the <a href="/facts/Vertex_arrangement/DFgCsP0n">vertex arrangement</a> of a <a href="/facts/Hypercubic_honeycomb/MQxLbDeB">hypercubic honeycomb</a> that has been squashed along its main diagonal until the distance between the points (0, 0, ..., 0) and (1, 1, ..., 1) becomes equal to the distance between the points (0, 0, ..., 0) and (1, 0, ..., 0).
</p><p>The resulting coordinate (<i>x</i>', <i>y</i>', ...) is then used in order to determine which skewed unit hypercube cell the input point lies in, (<i>xb</i>' = floor(<i>x</i>'), <i>yb</i>' = floor(<i>y</i>'), ...), and its internal coordinates (<i>xi</i>' = <i>x</i>' − <i>xb</i>', <i>yi</i>' = <i>y</i>' − <i>yb</i>', ...).
</p>
<h3>Simplicial subdivision</h3>
<p>Once the above is determined, the values of the internal coordinate (<i>xi</i>', <i>yi</i>', ...) are sorted in decreasing order, to determine which skewed <a href="/facts/Schl%25C3%25A4fli_orthoscheme/jwXB2mQV">Schläfli orthoscheme</a> simplex the point lies in. Then the resulting simplex is composed of the vertices corresponding to an ordered edge traversal from (0, 0, ..., 0) to (1, 1, ..., 1), of which there are <i>n</i>! possibilities, each of which corresponds to a single permutation of the coordinate. In other words, start with the zero coordinate and successively add-ones starting in the value corresponding to the largest internal coordinate's value, ending with the smallest.
</p><p>For example, the point (0.4, 0.5, 0.3) would lie inside the simplex with vertices (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1). The <i>yi</i>' coordinate is the largest, so it is added first. It is then followed by the <i>xi</i>' coordinate, and finally <i>zi</i>'.
</p>
<h3>Gradient selection</h3>
<p>Each simplex vertex is added back to the skewed hypercube's base coordinate and hashed into a pseudo-random gradient direction. The hash can be implemented in numerous ways, though most often uses a permutation table or a bit manipulation scheme.
</p><p>Care should be taken in the selection of the set of gradients to include, to keep directional artifacts to a minimum.
</p>
<h3>Kernel summation</h3>
<p>The contribution from each of the <i>n</i> + 1 vertices of the simplex is factored in by a summation of radially symmetric kernels centered around each vertex. First, the unskewed coordinate of each of the vertices is determined using the inverse formula
</p>

x
        =
        
          x
          ′
        
        −
        (
        
          x
          ′
        
        +
        
          y
          ′
        
        +
        ⋯
        )
        ⋅
        G
        ,
      
    
    {\displaystyle x=x'-(x'+y'+\cdots )\cdot G,}

y
        =
        
          y
          ′
        
        −
        (
        
          x
          ′
        
        +
        
          y
          ′
        
        +
        ⋯
        )
        ⋅
        G
        ,
      
    
    {\displaystyle y=y'-(x'+y'+\cdots )\cdot G,}

⋯
        ,
      
    
    {\displaystyle \cdots ,}

<p>where
</p>

G
        =
        
          
            
              1
              −
              1
              
                /
              
              
                
                  n
                  +
                  1
                
              
            
            n
          
        
        .
      
    
    {\displaystyle G={\frac {1-1/{\sqrt {n+1}}}{n}}.}

<p>This point is subtracted from the input coordinate to obtain the unskewed displacement vector. This unskewed displacement vector is used for two purposes:
</p>
<ul><li>To compute the extrapolated gradient value using a <a href="/facts/Dot_product/tNz8MLjT">dot product</a>.</li>
<li>To determine <i>d</i>2, the squared distance to the point.</li></ul>
<p>From there, each vertex's summed kernel contribution is determined using the expression
</p>

(
          
        
        max
        (
        0
        ,
        
          r
          
            2
          
        
        −
        
          d
          
            2
          
        
        )
        
          
            
              )
            
          
          
            4
          
        
        ⋅
        
          
            (
          
        
        ⟨
        Δ
        x
        ,
        Δ
        y
        ,
        …
        ⟩
        ⋅
        ⟨
        grad
        ⁡
        x
        ,
        grad
        ⁡
        y
        ,
        …
        ⟩
        
          
            )
          
        
        ,
      
    
    {\displaystyle {\big (}\max(0,r^{2}-d^{2}){\big )}^{4}\cdot {\big (}\langle \Delta x,\Delta y,\dots \rangle \cdot \langle \operatorname {grad} x,\operatorname {grad} y,\dots \rangle {\big )},}

<p>where <i>r</i>2 is usually set to either 0.5 or 0.6: the value 0.5 ensures no discontinuities, whereas 0.6 may increase visual quality in applications for which the discontinuities are not noticeable; 0.6 was used in Ken Perlin's original reference implementation.
</p>
<h2 id="legal-status">Legal status</h2>
<p>Uses of implementations in <i>3D and higher</i> for <i>textured image synthesis</i> were covered by <a href="https://patents.google.com/patent/US6867776">U.S. patent 6,867,776</a>, if the algorithm were implemented using the specific techniques described in any of the patent claims, which expired on January 8, 2022.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/OpenSimplex_noise/QKn9mm5F">OpenSimplex noise</a></li>
<li><a href="/facts/Isotropy/mc3QEY2x">Isotropy</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://github.com/stegu/perlin-noise/blob/master/simplexnoise.pdf">Short technical article with source code by Stefan Gustavson</a> (PDF)</li>
<li><a href="http://mrl.nyu.edu/~perlin/homepage2006/simplex_noise/index.html">Perlin's animated "rubber sheet" simplex noise demo</a></li>
<li><a href="https://www.itn.liu.se/~stegu76/aqsis/aqsis-newnoise/">Another implementation of Simplex Noise in C++ (SimplexNoise1234)</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Ken Perlin, Noise hardware. In Real-Time Shading SIGGRAPH Course Notes (2001), Olano M., (Ed.). (pdf) <a href="http://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf" target="_blank">http://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Ken Perlin, Making noise. Based on a talk presented at GDCHardcore (Dec 9, 1999). (url) <a href="http://www.noisemachine.com/talk1/32.html" target="_blank">http://www.noisemachine.com/talk1/32.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>"image processing - Why does increasing simplex noise dimension wash it out?". Computer Graphics Stack Exchange. Retrieved 2021-03-10. <a href="https://computergraphics.stackexchange.com/questions/4212/why-does-increasing-simplex-noise-dimension-wash-it-out" target="_blank">https://computergraphics.stackexchange.com/questions/4212/why-does-increasing-simplex-noise-dimension-wash-it-out</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Simplex noise open-in-new

Simplex noise