光子映射

光線跟蹤雖然簡單、強大、易實現，但真實世界的很多東西無法很好地處理。比如：Bleeding（輝映），Caustics（焦散）－－光被匯聚在一起的現象。

直到1993年，光子映射被提出，光線跟蹤都無法有效解決這兩個問題，而光子映射對這兩個問題提供了良好的解決方案。輝映和焦散現象都是漫反射面的間接光照造成的。用光子映射方法，這類光照可以用預計算的光子圖（Photon map）來估計。將光線跟蹤擴展為光子映射，可以產生一種能解決任何直接或間接光照的方法。而且光子映射也能處理中間介質（participating media）情況，並且很易於做並行計算。

基於光子映射的全局光照算法有兩步：第一步，從光源向場景發射光子，並在它們碰到非鏡面物體時將它們保存在一個光子圖（photon map）中，以建立光子圖。第二步，使用統計技術從光子圖中提取出場景中所有點的入射通量以及反射輻射能。光子圖與場景表述是完全分離開的，這一特性使得光子映射方法能處理很複雜的場景，包括千萬個三角面片，實例化的幾何體，複雜的過程式物體。

與有限元輻射度方法相比，光子映射的優勢是不用Meshing。簡單場景下輻射度的速度可以很快，但一旦場景複雜，輻射度速度就遠遠落後於光子映射了。而且光子跟蹤還能處理非漫射表面及焦散線，輻射度就辦不到。

和光路跟蹤，雙向光路跟蹤及Metropolis這些能用很少的內存開銷模擬所有全局光照效果的Monte Carlo光線跟蹤方法相比，光子映射的最大優點就是高效，不過代價是需要額外的內存存放光子圖。對大部分場景光子映射算法都很快，而且最終效果比Monte Carlo的要好，因為光子映射產生的錯誤大多產生的是不易引起注意低頻信號，Monte Carlo的則往往是高頻信號。

另一個好處是光子映射方法沒有什麼專利，如果從經濟角度來考慮的話。（當然這是Jensen搞笑的説法）

光子的發射是有具體的分佈函數的，比如對於一個平面光源，光子往各個方向發射的概率呈Cos分佈－－即，垂直光源平面方向的概率最大，越接近於平行方向發射出光子的可能性越小。

光子跟蹤和光線跟蹤的區別就在於光線跟蹤是收集光亮度（radiance），而光子跟蹤收集光通量（flux）。

這點區別很重要，因為一束光線與某一材質的交互作用肯定有別於一個光子與材質的交互作用，比較明顯的一個實例就是折射－－光亮度應該隨折射率的變化而變化，而光子跟蹤就不受這個因素影響（因為收集的是光通量）。當光子擊中一個面的時候，不是被反射、或傳送（折射），就是被吸收了，其結果跟該表面的參數有關，目前用來決定結果是反射、折射或吸收的技術是俄羅斯轉盤－－基本上就是隨機決定光子是否未被吸收而進行下一個光子跟蹤步驟。

哪些光子-表面的相互作用要被保存下來：只有在光子擊中漫射或更精確得講，非鏡面表面時，光子要被存下來。因為保存鏡面表面的光子不會為我們提供任何有用的信息：恰好在鏡面方向上有個光子過來的可能性是0，精確繪製境面反射的最好方法是用光線跟蹤方法，向鏡面對稱方向跟蹤光線。

每個光子在它傳輸的路徑上可以被存儲多次，包括最後它被某個漫射表面吸收。每次光子擊中表面，其位置、光子能量、入射方向將被保存下來，還有一個標記用於建造查找結構。

在光子跟蹤那一步的時候光子圖被組織為一個光子的序列，但在繪製之前，出於效率考慮，該序列被重組為一個平衡kd樹。

擴展到有中間介質的情況

一般都是假設光子的交互發生在物體表面，並默認物體的“體”對對光子沒有影響。其實把光子映射擴展到有中間介質的體上也不難，98年Jensen有一篇關於體的光子映射文章。

事實上，光子不旦可以從點、面發出，也可以從體中發出，比如一個燭火可以用從一個火焰形狀的體發出光子來模擬。

當一個光子在介質中穿過時，它有可能被散射，也可能被吸收，其概率取決於介質的密度和光子在介質中走的距離。對於不均勻的介質，光子映射方法也能比較方便得用Ray Marching解決[Jensen98]，一個簡單的Ray Marcher將介質分為許多小的Step，每一個Step更新積累的密度（積分消失係數），然後根據預計算的概率，決定光子是否被散射或吸收，是否需要進行下一個Step。

構建光子圖的過程是在光子跟蹤的時候做的，在繪製階段光子圖就只是一個用來估算場景中的那些點上的光通量以及反射光亮度的一組靜態數據。

繪製過程中將不斷在光子圖中查找離某個點最近的光子，因而找一種合適的數據結構來重組光子圖對算法的效率影響就很大，這種數據結構的要求一是要緊湊，二是要能最快搜索到最近光子。平衡kd樹就比較符合這兩個要求。在Jensen96a的文章中有比較平衡與非平衡kd樹的例子。

對場景中某一點的光亮度估計是利用該點附近的N個光子的光通量信息來進行估算的，最簡單的方法在該點周圍找能包圍N個已有光子的最小球體，處在這個球體中的N個光子的總光通量除以這個球的投影面積（也就是PI*r^2）就相當於是照度（irradiance），再乘以BRDF函數，就能得到在該照度下，場景這一點往眼睛這一方向反射的光亮度了，而這一光亮度就是我們最終合成的Image上的相應方向上那個像素的顏色。

除了用球體來Locate需要的N個光子外，還可以用Disc，橢圓平面等，可以減輕面與面之間交線處的走樣。選擇不同類型的Filter，也可以處理一些光子密度不足而產生的噪聲。

通常，最終圖像的繪製使用兩種技術，Splatting（由光子依照光亮度擴散後模糊處理，或對光子聚類後擴散）或Final Gathering（對屏幕每點，收集空間中的光子，將每個收集到的光子光亮度進行加權平均），因為直接將光子圖可視化的話，要得到一副高質的圖像需要大量的光子，而使用光線跟蹤產生比較精確的圖像需要的光子卻少得多。 像素的光亮度由一系列採樣的平均值來近似，每個採樣都是由從眼睛過一像素向場景跟蹤一條視線得到。

返回的光亮度值等於視線第一次和某個非鏡面表面相交的交點沿該視線方向的出射光亮度。

（Interactive Photon Mapping）

又稱實時光子映射（Real-time Photon Mapping），即指通過使用GPU等現代顯示硬件對光子映射過程進行加速或/並使用傳統光子映射算法中的某些步驟的近似算法進行光子映射的技術，是目前被視為將可以秒殺幾乎一切遊戲光影需求的終極圖形引擎算法，其渲染畫面可媲美現有的一切CG。目前仍屬前沿研究，使用該技術的遊戲引擎尚全部屬實驗室產品，據信其成果將在不久的將來投入工業開發。截至2010年，最快的實時光子映射算法在犧牲一些可接受的細節的情況下可以對簡單場景在NVIDIA GTX280等硬件上取得10~30fps的幀率。

Multi-Image Based Photon Tracing for Interactive Global Illumination of Dynamic Scenes, EGSR10

Interactive Screen-Space Accurate Photon Tracing on GPUs, EG06

Hardware-Accelerated Global Illumination by Image Space Photon Mapping

等