【图形学】谈谈噪声

时间 2019-12-11 标签图形学谈谈噪声

写在前面

很早就想学习和整理下噪声，稍微接触过图形学的人大概都听到过噪声，而后就会发现有各类噪声，Perlin噪声，Worley噪声，分形（fractal）噪声等等。尤为是Perlin噪声，一搜资料发现你们说的各不相同，更加不明因此。我也老是困惑，后来发现仍是要相信wiki和paper。php

这篇文章在于总结上面这些常见的噪声（即图形学中常见的程序噪声），它们是什么，怎么算出来的，以及一些应用。文章里的全部代码能够在个人Shadertoy上找到：html

2D版：git

width="500" height="320" src="https://www.shadertoy.com/embed/ldc3RB?gui=true&t=10&paused=true&muted=false" allowfullscreen="">

3D版：github

width="500" height="320" src="https://www.shadertoy.com/embed/4sc3z2?gui=true&t=10&paused=false&muted=false" allowfullscreen="">

什么是噪声

在图形学中，咱们使用噪声就是为了把一些随机变量来引入到程序中。从程序角度来讲，噪声很好理解，咱们但愿给定一个输入，程序能够给出一个输出：web

value_type noise(value_type p) {
    ...
}

它的输入和输出类型的维数能够是不一样的组合，例如输入二维输出一维，输入二维输出二维等。咱们今天就是想讨论一下上面函数中的实现部分是长什么样的。算法

为何咱们须要这么多噪声

我对噪声的学习尚未很深，在此只想谈一点本身的想法。噪声其实就是为了把一些随机变量引入到程序中。在咱们写一些C++这样的程序时，也常常会使用random这样的函数。这些函数一般会产生一些伪随机数，但不少状况下也足够知足咱们的须要。一样，在图形学中咱们也常常会须要使用随机变量，例如火焰、地形、云朵的模拟等等。相信你确定听过大名鼎鼎的Minecraft游戏，这个游戏里面的地形生成也大量使用了随机变量。那么咱们直接使用random这种函数不就行了吗？为何要引入这么多名字的噪声呢？api

这种直接使用随机生成器生成的随机值当然有它的好处，但它的问题在于生成的随机值太“随机”了。在图形学中，咱们能够认为这种噪声就是白噪声（White noise）。wiki上说白噪声是功率谱密度在整个频域内均匀分布的噪声，听不懂对不对？通俗来说，之因此称它为“白”噪声，是由于它相似于光学中包括所有可见光频率在内的白光。我相信你确定听过白噪声，小时候电视机收音机没信号时，发出的那个沙沙声就是一种声音上的白噪声。咱们这里只须要把白噪声理解为最简单的随机值，例如二维的白噪声纹理能够是下面这个样子：数组

能够看出白噪声很是不天然，听起来很刺耳，看起来也很差看。不光你这么想，图形学领域的前辈们也早发现了。若是你观察现实生活中的天然噪声，它们不会长成上面这个样子。例如木头纹理、山脉起伏，它们的形状大可能是趋于分形状（fractal）的，即包含了不一样程度的细节。好比地形，它有起伏很大的山脉，也有起伏稍小的山丘，也有细节很是多的石子等，这些不一样程度的细节共同组成了一个天然的地形表面。那么，咱们如何用程序来生成相似这样的天然的随机数（能够想象对应了地形不一样的高度）呢？学者们根据效率、用途、天然程度（即效果好坏）等方面的衡量，提出了许多但愿用程序模拟天然噪声的方法。例如，Perlin噪声被大量用于云朵、火焰和地形等天然环境的模拟；Simplex噪声在其基础上进行了改进，提到了效率和效果；而Worley噪声被提出用于模拟一些多孔结构，例如纸张、木纹等。网络

所以，学习和理解这些噪声在图形学中是十分必要的，由于它们的应用实在是太普遍了！app

噪声的分类

根据wiki，由程序产生噪声的方法大体能够分为两类：

类别	名称
基于晶格的方法（Lattice based）	又可细分为两种：第一种是梯度噪声（Gradient noise），包括Perlin噪声， Simplex噪声，Wavelet噪声等；第二种是Value噪声（Value noise）。
基于点的方法（Point based）	Worley噪声

须要注意的是，一些文章常常会把Perlin噪声、Value噪声与分形噪声（Fractal noise）弄混，这实际在概念上是有些不同的。分形噪声会把多个不一样振幅、不一样频率的octave相叠加，获得一个更加天然的噪声。而这些octave则对应了不一样的来源，它能够是Gradient噪声（例如Perlin噪声）或Value噪声，也能够是一个简单的白噪声（White noise）。

一些很是出色的文章也错误把这种分形噪声声称为Perlin噪声，例如：

Hugo Elias的文章，这篇文章讲得挺有趣的，关于什么是octave、怎么混合它们都讲得很细致，也很是有名，但做者错误地把值噪声+分形噪声标识为Perlin噪声，他的文章连接也出现了wiki的值噪声（Value noise）的页面中。
Devmag的如何在你的游戏中使用Perlin噪声一文，一样很是有名，但一样错误地把白噪声+分形噪声认为是Perlin噪声。

