?一、噪聲

噪聲是游戲編程的常見技術，廣泛應用于地形生成，圖形學等多方面。

那么為什么要引入噪聲這個概念呢？在程序中，我們經(jīng)常使用直接使用最簡單的rand()生成隨機值，但它的問題在于生成的隨機值太“隨機”了，得到的值往往總是參差不齊，如下圖使用隨機值作為像素點的黑白程度：

而使用噪聲，我們得到的值看起來雖然隨機但平緩，這種圖也看起來更自然和舒服：

1.1 隨機性

隨機性是噪聲的基礎，不必多說。

1.2 哈希性

在《Minecraft》里，由于世界是無限大的，它以“Chunk”區(qū)塊（16×16×256格子）為單位，只加載玩家附近的區(qū)塊。也就是說，當玩家在移動時，它會卸載遠離的區(qū)塊，然后加載靠近的區(qū)塊。

一個問題是，當玩家離開一個區(qū)塊時，進入第二個區(qū)塊，然后又回到第一個區(qū)塊，此時玩家期望看到的第一個區(qū)塊和之前看到的保持一致。例如，輸入1時得到0.3，輸入2時得到0.7，當再次輸入1時預期得到0.3。

因此噪聲的一個重要性質(zhì)是哈希性（可哈希的）。

?盡管使用輸入值作為srand()的參數(shù)來設置rand()的種子，從而達到哈希效果也是可行的。
?然而最好花點時間寫一個自己的哈希函數(shù)，使其簡易使用而且也不破壞程序其他地方使用rand()的效果。

//一個隨機性的哈希函數(shù)
unsigned int hash11(int position){
const unsigned int BIT_NOISE1 = 0x85297A4D;
const unsigned int BIT_NOISE2 = 0x68E31DA4;
const unsigned int BIT_NOISE3 = 0x1B56C4E9;
unsigned int mangled = position;
mangled *= BIT_NOISE1;
mangled ^= (mangled >> 8);
mangled += BIT_NOISE2;
mangled ^= (mangled << 8);
mangled *= BIT_NOISE3;
mangled ^= (mangled >> 8);
return mangled;
}

1.3 平滑性

對一個隨機生成地形來說，如果簡單的使用隨機和哈希組合，
那么容易得到下圖（以一維地圖舉例，x軸為位置，y軸為地形高度）：

容易看出的問題是，由于隨機的雜亂無章，地形非常的參差不齊，這可不是一個自然的地形。

我們期望得到的地形不僅隨機還應該是平滑的，這樣才顯得自然，如下圖：

為了達到連續(xù)性，自然想到利用插值函數(shù)進行插值，常見的插值方法有：線性插值、緩和曲線插值

二、Value噪聲

Value噪聲是最簡單的一種噪聲，其主要思路是定義若干個頂點且每個頂點含有一個隨機值（以頂點坐標作為參數(shù)通過哈希運算得到的），該隨機值會周圍坐標產(chǎn)生影響，越靠近頂點則越容易受該頂點影響（輸出值越接近頂點隨機值）。當需要求某個坐標的輸出值時，需要將該坐標附近的各個頂點所造成的影響值進行疊加，從而得到一個總值并輸出之。

原理：

1.首先定義一個晶格結構，每個晶格的頂點有一個偽隨機值（Value）。對于二維的Value噪聲來說，晶格結構就是一個平面網(wǎng)格（通常是正方形），三維的就是一個立體網(wǎng)格（通常是正方體）。

2.輸入一個點（二維空間的話就是2D坐標），我們找到它所在晶格的頂點（二維下有4個，三維下有8個，N維下有個），并經(jīng)過哈希運算得到這些頂點的偽隨機值。

3.根據(jù)這些頂點的偽隨機值，使用插值函數(shù)計算出輸入點的輸出值。對于插值函數(shù)的權重，我們還需要使用緩和曲線（ease curves）來計算這些偽隨機值的權重和。在原始的Perlin噪聲實現(xiàn)所使用的緩和曲線是，在2002年的論文中Perlin又改進為。

實現(xiàn)：

int valueNoise(Vector2 p){//晶格以1為長度單位，通過向下取整可以確定p點所在晶格//注意：不應使用轉變整型，因為負數(shù)的轉整型是向上取整，而正數(shù)則是向下取整，這可能會導致(-1~0)和(0~1)的邊緣問題Vector2 pi = Vector2(floor(p.x),floor(p.y));//找到對應晶格的四個頂點坐標Vector2 vertex[4] = {{pi.x,pi.y},{pi.x+1,pi.y},{pi.x,pi.y+1},{pi.x+1,pi.y+1}};//通過hash21函數(shù)得出坐標對應的隨機值float vertexRandom[4] = {{hash21(vertex[0])},{hash21(vertex[1])},{hash21(vertex[2])},{hash21(vertex[3])}};  //wx、wy代表p點的權重，實際就是以(0.0~1.0)的范圍表示在晶格中的位置比例float wx = (p.x-pi.x))/1.0f;float wy = (p.y-pi.y))/1.0f;//插值return interpolation(wx,wy,vertexRandom);
}

