LUNG LUNG DESIGN: 功能強大的碎形程式／Fractal Lab Demo 2015

2015年5月9日星期六

功能強大的碎形程式／Fractal Lab Demo 2015

功能強大的碎形程式／Fractal Lab Demo 2015
原文出處：FRACTAL LAB

圖片出處：Vimeo

History／發展沿革

Fractal Lab 計畫成立於2011年初，是由一位英國的物理學者 Tom Beddard 所開發，初期是為了測試在網頁瀏覽器上使用 WebGL 架構，進行碎形（Fractal）的運算而撰寫。在那之前，Tom Beddard 是使用 Adobe PixelBender 以及 QuartzComposer 製做一些碎形的創作（2009），這兩者的優勢在於可以輕易的整合於 Photoshop 和 AfterEffects，但是在遊走碎形空間時，互動的介面常常綁手綁腳。

碎形是一種源自於自然的高完成度細部，換一種方式來說，即便是在輸入的參數做出一點點小到無法察覺的異動，經過不斷又不斷的自身演化，最後產出的形體也會是戲劇性的迥異。為了要能夠更輕易的來觀察這樣的奇幻空間（同時探索特殊參數下，coalesce 運算式內的一些隱匿的圖形管理器...），Tom Beddard 決定建構一個嶄新且容易操作的使用者介面，一個基於 WebGL 架構下的 GLSL（OpenGL Shading Language）渲染器，讓瀏覽器可以借重於平行運算的技術，透過 GPU 的運算能力來建置這個新的控制介面。

第一個推出的版本（見下方影片）是一個概念上的驗證，讓使用者可以在瀏覽器的架構下，即時性的更動參數並遨遊在碎形的空間內。（這個作品樹立了一個里程碑，變成 Tom Beddard 先生開啟日後求職升遷的立基）

雖然一直朝著把 Fractal Lab 頁面發展成一個全功能的商品邁進，但目前這個架構下仍然遺留著許多個人測試階段的殘跡（不外乎是一些還在測試階段的網路渲染技術）。這樣的架構可以滿足原作者對創作的渴望，一種將所有測試結果整合在一起的狀態。

Implementation／執行方式

目前是以呼叫四次的 iterations 來運作，前面看到的範例版本是以 Coffeescript 編譯器來撰寫。並使用 micro MVC framework Spine 延用 Gulp 和 Browserify 的工作流程。

註解：
iterations 翻譯為迭代或疊代；疊代法 iterative method 是用迴圈去循環重複程式碼的某些部分來得到答案，而遞迴法 recursive method 則是重複呼叫自身程式碼來得到答案。

Tom Beddard 先生近期的作品是使用 Javascript ES6 架構和搭配 Webpack 的 React.js 以及採用 Node.js 做為後端的處理程式。也許 Fractal Lab 將會跟進也說不定？

Ray Marching／光跡行進

Fractal Lab 目前使用的 3D 碎形技術稱為 distance field ray marching（一般較為熟知的說法是 sphere tracing，相關學術論文）；這是一種廣為人知的渲染演算法，iñigo quilez（Youtube）先生為其一關鍵人物。

作品節錄自 iñigo quilez 先生的 Youtube 頻道

對這部分技術有興趣的朋友，可以參考這個網頁，Mikeal Christensen 先生對 Raymarching Distance Fields 有非常清楚的說明。

Classic raytracing shoots one (or more) rays per pixel and calculate where the rays intersect the geometry in the scene. Normally the geometry is described by a set of primitives, like triangles or spheres, and some kind of spatial acceleration structure is used to quickly identify which primitives intersect the rays. Distance Estimation, on the other hand, is a ray marching technique. Instead of calculating the exact intersection between the camera ray and the geometry, you proceed in small steps along the ray and check how close you are to the object you are rendering. When you are closer than a certain threshold, you stop. In order to do this, you must have a function that tells you how close you are to the object: a Distance Estimator. The value of the distance estimator tells you how large a step you are allowed to march along the ray, since you are guaranteed not to hit anything within this radius.

Schematics of ray marching using a distance estimator.
使用距離估計光線行進的原理圖。（原文出處／2011）

另外有一群極具天分的人在 fractalforums.com 社群裡討論這個演算法，Fractal Lab 發展的技術是以此為基礎。

當心，一旦踏入這個奇幻的兔子洞裡，就別想離開了！