若是读者常逛shadertoy的话，会发现不少shader使用了相似名为fbm的噪声函数。fbm实际就是分型布朗运动（Fractal Brownian Motion）的缩写，读者能够把它等同于咱们上面所说的分形噪声（Fractal noise），咱们如下均使用fbm来表示这种噪声的计算方法。若是要通俗地说fbm和以前说起的Perlin噪声、Simplex噪声、Value噪声、白噪声之间的联系，咱们能够认为是不少个不一样频率、不一样振幅的基础噪声（指以前提到的Perlin噪声、Simplex噪声、Value噪声、白噪声等之一）之间相互叠加，最后造成了最终的分形噪声。这里的频率指的是计算噪声时的采样距离，例如对于基于晶格的噪声们，频率越高，单位面积（特指二维）内的晶格数目越多，看起来噪声纹理“越密集”；而振幅指的就是噪声的值域。下图显示了一些基础噪声和它们fbm后的效果：

说明：分割线左侧表示单层的基础噪声，右侧表示经过叠加不一样频率噪声后的fbm效果。上面效果来源于shadertoy：Perlin噪声，Simplex噪声，Value噪声，Worley噪声。

因为Worley噪声的生成和其余噪声有明显不一样，所以不是本文的重点。它主要用于产生孔状的噪声，有兴趣的读者能够参见偶像iq的文章：

Perlin噪声、Simplex噪声和Value噪声在性能上大体知足：Perlin噪声 > Value噪声 > Simplex噪声，Simplex噪声性能最好。Perlin噪声和Value噪声的复杂度是 $O(2^n)$ ，其中n是维数，但Perlin噪声比Value噪声须要进行更多的乘法（点乘）操做。而Simplex噪声的复杂度为 $O(n^2)$ ，在高纬度上优化明显。

下面的内容就是重点解释Perlin噪声、Perlin噪声和Simplex噪声这三种常见的噪声，最后再介绍fbm。

Perlin噪声

先介绍大名鼎鼎的Perlin噪声。不少人都知道，Perlin噪声的名字来源于它的创始人Ken Perlin。Ken Perlin早在1983年就提出了Perlin noise，当时他正在参与制做迪士尼的动画电影《电子世界争霸战》（英语：TRON），可是他不知足于当时计算机产生的那种很是不天然的纹理效果，所以提出了Perlin噪声。随后，他在1984年的SIGGRAPH Course上作了名为Advanced Image Synthesis1的课程演讲，并在SIGGRAPH 1985上发表了他的论文2。因为Perlin噪声的算法简单，被迅速应用到各类商业软件中。咱们这位善良的Perlin先生却并无对Perlin噪声算法申请专利（他说他的祖母曾叫他这么作过……），若是他这么作了那会是多大一笔费用啊！（不过在2001年的时候，旁人看不下去了，把三维以上的Simplex噪声的专利主动授予了Perlin。对，Simplex噪声也是人家提出的……）再后来Perlin继续研究程序纹理的生成，并和他的一名学生又在SIGGRAPH 1989上发表了一篇文章3，提出了超级纹理（hypertexture）。他们使用噪声+fbm+ray marching实现了各类有趣的效果。到1990年，已经有大量公司在他们的产品中使用了Perlin噪声。在1999年的GDCHardCore大会上，Ken Perlin作了名为Making Noise的演讲4，系统地介绍了Perlin噪声的发展、实现细节和应用。若是读者不想读论文的话，强烈建议你看一下Perlin演讲的PPT。

后来在2002年，Perlin又发表了一篇论文5来改进原始的Perlin噪声中的一些问题，例如原来的缓和曲线 $s(t) = 3t^2-2t^3$ 的二阶导 $6 - 12t$ 在 $t = 0$ 和 $t = 1$ 时均不等于0，这使得在相邻的晶格处它们的二阶导并不连续。所以Perlin提出使用一个更好的缓和曲线 $s(t) = 6t^5 - 15t^4 + 10t^3$ ；此外还改进了晶格顶点处随机梯度向量的选取。有兴趣的读者能够参考：

Perlin在2002年发表的论文：http://mrl.nyu.edu/~perlin/paper445.pdf
GPU Gems的文章：http://http.developer.nvidia.com/GPUGems/gpugems_ch05.html
GPU Gems 2的文章：http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter26.html

后面只介绍原始Perlin噪声的实现。

实现

Perlin噪声仍是比较简单的，在1983年的计算机上实现的算法也不容许对计算量、内存有多大的要求。归纳来讲，Perlin噪声的实现须要三个步骤：