三、柏林噪聲

談起噪聲，最著名的且最常用的莫過于Perlin噪聲，Perlin噪聲的名字來源于它的創(chuàng)始人Ken Perlin。

在理解了上面Value噪聲后，我們再來看看柏林噪聲的主要想法：
定義若干個頂點且每個頂點含有一個隨機梯度向量，這些頂點會根據(jù)自己的梯度向量對周圍坐標產(chǎn)生勢能影響，沿著頂點的梯度方向越上升則勢能越高。當需要求某個坐標的輸出值時，需要將該坐標附近的各個頂點所造成的勢能進行疊加，從而得到一個總勢能并輸出之。

我們給頂點賦予一個隨機性的哈希函數(shù)，輸入一個坐標可以得到一個隨機向量，滿足上述隨機性和哈希性。
此外，由于勢能是沿著梯度方向漸變的，所以很容易得到平滑性。

原理：

和Value噪聲一樣，它也是一種基于晶格的噪聲，也需要三個步驟：

1.首先定義一個晶格結構，每個晶格的頂點有一個隨機的梯度向量。對于二維的Perlin噪聲來說，晶格結構就是一個平面網(wǎng)格（通常是正方形），三維的就是一個立體網(wǎng)格（通常是正方體）

2.輸入一個點（二維空間的話就是2D坐標），我們找到它所在晶格的頂點（二維下有4個，三維下有8個，N維下有個），并經(jīng)過哈希運算得到這些頂點的梯度向量（隨機向量）；接著計算該點到各個晶格頂點的距離向量，再分別與頂點代表的梯度向量做點乘，得到個梯度值結果

//點乘
float dot(Vector2 v1,Vector2 v2){return v1.x*v2.x+v1.y*v2.y;
}//求梯度值（本質(zhì)是求頂點代表的梯度向量與距離向量的點積）
float grad(Vector2 vertex, Vector2 p)
{return dot(hash22(vertex), p);
}

3.使用緩和曲線來計算它們的權重和（同樣的，可以是，也可以是

下圖通過顏色差異顯示了由2D柏林噪聲生成的各像素點的值：

實現(xiàn)：

//二維柏林噪聲
float perlinNoise(Vector2 p)
{  //向量兩個緯度值向下取整Vector2 pi = Vector2(floor(p.x),floor(p.y));//找到對應晶格的四個頂點坐標Vector2 vertex[4] = {{pi.x,pi.y},{pi.x+1,pi.y},{pi.x,pi.y+1},{pi.x+1,pi.y+1}};//通過grad函數(shù)得出坐標對應的隨機值float vertexRandom[4] = {grad(vertex[0],p),grad(vertex[1],p),grad(vertex[2],p),grad(vertex[3],p)};  //wx、wy代表p點的權重，實際就是以(0.0~1.0)的范圍表示在晶格中的位置比例float wx = (p.x-pi.x))/1.0f;float wy = (p.y-pi.y))/1.0f;//插值return interpolation(wx,wy,vertexRandom);
}

gard函數(shù)另一個更快的實現(xiàn)方式，它與標準實現(xiàn)方式的區(qū)別是：晶體頂點是從若干個梯度向量里隨機選擇一個向量而不是產(chǎn)生一個隨機向量，這樣做可以預先計算好求梯度值時各項的系數(shù)。因此我們只需這樣重寫一下grad函數(shù)：

//求梯度值（本質(zhì)是求頂點代表的梯度向量與距離向量的點積）
float grad(Vector2 vertex, Vector2 p)
{switch(hash21(vertex) % 4){case 1: return  p.x + p.y;  //代表梯度向量(1,1)case 2: return -p.x + p.y;  //代表梯度向量(-1,1)case 3: return  p.x - p.y;  //代表梯度向量(1,-1)case 4: return -p.x - p.y;  //代表梯度向量(-1,-1)default: return 0; // never happens}
}

這里示例提供了4個可選的隨機向量，實際上這個數(shù)量是偏少的，如果想要更加多樣的效果，建議在實現(xiàn)時多提供些可選的隨機向量。

四、Simplex噪聲

Simplex噪聲也是一種基于晶格的梯度噪聲，它和Perlin噪聲在實現(xiàn)上唯一不同的地方在于，它的晶格并不是方形（在2D下是正方形，在3D下是立方體，在更高緯度上我們稱它們?yōu)槌⒎襟w，hypercube），而是單形（simplex）。

通俗解釋單形的話，可以認為是在N維空間里，選出一個最簡單最緊湊的多邊形，讓它可以平鋪整個N維空間。我們可以很容易地想到一維空間下的單形是等長的線段，把這些線段收尾相連即可鋪滿整個一維空間。在二維空間下，單形是三角形，我們可以把等腰三角形連接起來鋪滿整個平面。三維空間下的單形就是四面體。更高維空間的單形也是存在的。

