Perlin_noise

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

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

## Simplex 噪聲

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

* * * *

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

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

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

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

### 經典 Perlin 噪聲

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

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

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

 $(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_{0}f(1-t)+c_{1}f(t)$ 。

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

1. 為所有坐標為 $(x,y)$ 且 $x,y$ 都是整數的點指定一個值，同時指定一個梯度，這些點將空間分成方格；
2. 對於坐標軸為整數的點，即上述方格的頂點，將為它指定的值作為該點的值；對於某個方格內部的點 $(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 最初提出的數組：

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

使用以上示例中的 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 噪聲

* *

為了簡化計算，方便使用硬體實現，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 噪聲頻率頻率在不斷倍增，振幅不斷倍減的情況，右圖是左邊這些函數求和的圖像。

* *

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

$$
\sum _{t}{\frac {Noise(2^{i}point)}{2^{i}}}
$$

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

### 二維分形噪聲

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

* * * *

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

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

## 參考文獻

## 外部連結

* 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 的主頁（頁面存檔備份，存於網際網路檔案館）