定义一个晶格结构，每一个晶格的顶点有一个“伪随机”的梯度向量（其实就是个向量啦）。对于二维的Perlin噪声来讲，晶格结构就是一个平面网格，三维的就是一个立方体网格。
输入一个点（二维的话就是二维坐标，三维就是三维坐标，n维的就是n个坐标），咱们找到和它相邻的那些晶格顶点（二维下有4个，三维下有8个，n维下有 $2^n$ 个），计算该点到各个晶格顶点的距离向量，再分别与顶点上的梯度向量作点乘，获得 $2^n$ 个点乘结果。
使用缓和曲线（ease curves）来计算它们的权重和。在原始的Perlin噪声实现中，缓和曲线是 $s(t) = 3t^2-2t^3$ ，在2002年的论文6中，Perlin改进为 $s(t) = 6t^5 - 15t^4 + 10t^3$ 。这里简单解释一下，为何不直接使用 $s(t) = t$ ，即线性插值。直接使用的线性插值的话，它的一阶导在晶格顶点处（即t = 0或t = 1）不为0，会形成明显的不连续性。 $s(t) = 3t^2-2t^3$ 在一阶导知足连续性， $s(t) = 6t^5 - 15t^4 + 10t^3$ 在二阶导上仍然知足连续性。

咱们下面以二维的为例，再详细解释一下。咱们能够用下面的图来表示上面的第一步和第二步：

一个问题是晶格顶点处的伪随机梯度向量是如何获得的，固然咱们能够经过random这样的函数来计算单位正方形（二维）内的x和y份量值，但咱们更愿意要那些在单位圆内的梯度向量。Perlin在他的实现中选择使用蒙特卡洛模拟方法来选取这些随机梯度向量。具体方法是（我把描述适应到了二维）：首先按以前的方法生成在单位正方形内随机梯度向量，而后剔除那些不在单位圆内的向量，直到找到了须要数目的随机梯度向量。Perlin把这些预计算获得的向量存储在一个查找表G[n]中，n是纹理大小，例如256 x 256大小的纹理对应n为256。虽然咱们实际上须要n x n个梯度向量，这样会形成有些顶点的梯度是重复的。Perlin认为，重复是能够容许的，只要它们的间距够大就不会被察觉。所以，Perlin还预计算了一个随机排列数组P[n]，P[n]里面存储的是打乱后的0~n-1的排列值。这样一来，当咱们想要获得(i, j)处晶格的梯度向量时，可使用：

G = G [(i + P [j]) m o d n]

$G = G[(i + P[j])_{mod \ n}]$

获得了梯度后，咱们就能够进行点乘，获得4个点乘结果，而后使用缓和曲线对它们进行插值便可。这里使用的权重就是输入点到4个顶点的横纵距离。

在原始的Perlin噪声实现中，Perlin对梯度向量的选择通常是取单位圆（三维就是单位球）内一些不一样方向的向量。在他后面的改进算法7中，Perlin建议把三维的梯度向量初始化为到立方体12条边的向量值，来保证各个方向之间的不关联性。

能够看出，Perlin噪声算法的时间复杂度为 $O(2^n)$ （n是维数）， $2^n$ 其实就是每一个晶格的顶点个数，对于每一个输入点咱们须要进行这么屡次的点乘操做。所以，随着维数的增大，例如计算三维四维的Perlin噪声，时间会迅速增长。Perlin在2002年介绍了他优化后的一种噪声——Simplex噪声，这种噪声的复杂度是 $O(n^2)$ ，在高纬度上时间优化明显，咱们后面会讲到这种噪声。

效果

Shadertoy上有不少关于Perlin噪声的实现，我也山寨了一个：

它的主要代码以下：

vec2 hash22(vec2 p)
{
    p = vec2( dot(p,vec2(127.1,311.7)),
              dot(p,vec2(269.5,183.3)));

    return -1.0 + 2.0 * fract(sin(p)*43758.5453123);
}
float perlin_noise(vec2 p)
{
    vec2 pi = floor(p);
    vec2 pf = p - pi;

    vec2 w = pf * pf * (3.0 - 2.0 * pf);

    return mix(mix(dot(hash22(pi + vec2(0.0, 0.0)), pf - vec2(0.0, 0.0)), 
                   dot(hash22(pi + vec2(1.0, 0.0)), pf - vec2(1.0, 0.0)), w.x), 
               mix(dot(hash22(pi + vec2(0.0, 1.0)), pf - vec2(0.0, 1.0)), 
                   dot(hash22(pi + vec2(1.0, 1.0)), pf - vec2(1.0, 1.0)), w.x),
               w.y);
}

这里的实现实际是简化版的，咱们在算梯度的时候直接取随机值，而没有归一化到单位圆内。

上图包含了四种噪声组合，这也是Perlin在1999年的GDC上作演讲时采用的一个示例，不过Perlin的例子是三维的，并且添加了光照等计算。

左上角的部分。这是最简单的单独的Perlin噪声，它的噪声模拟以下：
```
float noise_itself(vec2 p)
{
    return noise(p * 8.0);
}
```
上面的代码在整个屏幕上模拟了一个8 x 8的网格结构。在绘制时，咱们只须要将一个深蓝色乘以噪声便可获得相似的效果。