Optimisation Notes／最佳化建議

碎形的渲染是一個龐大的運算過程；光是處理一個 2D 的碎形，每一個像素（pixel）就必須經歷數十次到上百次的迭代運算。一個 3D 碎形則是以數十倍到上百倍的運算量，重覆計算光線行進到場景內的過程。目前架構下的 GPU 可以透過平行運算的方式同步處理許多 Pixel 的資訊，但是即便是最頂級規格的硬體系統，也很容易在解析度全開的狀態下停滯或是渲染失敗。為了要維持操控的可能性，Fractal Lab 採用了 progressive rendering（這個技術的詳細說明，請參考 Hammer Chen 先生介紹的這篇文章，文章內容部分截圖如下圖所示），可以想像成是一種網格狀，隔行掃描的技術。

圖面出處：CG Taiwaner 台灣人玩動畫

一個全解析度的畫面緩衝區，作用就像是一個累加器（accumulator），但是一旦渲染結束只會存於四分之一尺寸的緩衝區。在第一個處理階段，這個壘加器呈現出一個像素化的畫面（Pixelated view）。隨後將每四格中的一個像素著色；第二個處理階段對右上角著色，然後第三個階段針對左下角著色，並在最後階段完成右下角的著色。透過這樣的方式，可以即時對整個場景的呈現有個大輪廓的認知。

在這樣的技術架構下，以一個 1280 x 720 的畫面為例，四倍超取樣的設定（4x super-sampled）下仍可以在一秒內有 30 fps 的快速反應頻率。

在互動編輯模式下，超取樣（Super-sampling）在這裡是很重要的技術。一般的互動狀態下，細部多呈現一次性計算的鋸齒狀結果。

另一個校能最佳化的重點是在使用 GLSL renderer 時，避免使用條件敘述（condition statements）。通常這樣可以更有效率的讓 GPU 單元以不考慮（min / max / mix / step statements）的情況下做運算，用意在避免深入這些枝枝節節的運算，可以規避掉整個系統為了等待單一複雜的像素運算結果而延遲的窘境。

Fractal Lab 同時使用了一個預處理著色器（pre-processor shader），可以在轉譯前從使用者控制介面更新 #define statements，如此一來可以許多布林值（boolean）和全域狀態選項（global state options）可以在轉譯 time #ifdef statements 時置換。這樣的步驟將允許大量未使用的資料區塊（chunks）在著色運算時被忽略而加速。

From th browser to desktop／從瀏覽器邁入桌上型電腦架構

瀏覽器是在一種擬真測試環境（sand-boxed environment）下執行，受限於無法存取主機的資料系統。為了要儲存瀏覽器的渲染效果，Fractal Lab 使用 Dropbox API 來上傳處理好的影像檔，數秒後將會同步於桌上型電腦的 Dropbox 資料夾內。雖然是一種迂迴的方式，但相對可靠。

在動畫的使用需求時，Tom Beddard 先生使用 NodeWebkit 來創建一個桌面的應用程式，透過 Node.js 腳本將影像們儲存在電腦內，然後使用 FFMPEG 來轉譯成影片檔。

Next steps／接下來的路

Tom Beddard 先生說，Fractal Lab 對他而言就像是一塊施展個人技術與創意的畫布，在這裡可以自由的用自己的時間來探索天馬行空的想法（不用承擔任何義務與承諾，好爽），因此目前的階段並沒有開放在網路上或是安裝執行。

由於現階段手邊還有一些作品的想法要使用 Fractal Lab 來發展，也許在那之後會釋出一些程式碼也說不定？

雖然如此，對於求知若渴的人，下面這些建構完整的 app 會是你們正確探索 3D 碎形和互動式光跡行進演算法的路。

Fragmentarium
Fragmentarium 是一個由 Mikael Christensen 先生（前面有提及）創建的跨平台桌面應用程式。這個程式可以讓你撰寫並編輯 GLSL fragment shaders 並且建溝一些基礎的使用者介面，控制輸入的參數。

圖片出處：FRAGMENTARIUM
Mandelbulb3D
一個 Windows 系統架構的 app，富含大量的方程式選單和功能。雖然不是使用 GPU 進行運算處理（相對緩慢），但是相對的沒有 GPU renderer 的單精度浮點數限制（single precision limit），這意味著你可以 zoom in 到更深層的地方。