總結起來，在n維空間下，超立方體的頂點數(shù)目是，而單形的頂點數(shù)目是n+1，這使得我們在計算梯度噪聲時可以大大減少需要計算的頂點權重數(shù)目。

一個潛在的問題是如何找到輸入點所在的單形。
在計算Perlin噪聲時，判斷輸入點所在的正方形是非常容易的，我們只需要對輸入點下取整即可找到。
對于單形來說，我們需要對單形進行坐標偏斜（skewing），把平鋪空間的單形變成一個新的網(wǎng)格結構，這個網(wǎng)格結構是由超立方體組成的，而每個超立方體又由一定數(shù)量的單形構成：

我們之前講到的單形網(wǎng)格如上圖中的紅色網(wǎng)格所示，它們有一些等邊三角形組成（注意到這些等邊三角形是沿空間對角線排列的）。經(jīng)過坐標傾斜后，它們變成了后面的黑色網(wǎng)格，這些網(wǎng)格由正方形組成，每個正方形是由之前兩個等邊三角形變形而來的三角形組成。這個把N維空間下的單形網(wǎng)格變形成新網(wǎng)格的公式如下：

其中，?

在二維空間下，取n為2即可。這樣變換之后，我們就可以按照之前方法判斷該點所在的超立方體，在二維下即為正方形。

原理：

1.坐標偏斜：把輸入點坐標進行坐標偏斜。

2.找到頂點：對偏斜后坐標下取整得到輸入點所在的超立方體,...我們還可以得到小數(shù)部分,...我們把之前得到的(xf,yf,...)中的數(shù)值按降序排序，來決定輸入點位于變形后的哪個單形內(nèi)。這個單形的頂點是由按序排列的(0, 0, …, 0)到(1, 1, …, 1)中的n+1個頂點組成，共有n!種可能性。
我們可以按下面的過程來得到這n+1個頂點：從零坐標(0, 0, …, 0)開始，找到當前最大的分量，在該分量位置加1，直至添加了所有分量。這一步的算法復雜度即為排序復雜度。

3.梯度選取：我們在偏斜后的超立方體網(wǎng)格上獲取該單形的各個頂點的偽隨機梯度向量。

4.變換回單形網(wǎng)格里的頂點：我們首先需要把單形頂點變回到之前由單形組成的單形網(wǎng)格。這一步需要使用第一步公式的逆函數(shù)來求得：

其中，?

5.貢獻度取和：我們由此可以得到輸入點到這些單形頂點的位移向量。這些向量有兩個用途，一個是為了和頂點梯度向量點乘，另一個是為了得到之前提到的距離值dist，來據(jù)此求得每個頂點對結果的貢獻度：

實現(xiàn)：

float simplexNoise(Vector2 p)
{const float K1 = 0.366025404; // (sqrt(3)-1)/2;const float K2 = 0.211324865; // (3-sqrt(3))/6;//坐標偏斜float s = (p.X + p.Y) * K1;Vector2 pi = Vector2(floor(p.X+s),floor(p.Y+s));float t = (pi.X + pi.Y) *K2;Vector2 pf = p-(pi-t*Vector2::UnitVector);Vector2 vertex2Offset = (pf.X < pf.Y) ? Vector2(0, 1) : Vector2(1, 0);//頂點變換回單行網(wǎng)格空間Vector2 dist1 = pf;Vector2 dist2 = pf - vertex2Offset + K2 * Vector2::UnitVector;Vector2 dist3 = pf - Vector2(1,1) + 2 * K2 * Vector2::UnitVector;//計算貢獻度取和float hx = 0.5f - Vector2::DotProduct(dist1, dist1);float hy = 0.5f - Vector2::DotProduct(dist2, dist2);float hz = 0.5f - Vector2::DotProduct(dist3, dist3);hx=hx*hx*hx*hx;hy=hy*hy*hy*hy;hz=hz*hz*hz*hz;//結果范圍是[-1,1]return 70*(hx*Vector2::DotProduct(dist1, hash22(pi)) +hy*Vector2::DotProduct(dist2, hash22(pi + vertex2Offset))+hz*Vector2::DotProduct(dist3, hash22(pi + Vector2(1,1))));
}

雖然理解上Simplex噪聲相比于Perlin噪聲更難理解，但由于它的效果更好、速度更優(yōu)，因此很多情況下會替代Perlin噪聲。

而且高維的噪聲并不少見，例如對于常見的二維噪聲紋理，我們可以額外引入時間分量，變成一個2D紋理動畫（三維噪聲），用于火焰紋理動畫等..
對于常見的三維噪聲紋理，引入額外的時間分量，就可以變成一個3D紋理動畫（四維噪聲），用于3D云霧動畫等..
當我們需要一個可循環(huán)無縫銜接的動畫時（見下文可平埔的噪聲），那噪聲又要提高一個維度。