Perlin噪聲

柏林雜訊（Perlin noise）指由Ken Perlin發明的自然噪聲生成演算法，具有在函數上的連續性，並可在多次調用時給出一致的數值。在電子遊戲領域中可以透過使用Perlin噪聲生成具連續性的地形；或是在藝術領域中使用Perlin噪聲生成圖樣。由於Perlin本人的失誤，Perlin噪聲這個名詞現在被同時用於指代兩種有一定聯繫的的噪聲生成演算法。這兩種演算法都廣泛地應用於電腦圖形學，因此人們對這兩種演算法的稱呼存在一定誤解。下文中的Simplex噪聲和分形噪聲都曾在嚴肅學術論文中被單獨的稱作Perlin噪聲。

本文僅討論灰度圖的情況。對於彩色圖像的噪聲生成，只要將同樣的方法分別應用於各個顏色分量上，再加以合成即可。

## Simplex噪聲

生成噪聲最通常的想法是為每個像素賦予一個隨機的灰度值。如此產生的圖像如下圖左。

- 使用隨機方法產生的白噪聲
- 左圖的頻譜
- 對隨機噪聲進行柔化
- 左圖的頻譜

用隨機法產生的噪聲圖像和顯然自然界物體的隨機噪聲有很大差別，不夠真實。1985年Ken Perlin指出，一個理想的噪聲應該具有以下性質：

- 對旋轉具有統計不變性。
- 能量在頻譜上集中於一個窄帶，即：圖像是連續的，高頻分量受限。
- 對變換具有統計不變性。

對於電腦圖形學中的普遍應用，噪聲應該是偽隨機的，兩次調用應得到同樣的結果。

上圖的噪聲之所以不夠真實是因為它的能量在頻譜中平均分布，即它是白噪聲。對白噪聲進行柔化處理後限制了噪聲的頻譜，比之前者和自然界中的噪聲現象更加接近，但是依然不能令人滿意。

### 經典Perlin噪聲

Perlin在上述文章中提出了一種產生符合要求的一維噪聲函數的簡單方法，這是後續工作的基礎：

- 在一維坐標軸上，選擇等距的無窮個點，將值空間劃分為等長的線段（為方便起見，選擇坐標值為整數的點），為每個點隨機指定一個值。
- 對於坐標值為整數的點，將該點對應的值作為噪聲圖像上該點的值；對於坐標值不為整數的點，將相鄰兩點的值進行插值運算，獲得該點的數值(灰度)。

插值使用的函數是一個在0處為1，在1處為0，在0.5處為0.5的連續單調減函數。例如，設 $c_0, c_1$ 為左右兩整數點的數值，$t$ 為該點距離左邊點的距離，使用 $(1-t)$ 作為插值函數，則該點的值為 $c_1(1-t) + c_0t$。

$(1-t)$ 是線性插值，得到的結果人工痕跡嚴重，且在整數點上不連續。Perlin建議使用 $3t^2 - 2t^3$ 作為插值函數，後來又建議使用 $6t^5-15t^4+10t^3$ 作為插值函數；事實上，只要是在區間0,1內連續的函數$f$，有$f(0)=1$，$f(1)=0$且$f'(0)=f'(1)=0$的函數皆可做為插值函數。實際應用如下：設$f$為插值函數，插值結果為$c_0f(1-t) + c_1f(t)$。

對於二維的情況，可以將上述演算法進行推廣，即：

- 為所有坐標為 $(x, y)$ 且 $x, y$ 都是整數的點指定一個值，同時指定一個梯度，這些點將空間分成方格。
- 對於坐標軸為整數的點，即上述方格的頂點，將為它指定的值作為該點的值；對於某個方格內部的點 $(x, y)$，用所在方格四個頂點的值和梯度進行插值。

例如，對於點 $(x, y)$，令 $i = \lfloor x \rfloor, j = \lfloor y \rfloor$ 它所在方格的四個頂點分別為： $(i, j)$、$(i+1, j)$、$(i+1, j+1)$、$(i, j+1)$。令 $u=x-i, v = y-j$，這四個頂點對點 $(x, y)$ 的貢獻可以用它們的梯度（$g_{00}, g_{10}, g_{11}, g_{01}$）和 $(x, y)$ 點與這四個頂點的方向（$(u, v)$、$(u-1, v)$、$(u-1, v-1)$、$(u, v-1)$）進行點積獲得。但是在二維的情況下，插值更為複雜。首先需要對 $(i, j)$ 和 $(i+1, j)$ 兩點在 $x$ 方向插值，得到點 $(x, j)$ 的值；之後對 $(i, j+1)$ 和 $(i+1, j+1)$ 兩點在x方向插值，得到點 $(x, j+1)$ 的值；最後對 $(x, j)$ 和 $(x, j+1)$ 在 y 方向插值，得到 $(x, y)$ 的值。

