光線跟蹤算法

為了生成在三維計算機圖形環境中的可見圖像，光線跟蹤是一個比光線投射或者掃描線渲染更加逼真的實現方法。這種方法通過逆向跟蹤與假象的照相機鏡頭相交的光路進行工作，由於大量的類似光線橫穿場景，所以從照相機角度看到的場景可見信息以及軟件特定的光照條件，就可以構建起來。當光線與場景中的物體或者媒介相交的時候計算光線的反射、折射以及吸收。

光線跟蹤的場景經常是由程序員用數學工具進行描述，也可以由視覺藝術家使用中間工具描述，也可以使用從數碼相機等不同技術方法捕捉到的圖像或者模型數據。

由於一個光源發射出的光線的絕大部分不會在觀察者看到的光線中佔很大比例，這些光線大部分經過多次反射逐漸消失或者至無限小，所以對於構建可見信息來説，逆向跟蹤光線要比真實地模擬光線相互作用的效率要高很多倍。計算機模擬程序從光源發出的光線開始查詢與觀察點相交的光線從執行與獲得正確的圖像來説是不現實的。

這種方法的一個明顯缺點就是需要假設光線在觀察點處終止，然後進行逆向跟蹤。在一定數量的最大反射之後，最後交點處的光線強度使用多種算法進行估計，這些算法可能包括經典的渲染算法，也可能包括如輻射着色這樣的技術。

在自然界中，光源發出的光線向前傳播，最後到達一個妨礙它繼續傳播的物體表面，我們可以將“光線”看作在同樣的路徑傳輸的光子流，在完全真空中，這條光線將是一條直線。但是在現實中，在光路上會受到三個因素的影響：吸收、反射與折射。物體表面可能在一個或者多個方向反射全部或者部分光線，它也可能吸收部分光線，使得反射或者折射的光線強度減弱。如果物體表面是透明的或者半透明的，那麼它就會將一部分光線按照不同的方向折射到物體內部，同時吸收部分或者全部光譜或者改變光線的顏色。吸收、反射以及折射的光線都來自於入射光線，而不會超出入射光線的強度。例如，一個物體表面不可能反射 66% 的輸入光線，然後再折射 50% 的輸入光線，因為這二者相加將會達到 116%。這樣，反射或者折射的光線可以到達其它的物體表面，同樣，吸收、反射、折射的光線重新根據入射光線進行計算。其中一部分光線通過這樣的途徑傳播到我們的眼睛，我們就能夠看到最終的渲染圖像及場景。

Arthur Appel 於 1968 年首次提出用於渲染的光線投射算法。光線投射的基礎就是從眼睛投射光線到物體上的每個點，查找阻擋光線的最近物體，也就是將圖像當作一個屏風，每個點就是屏風上的一個正方形。通常這就是眼睛看到的那個點的物體。根據材料的特性以及場景中的光線效果，這個算法可以確定物體的濃淡效果。其中一個簡單假設就是如果表面面向光線，那麼這個表面就會被照亮而不會處於陰影中。表面的濃淡效果根據傳統的三維計算機圖形學的濃淡模型進行計算。光線投射超出掃描線渲染的一個重要優點是它能夠很容易地處理非平面的表面以及實體，如圓錐和球體等。如果一個數學表面與光線相交，那麼就可以用光線投射進行渲染。複雜的物體可以用實體造型技術構建，並且可以很容易地進行渲染。

位於紐約Elmsford, New YorkMathematical Applications Group, Inc.（MAGI）的科學家首次將光線投射技術用於生成計算機圖形。1966 年，為了替美國國防部計算放射性污染創立了這個公司。MAGI 不僅計算了伽馬射線如何從表面進行反射（輻射的光線投射自從二十世紀四十年代就已經開始計算了），也計算了它們如何穿透以及折射。這些研究工作幫助政府確定一些特定的軍事應用；建造能夠保護軍隊避免輻射的軍用車輛，設計可以重入的太空探索交通工具。在 Philip Mittelman 博士的指導下，科學家們開發了一種使用同樣基本軟件生成圖像的方法。1972 年，MAGI 轉變成了一個商業動畫工作室，這個工作室使用光線投射技術為商業電視、教育電影以及最後為故事片製作三維計算機動畫，他們全部使用光線投射製作了 Tron 電影中的絕大部分動畫。MAGI 於 1985 年破產。

