パーリンノイズ

thumb|right|128px|3次元パーリンノイズの2次元スライス
**パーリンノイズ**（英: **Perlin noise**）とは、コンピュータグラフィックスのリアリティを増すために使われるテクスチャ作成技法。擬似乱数的な見た目であるが、同時に細部のスケール感が一定である。このため制御が容易であり、各種スケールのパーリンノイズを数式に入力することで多彩なテクスチャを表現できる。パーリンノイズによるテクスチャは、CGIで自然な外観を物に与えるためによく使われる。

が Mathematical Applications Group, Inc. で勤務しているときに開発した。彼はこの業績により、1997年、映画芸術科学アカデミーからアカデミー科学技術賞（Technical Achivement）を受賞した。

パーリンノイズは (x,y,z) または (x,y,z,time) の関数として実装され、事前に計算された勾配に従って内挿を行い、時間的/空間的に擬似乱数的に変化する値を生成する。ケン・パーリンは2002年に実装を改善し、より自然に見えるようにした（外部リンク参照）。

パーリンノイズは、コンピュータグラフィックスで炎や煙や雲を表現するのによく使われている。また、メモリ使用量が少ないため、メモリ容量が小さい場面でのテクスチャ生成にも使われ、パソコンゲームでのリアルタイムCG生成時にGPU上で使われることが増えている。

2001年、パーリン氏はパーリンノイズの制限に対処した、n次元対応と高次元での計算オーバーヘッドを低くしたシンプレックスノイズ()を発表した。

## アルゴリズムの詳細
パーリンノイズは一般的には2～4次元の関数として実装されるが、任意次元に対して定義することも可能である。典型的な実装では、ランダムな勾配ベクトルのグリッドを定義する、各勾配ベクトルとそのオフセットとの内積を計算する、得られた値を補完する、という3段階から成る。

### グリッドの定義

各グリッドの交差点にランダムなn次元単位勾配ベクトルを割り当てたn次元グリッドを定義する。(1次元の場合のみ勾配は-1から1のランダムなスカラー値が割り当てられる)

### 内積の計算

対象となる任意の点に対する値を計算するため、まずその点が含まれるセルを計算し、そのセルの2^n個の交点に割り当てられた勾配ベクトルを特定する。次に、各交点に対し、オフセットを計算する。ここで、オフセットとは交点から対象となる点への変位ベクトルである。

各交点に対し、勾配ベクトルとオフセットの内積を計算する。この内積は対象となる点がグリッドの頂点に重なっている場合0となる。

2次元グリッド上の点であれば4つのオフセットおよび内積の計算が必要となり、3次元では8つ必要である。一般にはこのアルゴリズムの計算量はn次元の場合に \mathrm{O}(2^n) となる。

### 値の補完

最後の手順は 2^n 個の内積間の補完である。補完は2^n個のグリッド交点において1階微分(あるいは2階微分も) 0となるような関数を用いて行う。したがって、グリッド頂点に近い点では、出力はその交点の勾配ベクトルとオフセットの内積に近い値となり、これは各交点でノイズ関数が必ず0を通ることを意味する。これによりパーリンノイズは特徴的な見た目を有することになる。

n=1であれば、グリッド交点0での値 a_0 とグリッド交点1での値 a_1 間で値を補完する関数の例を示す:f(x)=a_0+\mathrm{smoothstep}(x)\cdot (a_1-a_0)\ (0\leq x\leq 1)この例ではsmoothstep関数が使われている。

コンピュータグラフィックスで利用されるノイズ関数は一般的に[-1.0, 1.0]の範囲で値を生成し、場合に応じてスケーリングされる。

## 勾配順列
パーリンによるオリジナルの実装では、各グリッド交点に割り当てる勾配ベクトルを決定するために、簡単なハッシュスキームが使われた。 事前に計算された順列テーブルは、与えられたグリッド座標をランダムな数値に変換するために利用される。オリジナルの実装では256交点のグリッドを扱っていたため、以下に示すような順列テーブルが含まれている。
```c
int permutation[] = { 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 };
```
この特定の順列が必須である訳ではないが、0から255までの整数がランダムに配列された順列が必要である。 順列テーブルを用いて勾配ベクトルを取得する際には、グリッド交点座標の各成分について、前の成分を参照した値に次の成分を足して参照することを繰り返す。例えば、オリジナルの実装ではこれを3次元で以下のように行っている。
```java
// 255を超える値は順列テーブルを2周繰り返すことで処理される。
static final int p[] = new int[512];
static { for ( int i = 0; i < 256; i++ ) p[256 + i] = p[i] = permutation[i]; }

int hash = p[ p[ p[ X ] + Y] + Z];
```
得られたハッシュの下位4ビットを参照し、12個の勾配ベクトルの中からそのグリッド交点に割り当てるものをひとつ選ぶ。

## 計算量
ノイズ関数の各評価ごとに、オフセットと勾配ベクトルの内積を点が含まれるセルの各頂点に対して計算しなければならない。したがって、n次元のパーリンノイズの計算量は \mathrm{O}(2^n) となる。 シンプレックスノイズやOpenSimplexノイズはよりよい計算量で似た結果を生成するパーリンノイズの大体アルゴリズムである。

## 脚注

## 関連項目
* フラクタル地形

## 外部リンク
* Making Noise Ken Perlin
* Ken Perlin のホームページ
* Ken Perlin's Academy Award
* Ken perlin による改良パーリンノイズ（2002年）のJavaソースコード
* Matt Zucker's Perlin noise math FAQ
* Perlin Noise 解説と擬似コードによる実装例
* The Random Universe - 天体構造をパーリンノイズで擬似表現する。
* Using Perlin Noise to Generate 2-Dimensional Clouds in Paint.NET