Perlin noise

一、分形噪声
  分形几何学的基本思想是：客观事物具有自相似的层次结构，局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性，称为自相似性。客观自然界中许多事物，具有自相似的“层次”结构，在理想情况下，甚至分形分形至具有无穷层次。适当的放大或缩小事物的几何尺寸，整个结构并不改变。不少复杂的物理现象，背后就是反映着这类层次结构的分形几何学。分形思想的提出让我们了解事物的本质更进一步，同时也提供了一种研究问题的方法，那就是通过叠加来最终模拟出超乎想像的自然物体。更通俗易懂的来说，分形就是把复杂的自然物体分成一个个的简单形态，这有点像傅立叶提出的“任何连续周期信号可以由一组适当的正弦曲线组合而成”，事实证明傅立叶是对的，即便是拉格朗日也阻止不了。反过来说，可以由简单的形态通过无限次的叠加来模拟自然现象。 

  这是计算机图形学家利用分形理论通过迭代算法最终生成的精美图像。分形理论打开了图形学描述自然的一扇大门，影响着图形学、几何学的发展。在了解完分形概念之后，我们再来回顾一些基本知识。 

波长(Wavelength)：指的是两个波谷（波峰）之间的距离 
振幅(amlitude)：指波的高度 
频率(frequency)：指的是波的振动快慢，频率就是1/波长 
在正弦波中，他们非常容易区分。在噪声波中，也有波长，振幅，频率之分，如下图所示。 

波长(Wavelength)：指的是波峰与波谷之间的距离 
振幅(amlitude)：指波的高大高度 
频率(frequency)：指的是波的振动快慢，频率就是1/波长
持续度（Persistence）：这个词是由《大自然的分形几何学》[波] 伯努瓦·B. 曼德布罗特（Mandelbrot）引入的，Mandelbrot开创了分形几何先河。持续度指的是表示每个频率下的振幅，也可以看成是柔合了频率和振幅，或者说是分形中某种单一层次分形波的特征，持续度展示了叠加的每个组成部分：

frequency=2ifrequency=2i
amplitude=persistenceiamplitude=persistencei
下图中，Persistence值分别为 1/4, 1/2 与 3/4。可以看出不同的Persistence值对每个倍频的频率和波幅以及最后结果的影响。（注：以下若干图片来自参考文献3） 

倍频 （Octaves）：从字面上来理解，倍频就是加倍的频率，也是分形叠加中叠加的某种单一层次分形波的特征，倍频不一定是2倍，也可以是其他倍数，如4倍频与8倍频，倍频越高越多，最后得到的波形包含的细节越多，也越自然。

  为加深理解，我们来看看在频率加倍，振幅减半的一维perlin 噪声。 

  可以看到，随着频率的升高，在同一尺度下提供了更高的细节，但波动（振幅）影响的范围却更小了。为更直观的演示这种效果，我们分形叠加不同的倍频，分别是1倍频，2倍频，4倍频与8倍频。 

  可以看到倍频数越高，Perlin噪声就越精细，但整体形状不会有很大的改变。这符合自然现象。最平常的例子是山峰轮廓，它包含着高度上的很大变化（山峰），中等变化（丘陵），小的变化（砾石），微小变化（石头）…你可以继续想象。所以在我们程序中，我们用低频率，大振幅来模拟大尺度变化，用高频率，小振幅来模拟小尺度的变化，并将之分形叠加，最终达到我们想要的效果。
二、分形布朗运动
  布朗运动（Brownian movement） 指微小粒子表现出的无规则运动。1827年英国植物学家R.布朗在花粉颗粒的水溶液中观察到花粉不停顿的无规则运动。进一步实验证实，不仅花粉颗粒，其他悬浮在流体中的微粒也表现出这种无规则运动，如悬浮在空气中的尘埃。后人就把这种微粒的运动称之为布朗运动。这里我们要讲的布朗运动跟这个有点区别，要讲清分形布朗运动还得从《大自然的分形几何学》和最简单的正弦波入手，本篇开篇我们即阐明了：客观事物具有自相似的层次结构，局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性，称为自相似性。这是分形学的最重要的结论。下面我们从正弦波入手来分别讲解。 
  正弦波是最简单的波形之一，正弦波有个非常有意思的特性，那就是波可以叠加。如下： 

图上一个是频率为1的正弦波，另一个是频率为2的正弦波，通过叠加产生了一个新的波，这个波的振幅由这两个波通过简单的加减构成。不仅是正弦波，其他波也有类似的叠加特性。在音乐中，每一个音阶都对应着特定的频率，频率加倍或者减半对应着另一个八度音阶（octave），可以看到octave这个词是从音乐中引用过来的，前面我们翻译成倍频，根据我们刚说的，octave对应频率的加倍或减半而不是加1.5倍或减0.4倍。我们稍后也会对噪声作类似处理。 
  现在我们由正弦波来讨论Perlin噪声（下图是一维Perlin噪声图），Perlin噪声有着和正弦波一样的振幅和频率，虽然这个振幅和频率在一定的范围内波动，虽然不像正弦波那样规律，但我们还是可以看得出振幅和频率只是在一定范围内的合理偏离。由波的叠加可知，利用Perlin噪声不同倍频波的叠加可以很容易的更随机的波形。 

  我们通过一个步进值（lacunarity）逐渐的增大频率，同时也同过一个增益值（gain）逐渐的减小振幅，主可以得到不同的倍频（octaves），然后再将不同的倍频叠加，这种技术就叫分形布朗运动（fractal Brownian Motion（fBM） )。简单的分形布朗运动可以由下面的代码生成。

