基於substance gpu引擎的flood fill節點 演算法分析(I)

---

導言

substance designer最近的更新中, 個人覺得flood fill是其中最有用的之一.我在看完更新後就立刻自己試著做了一個材質, 就是封面啦......(不好看勿噴啊)

flood fill的功能是啥呢? 挺簡單的, 就和photoshop的填充油漆桶功能差不多;

用法挺簡單的, 但是其中的演算法非常有意思, 如果不了解演算法的話, 有些參數調起來是不知其所以然的. 這裡要先介紹一個功能強大的節點: pixel processor;

flood fill 節點的內部構造, 由3種不同, 共22個pixel processor構成

pixel processor在substance的基礎節點(噪音, 圖案)內部幾乎無處不在, 它的功能是同時處理輸入的圖片中每一個像素並對它賦值.說起來簡單, 真正複雜的是藏在pixel processor內部的演算法. 如上圖所示, 一共有三個演算法, 中間22個都是用的同一個(第二種)演算法. 順便一提, 這22個節點可以達到 指數級的效率. 這22接下來一個個分析.

---

I.第一步處理First Pass ------------ 遍歷邊緣

演算法總的思想是,

先對每個像素顏色值的頭兩項值(RGBA的R和G)設置下一個訪問的像素坐標, 如果該像素在子圖案邊緣處, 那麼就把沿著邊緣順時針下一個像素設為目標; 否則, 把右邊的像素設為目標.這樣一來, 每個子圖案內部節點就形成一個內部循環的多級鏈表, 如圖:

注意了, 這個遍歷演算法其實是有很大缺陷的, 原因之後再說;

R G值設好後, B A(Alpha)值先儲存為R,G同樣的值;起作用在第二階段再說;

第一步的主要目的是為每個像素設置下一個訪問的像素位置

Step 1:

這裡要強調下, 像素位置都是在0到1之間的小數, 這是和我們潛意識裡的認知是不同的, 比如這個圖是4096x4096的, 肯定第一印象就是, 從左往右第123個, 從上到下第596個像素的坐標就是像(123, 596)之類的, 其實不是的,應當為(123/4096, 596/4096); 所以每個像素邊長都為1/4096,設圖形長寬為size, 也就是1/size; 這樣整個圖就處於0-1的uv空間裡面了.

好的, 當我們獲得位置(x, y)和像素邊長w之後, 就可以通過 , 來進一步獲取其相鄰像素的位置, 以便之後用來確定RG值指向哪一個像素.(即鏈表中指向的下一像素)

Step 2:

這裡看起來複雜, 實際上就是在取周圍像素的灰度值, 然後看是偏亮(圖案)還是偏暗(邊緣);這裡只採樣目前像素及其左上角共四個像素的灰度, 再以它們灰度值來決定下一個要遍歷的像素.由於只採樣4個像素, 所以當形狀內部有洞(比如一塊白區域裡面有一塊或多塊黑區域)會導致一些問題.

Step 3:

這裡是根據step2中取到的左上角4個像素灰度值進行的一系列判定, 其實並不複雜, 你只要畫個圖, 想想按什麼規則, 依靠已知的step2那4個灰度值, 可以總是讓像素順時針遍歷, 然後把規則總結起來, 再做個邏輯表達式, 化簡一下, 就可以得到一組判定序列了.判定之後輸出的是下一個要遍歷的像素坐標.

Step4:

拿目標像素坐標減去當前像素坐標, 得到位移值, 然後再進行一系列變換, 這個變換說實話我也不是太懂, 為啥把位移乘0.5, 再加.499992, 其實在之後又要把這個值變回位移的...難道是便於存儲嗎?我發現0.499992好像是0.5灰度值顯示出來的值,挺奇怪的...

好了, 第二個演算法分析放在下一篇文章再寫吧......

(初稿在B站上發了, 感覺有問題, 就改了改)

推薦閱讀：