反向路徑採樣在MLT演算法中的運用

今年的SIGGRAPH還是蠻有趣的，以下介紹可能是有史以來SIGGRAPH同一年同時出現三篇思路非常類似的論文：

Reversible Jump Metropolis Light Transport using Inverse Mappings

Fusing State Spaces for Markov Chain Monte Carlo Rendering

Charted Metropolis Light Transport

故事要從PSSMLT和MMLT講起。自從1997年Eric Veach的MLT（Metropolis Light Transport）演算法發表以來，這個被稱為影響20世紀科技發展最重要的馬爾可夫蒙特卡洛方法（MCMC，Markov Chain Monte Carlo）演算法被引入到渲染領域，與傳統的蒙特卡洛方法（例如路徑追蹤）不同的是，它通過利用樣本之間的相關性來更好地探索一個分布函數，使得一些非常困難的路徑可以更輕易被採樣到，然而MLT演算法依賴於非常好的突變策略，原始的MLT演算法依賴於完全的隨機採樣，根本無法了解場景的一些幾何信息，突變路徑的接受概率極低，使得MLT演算法在相當一段時間並沒有太大進展。

時間到了2002年，Csaba Kelemen提出了PSSMLT演算法（Simple and Robust Mutation Strategy for Metropolis Light Transport Algorithm），如下圖所示，考慮到路徑採樣其實就是以增量的方式從每個頂點的BSDF分布從採樣得到一個方向，然後使用光線投射找到該方向與表面的交點，重複迭代直到一條路徑連接光源和攝像機，這個採樣的過程實際上是對多個[0,1]的隨機數的採樣過程，這些[0,1]隨機數構成一個高維的單位超立方體（unit-hypercube），這稱為原採樣空間（Primary sample space），所以如果直接對該空間採樣，也能夠得到一條路徑。於是PSSMLT（Primary sample space Metropolis light Transport）演算法轉而對該原採樣空間進行突變，這帶來一些好處，例如狀態轉移是對稱的，另外最重要的是因為使用重要性採樣，原採樣空間的被積函數為f/p接近為一個常數，這使得原採樣空間的被積函數更平坦，採樣的方差更低，考慮傳統的MLT演算法並沒有使用重要性採樣。

然而PSSMLT也是有缺點的，其中最重要的一點是它將「路徑採樣」當做一個黑盒子：它直觀給你一些隨機數，不管你使用什麼方法給我一條路徑就可以，例如可以使用路徑追蹤或者光子映射來產生一條突變路徑，這種原採樣空間和原始路徑空間的隔離關係使得原採樣空間並不會估計路徑空間的特徵，例如原採樣空間給定一個10個[0,1]隨機數，路徑採樣器用到第2個時發現路徑以及偏離種子路徑很遠了，如下圖所示，這種結果稱為漣漪效應（ ripple e ects），因為基於出射方向採樣的路徑追蹤無法預測後續頂點的分布，某個頂點一個微小的突變可能導致後續路徑發生較大的變換，從而使種子路徑和突變路徑差異太大而喪失相關性，進而接受率變低。由此，PSSMLT演算法在將近10年間並無太大進展。

MLT演算法被提出來後最重大的一個進展要數2014年Toshiya Hachisuka提出的MMLT演算法（Multiplexed Metropolis Light Transport），表面上看，MMLT只是將重要性採樣引入到原採樣空間，例如下圖左邊包含三個原採樣空間，每個原採樣空間對應一種特定的採樣技術，技術路徑採樣的長度，這使得可以實現這樣的功能：當有些路徑突變長時間無法被接受時，我們有可能通過改變採樣技術太快速找到突破的路徑。在下圖中，路徑除了在每個原採樣空間內部執行突變，還可以在不同採樣技術之間執行突變。

但從知識理論角度來講，MMLT的重要意義在於它將統計中的模擬回火（simulated tempering）的思路引入到了MLT演算法中，特定地，這裡使用的思路主要來自序列回火（serial tempering），回火的思路源自於模擬退火（simulated annealing），模擬退火本來用於解決最優質問題，由於物體加溫之後分子狀態之間的轉移更活躍，因此狀態更易於在全局轉移，而隨著溫度逐漸降低，狀態之間的轉移就逐漸減弱。所以為了求最優值，如下圖中的最大值，我們首先將溫度升高，然後讓其慢慢冷卻，在其過程中不斷尋找最大值，隨著溫度降低，最終將停留在最大值處。

