關於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噪聲下手,或許可以得到許多的靈感。

作者簡介


熱門新聞

Advertisement