噪声

Posted on | Edited on

PS：本文讨论的噪声是指用于程序生成随机值的算法

学习资料：

别人的文章写得真好，所以直接做总结吧～

总结

噪声的种类

  • 基于晶格

    • 梯度噪声：Perlin 噪声、Simplex 噪声、Wavelet 噪声等
    • Value 噪声

  • 基于点

    • Worley 噪声（又称：Voronoi 噪声）

Perlin 噪声

函数声明：

1
2
3
public float perlin(float x, float y)
public float perlin(float x, float y, float z)
public float perlin(float x, float y, float z, float w)
  • 常用 2 维、3 维、4 维（可根据算法思路实现更高维）
  • 输入为某点坐标（本文的实现用 float 类型）
  • 输出取值范围：[0,1]
  • 算法时间复杂度： \(O(2^n)\)（n 是维数）

实现

  • 接收输入（浮点型）

  • 计算输入点所在的晶格（整型坐标）（2 维 4 个顶点（正方形）、3 维 8 个顶点（正方体）、4 维 16 个顶点 …）

  • 晶格顶点各自生成一个伪随机的梯度向量

    • 2 维：预计算随机单位向量 G[n]、打乱 0～n-1 顺序的 P[n]，则顶点 (i,j) 的随机梯度向量为: \( g = G[(i + P[j]) \% n] \)

    • 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)

    • 4 维：选取方法与 3 维类似共 32 条单位向量

    • 实际实现中，P[] 长度一般先取 256，为避免缓存溢出，再重复填充一次数组的值，最终长度为 512

  • 计算晶体各顶点到输入点的距离向量

  • 对晶体各顶点的梯度向量和距离向量做点积运算

  • 对点积结果插值，求加权平均

3 维例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// fade() = t * t * t * (t * (t * 6 - 15) + 10);

float x,y,z; // 输入坐标
float g1,g2,g3,g4,g5,g6,g7,g8; // 8 个点积结果
float x1,x2,y1,2;

x1 = lerp(g1,g2,fade(x-(int)x));// PS：实际实现可缓存 fade(x-(int)x) 的值减少计算
x2 = lerp(g3,g4,fade(x-(int)x));
y1 = lerp(x1,x2,fade(y-(int)x));

x1 = lerp(g5,g6,fade(x-(int)x));
x2 = lerp(g7,g8,fade(x-(int)x));
y2 = lerp(x1,x2,fade(y-(int)x));

float result = (lerp(y1,y2,fade(z-(int)z)) + 1)/2; // 输出结果
  • fade() 称为缓和曲线（ease curves）(二阶导满足连续性): $$s(t)=6t^5−15t^4+10t^3$$

Value 噪声

与 Perlin 噪声实现步骤类似，实现更简单，不同之处：

  • 用伪随机值代替晶体顶点的伪随机梯度向量，不需要与距离向量点乘

Simplex 噪声

与 Perlin 噪声实现步骤类似，Simplex 噪声的时间复杂度更优，为 \(O(n^2)\)，不同之处：

  • Simplex 所选的晶体为单形（1 维：线段、2 维：等腰三角形、3 维：四面体、… ）

  • 每个顶点的权重计算：$$(r^2−|\vec {dist}|^2)^4×dot(\vec {dist},\vec {grad})$$

    • dist 是晶体顶点到输入点的距离向量
    • grad 是晶体顶点存储的伪随机梯度向量
    • \(r^2\) 的取值是 0.5 或 0.6：取 0.5 时可以保证没有不连续的间断点，在连续性并不那么明显时可以取 0.6 得到更好的视觉效果

  • 最后将各顶点权重相加再乘以一个系数（为了把结果归一到 [-1,1] 的范围）

难点：找到输入点所在的单形？？？

略具体推导

Worley 噪声

暂不研究

可平铺的（tiling）无缝的（seamless）噪声

目前公认比较好的一种方法，就是在 2n 维上计算 n 维可平铺噪声

具体做法，如：

  • 在二维噪声中画一个圆，可得一维无缝的噪声

  • 在四维的 xz 平面画圆得二维 x 轴的无缝噪声，在四维的 yw 平面画圆得二维 y 轴的无缝噪声

二维无缝噪声实现

1
2
3
4
5
6
7
8
9
10
11
12
//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);
}

  • 其中 Noise() 可以是 Perlin、Simplex、Worley 等

  • xyOffset 是指在四维空间某个平面上的偏移，即这个单位圆是以 xyOffset 为圆心的

分形噪声、FBM（分形布朗运动）

具体实现为：不断叠加更高频率的噪声，如：

$$noise(p)+\frac{1}{2}noise(2p)+\frac{1}{4}noise(4p)+…$$

$$|noise(p)|+\frac{1}{2}|noise(2p)|+\frac{1}{4}|noise(4p)|+…$$

$$sin(x+|noise(p)|+\frac{1}{2}|noise(2p)|+\frac{1}{4}|noise(4p)|+…)$$

三维 Perlin 分形示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public double OctavePerlin(double x, double y, double z, int octaves, double persistence) {
    double total = 0;
    double frequency = 1;
    double amplitude = 1;
    double maxValue = 0;  // Used for normalizing result to 0.0 - 1.0
    for(int i=0;i<octaves;i++) {
        total += perlin(x * frequency, y * frequency, z * frequency) * amplitude;
        
        maxValue += amplitude;
        
        amplitude *= persistence;
        frequency *= 2;
    }
    
    return total/maxValue;
}
  • octaves 为陪频
  • persistence 为持续性
  • amplitude 为振幅