单独一个Perlin噪声虽然也有必定用处，可是效果每每很无趣。所以，Perlin指出可使用不一样的函数组合来获得更有意思的结果，这些函数组合一般就是指经过分形叠加（fractal sum），也就是咱们以前说的fbm。
左下角的部分。这个部分使用了fbm进行叠加来造成一个分形噪声。公式以下：

noise(p)+12noise(2p)+14noise(4p)+...

即每一次噪声的采样频率翻倍，而振幅减小一倍。不少文章错误地把这种计算认为是Perlin噪声，这是不对的。Perlin噪声只是对应了其中每个octave。代码是：
```
float noise_sum(vec2 p)
{
    float f = 0.0;
    p = p * 4.0;
    f += 1.0000 * noise(p); p = 2.0 * p;
    f += 0.5000 * noise(p); p = 2.0 * p;
    f += 0.2500 * noise(p); p = 2.0 * p;
    f += 0.1250 * noise(p); p = 2.0 * p;
    f += 0.0625 * noise(p); p = 2.0 * p;

   return f;
}
```
上面叠加了5层，并把初始化采样距离设置为4，这都是能够自定义的。这种噪声能够用来模拟石头、山脉这类物体。
右下角的部分。这一部分只是在上一部分进行了一点修改，对噪声返回值进行了取绝对值操做。它使用的公式以下：

|noise(p)|+12|noise(2p)|+14|noise(4p)|+...

它对应的代码以下：
```
float noise_sum_abs(vec2 p)
{
    float f = 0.0;
    p = p * 7.0;
    f += 1.0000 * abs(noise(p)); p = 2.0 * p;
    f += 0.5000 * abs(noise(p)); p = 2.0 * p;
    f += 0.2500 * abs(noise(p)); p = 2.0 * p;
    f += 0.1250 * abs(noise(p)); p = 2.0 * p;
    f += 0.0625 * abs(noise(p)); p = 2.0 * p;

    return f;
}
```
因为进行了绝对值操做，所以会在0值变化处出现不连续性，造成一些尖锐的效果。经过合适的颜色叠加，咱们能够用这种噪声来模拟火焰、云朵这些物体。Perlin把这个公式称为turbulence（湍流？），由于它看起来挺像的。
右上角的部分。这个部分是在以前turbulence公式的基础上使用了一个关于表面x份量的正弦函数：

sin(x+|noise(p)|+12|noise(2p)|+14|noise(4p)|+...)

这个公式可让表面沿着x方向造成一个条纹状的结构。Perlin使用这个公式模拟了一些大理石材质。咱们的代码以下：
```
float noise_sum_abs_sin(vec2 p)
{
    float f = 0.0;
    p = p * 7.0;
    f += 1.0000 * abs(noise(p)); p = 2.0 * p;
    f += 0.5000 * abs(noise(p)); p = 2.0 * p;
    f += 0.2500 * abs(noise(p)); p = 2.0 * p;
    f += 0.1250 * abs(noise(p)); p = 2.0 * p;
    f += 0.0625 * abs(noise(p)); p = 2.0 * p;
    f = sin(f + p.x/32.0);

    return f;
}
```
咱们能够经过改变x份量前面的系数来控制条纹的疏密。

以上，咱们就演示了基本的Perlin噪声的实现。Perlin在1999年Making Noise的演讲8中，还介绍了如何使用噪声来控制纹理动画。他指出，想要一个二维的turbulence纹理动画（例如云、火焰等），咱们须要使用三维的噪声，其中第三维对应了时间变量。Shadertoy上有不少这样的例子，例以下面的就是模拟了Perlin演讲中实现的火球效果：

width="500" height="320" src="https://www.shadertoy.com/embed/lsf3RH?gui=true&t=10&paused=false&muted=false" allowfullscreen="">

有兴趣的能够尝试实现Perlin演讲中实现的云彩飘动效果。

Value噪声

在理解了Perlin噪声的实现后，Value噪声就很简单了。它把原来的梯度替换成了一个简单的伪随机值，咱们也不须要进行点乘操做，而直接把晶格顶点处的随机值按权重相加便可。

实现

和Perlin噪声同样，它也是一种基于晶格的噪声，也须要三个步骤：

定义一个晶格结构，每一个晶格的顶点有一个“伪随机”的值（Value）。对于二维的Value噪声来讲，晶格结构就是一个平面网格，三维的就是一个立方体网格。
输入一个点（二维的话就是二维坐标，三维就是三维坐标，n维的就是n个坐标），咱们找到和它相邻的那些晶格顶点（二维下有4个，三维下有8个，n维下有 $2^n$ 个），获得这些顶点的伪随机值。
使用缓和曲线（ease curves）来计算它们的权重和。一样，缓和曲线能够是 $s(t) = 3t^2-2t^3$ ，也能够是 $s(t) = 6t^5 - 15t^4 + 10t^3$ （若是二阶导不连续对效果影响较大时）。

Value噪声比Perlin噪声的实现更加简单，而且须要的乘法和加法操做也更少，它只须要获得晶格顶点的随机值再把它们按权重相加便可。

效果

咱们再次使用以前在Perlin噪声效果展现时使用的代码，但改变一些参数就能够获得下面的效果：