在三維的情況下，需要進行七次插值。可以證明，插值次數隨著維數的增長指數增長。

經典Perlin噪聲基本滿足Perlin提出的噪聲條件。但是由於 $3t^2 - 2t^3$ 導數中含有線性分量，在計算相鄰點差時會體現出人工效果，不夠自然。經典Perlin噪聲在進行下文的分形和運算後效果不夠自然。

### 經典Perlin噪聲的軟體實現

為了達到偽隨機性，經典Perlin噪聲（和隨後的Simplex噪聲）通過在一個轉置陣列中查詢點的坐標求每個點的梯度，而不使用隨機數發生器。這樣兩次調用可以獲得同樣的結果，達到偽隨機性。理論上轉置陣列可以任意指定，但是後續的實現都使用Perlin最初提出的陣列：

```c
unsigned char perm[256] = {151,160,137,91,90,15,
  131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
  190,6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
  88,237,149,56,87,174,20,125,136,171,168,68,175,74,165,71,134,139,48,27,166,
  77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
  102,143,54,65,25,63,161,1,216,80,73,209,76,132,187,208,89,18,169,200,196,
  135,130,116,188,159,86,164,100,109,198,173,186,3,64,52,217,226,250,124,123,
  5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
  223,183,170,213,119,248,152,2,44,154,163,70,221,153,101,155,167,43,172,9,
  129,22,39,253,19,98,108,110,79,113,224,232,178,185,112,104,218,246,97,228,
  251,34,242,193,238,210,144,12,191,179,162,241,81,51,145,235,249,14,239,107,
  49,192,214,31,181,199,106,157,184,84,204,176,115,121,50,45,127,4,150,254,
  138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180};
```

以下用python示例如何生成一維Perlin噪聲，更高維的情形可以在這個基礎去推廣：

```python
from math import floor

#Perlin 最初提出的数组
SEQ = [
  151,160,137,91,90,15,
  131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
  190,6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
  88,237,149,56,87,174,20,125,136,171,168,68,175,74,165,71,134,139,48,27,166,
  77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
  102,143,54,65,25,63,161,1,216,80,73,209,76,132,187,208,89,18,169,200,196,
  135,130,116,188,159,86,164,100,109,198,173,186,3,64,52,217,226,250,124,123,
  5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
  223,183,170,213,119,248,152,2,44,154,163,70,221,153,101,155,167,43,172,9,
  129,22,39,253,19,98,108,110,79,113,224,232,178,185,112,104,218,246,97,228,
  251,34,242,193,238,210,144,12,191,179,162,241,81,51,145,235,249,14,239,107,
  49,192,214,31,181,199,106,157,184,84,204,176,115,121,50,45,127,4,150,254,
  138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180]

#插值函数
def _blending(t):
    return t*(t*(t*(10+t*(-15+6*t))))              #6t^5 -15t^4 + 10t^3

def noise(pos):
    if pos%1 == 0:                                 #对于整数点，直接从数列中取得数值即可。
        return SEQ[int(pos%256)]
    else:                                          #对于非整数的点，由左右的整数进行插值运算得出数值。
        x0,x1 = floor(pos)%256,floor(pos+1)%256    #取得非整数点旁的两个整数。
        c0,c1 = SEQ[x0],SEQ[x1]                    #从数列中取得两个整数点的数值。
        t = pos%256 - x0                           #计算非整数点离左边整数点的距离。
        return (c0*_blending(1-t)+c1*_blending(t)) #使用插值函数计算非整数点的数值并输出。
```

使用以上示例中的noise函數便可生成Perlin噪聲。

在生成梯度時，理論上應該任意生成一個長度為1的向量。在實現中，一維的情況下可以在$8, 7, 6, 5, 4, 3, 2, 1, -1, -2, -3, -4, -5, -6, -7, -8$這16個整數中任選一個作為斜率，這樣可以方便的通過對坐標值進行位操作實現。二維的情況下，梯度可以從$(1,2), (2,1), (-1,2), (-2, 1), (-1, -2), (-2, -1), (1, -2), (2, -1)$這8個向量之中隨機選擇一個。這8個向量具有相同的長度，因此點積後的歸一化計算可以省略。三維的情況下，梯度可以從以原點為中心，邊長為2的正方體每邊的中點共12個向量中選擇，即從$(0, 1, 1), (0, 1, -1), (0, -1, -1), (0, -1, 1), (1, 0, 1), (1, 0, -1), (-1, 0, -1), (-1, 0, 1), (1, 1, 0), (-1, 1, 0), (-1, -1, 0), (1, -1, 0)$中選擇一個。在實際實現時也可以通過位操作進行。

### Simplex噪聲

- 使用Simplex方法產生噪聲
- 左圖的頻譜

