CSIE5098 - Digital Image Synthesis
Shiang-Yun Yang 楊翔雲
Date submitted: 21 Dec 2015
Code emailed: 21 Dec 2015
根據論文 P. Debevec, A Median Cut Algorithm for Light Probe Sampling, SIGGRAPH 2006 Sketches and Applications. 中，預期要將 pbrt/lights/infinite.cpp 中的 class InfiniteAreaLight 用數個點光源取代 Infinite Area Light 的寫法，提升均勻取樣的效能，而 Median Cut Algorithm 在預處理非常快，根據用多少量的點光源將影響品質，若在品質不用太好的 rendering 環境下，這是一個不錯的降質提升速度的方案。
在 Median Cut Algorithm 取樣 64 equal-energy region 的速度差異比較
算法的步驟如下：
Spectrum MedianCutEnvironmentLight::Sample_L(const Point&, float, const LightSample&, float, Vector&, float*, VisibilityTester*) 中使用)，用每一個區域內部的 pixel 位置和亮度計算重心作為代表的點光源。算法類似於 k-d Tree，但特別的是每次選擇區域維度最長的那一段進行切割，而不是像 k-d Tree 則是採用輪替維度進行。
Median Cut Algorithm 需要 \(\mathcal{O}(HW)\) 時間 \(\mathcal{O}(HW)\) 空間來預處理亮度資訊。若要切割成 \(N\) 個區域，需要 \(\mathcal{O}(\log N)\) 次迭代，每一次迭代增加兩倍區域數量。將一個區域切割時，針對維度最長的那一軸二分搜尋，二分搜尋計算其中一個區域的亮度和是否是整個區域亮度的一半，由於預處理完成的表格，可以在 \(\mathcal{O}(1)\) 時間內計算任意平行兩軸的矩形內部元素總和。
維護 sumTable[i][j] 計算左上角 \((0, 0)\) 右下角 \((i, j)\) 的亮度和，計算任意平行兩軸矩形內部和只需要 \(\mathcal{O}(1)\) 時間。
float getEnergy(float sumTable[], int width, int height) {
float e = sumTable[VERT(ru, rv)];
if (lu) e -= sumTable[VERT(lu-1, rv)];
if (lv) e -= sumTable[VERT(ru, lv-1)];
if (lu && lv) e += sumTable[VERT(lu-1, lv-1)];
return e;
}另一種方案，可以從 pbrt 原生的
class MIPMap取代上述寫法，MIPMap的寫法採用分層式的架構，每一層將原圖長寬各縮小一半。計算某矩形元素總和時，藉由兩層的總和估計進行內插。理論上，這種寫法雖然不夠精準，但提供很好的快取優勢。
一般重心計算採用以下公式：
\[X_c = \frac{\sum^{}_{(x, y) \in \mathit{region}} L_{(x, y)} \; x}{\sum^{}_{(x, y) \in \mathit{region}} L_{(x, y)}} \\ Y_c = \frac{\sum^{}_{(x, y) \in \mathit{region}} L_{(x, y)} \; y}{\sum^{}_{(x, y) \in \mathit{region}} L_{(x, y)}} \]
經由 Median-Cut Algorithm 在 Texmap 1 運行後，代表的點光源明顯地偏離亮區，因此為了讓代表的點光源更靠近亮區，我們將其重心公式修改成 Centroid Formula 2。
若以 \(\mathit{Energy} \propto L^2_{(x, y)}\)，能量與亮度二次成正比，則計算出的重心會更靠近亮區。
\[X_c = \frac{\sum^{}_{(x, y) \in \mathit{region}} L^2_{(x, y)} \; x}{\sum^{}_{(x, y) \in \mathit{region}} L^2_{(x, y)}} \\ Y_c = \frac{\sum^{}_{(x, y) \in \mathit{region}} L^2_{(x, y)} \; y}{\sum^{}_{(x, y) \in \mathit{region}} L^2_{(x, y)}} \]
比較結果如下：
拖曳圖片下方的白色鍵頭，左圖為 Centroid Formula 1 / 右圖為 Centroid Formula 2 (建議使用 Firefox)
拖曳圖片下方的白色鍵頭，左圖為 Centroid Formula 1 / 右圖為 Centroid Formula 2，由於圖片尺寸稍大需要放大觀看。
相較於原生寫 Infinite Area Light，用 64 個點光源明顯地造成在車頂過亮
Reference / Median Cut Algorithm (envlight 256 samples, Centroid Formula 1)
|
Reference / Median Cut Algorithm (envlight 256 samples, Centroid Formula 2)
|
利用 Photomatrix 進行 tone mapped 後，從地板影子看出 Centroid Formula 1 相較於 Centroid Formula 2 所選的點光源比較不集中，相當零散。
Reference / Median Cut Algorithm (envlight 256 samples, Centroid Formula 1, tone mapping)
|
Reference / Median Cut Algorithm (envlight 256 samples, Centroid Formula 2, tone mapping)
|
Centroid Formula 1 和 Centroid Formula 2 最大的差異在於車尾燈的光影，Centroid Formula 2 算出來較接近原圖。
Reference / Median Cut Algorithm (envlight-new 256 samples, Centroid Formula 1)
|
Reference / Median Cut Algorithm (envlight-new 256 samples, cCentroid Formula 2)
|
在 Median Cut Algorithm 取樣 64 equal-energy region 的速度差異比較
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
|
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
|
Infinite Area Light
|
My Implementation 1
|
My Implementation 2
|
|
|
|
My Implementation 1, 4 equal-energy region
|
My Implementation 1, 16 equal-energy region
|
My Implementation 1, 64 equal-energy region
|
My Implementation 1, 256 equal-energy region
|
|
My Implementation 1, 4 equal-energy region
|
My Implementation 1, 16 equal-energy region
|
My Implementation 1, 64 equal-energy region
|
My Implementation 1, 256 equal-energy region
|
|
My Implementation 2, 4 equal-energy region
|
My Implementation 2, 16 equal-energy region
|
My Implementation 2, 64 equal-energy region
|
My Implementation 2, 256 equal-energy region
|
|
My Implementation 1, 4 equal-energy region
|
My Implementation 1, 16 equal-energy region
|
My Implementation 1, 64 equal-energy region
|
My Implementation 1, 256 equal-energy region
|