它的主要代码以下：

float value_noise(vec2 p)
{
    vec2 pi = floor(p);
    vec2 pf = p - pi;

    vec2 w = pf * pf * (3.0 - 2.0 * pf);

    return mix(mix(hash21(pi + vec2(0.0, 0.0)), hash21(pi + vec2(1.0, 0.0)), w.x),
               mix(hash21(pi + vec2(0.0, 1.0)), hash21(pi + vec2(1.0, 1.0)), w.x),
               w.y);
}

能够看出，单独的Value噪声（左上角）会有很明显的像素块效果。其实我认为，当把Value噪声纹理的大小调的很大时，它近似就是一张白噪声纹理。不过所幸的是，在经过fbm叠加后，造成的分形噪声效果仍是能够接受的，这也是为何它会被大量应用在不少程序中来代替基于梯度的Perlin噪声。

Simplex噪声

最后，咱们来介绍本文最难理解的一种噪声。在2001年SIGGRAPH Course上，Ken Perlin进行了一次演讲9，他介绍了对Perlin噪声的一个改进版噪声——Simplex噪声。感兴趣的读者能够看一下Perlin原版的Course Note。咱们以前提到过不少次，Simplex噪声的计算复杂度为 $O(n^2)$ ，优于Perlin噪声的 $O(2^n)$ 。并且在效果上，Simplex噪声也克服了经典的Perlin噪声在某些视觉问题。但Simplex噪声的问题在于，它比较难理解，以致于当Perlin提出了后好几年的时间里它并无被普遍使用。

实现

Simplex噪声也是一种基于晶格的梯度噪声，它和Perlin噪声在实现上惟一不一样的地方在于，它的晶格并非方形（在2D下是正方形，在3D下是立方体，在更高纬度上咱们称它们为超立方体，hypercube），而是单形，simplex。那么什么是单形呢？

通俗解释单形的话，能够认为是在N维空间里，选出一个最简单最紧凑的多边形，让它能够平铺整个N维空间。咱们能够很容易地想到一维空间下的单形是等长的线段（1-单形），把这些线段收尾相连便可铺满整个一维空间。在二维空间下，单形是三角形（2-单形），咱们能够把等腰三角形链接起来铺满整个平面。三维空间下的单形，即3-单形就是四面体。更高维空间的单形也是存在的。

那么使用单形有什么好处呢？这能够从以前对单形的解释看出来——它的顶点数不多，要远小于超立方体（hypercube）的顶点个数。总结起来，在N维空间下，超立方体的顶点数目是 $2^n$ ，而单形的顶点数目是 $n+1$ ，这使得咱们在计算梯度噪声时能够大大减小须要计算的顶点权重数目。

在理解了单形后，Simplex噪声的计算过程其实和Perlin噪声基本同样。咱们以二维空间下的为例。二维空间下的单形便是等边三角形，以下图所示。这些单形组成了一个单形网格结构，和Perlin噪声相似，这些网格顶点处也存储了伪随机梯度向量。

当输入一点后，咱们找到该点所在的三角形（图中红色三角形），再找到该三角形三个顶点的梯度向量和每一个顶点到输入点的差值向量，把每一个顶点的梯度向量和插值向量作点乘，获得三个点乘结果。最后，咱们把它们按权重进行叠加混合，这个权重与输入点到每一个顶点的有关，即每一个顶点的噪声贡献度为：

(r 2 - | d i s t | 2) 4 \times d o t (d i s t, g r a d)

$(r^2 - |\boldsymbol{dist}|^2)^4 \times dot(\boldsymbol{dist},\boldsymbol{ grad})$

其中， $\boldsymbol{dist}$ 是输入点到该顶点的距离向量， $\boldsymbol{grad}$ 是该点存储的伪随机梯度向量， $r^2$ 的取值是0.5或0.6。取0.5时能够保证没有不连续的间断点，在连续性并不那么明显时能够取0.6获得更好的视觉效果。在Perlin原始的论文中，r的取值是0.6（后面咱们会讲到0.5的值是如何获得的）。当获得单形每一个顶点的噪声贡献度后，就能够把它们相加起来。为了把结果归一到-1到1的范围，咱们每每还须要在最后乘以一个系数，这个系数值咱们以后会讲到。

能够看出，Simplex噪声的实现过程和Perlin几乎彻底同样。可是，在上面的实现中咱们始终忽略了一个问题，就是如何找到输入点所在的单形？在计算Perlin噪声时，判断输入点所在的正方形是很是容易的，咱们只须要对输入点下取整便可找到，那么这里能不能也这么计算呢？幸运的是，数学家们已经为咱们解决了这个问题：咱们能够把单形进行坐标偏斜（skewing），把平铺空间的单形变成一个新的网格结构，这个网格结构是由超立方体组成的，而每一个超立方体又由必定数量的单形构成。听不懂是否是？2005年Stefan的一篇论文10里的一张图大概能够解救你！