const int octaves = 2;
float lacunarity = 2.0;
float gain = 0.5;
float amplitude = 1.;
float frequency = 1.;

// 叠代 octaves，y纵轴，x为横轴
for (int i = 0; i < octaves; i++) 
{
    y += amplitude * noise(frequency*x);
    frequency *= lacunarity;
    amplitude *= gain;
}

  下面是octaves为2，4，8时的一维Perlin噪声，可以看到叠加的octave越多，噪声的细节就越多，另外一个值得注意的地方是，叠加的细节与原波形具备宏观上的相似性，这就是我们说过的分形的最重要的特征。 

  分形布朗运动是分形几何里的重要概念，理论上叠加无限多的octave,可以得到无限细节的分形几何图形，在实际运用中，过多的叠加会削弱图形性能，根据需要取合适的值。
三、Perlin noise原理
  Perlin noise原理很简单： 
  第一步：定义一个晶格结构，每个晶格的顶点有一个“伪随机”的梯度向量。对于二维的Perlin噪声来说，晶格结构就是一个平面网格，三维的就是一个立方体网格。 
  第二步：输入一个点（二维的话就是二维坐标，三维就是三维坐标，n维的就是n个坐标），我们找到和它相邻的那些晶格顶点（二维下有4个，三维下有8个，n维下有2n2n个），计算该点到各个晶格顶点的距离向量，再分别与顶点上的梯度向量做点乘，得到2n2n个点乘结果。 
  第三步：使用缓和曲线（ease curves）来计算它们的权重和。在原始的Perlin噪声实现中，缓和曲线是s(t)=3t2−2t3s(t)=3t2−2t3，在2002年的论文6中，Perlin改进为s(t)=6t5−15t4+10t3s(t)=6t5−15t4+10t3。由高等数学可以知道，函数越是高阶可导函数曲线越是平滑，s(t)=3t2−2t3s(t)=3t2−2t3在一阶导满足连续性，但它的二阶导在晶格顶点处（即t = 0或t = 1）不为0，会造成明显的不连续性。s(t)=6t5−15t4+10t3s(t)=6t5−15t4+10t3在二阶导上仍然满足连续性。 
  这就是计算Perlin噪声的逻辑和流程。下面我们以二维Perlin噪声为例加以说明： 
第一步：构建一个二维平面，同时生成每个顶点的“伪随机”的梯度向量： 

  这里，每个顶点各自生成一个伪随机的梯度向量。梯度向量代表该顶点相对单元正方形内某点的影响是正向还是反向的（一会我们会看到梯度向里对最终效果的影响）。而伪随机是指，对于任意组相同的输入，必定得到相同的输出。虽然每个顶点生成的梯度向量看似随机，实际上并不是。这保证了在生成函数不变的情况下，每个坐标的梯度向量都是确定不变的。同时，这些梯度向量并不是完全随机的，而是由单位正方体（3维）的中心点指向各条边中点的12个向量： 
(1,1,0),(-1,1,0),(1,-1,0),(-1,-1,0), (1,0,1),(-1,0,1),(1,0,-1),(-1,0,-1), (0,1,1),(0,-1,1),(0,1,-1),(0,-1,-1) 
采用这些特殊梯度向量的原因在Ken Perlin’s SIGGRAPH 2002 paper: Improving Noise这篇文章里有具体说明。主要是为了避免“镜像”现象。 
第二步：输入一个点，找到和它相邻的那些晶格顶点： 

找到输入点所在的晶格的顶点梯度向量: 

接着，求出另外4个距离向量，它们分别从各顶点指向输入点（蓝色点）: 

接下来，对相应的顶点梯度向量与距离向里作点积运算。从点积的特性可知：当两个向量的夹角小于90度时点积结果为正；当两个向量夹角大于90度时点积结果为负；当两个向量夹角等于90度时点积结果为0。因此点积后的结果图如下： 

此图很直观的表现了梯度向量对最终效果的影响，这也是Perlin噪声最终外观表现的内在原因。 
第三步：对4个顶点的影响值做插值，缓和曲线的值会用来计算插值因子，这样插值变化不再是单调的线性变化，而是这样一个过程：初始变化慢，中间变化快，结尾变化又慢下来（也就是在当数值趋近于整数时变化变慢，或者说是接近固定点时变化速率变缓）。我们用Perlin改进的缓和曲线s(t)=6t5−15t4+10t3s(t)=6t5−15t4+10t3。 
这就是Perlin噪声生成的原理同时也是步骤，理解起来不难。这里也可以看到，梯度值在生成噪声中影响可谓是举足轻重，这也是Perlin噪声叫作梯度噪声的来源。
四、小结
  本篇文章主要关注了分形噪声，分形布朗运动，介绍了Perlin噪声原理，通过上文，我们可以看到，分形噪声跟噪声一点关系都没有，分形布朗运动跟运动一点关系都没有，不要仅仅局限于字面的理解，更要理解概念的实质，这更重要。 
参考文献： 
1、《大自然的分形几何学》[波] 伯努瓦·B. 曼德布罗特（Mandelbrot） 
2、Perlin Noise http://freespace.virgin.net/hugo.elias/models/m_perlin.htm 
3、关于噪声的一些基本定义 http://www.gamersky.com/handbook/201601/708963_2.shtml?tag=wap 
4、Fractal Brownian Motion https://thebookofshaders.com/13/ 
5、Understanding Perlin Noise ，https://flafla2.github.io/2014/08/09/perlinnoise.html 
6、谈谈噪声 http://blog.****.net/candycat1992/article/details/50346469