模擬回火則是借鑒了模擬退火的思路，實際上它們並無太大聯繫（除了名字），模擬回火就是將模擬退火中的溫度看成一個離散的函數，不同的離散溫度值對應著整個狀態空間的一種劃分，這樣狀態可以在每個子狀態內部轉移，也可以在不同狀態（即溫度）之間轉移。在MMLT演算法中，溫度即是採樣技術，不同的採樣技術將原採樣空間劃分為多個子空間。

至此，MMLT演算法中路徑空間和原採樣空間仍然是相對隔離的，雖然MMLT演算法中可以在原採樣控制路徑使用的採樣技術，但是僅限於此。也由於這種隔離，另一個問題來了，即採樣技術之間的突變也可能導致漣漪效果，如下圖所示，當由攝像機向光源方向的單向路徑採樣轉變為由光源向攝像機方向的路徑採樣時，由於桌子的遮擋，其突變路徑將產生非常大的差異，從而很難被接受。

於是，我們本文的主角出現了。在上述情況中，當採樣技術發生改變時，雖然所有的[0,1]隨機數並沒有發生變化，但是由於使用了不同的採樣技術，這些隨機數被使用的方式也完全不同了，從而到時路徑發生了很大的變化。因此，理想情況下，我們希望在改變採樣技術時，能夠保持路徑不變。因此， Benedikt Bitterli於今年提出的RJMCMC（Reversible Jump Metropolis Light Transport using Inverse Mappings）使用一個反向映射方法，當從採樣技術1向採樣技術2轉移時，它將狀態1對應的原採樣空間的路徑在對應路徑空間中的形式，通過一個反向映射轉換到採樣技術2對應的原採樣空間，這個過程是決定性（deterministic）計算的，不含任何採樣的結果，由於它們在各自的原採樣空間雖然具有不同的值，但是在路徑空間它們的值是相同的，因此在計算MLT演算法中的接受率時，僅剩下跟採樣技術權重相關的項，我們可以選擇最優的採樣技術來使接受率變為1。由此，我們通過一個確定性的方法產生了一個不同狀態之間的轉移，並且它完全被接受，這種採樣技術之間的轉移太高效了。

而今年的另一篇論文， Jacopo Pantaleon的CMLT（Charted Metropolis Light Transport）幾乎也與上述思路類似，但是強調更泛化的概念，即將原採樣空間按某種標準劃分成多個不同的子空間，然後在不同子空間之間進行轉移，在轉移的過程中使用反射映射來保持路徑不變。

HISANARI OTSU的Fusing State Spaces for Markov Chain Monte Carlo Rendering在演算法上稍微不同於上述兩篇論文，但是其使用的核心概念，即由路徑空間向原採樣空間的反向映射是一致的。HISANARI OTSU的核心思路在於組合路徑空間和原採樣空間的優勢，例如對於路徑空間的Manifold Exploration，其由於探索路徑的局部流形空間的特徵，因此突變路徑的採樣效率很高，然而它卻不能有效考慮路徑的全局特徵，例如該路徑使用的採樣技術的權重。因此HISANARI OTSU將當前路徑的狀態保存在原採樣空間，這包括路徑使用採樣技術的權重，但是它並不直接對原採樣空間執行突變，而是使用流形探索對路徑執行突變，但是與流行探索直接使用突變路徑不同，HISANARI OTSU將突變的結果通過反向映射轉換會原採樣空間，然後提取其權重值，使得可以按全局對路徑的採樣結果給予評估，同時兼顧局部和全局特徵。

今年這幾篇論文質量還是可以的，並且更是有Wojciech Jarosz，Wenzel Jakob, Carsten Dachsbacher, Anton S. Kaplanyan等這些保駕護航。

《全局光照技術：從離線到實時渲染》會包含上述所有技術的詳細討論，敬請期待！