随机与噪声

发表于 2020-04-11 分类于笔记

前言

随机和噪声是计算机图形生成艺术中的常用手段，可以利用随机和噪声构建出迷人又不尽相同的图案。

随机

一个随机的过程是一个不定因子不断产生的重复过程，但它可能遵循某个概率分布。

—— https://zh.wikipedia.org/wiki/随机性

随机数：即随机产生的数字，计算机中常用的随机算法都是产生一个[0, 1)之间的数；随机数最重要的特性是它在产生时后面的那个数与前面的那个数毫无关系。
伪随机（确定性随机）：即通过一个固定的计算函数来获取一个『随机』数，只要初值（随机种子）相同，得到的随机数就是相同的，得到随机数就是伪随机数，但是它们具有类似于随机数的统计特征。

伪随机函数

注：这里提及的伪随机函数只是简单地使用一些常见函数模拟出一个伪随机数，与『伪随机数生成器』有一定区别；

伪随机函数有以下几个特点：

足够混乱（相邻的种子数得到的『随机数』应该有较大差别）
~~周期应该比较长~~
不太容易预测出『随机值』（虽然确实有具体的函数描述）

相似概念：伪随机数生成器（pseudo random number generator，PRNG）；

三角函数

显然，初始的三角函数都不够混乱；要使得三角函数看起来足够混乱，有以下一些方法：

使周期变小，小到无法分辨；

上面这个图像是函数 $y = |sin(x * 545673.42)|$ 生成的随机数图像，可以看到取得周期数极小，得到的随机图像也是『杂乱无章』，但是如果周期数与当前系统的最小精度之间存在倍数关系时，就会出现很有规律的随机值分布，如 $y = |sin(x * 4153745.42)|$ ：
使长度变大，截取小数部分（相当于放大小数部分）；

上述图像是函数 $y = fract(sin(x) * 85595.42)$ 得到的随机数分布图像；可以很明显的看到在函数极值处有比较明显的分割；且这种方法也同样存在第一种方法的问题，即放大倍数过大时，以至于得到的随机数分布出现比较规律的变化，如 $y = fract(sin(x) * 23485595.42)$ ：
两种方法结合可以避免一些问题：

函数为： $y = fract(sin(x / 84.462) * 59595.42)$ ；通过同时放大小数部分，提高函数周期，可以使得到的随机数分布更均匀，更『随机』；

取小数部分

实际上，直接通过取一维线性函数的小数部分也能得到比较混乱的随机数分布； $y = fract(x)$ 的周期就是 $1$ ，然后缩小周期（对于一维线性函数来说，同时也是放大小数部分）至无法分辨即可：

函数为： $y = fract(x * 68875.42)$

降维

有时候需要对一个二维及以上的向量生成一个随机数，这时候需要将向量降维至一维值，然后再使用伪随机函数生成伪随机数；而降维的方法就是向量点乘，通过将输入值点乘一个相应维度的固定向量值得到一个降维后的值。

噪声

简单地可以这么理解：噪声 = 随机数之间的插值；

数学的数值分析领域中，内插或称插值（英语：interpolation）是一种通过已知的、离散的数据点，在范围内推求新数据点的过程或方法。

一维线性插值

假设有 $a$ 和 $b$ 两个值，则根据插值系数 $k(\in[0,\ 1])$ ，可以得到插值 $c$ ：

c = a + k * (b - a)

一维多项式插值

同上的假设：

\begin{cases} u &= \displaystyle\sum_{i=1}^n{p_i * k^i},\ (p_i\text{是对应项的系数}) \\ c &= a + u * (b - a) \end{cases}

一般来说，插值函数需要满足在定义域为 $[0,\ 1]$ 上的值域为 $[0,\ 1]$ 这个条件；

三次多项式插值

在噪声的插值中，用的最多的插值方法就是三次多形式插值了；因为三次多项式插值具有平滑且计算快的特点。GLSL内置的smoothstep()函数本质上就是一个三次多项式插值函数，插值效果如下所示：

其插值函数为：

u(k) = 3*k^2 - 2*k^3

也就是著名的 Perlin 噪声的三次多项式形式！

Perlin 噪声

Perlin噪声满足以下特征^[1]：

对旋转具有统计不变性；
能量在频谱上集中于一个窄带，即：图像是连续的，高频分量受限；
对变换具有统计不变性。

经典的 Perlin 噪声有两种形式：

三次多项式：

u(k) = 3*k^2 - 2*k^3

五次多项式：

u(k) = 6*k^5 - 15*k^4 + 10 * k^3

二维插值

二维插值的原理就是在插值点附近的方格（矩形）顶点之间进行三次一维插值：即先对x方向进行两次插值得到插值点上下两个插值（即下图的 $(x + a, y)$ 和 $(x + a, y + 1)$ 两个点的插值），然后利用这两个点再对y方向做一次插值即可得到 $(x + a, y + b)$ 点的插值！

最后可以得到点 $(x + a, y + b)$ 的插值为：

f'(x + a, y + b) = \begin{bmatrix} 1 - u(a) & u(a) \end{bmatrix} \begin{bmatrix} f(x, y) & f(x, y + 1) \\ f(x + 1, y) & f(x + 1, y + 1) \end{bmatrix} \begin{bmatrix} 1 - u(b) \\ u(b) \end{bmatrix}

推导过程我就懒得用latex写一遍了，看图吧：

其中 $u(k)$ 就是各类一维插值函数；联系到噪声本身，其中四个顶点的值就是当前方格四个顶点位置的随机值。这里有一个简单2D噪声生成的demo。

其它更高维的插值可以以此类推，可以想象当维度变大时，插值次数会呈指数型增长！

Simplex 噪声

Simplex噪声是Ken Perlin（没错，就是Perlin噪声的提出者）提出的更自然，性能更好的噪声算法。

其不同的地方在于：

在二维插值的时候，不使用正方形的四个顶点进行插值，而是使用等边三角形的三个顶点进行插值；更高维的插值也是如此，也就是说N维的插值只需要N+1个点！比传统的指数型增长相比改善显著！
使用五次多项式进行插值，使边界处的衔接更平滑。

如何在二维平面构建等边三角形单元格？The Book of Shaders提到了一个巧妙的构建方法：首先将正方形单元格平分为两个等腰三角形，然后进行斜切变换将等腰三角形变成等边三角形^[2]！

前言

随机