為了簡化計算，方便使用硬體實現，Ken Perlin在2002年對他的方法進行了改進，改進的方法稱為 Simplex 噪聲。Simplex 噪聲使用 $6t^5-15t^4+10t^3$作為插值函數，杜絕了導數中的線性部分。另外，Simplex 噪聲演算法有效地降低了插值次數。

如上文，二維經典Perlin噪聲將二維空間用正方形填充，用四個頂點進行3次插值，而Simplex噪聲將二維空間用等邊三角形填充，使用三個頂點進行插值。三維經典Perlin噪聲將三維空間用立方體進行填充，使用8個頂點進行7次插值，三維Simplex噪聲使用正四面體填充空間，用4個頂點進行插值。對於更高維（N維）的情況，經典Perlin噪聲將空間用超立方體填充，頂點數目是$2^N$，而Simplex噪聲使用高維正三角形（稱為Simplex）進行填充，頂點數目為$N+1$。Simplex噪聲插值次數隨維數增長線性增長。

對於二維的情況，使用正三角形填充空間使得直接判斷某點落在哪個正三角形中，計算該三角形的頂點位置變得複雜。在實現上通常通過坐標變換將正三角形映射成直角三角形。使用該方法進行變換可以使用和經典Perlin噪聲相同的方法對頂點進行求值。

### Simplex噪聲和經典Perlin噪聲的應用

Perlin噪聲可以用來模擬自然界中的噪聲現象。由於它的連續性，如果將二維噪聲中的一個軸作為時間軸，得到的就是一個連續變化的一維函數。同樣的也可以得到連續變化的二維圖像。該噪聲可以用來模擬人體的隨機運動，螞蟻行進的線路等。另外，還可以通過計算分形和模擬雲朵，火焰等非常複雜的紋理。

Perlin噪聲對各個點的計算是相互獨立的，因此非常適合使用圖形處理器進行計算。OpenGL在GLSL中定義了一維至四維的噪聲函數noise1、noise2、noise3、noise4，在該規範中噪聲的性質與上述Perlin提出的性質相同。在Mesa 3D實現中，這一組函數是使用Simplex演算法實現的。在硬體的實現中，噪聲的生成可以達到實時效果。

## 分形噪聲

分形噪聲是上述Perlin 1985年的文章中提出的將符合上文所述三條件的噪聲通過計算分形和構造更複雜效果的演算法。

分形噪聲可以用來模擬自然界的自相似過程，包括海岸線，地形，海浪等。分形噪聲的原理是利用Perlin噪聲頻率受限的特性，通過不斷疊加更高頻率的Perlin噪聲達到自相似的效果。

### 一維分形噪聲

在一維的情況下，設噪聲函數為$noise(x)$，則通過$noise(2x), noise(4x)$等就可以構造更高頻率的噪聲。

下圖左邊是一維Perlin噪聲頻率頻率在不斷倍增，振幅不斷倍減的情況，右圖是左邊這些函數求和的圖像。

- 6條頻率倍增的一維Perlin噪聲
- 一維Perlin噪聲分形和右邊的圖像是自相似的，將它放大會得到和原圖相似的效果。

從數學上描述分形噪聲，則是：

$$\sum_t{\frac{\text{Noise}(2^i \text{point})}{2^i}}$$

分形噪聲有時也被稱作$1/f$噪聲。

### 二維分形噪聲

對於二維的情況，可以使用類似的方法進行分形和運算，產生的效果類似於雲層，如下圖所示。

- 二維Simplex噪聲原函數
- 二維Simplex噪聲疊加2倍頻
- 二維Simplex噪聲疊加到4倍頻
- 二維Simplex噪聲疊加到128倍頻

對分形和函數進行一些小修改可以模擬各種複雜效果。

描述｜結果

$\sum_t{\frac{\left|Noise(2^i point)\right|}{2^i}}$

$\sin(x + \sum_t{+ \frac{\left|Noise(2^i point)\right|}{2^i}})$

同上，將三維分形噪聲中的一個軸作為時間軸，可以構造連續動態的噪聲效果。

## 外部連結

- An image synthesizer Ken Perlin在1985年研究像素渲染器時提出了噪聲的性質
- Noise Hardware Ken Perlin在2002年研究用硬體發生噪聲時改進了原有的噪聲生成演算法，新算法稱為Simplex噪聲
- Simplex noise demystified對Simplex noise進行詳細的介紹
- Implementing Improved Perlin Noise Ken Perlin為NVIDIA GPU Gems第一版撰寫了一篇關於Perlin噪聲的短文
- Implementing Improved Perlin Noise NVIDIA GPU Gems第二版中給出的使用Cg生成Perlin噪聲的程序
- Perlin Noise關於一維Perlin噪聲和分形噪聲的簡單介紹
- Ken Perlin的主頁