咱们以前讲到的单形网格如上图中的红色网格所示，它们有一些等边三角形组成（注意到这些等边三角形是沿空间对角线排列的）。通过坐标倾斜后，它们变成了后面的黑色网格，这些网格由正方形组成，每一个正方形是由以前两个等边三角形变形而来的三角形组成。这个把N维空间下的单形网格变造成新网格的公式以下：

x' = x + (x + y + . . .) \cdot K 1 y' = y + (x + y + . . .) \cdot K 1 . . . 其 中 ， K 1 = n + 1 ‾ ‾ ‾ ‾ ‾ \sqrt - 1 n

$x^{'} = x + (x + y + ...) \cdot K1 \\ y^{'} = y + (x + y + ...) \cdot K1 \\ ... \\ 其中，K1 = \frac{\sqrt{n + 1} - 1}{n}$

在二维空间下，取n为2便可。这样变换以后，咱们就能够按照以前方法判断该点所在的超立方体，在二维下即为正方形。这样咱们就有了Simplex噪声的第一步：

1 坐标偏斜：把输入点坐标进行坐标偏斜，对坐标下取整获得输入点所在的超立方体 $x_i = floor(x^{'}), y_i = floor(y^{'}), ...$ ，咱们还能够获得小数部分 $x_{f} = x^{'} - x_i, y_{f} = y^{'} - y_i, ...$ ，这些小数部分能够帮助咱们进一步判断输入点所在的单形以及计算权重。

但咱们的目标实际上是要获得输入点所在的单形，而不是超立方体。所以咱们须要继续作判断。仍是如以前的图所示，通过坐标偏斜后，一个正方形由两个三角形组成，咱们能够判断 $x_f$ 和 $y_f$ 之间的关系来判断输入点位于哪一个三角形内，并获得该三角形的三个顶点。由此，咱们有了Simplex噪声的第二步：

2 单形分割：咱们把以前获得的 $(x_f, y_f, ...)$ 中的数值按降序排序，来决定输入点位于变形后的哪一个单形内。这个单形的顶点是由按序排列的(0, 0, …, 0)到(1, 1, …, 1)中的 $n + 1$ 个顶点组成，共有 $n!$ 种可能性。咱们能够按下面的过程来获得这 $n + 1$ 个顶点：从零坐标(0, 0, …, 0)开始，找到当前最大的份量，在该份量位置加1，直至添加了全部份量。例如，对于二维空间来讲，若是 $x_f, y_f$ 知足 $x_f > y_f$ ，那么对应的3个单形坐标为：首先找到(0, 0)，因为x份量比较大，所以下一个坐标是(1, 0)，接下来是y份量，坐标为(1, 1)；对于三维空间来讲，若是 $x_f, y_f, z_f$ 知足 $x_f > z_f > y_f$ ，那么对应的4个单形坐标位：首先从(0, 0, 0)开始，接下来在x份量上加1得(1, 0, 0)，再在z份量上加1得(1, 0, 1)，最后在y份量上加1得(1, 1, 1)。这一步的算法复杂度即为排序复杂度 $O(n^2)$ 。

找到了对应的单形后，后面的工做就比较简单了。咱们首先找到该单形各个顶点上的伪随机梯度向量，这就是第三步：

3 梯度选取：咱们在偏斜后的超立方体网格上获取该单形的各个顶点的伪随机梯度向量。

如今咱们须要的东西基本都准备好了，最后一步就是计算全部单形顶点对输出的噪声贡献度。

4 贡献度取和：咱们首先须要把单形顶点变回到以前由单形组成的单形网格。这一步须要使用第一步公式的逆函数来求得：

$x = x' + (x' + y' + . . .) \cdot K 2 y = y' + (x' + y' + . . .) \cdot K 2 . . . 其中， K 2 = 1 n + 1 \sqrt - 1 n$ $x = x^{'} + (x^{'} + y^{'} + ...) \cdot K2 \\ y = y^{'} + (x^{'} + y^{'} + ...) \cdot K2 \\ ... \\其中，K2 = \frac{\frac{1}{\sqrt{n + 1}} - 1}{n}$
咱们由此能够获得输入点到这些单形顶点的位移向量。这些向量有两个用途，一个是为了和顶点梯度向量点乘，另外一个是为了获得以前提到的距离值 $\boldsymbol{dist}$ ，来据此求得每一个顶点对结果的贡献度：
$(r 2 - | d i s t | 2) 4 \times d o t (d i s t, g r a d)$ $(r^2 - |\boldsymbol{dist}|^2)^4 \times dot(\boldsymbol{dist},\boldsymbol{ grad})$

如今咱们能够来解释 $r^2$ 取0.5的缘由了。因为要求通过第一步坐标偏斜后获得的网格宽度为1，所以咱们能够倒推出在变形前单形网格中每一个单形边的边长为 $\sqrt{\frac{2}{3}}$ ，这样一来单形每一个顶点到对面边的距离（即高）的长度为 $\frac{\sqrt{2}}{2}$ ，它的平方即为0.5。很奇妙的是，不只是二维，在其余维度下，每一个单形顶点到对面边/面的距离都是0.5。

