?一、噪聲

噪聲是游戲編程的常見技術(shù)，廣泛應(yīng)用于地形生成，圖形學(xué)等多方面。

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

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

1.1 隨機(jī)性

隨機(jī)性是噪聲的基礎(chǔ)，不必多說。

1.2 哈希性

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

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

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

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

//一個(gè)隨機(jī)性的哈希函數(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 平滑性

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

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

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

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

二、Value噪聲

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

原理：

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

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

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

實(shí)現(xiàn)：

int valueNoise(Vector2 p){//晶格以1為長(zhǎng)度單位，通過向下取整可以確定p點(diǎn)所在晶格//注意：不應(yīng)使用轉(zhuǎn)變整型，因?yàn)樨?fù)數(shù)的轉(zhuǎn)整型是向上取整，而正數(shù)則是向下取整，這可能會(huì)導(dǎo)致(-1~0)和(0~1)的邊緣問題Vector2 pi = Vector2(floor(p.x),floor(p.y));//找到對(duì)應(yīng)晶格的四個(gè)頂點(diǎn)坐標(biāo)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ù)得出坐標(biāo)對(duì)應(yīng)的隨機(jī)值float vertexRandom[4] = {{hash21(vertex[0])},{hash21(vertex[1])},{hash21(vertex[2])},{hash21(vertex[3])}};  //wx、wy代表p點(diǎn)的權(quán)重，實(shí)際就是以(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噪聲后，我們?cè)賮砜纯窗亓衷肼暤闹饕敕?#xff1a;
定義若干個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)含有一個(gè)隨機(jī)梯度向量，這些頂點(diǎn)會(huì)根據(jù)自己的梯度向量對(duì)周圍坐標(biāo)產(chǎn)生勢(shì)能影響，沿著頂點(diǎn)的梯度方向越上升則勢(shì)能越高。當(dāng)需要求某個(gè)坐標(biāo)的輸出值時(shí)，需要將該坐標(biāo)附近的各個(gè)頂點(diǎn)所造成的勢(shì)能進(jìn)行疊加，從而得到一個(gè)總勢(shì)能并輸出之。

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

原理：

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

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

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

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

3.使用緩和曲線來計(jì)算它們的權(quán)重和（同樣的，可以是，也可以是

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

實(shí)現(xiàn)：

//二維柏林噪聲
float perlinNoise(Vector2 p)
{  //向量?jī)蓚€(gè)緯度值向下取整Vector2 pi = Vector2(floor(p.x),floor(p.y));//找到對(duì)應(yīng)晶格的四個(gè)頂點(diǎn)坐標(biāo)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ù)得出坐標(biāo)對(duì)應(yīng)的隨機(jī)值float vertexRandom[4] = {grad(vertex[0],p),grad(vertex[1],p),grad(vertex[2],p),grad(vertex[3],p)};  //wx、wy代表p點(diǎn)的權(quán)重，實(shí)際就是以(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ù)另一個(gè)更快的實(shí)現(xiàn)方式，它與標(biāo)準(zhǔn)實(shí)現(xiàn)方式的區(qū)別是：晶體頂點(diǎn)是從若干個(gè)梯度向量里隨機(jī)選擇一個(gè)向量而不是產(chǎn)生一個(gè)隨機(jī)向量，這樣做可以預(yù)先計(jì)算好求梯度值時(shí)各項(xiàng)的系數(shù)。因此我們只需這樣重寫一下grad函數(shù)：

//求梯度值（本質(zhì)是求頂點(diǎn)代表的梯度向量與距離向量的點(diǎn)積）
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個(gè)可選的隨機(jī)向量，實(shí)際上這個(gè)數(shù)量是偏少的，如果想要更加多樣的效果，建議在實(shí)現(xiàn)時(shí)多提供些可選的隨機(jī)向量。

四、Simplex噪聲

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

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

總結(jié)起來，在n維空間下，超立方體的頂點(diǎn)數(shù)目是，而單形的頂點(diǎn)數(shù)目是n+1，這使得我們?cè)谟?jì)算梯度噪聲時(shí)可以大大減少需要計(jì)算的頂點(diǎn)權(quán)重?cái)?shù)目。

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

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

其中，?

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

原理：

1.坐標(biāo)偏斜：把輸入點(diǎn)坐標(biāo)進(jìn)行坐標(biāo)偏斜。

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

3.梯度選取：我們?cè)谄焙蟮某⒎襟w網(wǎng)格上獲取該單形的各個(gè)頂點(diǎn)的偽隨機(jī)梯度向量。

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

其中，?

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

實(shí)現(xiàn)：

float simplexNoise(Vector2 p)
{const float K1 = 0.366025404; // (sqrt(3)-1)/2;const float K2 = 0.211324865; // (3-sqrt(3))/6;//坐標(biāo)偏斜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);//頂點(diǎn)變換回單行網(wǎng)格空間Vector2 dist1 = pf;Vector2 dist2 = pf - vertex2Offset + K2 * Vector2::UnitVector;Vector2 dist3 = pf - Vector2(1,1) + 2 * K2 * Vector2::UnitVector;//計(jì)算貢獻(xiàn)度取和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;//結(jié)果范圍是[-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)，因此很多情況下會(huì)替代Perlin噪聲。

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