パーリンノイズ

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

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

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

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

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

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

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

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

パーリンによるオリジナルの実装では、各グリッド交点に割り当てる勾配ベクトルを決定するために、簡単なハッシュスキームが使われた。^[3] 事前に計算された順列テーブルは、与えられたグリッド座標をランダムな数値に変換するために利用される。オリジナルの実装では256交点のグリッドを扱っていたため、以下に示すような順列テーブルが含まれている。

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までの整数がランダムに配列された順列が必要である。^[4] 順列テーブルを用いて勾配ベクトルを取得する際には、グリッド交点座標の各成分について、前の成分を参照した値に次の成分を足して参照することを繰り返す。例えば、オリジナルの実装ではこれを3次元で以下のように行っている。

// 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個の勾配ベクトルの中からそのグリッド交点に割り当てるものをひとつ選ぶ。

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