至此，咱们解释了Simplex噪声的实现。虽然理解上Simplex噪声相比于Perlin噪声更难理解，但因为它的效果更好、速度更优，所以不少状况下会替代Perlin噪声。

效果

下面是Simplex噪声和fbm组合以后的一些效果：

它的主要代码以下：

float simplex_noise(vec2 p)
{
    const float K1 = 0.366025404; // (sqrt(3)-1)/2;
    const float K2 = 0.211324865; // (3-sqrt(3))/6;

    vec2 i = floor(p + (p.x + p.y) * K1);

    vec2 a = p - (i - (i.x + i.y) * K2);
    vec2 o = (a.x < a.y) ? vec2(0.0, 1.0) : vec2(1.0, 0.0);
    vec2 b = a - o + K2;
    vec2 c = a - 1.0 + 2.0 * K2;

    vec3 h = max(0.5 - vec3(dot(a, a), dot(b, b), dot(c, c)), 0.0);
    vec3 n = h * h * h * h * vec3(dot(a, hash22(i)), dot(b, hash22(i + o)), dot(c, hash22(i + 1.0)));

    return dot(vec3(70.0, 70.0, 70.0), n);
}

我仍是要稍微解释下上面的代码。vec2 i即为咱们在第二步中提到的超立方体索引号（也就是超立方体中的(0, 0)点）。vec2 a是在变形前输入点到(0, 0)点的距离向量。接着，咱们经过判断a的x份量和y份量的大小（变形先后不会对结果有影响，所以这里直接使用变形前的距离向量），来获得输入点所在的单形顶点。接着，咱们计算输入点到第二个单形顶点的距离向量vec2 b以及到第三个单形顶点的距离向量vec2 c。而后，咱们计算每一个顶点的 $r^2 - |\boldsymbol{dist}|^2$ ，取 $r^2$ 为0.5，并把结果截取到不小于0的部分，获得每一个顶点的权重vec3 h。以后，咱们计算每一个顶点的梯度向量和距离向量的点乘结果，并和它们的权重相乘获得vec3 n。在把它们相加并返回最终结果前，咱们须要保证返回值的范围在-1到1，这就须要咱们计算n每一个份量相加后的最大值。这个最大值能够在输入点在某一边中点时取得，此时 $|a| = \frac{\sqrt{2}}{2}, |b| = |c| = \frac{1}{\sqrt{6}}$ ，得 $h = (0, \frac{1}{3}, \frac{1}{3})$ 。取最大值时，梯度和距离向量的点乘结果能够认为是二者模的乘积，而梯度模的最大值为 $\sqrt{2}$ ，所以最后和的最大值为：

1 3 4 \cdot 1 6 ‾ ‾ \sqrt \cdot 2 ‾ ‾ \sqrt \cdot 2 \approx 1 70

${\frac{1}{3}}^4 \cdot \frac{1}{\sqrt{6}} \cdot \sqrt{2} \cdot 2 \approx \frac{1}{70}$

所以，咱们最后把结果乘以70。那么，若是 $r^2$ 取0.6，最后须要乘以多少呢？答案大约为24.51。利用这个想法，咱们能够在任意维度下计算最后的伸缩值，例如在三维下，单形，即正四面体的边长为 $\frac{\sqrt{3}}{2}$ ，当 $r^2$ 取0.5时，最后大概须要乘以31.32。

可平铺的噪声

这部分是新加的。可平铺的噪声就是指那些能够tiling的、seamless的噪声，由于不少时候咱们想要让噪声纹理能够无缝链接，例如在生成地形时。按照咱们以前提到的方法直接产生噪声，获得的噪声纹理实际上是不能够平铺的，你能够看生成纹理的左右、上下实际上是不同的。那么，怎么生成可平铺的噪声纹理呢？

我直接说目前公认比较好的一种方法，就是在2n维上计算n维可平铺噪声。咱们以二维噪声为例，若是咱们想要获得二维的无缝Perlin噪声，就须要用四维噪声算法来产生。这种方法是思想是，因为咱们想要每一个维度都是无缝的，也就是当该维度的值从0变成1的过程当中，0和1之间比较是平滑过渡的，这让咱们想起了“圆”，绕圆一周就是对该维度的采样过程，这样就能够保证无缝了。所以，对于二维噪声中的x轴，咱们会在四维空间下的xz平面上的一个圆上进行采样，而二维噪声的y轴，则会在四维空间下的yw平面上的一个圆上进行采样。这个转化过程很简单，咱们只须要使用三角函数sin和cos便可把二维采样坐标转化到单位圆上。一样，三维空间的也是相似的，咱们会在六维空间下计算。这种方法不只适用于Perlin噪声，像Worley噪声这种也一样是适合的。

固然上述方法也有本身的缺点，最明显的就是计算量大大增长，通常噪声的复杂度为 $O(2^n)$ （Simplex噪声例外，是 $O(n^2)$ ），是指数增长的。可是因为噪声纹理通常只须要前期计算一次便可，所以大部分时候是能够承担的。

