深入Worley噪聲

關於Worley噪聲，是構造Voronoi圖最簡單的方式，不涉及複雜的幾何運算或演算法，單純就是像素與點的距離，如果用於理解Voronoi原理，將會非常適合，而且此種做法在程式實作面上，簡單且容易變化與應用。

建立勢力範圍

Voronoi圖形這個名詞看來神祕，然而每個人的生活經驗中，一定都看過這類圖形，例如肥皂泡泡、長頸鹿身上的圖塊、葉片脈絡、蜻蜓翅膀紋路等，看似隨機，然而，在不同場合都會出現類似圖案，表示其隱含著規則。

隨機的是點出現的位置，規則就是勢力均衡，正因為勢力均衡，Voronoi圖形一直以來都是個值得研究，也兼具實用的課題，應用方面不單只是作為繪圖紋理，電信基地臺、城市設施資源規畫等，都可以基於Voronoi圖形勢力均衡，也就是涵蓋範圍作為設置的出發點。

我在先前專欄文章〈隨機演算之美〉提過Voronoi空間分割演算的基本原理，然而程式實作上很複雜，就算是基本的半平面交集法（Half-plane Intersection），也需處理線的交點、多邊形交集等問題，有沒有更簡單的構造方式？

如果我們在畫布中指定一個點，每個像素至該點的距離，作為灰階值0至255的計算來源，此時。所畫出來的圖會是：越接近該點越黑，越遠離該點越白的圓形圖案。之所以會有如此結果，原因在於，就自然界而言，圓形本身就是力量均衡下才會產生的形狀。

因此，若有兩個點，每個像素至該兩點的距離取較小者，作為灰階值0至255的計算來源，結果會像兩個互相擠壓的泡泡，因為計算像素至點的距離，就是在計算點給予像素的影響力，若有兩個以上的點，有些像素大致介於點與點之間勢力均衡的邊緣，藉由灰階帶來的視覺差異，就會帶來模糊的邊緣感。

如果有很多點，而且這些點是隨機分布，取像素至最近點的距離傳回，這樣會如何呢？就像是一堆泡泡擠在一起，形成了勢力均衡，最後構成的圖案就是Voronoi圖。

若想解決模糊的邊緣感，我們對於每個像素，可以傳回對其給予影響力的點（也就是最接近的點），接著運用這個點來繪圖，或許用該點與原點的距離來作為顏色值的計算基準，如此一來，接受同個點所影響的像素，顏色就會相同，因而產生色塊組成的Voronoi圖。

圍繞的細胞

由於點是隨機分布，像素與最近點之間的距離也就是隨機的，就因此構成了一種噪聲（Noise）。事實上，這是由Steven Worley在1996年撰寫的〈A Cellular Texture Basis Function〉提到的方式，因而稱為Worley噪聲，我在先前專欄文章〈自然噪聲與碎形〉當中，也略提過這種噪聲。

問題在於，對於每個像素，都要計算與每個點的距離，計算上會花很長的時間，若能事先排除太遠處的點，就可以省下不少計算的時間，只不過這些點又要有隨機性，如何能事先排除遠處的點？答案是可以將畫布分割為網格，然後在每個網格中隨機散布一個點。

可以想像各網格中的點是作為細胞核，細胞開始成長，然後彼此開始擠壓，直到勢力均衡，網格最終只會與周圍九宮格的細胞擠壓，因此，就計算上來說，不用計算全部的點，只要取像素所在九宮格內的九個點，計算最近點的距離就可以了，如此一來，大大地減少了計算量，也是Steven Worley當年採取的方式。

而這種做法，還可以擴充至3D版本的Worley噪聲，我們只要取到體素（Voxel）所在的27個方塊內的點。

以網格方式定義圍繞的細胞，畫出的Voronoi圖中，每個細胞的大小不致於相差太大，當然，若希望點的散布並不是以網格的方式畫分，而是隨機分布時，還是必須對每個點進行計算。

其實，這也不是壞事，因為，在必要時，可以藉此構成有趣的圖案，例如，若點散布在黃金螺線上，我們以此計算而得的Worley噪聲，將會形成貝殼化石般的紋理（可參考〈Worley 噪聲（二）〉）。

不只是Voronoi圖案

雖然我們可以傳回最接近像素的點，用以計算顏色產生色塊式的Voronoi圖，若只想產生色塊邊緣的部份呢？

單純計算最接近點的距離，會構成圓的勢力範圍，若打算基於某個距離閥值來畫邊緣，結果只會產生圓形的空洞，當然，這也可以是一種風格，因為將閥值條件反過來，就可以構成像是泡泡稀疏相連的圖案（可參考〈Worley 噪聲（三）〉）。

在Steven Worley的原始做法中，第二接近距離減去第一接近距離，也就是被稱為F2-F1的方式，圖案會有突起的效果，令邊緣明顯。

會有這樣的結果，原因在於兩個細胞的邊界處，F2-F1一定是0，像素越靠近其中一點，F2-F1的值會有較大變化，用來做為是否繪製邊緣的閥值，如此一來，所產生的邊緣就會明顯許多；然而，這並不是很精確的做法，畢竟只是單純地計算距離差，而不是去計算像素與細胞邊界的距離。

如果要更準確地描繪出邊界，計算出像素與細胞邊界之間的距離，將會是必要的，正如2012年Inigo Quilez撰寫的〈voronoi edges〉，我們可以利用兩個最接近點，計算它們的中點後，取像素與中點向量的投影，以確實地計算出細胞邊界的距離，結果就是細胞突起更為明顯，若小於某個閥值才繪製像素，此時，就會產生更精確的邊界。

既然可以傳回F2-F1，或者是像素與細胞邊界的距離作為噪聲值，可否傳回其他值呢？

在Steven Worley的文件當中，其實也提到，我們可以取不同的距離傳回，例如，第二接近點、第三接近點的距離等，若用這些噪聲值來作為灰階值，會構成不同的圖案。

你也可以傳回曼哈頓距離，其構成的圖案與Voronoi會非常不同，由於曼哈頓距離的正式意義為城市區塊距離，就城市資源規畫而言，這樣的圖案或許更具意義（因為涉及走路、開車的距離），若以色塊來表示，曼哈頓距離構成的圖案更像行政區域圖，也就是說，針對不同的需求，可以採用不同的距離法。

不只是噪聲值

只不過，運用全部像素來計算Voronoi圖案，對於CPU而言，將會是極為吃力的方式，因而Worley噪聲常屬於GPU著色器討論的範圍，或許是因為這樣，Worley噪聲常令人誤以為，它主要用於產生紋理圖案。

然而，Worley噪聲是構造Voronoi圖最簡單的方式，不用涉及複雜的幾何運算或演算法，單純就是像素與點的距離，因此，更容易變化應用，實作上也極為容易。

如果你曾挑戰Voronoi圖的構造，卻被一堆幾何運算或演算法給困住了，不如試著從Worley噪聲下手，或許可以得到許多的靈感。