下一個重要的研究突破是 Turner Whitted 於 1979 年做出的。以前的算法從眼睛到場景投射光線，但是並不跟蹤這些光線。當光線碰到一個物體表面的時候，可能產生三種新的類型的光線：反射、折射與陰影。光滑的物體表面將光線按照鏡像反射的方向反射出去，然後這個光線與場景中的物體相交，最近的相交物體就是反射中看到的物體。在透明物質中傳輸的光線以類似的方式傳播，但是在進入或者離開一種物質的時候會發生折射。為了避免跟蹤場景中的所有光線，人們使用陰影光線來測試光線是否可以照射到物體表面。光線照射到物體表面上的某些點上，如果這些點面向光線，那麼就跟蹤這段交點與光源之間的光線。如果在表面與光源之間是不透明的物體，那麼這個表面就位於陰影之中，光線無法照射。這種新層次的光線計算使得光線跟蹤圖像更加真實。

光線跟蹤的流行來源於它比其它渲染方法如掃描線渲染或者光線投射更加能夠現實地模擬光線，象反射和陰影這樣一些對於其它的算法來説都很難實現的效果，卻是光線跟蹤算法的一種自然結果。光線跟蹤易於實現並且視覺效果很好，所以它通常是圖形編程中首次嘗試的領域。

光線跟蹤的一個最大的缺點就是性能，掃描線算法以及其它算法利用了數據的一致性從而在像素之間共享計算，但是光線跟蹤通常是將每條光線當作獨立的光線，每次都要重新計算。但是，這種獨立的做法也有一些其它的優點，例如可以使用更多的光線以抗混疊現象，並且在需要的時候可以提高圖像質量。儘管它正確地處理了相互反射的現象以及折射等光學效果，但是傳統的光線跟蹤並不一定是真實效果圖像，只有在非常近似或者完全實現渲染方程的時候才能實現真正的真實效果圖像。由於渲染方程描述了每個光束的物理效果，所以實現渲染方程可以得到真正的真實效果，但是，考慮到所需要的計算資源，這通常是無法實現的。於是，所有可以實現的渲染模型都必須是渲染方程的近似，而光線跟蹤就不一定是最為可行的方法。包括光子映射在內的一些方法，都是依據光線跟蹤實現一部分算法，但是可以得到更好的效果。

從眼睛發出光線到達光源從而渲染圖像的過程有時也稱為後向光線跟蹤，這是因為它是實際光線傳播方向的反方向。但是，對於這個術語來説還有一些混淆的地方。早期的光線跟蹤經常是從眼睛開始，James Arvo 等早期研究人員用後向光線跟蹤表示從光源發出光線然後收集得到的結果。因為如此，將它們分成基於眼睛或者基於光源的光線跟蹤將會更加清楚。在過去的幾十年中，研究人員已經開發了許多組合了這兩種方向的計算方法與機制以生成投降或者偏離交叉表面的或多或少的光線。例如，輻射着色算法通常根據光源對於表面的影響進行計算並且存儲這些結果，然後一個標準的遞歸光線跟蹤器可以使用這些數據生成場景的真實、物理正確的圖像。在全局照明算法如光子映射以及 Metropolis light transport 中，光線跟蹤只是一個用來計算光線在表面之間傳輸的簡單工具。

對圖像中的每一個像素 {創建從視點通過該像素的光線 初始化 最近T 為 無限大，最近物體 為 空值 對場景中的每一個物體 {如果光線與物體相交 {如果交點處的 t 比 最近T 小 {設置 最近T 為焦點的 t 值 設置 最近物體 為該物體}}}如果 最近物體 為 空值{用背景色填充該像素}否則{對每個光源射出一條光線來檢測是否處在陰影中 如果表面是反射面，生成反射光；遞歸 如果表面透明，生成折射光；遞歸 使用 最近物體 和 最近T 來計算着色函數 以着色函數的結果填充該像素}}

人們已經進行了許多努力，改進如計算機與視頻遊戲這些交互式三維圖形應用程序中的實時光線跟蹤速度。

OpenRT 項目包含一個高度優化的光線跟蹤軟件內核，並且提供了一套類似於 OpenGL 的 API 用於替代目前交互式三維圖形處理中基於光柵化（rasterization）的實現方法。

一些光線跟蹤硬件，如 Saarland 大學開發的實驗性光線處理單元，都是設計用來加速光線跟蹤處理中那些需要大量計算的操作。

