光線追蹤

光线跟踪计算机算法的一般描述

为了生成在三维计算机图形环境中的可见图像，光线跟踪是一个比光线投射或者扫描线渲染更加逼真的实现方法。这种方法通过逆向跟踪与假想的照相机镜头相交的光路进行工作，由于大量的类似光线横穿场景，所以从照相机角度看到的场景可见信息以及软件特定的光照条件，就可以构建起来。当光线与场景中的物体或者介质相交的时候计算光线的反射、折射以及吸收。
光线跟踪的场景经常是由程序员用数学工具进行描述，也可以由视觉艺术家使用中间工具描述，也可以使用从数字相机等不同技术方法捕捉到的图像或者模型数据。
由于一个光源发射出的光线的绝大部分不会在观察者看到的光线中占很大比例，这些光线大部分经过多次反射逐渐消失或者至无限小，所以对于构建可见信息来说，逆向跟踪光线要比真实地模拟光线相互作用的效率要高很多倍。计算机模拟程序从光源发出的光线开始查询与观察点相交的光线从执行与获得正确的图像来说是不现实的。
这种方法的一个明显缺点就是需要假设光线在观察点处终止，然后进行逆向跟踪。在一定数量的最大反射之后，最后交点处的光线强度使用多种算法进行估计，这些算法可能包括经典的渲染算法，也可能包括如辐射着色这样的技术。

自然现象

在自然界中，光源发出的光线向前传播，最后到达一个妨碍它继续传播的物体表面，我们可以将“光线”看作在同样的路径传输的光子流，在完全真空中，这条光线将是一条直线。但是在现实中，在光路上会受到三个因素的影响：吸收、反射与折射。物体表面可能在一个或者多个方向反射全部或者部分光线，它也可能吸收部分光线，使得反射或者折射的光线强度减弱。如果物体表面是透明的或者半透明的，那么它就会将一部分光线按照不同的方向折射到物体内部，同时吸收部分或者全部光谱并发出辐射。吸收、反射以及折射的光线都来自于入射光线，而不会超出入射光线的强度。例如，一个物体表面不可能反射66% 的输入光线，然后再折射50% 的输入光线，因为这二者相加将会达到116%。这样，反射或者折射的光线可以到达其它的物体表面，同样，吸收、反射、折射的光线重新根据入射光线进行计算。其中一部分光线通过这样的途径传播到我们的眼睛，我们就能够看到最终的渲染图像及场景。

光线投射算法

Arthur Appel 于 1968 年首次提出用于渲染的光线投射算法。光线投射的基础就是从眼睛投射光线到物体上的每个点，查找阻挡光线的最近物体，也就是将图像当作一个屏风，每个点就是屏风上的一个正方形。通常这就是眼睛看到的那个点的物体。根据材料的特性以及场景中的光线效果，这个算法可以确定物体的浓淡效果。其中一个简单假设就是如果表面面向光线，那么这个表面就会被照亮而不会处于阴影中。表面的浓淡效果根据传统的三维计算机图形学的浓淡模型进行计算。光线投射超出扫描线渲染的一个重要优点是它能够很容易地处理非平面的表面以及实体，如圆锥和球体等。如果一个数学表面与光线相交，那么就可以用光线投射进行渲染。复杂的物体可以用实体造型技术构建，并且可以很容易地进行渲染。
位于纽约 Elmsford, New York Mathematical 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 大学开发的实验性光线处理单元，都是设计用来加速光线跟踪处理中那些需要大量计算的操作。
自从二十世纪九十年代末开始，一些演示场景爱好者就已经开发了一些光线跟踪的实时三维引擎软件。但是，演示中的光线跟踪为了实现足够高的帧速经常使用一些不正确的近似甚至是欺骗的手段。
2008年6月12日，英特尔展示了一个名为《雷神战争：光线跟踪》的特殊版本《深入敌后：雷神战争》，其使用光线跟踪技术进行渲染，在720p的分辨率下每秒14-29帧。该演示采用16核（4路×4核）Xeon Tigerton系统，运行频率为2.93 GHz。
AMD在Radeon Vega 系列显卡上通过GPUOpen Radeon ProRender实现实时光线跟踪。Nvidia已经宣布在Quadro RTX工作站显卡上可进行实时光线跟踪，GeForce 20系列显卡已经具有实时光线跟踪功能。