代码的话，Unity Wiki里给出了二维可平铺的Simplex噪声的实现，关键代码以下：

//X, Y is [0..1]
public static float SeamlessNoise( float x, float y, float dx, float dy, float xyOffset ) {
    float s = x;
    float t = y;

    float nx = xyOffset + Mathf.Cos(s * 2.0f * Mathf.PI) * dx / (2.0f * Mathf.PI);
    float ny = xyOffset + Mathf.Cos(t * 2.0f * Mathf.PI) * dy / (2.0f * Mathf.PI);
    float nz = xyOffset + Mathf.Sin(s * 2.0f * Mathf.PI) * dx / (2.0f * Mathf.PI);
    float nw = xyOffset + Mathf.Sin(t * 2.0f * Mathf.PI) * dy / (2.0f * Mathf.PI);

    return Noise(nx, ny, nz, nw);
}

其中，xyOffset是指在四维空间某个平面上的偏移，即这个单位圆是以xyOffset为圆心的。全部能够用这种方法来产生无缝噪声的实现都和上面的代码是同样的，它们的区别仅仅在于Noise(nx, ny, nz, nw)的实现，若是它是四维Perlin噪声，那就会产生二维可平铺的Perlin噪声，若是是四维的Worley噪声，就会产生二维可平铺的Worley噪声。

若是你有兴趣更深刻地理解这种方法，能够阅读下面的一些文章：

这是出处：http://www.gamedev.net/blog/33/entry-2138456-seamless-noise/
一个有图示的文章，帮助理解：http://ronvalstar.nl/creating-tileable-noise-maps
Unity wiki对于二维无缝Simplex噪声的实现：http://wiki.unity3d.com/index.php/Tileable_Noise
GameDev上关于可平铺噪声的讨论：http://gamedev.stackexchange.com/questions/23625/how-do-you-generate-tileable-perlin-noise

扩展阅读

网上有不少优秀的阅读的资料，这里只是我找到的一小部分（wiki我就不说了，通常是必看的）：

Perlin噪声
- 这篇详细地解释了真正的Perlin噪声以及和fbm的结合：http://flafla2.github.io/2014/08/09/perlinnoise.html
- 2005年的这篇论文11的开头部分也给出了不错的Perlin噪声的解释：http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
- GPU Gems的文章：http://http.developer.nvidia.com/GPUGems/gpugems_ch05.html
- GPU Gems 2的文章：http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter26.html
- 大牛scrawk的博客在Unity里实现了GPU Gems里面的方法：https://scrawkblog.com/2013/05/18/gpu-gems-to-unity-improved-perlin-noise/
Value噪声
- 这个课程比较详细地讲了噪声的来源、应用和实现：http://scratchapixel.com/old/lessons/3d-advanced-lessons/noise-part-1/
- 网络上不少号称是Perlin噪声的文章讲的其实都是Value噪声。好比这篇很是著名又挺有意思的文章：http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
Simplex噪声
- 这篇文章讲得很细，若是你想再理解下三维的Simplex噪声能够看看：http://catlikecoding.com/unity/tutorials/simplex-noise/
- Shadertoy上也有三维Simplex噪声的实现：https://www.shadertoy.com/view/XsX3zB和个人https://www.shadertoy.com/view/4sc3z2。
fbm
- 其实几乎全部讲噪声的都会讲和fbm的结合。这篇文章单独拿出来说了：https://code.google.com/p/fractalterraingeneration/wiki/Fractional_Brownian_Motion
hash
- 在计算随机值和随机梯度时每每都须要使用哈希函数来进行预计算或实时计算，Shadertoy上有我的总结了不一样数据类型组合下的哈希函数：https://www.shadertoy.com/view/4djSRW

参考文献

Perlin K. Course in advanced image synthesis[C]//ACM SIGGRAPH Conference. 1984, 18. ↩
Perlin K. An image synthesizer[J]. ACM Siggraph Computer Graphics, 1985, 19(3): 287-296. ↩
Perlin K, Hoffert E M. Hypertexture[C]//ACM SIGGRAPH Computer Graphics. ACM, 1989, 23(3): 253-262. ↩
Perlin K. Making noise[C]//Proc. of the Game Developer Conference. 1999. ↩
Perlin K. Improving noise[C]//ACM Transactions on Graphics (TOG). ACM, 2002, 21(3): 681-682. ↩
Perlin K. Improving noise[C]//ACM Transactions on Graphics (TOG). ACM, 2002, 21(3): 681-682. ↩
Perlin K. Improving noise[C]//ACM Transactions on Graphics (TOG). ACM, 2002, 21(3): 681-682. ↩
Perlin K. Making noise[C]//Proc. of the Game Developer Conference. 1999. ↩
Perlin K. Noise hardware[J]. Real-Time Shading SIGGRAPH Course Notes, 2001. ↩
Gustavson S. Simplex noise demystified[J]. Linköping University, Linköping, Sweden, Research Report, 2005. ↩
Gustavson S. Simplex noise demystified[J]. Linköping University, Linköping, Sweden, Research Report, 2005. ↩