自從二十世紀九十年代末開始，一些 demo programmers 愛好者就已經開發了一些光線跟蹤的實時三維引擎軟件。但是，demos 中的光線跟蹤為了實現足夠高的幀速經常使用一些不正確的近似甚至是欺騙的手段。

計算機圖形學中的光線跟蹤的名稱與原理源自於二十世紀最初十年就已經開始出現的光學鏡頭設計中的古老技術。幾何光線跟蹤用於描述光線通過鏡頭系統或者光學儀器時的傳輸特性，並創建系統的成像屬性模型。這用於建造前優化光學儀器的設計，例如減少色像差或者其它的光學像差。光線跟蹤也用於計算光學系統中的光程差，光程差用於計算光學波前，而光學波前用於計算系統的衍射作用，例如點擴展函數、調製傳遞函數以及 Strehl ratio。光線跟蹤不僅用於攝影領域的鏡頭設計，也可以用於微波設計甚至是無線電系統這樣的較長波長應用，也可以用於紫外線或者X射線光學這樣的較短波長領域。

計算機圖形學與光學設計領域所用的光線跟蹤的基本原理都是類似的，但是光學設計所用的技術通常更加嚴格，並且能夠更加正確地反映光線行為。尤其是光的色散、衍射效應以及光學鍍膜的特性在光學鏡頭設計中都是非常重要的，但是在計算機圖形學領域就沒有那麼重要了。

在計算機出現以前，光線跟蹤需要使用三角以及對數表手工計算，許多傳統攝影鏡頭的光學公式都是許多人共同完成優化的，每個人只能處理其中一小部分的計算工作。現在這些計算可以在如來自於 Lambda Research 的 OSLO 或者 TracePro、Code-V 或者 Zemax 這些光學設計軟件上完成。一個簡單的光線跟蹤版本是光線傳遞矩陣分析，它通常用於激光光學諧振腔的設計。

為了説明光線跟蹤所用的基本原理，我們來看計算一個光線與球體交點的例子。用 I 表示球面上的點，C 表示球心，r 表示半徑，那麼球面的公式為 . 如果定義一條線的起點即光線起點是 S，方向是 d，那麼線上的每個點都可以表示為

其中 t 是定義線上與起點距離的常數，為了簡化起見，通常 d 定義為單位矢量。那麼，在這種情況下已知 S、d、C 以及 r，於是代入 I 得到：

簡化 ，那麼

那麼二次方程的解是

這只是直線光線與球體交點的所用的數學公式，當然對於通用的光線跟蹤來説是遠遠不夠的，但是它至少表示了這個算法如何使用的一個實例。

Actual state

光束跟蹤

BRL-CAD

錐體跟蹤

分佈式光線跟蹤

整體光照

Line-sphere intersectionPencil tracingPhilipp Slusallek

光子映射

輻射着色

Radiance (software)

光線跟蹤硬件

鏡面反射與鏡子球體跟蹤

Target stateYafRay

Glassner, Andrew (Ed.) (1989). 光線跟蹤入門. Academic Press. ISBN 0-12-286160-4. Shirley, Peter and Morley Keith, R. (2001) Realistic Ray Tracing,2nd edition. A.K. Peters. ISBN 1-56881-198-5. Henrik Wann Jensen. (2001) Realistic image synthesis using photon mapping. A.K. Peters. ISBN 1-56881-147-0. Pharr, Matt and Humphreys, Greg (2004). Physically Based Rendering : From Theory to Implementation. Morgan Kaufmann. ISBN 0-12-553180-X.

光線跟蹤新聞 - 短小的研究文章以及新的資源鏈接 使用實時光線跟蹤的遊戲用 C++ 實現光線跟蹤的系列教程The Internet Ray Tracing Competition - 靜止與動畫分類

BlenderPOV-RayPixiePBRT - 基於物理的光線跟蹤

TachyonRayshadeOpenRT - 實時光線跟蹤庫

RPS Ray Tace - 用於 SketchUp 的光線跟蹤

AccuRenderRaster3DRealStorm Engine - 實時光線跟蹤引擎

BRL-CAD更多的光線跟蹤源代碼鏈接ZemaxRadianceYafrayOSLO - 鏡頭設計與優化軟件，OSLO-EDU 可以自由下載 TracePro - 帶有 CAD 界面的散射光與照明軟件