什么是全局光照

前面的计算机图形：光照模型讲的是局部光照，通过对象表面和光源的入射光线实现表面绘制.

但真实的光照效果，还包括从其他对象反射的光线，也会产生明暗效果. 这种光照计算的模型，称为全局光照. 好处是更有真实感，代价是大量计算.

光线跟踪方法

光线跟踪（ray tracing）是一种全局光照方法，核心思想：沿着到达视点的光线的反方向，从视点出发经过图像平面每个像素，找出与视线相交的物体表面点P0，继续跟踪，找出影响P0点光强的所有光源，从而算出P0点精确的光线强度，事先表面明暗效果.

优缺点：
光线跟踪算法能生成高度真实感图形，但对于表面光滑的对象，需要惊人的计算量.

基本光线跟踪算法

步骤：

建投影立坐标系
建立投影参考点（视点）在z轴、像素位置在xy平面的坐标系统.
生成像素光线
在该坐标系统中，描述场景的几何数据、生成像素光线.
对于透视投影视图，每一光线从投影参考点出发穿过每个像素中心进入场景并沿反射和投射路径形成各种光线分支.
计算光强贡献
在该表面交点（光线入射点）计算像素强度的贡献.
相交测试
为每个像素生成一条逆向光线后，需要测试场景中所有对象表面是否与该光线相交. 如果表面与光线相交，则计算处交点到像素的距离.
计算出所有表面的和该光线交点后，具有最小距离的交点，即可代表该像素所对应的可见面.
确定反射、折射路径
将该光线在该可见面上沿镜面反射路径（反射角=入射角）反射. 如果该表面是透明的，还需要考察折射光线.
反射、折射光线，统称从属光线（secondary ray）.
递归处理从属光线
对每条从属光线重复该光线处理过程. 如果有表面和其相交测试确定最近的相交表面，则递归地在沿从属光线方向最近的对象表面上生成下一条折射和反射光线.
像素（发出的）光线在场景中被反射、折射时，逐个将相交表面加入到一个二叉光线跟踪树（ray-tracing tree）. 树的做枝表示反射光线，右枝表示透射光线（折射）. 光线跟踪的最大深度可由用户指定，或由存储容量决定.
递归结束
当满足下列任一条件，就停止跟踪：

该光线不与任何表面相交
该光线与一个光源相交且该光源不是一个反射面
该树到达最大允许深度

步骤3如何计算光强贡献？
在每一表面交点，引入基本光照模型确定表面强度的贡献. 强度值存放在像素树（光线跟踪树？）的表面节点位置. 与非反射面光源（点光源？）相交的光线，可用该光源对强度赋值.
求从属光线方向

对于镜面反射，
如下图所示，将入射光线看作由视点发出，对应单位向量u，射向物体表面得到反射光线，对应单位向量R，物体表面单位法向量N，射向点光源的单位向量L. 入射角为α，反射角β.

设-u是u的反向单位向量. 有，
\((-\bm{u})\cdot \bm{N} = |-\bm{u}| |\bm{N}|\cos α\)

-u在N方向投影：\(-\bm{u_1}=(|-\bm{u}|\cos α)\bm{N}=((-\bm{u})\cdot \bm{N})\bm{N}=-(\bm{u}\cdot \bm{N})\bm{N}\)

由反射定律知，β=α，即N是R、-u的半角向量，有

\[\bm{R}+(-\bm{u})=2(-\bm{u_1})\\ \implies \bm{R}=\bm{u}-2(\bm{u}\cdot \bm{N})\bm{N} \]

对于折射（透明表面），
如下图所示，将入射光线看作由视点发出，对应单位向量u，折射光线对应单位向量T，物体表面单位法向量N，入射角\(θ_i\)，折射角\(θ_r\).

前面计算机图形：光照模型中有关折射率的部分，已经证明T可以用N、u表示.

\[\bm{T}=\frac{θ_i}{θ_r}\bm{u}-(\cos θ_r - \frac{\eta_i}{\eta_r}\cos θ_i)\bm{N} \]

其中，\(\eta_i\)和\(\eta_r\)分别表示入射材料和折射材料的折射率.
而折射角\(θ_r\)可由折射定律（Snell定律）得到：

\[\begin{aligned} &∵\eta_i\sin θ_i=\eta_r\sin θ_r\\ &∴\cos^2 θ_r=1-\sin^2 θ_r=1-(\frac{\eta_i}{\eta_r})^2\sin^2 θ_i=1-(\frac{\eta_i}{\eta_r})^2(1-\cos^2 θ_i)\\ &∵θ_r\in [0, \pi]\\ &∴\cos θ_r=\sqrt{1-(\frac{\eta_i}{\eta_r})^2(1-\cos^2 θ_i)} \end{aligned} \]

如何确定像素光线是否与对象表面相交？
这是接下来要探讨的内容.

光线与对象表面的求交计算

光线方程

一束光线沿光束方向距离\(\bm{P_0}\)为s的任一点坐标\(\bm{P}\)，可由光线方程（ray equation）表示：

\[\bm{P}=\bm{P_0}+s\bm{u} \]

其中，\(\bm{P_0}\)是初始位置，初值可设为投影平面某像素点\(P_{pix}\)或投影参考点（即视点）. 初始单位向量\(\bm{u}\)可有投影参考点\(\bm{P_{prp}}\)和光线穿过的像素位置\(\bm{P_{pix}}\)得到：

\[\bm{u}=\frac{\bm{P_{pix}-\bm{P_{prp}}}}{|\bm{P_{pix}-\bm{P_{prp}}}|} \]

\(\bm{u}\)没必要是单位向量，但作为单位向量可简化计算.

光线方程写成向量形式：

\[\overrightarrow{P_0P}=s\bm{u} \]

将光线方程应用到与对象表面求交时，只需要求出\(\bm{P_0}\)到对象表面距离s时，就能求出光线与对象表面交点\(\bm{P}\).

光线每次与表面相交，向量\(\bm{P_0}、\bm{u}\)由交点处的从属光线更新，\(\bm{u}\)的反射方向\(\bm{R}\)，折射方向\(\bm{T}\)（前面已经求出\(\bm{R},\bm{T}\)与\(\bm{u},\bm{N}\)的关系）.

求交点

光线方程将光线与对象的求交运算，转化为求光线发射点\(\bm{P_0}\)沿光线方向\(\bm{u}\)到对象表面距离s.

一般做法：联立光线方程和描述表面的方程，求解s. 通常是对方程进行数值求根和增量计算. 而对于复杂对象，经常将光线方程转换到定义对象的局部坐标系中，将对象变换成更适当的形状以简化计算.

光线-球面求交

球体：光线跟踪中最简单的对象.
给定半径r、中心\(P_c\)的球体，球面任意点P满足球面方程：

\[|\bm{P}-\bm{P_c}|^2-r^2=0 \]

∵交点P在光线u上
∴P满足光线方程：

\[\bm{P}=\bm{P_0}+s\bm{u} \]

代入球面方程：

\[|\bm{P_0}+s\bm{u}-\bm{P_c}|^2-r^2=0 \]

令\(Δ\bm{P}=\bm{P_c}-\bm{P_0}\)，而\(|\bm{u}|=1\)，可得：

\[\begin{aligned} |Δ\bm{P}+s\bm{u}|^2-r^2&=0\\ s^2(|\bm{u}|^2)+2(Δ\bm{P}\cdot \bm{u})s+|Δ\bm{P}|^2-r^2&=0\\ s^2+2(Δ\bm{P}\cdot \bm{u})s+|Δ\bm{P}|^2-r^2&=0 \end{aligned} \]

利用一元二次方程（\(ax^2+bx+c=0\)）求根公式（\(x=\frac{b±\sqrt{b^2-4ac}}{-2a}\)），可解得：

\[s=\bm{u}\cdot Δ\bm{P}±\sqrt{(\bm{u}\cdot Δ\bm{P})^2-|Δ\bm{P}|^2+r^2} \]

以下两种情况，可以不再考虑该球面：
1）如果无（实数）解，即\(\sqrt{Δ}\)无意义，说明光线与球面不相交；
2）如果2个根s均为负，说明球面在\(\bm{P_0}\)之后，即沿着\(\bm{u}\)的反向；

如果2个根均为正，则取s为模更小的那个.

优化

对于远离光束出发点的小球体，即\(r^2\ll|Δ\bm{P}|^2\)，求根近似运算时容易丢失\(r^2\)项.

此时，可重新计算s以消除误差：

\[s=\bm{u}\cdot Δ\bm{P}±\sqrt{r^2-|Δ\bm{P}-(\bm{u}\cdot Δ\bm{P})\bm{u}|^2} \]

证明：

\[\begin{aligned} Δ&=r^2-|Δ\bm{P}-(\bm{u}\cdot Δ\bm{P})\bm{u}|^2\\ \Leftrightarrow Δ&=r^2-|Δ\bm{P}|^2-(\bm{u}\cdot Δ\bm{P})^2+2(Δ\bm{P}(\bm{u}\cdotΔ\bm{P})\bm{u})\\ \Leftrightarrow Δ&=r^2-|Δ\bm{P}|^2+(\bm{u}\cdot Δ\bm{P})^2 \end{aligned} \]

即得证.

光线-多面体求交

多面体更复杂.

1）先用简单包围体进行求交测试以提高效率.
如一个被球体包围的多面体，如果光线与球面无交点，则无需再对多面体进行测试.

2）如果光线与球体（包围体）相交，则需测试不等式（前表面）：

\[\bm{u}\cdot \bm{N} < 0 \]

其中，u是光线方向单位向量，N是多面体表面法向量.

如果多面体某个表面满足求交测试，说明该面为前表面，而非后表面.

3）联立方程求交点
如何求光线与该前表面交点P？

思路：联立多面体表面方程与光束方程，得到初始光线位置\(P_0\)到平面的距离s.

设前表面所在平面方程：
Ax+By+Cz+D=0

则法向量N=(A,B,C)，参数A、B、C、D可由前表面3个多边形顶点确定（不共线三点确定一个平面）.

前表面上任一点\(P(x_p,y_p,z_p)\)满足平面方程：

\[\bm{N}\cdot \bm{P}=(A,B,C)\cdot (x_p,y_p,z_p)=Ax_p+By_p+Cz_p=-D \]

将光束方程\(\bm{P}=\bm{P_0}+s\bm{u}\)代入上式：

\[\bm{N}\cdot(\bm{P_0}+s\bm{u})=-D \]

可得，

\[s=-\frac{D+\bm{N}\cdot \bm{P_0}}{\bm{N}\cdot \bm{u}} \]

其中，s代表光线初始位置\(P_0\)沿着光束方向\(\bm{u}\)到达多边形一个表面所在平面的距离.

4）光线与多边形相交测试（内-外测试）

多边形是一个有限区域（并非无限平面），因此还需确定光线是否与该表面相交，可对通过1）的表面进行内-外测试.
前面计算机图形：输出图元讲过，这里复习下. 内外测试法用于判断对象的内部区域，有2种常用方法：奇偶规则、非零环绕数规则.

奇偶规则：从任意位置P到对象坐标范围以外的远点画一条概念上的射线，统计该射线与各边的交点数目. 如果交点数目为奇数，则P是内部点；否则P是外部点.

非零环绕数规则：统计多边形以逆时针方向环绕某一特定点的次数，称为环绕数，初值0. 从任意位置P到对象坐标范围外的远点画一条射线，射线不能与多边形顶点相交. 当P沿着射线方向移动时，统计穿过该射线的边的方向. 当多边形从右到左穿过射线时，环绕数+1；从左到右时，环绕数-1. 所有穿过的边都已经计数后，环绕数最终值决定了P的相对位置：如果环绕数≠0，则P定义为内部点；否则，P是外部点.

减少求交计算的方法

光线跟踪中，约95%时间用于光线与表面求交计算. 而求交计算中，大部分时间用于计算沿光束方向不可见对象的求交.

如何减少花费在求交计算上的时间？
有两种方法：包围盒，空间分割.

包围盒方法

包围盒：将相邻对象用一个包围盒（盒或球）包起来，然后测试光线与包围体的交点. 如果没有交点，则无须对被包围对象进行求交测试.

可以推广到利用包围体的层次结构，将几个包围体包围在一个更大的包围体中，方便对场景对象进行层级式分割，对各层包围体进行相交测试.

空间分割方法

空间分割（space-subdivision）：将整个场景包含在一个立方体中，然后将立方体逐次分割，直到每个子立方体（体元）单元所包含的对象的表面或表面数目 ≤ 预设最大值.

如果用并行和向量处理技术，每个体元包含的最大表面数目，可由向量寄存器的大小、处理器的个数决定. 分割单元可用一颗八叉树或二叉分割树（BSP树）存储.

如何分割立方体？

2种策略：
1）均匀分割（uniform subdivision），每次将立方体分割成8个相同大小的体元；
2）自适应细分（adaptive subdivision），仅对包含对象的立方体区域进行分割.

如何求交测试？

跟踪穿过立方体体元的光线，只需要对包含表面的单元执行求交测试，所得相交的第一个对象表面就是可见面.

体元大小和所包含的表面数目（最大值）之间进行取舍，如果最大表面数目定得太小，则体元体积将过小，大量时间耗费在体元的相交测试中；如果数目定得太大，则体元体积过大，可能起不到分割空间的效果.

像素光线与体元表面相交示意图：

将其单独拎出来：

给定光束方向\(\bm{u}\)和某个体元的入口位置\(\bm{P_{in}}\)，则可能的出口表面法向量\(N_k\)与\(\bm{u}\)夹角\(θ_k\)为锐角，即

\[\bm{u}\cdot \bm{N_k}=|\bm{u}||\bm{N_k}|\cos θ_k=\cos θ_k>0,k=1,2,3 \]

其中，\(\bm{N_k}\)表示该立方体体元的第k个面的单位法向量. 如果让分割体元的表面与坐标轴对齐，则有

\[\bm{N_k}=\begin{cases} (±1,0,0)\\ (0,±1,0)\\ (0,0,±1) \end{cases},k=1,2,3 \]

对于每个体元表面，法向量\(\bm{N_k}\)是固定的，因此只需要检查\(\bm{u}(u_x,u_y,u_z)\)中各分量符号即可，就能确定3个可能出口表面.

由光线方程，可得三个表面（所在平面）的出口位置：

\[\bm{P_{out,k}}=\bm{P_{in}}+s_k\bm{u} \]

其中，\(s_k\)为沿光线从\(\bm{P_k}\)至\(\bm{P_{out,k}}\)的距离.

前面已证明，单位法向量N的平面上任一点P满足：\(\bm{N}\cdot \bm{P}=-D\)，D是平面方程\(Ax+By+Cz+D=0\)的参数.

∵出口点\(\bm{P_{out,k}}\)位于出口平面，法向量\(\bm{N_k}\)

∴\(\bm{N_k}\cdot \bm{P_{out,k}}=-D_k\)

结合光线方程，可得：

\[\begin{aligned} &\bm{N_k}\cdot (\bm{P_{in}}+s_k\bm{u})=-D_k\\ &s_k=\frac{-D_k-\bm{N_k}\bm{P_{in}}}{\bm{N_k}\cdot \bm{u}} \end{aligned} \]

因为一条直线与一个立方体最多有2个交点（出去重合），其中一个已是入口点，另一个是出口点. 取最小的\(s_k\)，对应表面为出口表面.

简化：
如果让体元的表面与坐标轴平行，取法向量\(\bm{N_k}=(1,0,0)\)，设\(\bm{u}=(u_x,u_y,u_z), \bm{P_{in}}=(x_0,y_0,z_0), \bm{P_{out,k}}=(x_k,y_k,z_k)\)，则

\[s_k=\frac{\bm{N_k}\cdot \bm{P_{out,k}}-\bm{N_k}\cdot \bm{P_{in}}}{\bm{N_k}\cdot \bm{u}}=\frac{x_k-x_0}{u_x} \]

又\(\bm{N_k}\cdot \bm{P_{out,k}}=-D_k\)
∴\(x_k=-D_k\)

加速（3种方法）：
1）将与\(\bm{u}=(u_x,u_y,u_z)\)的最大分量垂直的表面作为特定出口表面k，然后将该出口表面分成多个部分（0,1,2,...,8）.

如果交点\(\bm{P_{out,k}}\)在区域0，则该表面为真正的出口表面；
如果交点在区域1，则上表面为真正的出口表面；
如果交点在区域3，则下表面为真正的出口表面；
如果交点在区域4或2，则左或右边界表面为真正的出口表面（从右往左看立方体区域0）；
如果交点在5、6、7、8，则有3个表面为可能的出口表面，需要进一步求交计算；

2）光线缓存（light-buffer）技术绘制.

基本思想：每个立方体中心定位在一个点光源上，立方体的每个表面由一个正方形网格分割. 光线跟踪程序保存一张透过每个正方形光线能看见的对象的排列列表，从而加速光线的处理.

3）方向分割

求交测试中，可用方向分割加速. 用一组光线的夹角区域，对方向进行分割. 每个区域内，将对象表面按深度排序，每束光线只需要在包含它的区域内对对象测试.

模拟相机的聚焦效果

需要为投影平面前的凸透镜（或相机的光圈）指定聚焦长度、其他参数，使有些对象能聚焦而另一些对象在交点之外.

聚焦长度指从透镜中心到聚焦点F之间的距离，F是一组经过该透镜的平行线的汇聚点. 35mm相机的聚焦长度一般是50mm.

相机光圈常用参数n描述：

\[n=\frac{f}{2r} \]

其中，f称为f数或f刻度（光圈数），r是光圈半径.

典型的凸透镜侧视图：

光线跟踪算法一般用薄透镜公式（thin-lens equation）：

\[\frac{1}{d}+\frac{1}{d_i}=\frac{1}{f} \]

其中，参数d是透视中心到一个对象的距离，\(d_i\)是透镜中心到聚焦该对象的图像平面的距离. 对象与其图像位于经过透镜中心的一条直线上、透镜的两侧，d>f.

也就是说，要讲距离透镜d的特定对象聚焦，可将像素平面置于透镜后\(d_i\)处.

注意：透镜的焦点是平行光线垂直入射透镜后聚焦到一点，非垂直入射光线不一定落到焦点.

设场景中一对象距离透镜距离为d'，
如果d' ≠ d，则对象的投影点不会聚焦在图像平面；
如果d' > d，则该点聚焦到图像平面之前；
如果d' < d，则该点聚焦到图像平面之后.

位于d'的一个点（看作直径1）在图像平面上的投影近似一个小圆圈，称为模糊圆（the circle of confision），直径：

\[2r_c=\frac{|d'-d|f}{nd} \]

选择相机参数，使得一定距离范围内的模糊圆尺寸最小（\(2r_c\)最小），该距离范围称为相机的景深（depth of field）.

光线跟踪反走样

走样是由于低频取样造成信息失真.

2种基本的光线跟踪反走样技术：过取样（super sampling）、适应性取样（adaptive sampling）.

基本思想

将像素看成一个有限的正方形区域，而非一个单独的点.

1）过取样：在每个像素区域内，采用多束均匀排列的光线（取样点）；

2）适应性取样：在像素区域内，对一些部分采用不均匀排列的光线，也可用随机分布的光线.

当每个像素采用多束光线时，像素的光强通过区域内各束光线强度求平均得到.

一个简单的过取样示意图：

过取样在每个像素的4个角都生成一束光线，如果4束光线强度差异较大，或光线之间有小对象存在，则需要将该像素区域进一步分割，并重复以上过程.

分割像素区域：比如可以用16束光线分割9个子区域，每束光线位于子像素的（4个）角点. 如下图：

适应性取样对四角光束强度不相同（更严格）或有小对象的子像素进行细分，细分一直持续到每个子像素的光强近似相等或者每个像素中光束数达上限（如256）.

分布式光线跟踪

分布式光线跟踪（distributed ray tracing）：根据光照模型中多种参数随机分布光线的取样方法.

光照参数：像素区域、反射、折射方向、相机镜头区域、时间等.

分布式光线跟踪主要提供在对对象表面光照进行准确的物理描述时所需的多重积分的Monte Carlo（蒙特卡洛）估计值.

随机分布光线缺点：
像素平面随机分布光线，可以实现像素区域，但完全随机的光线位置可能导致像素内部分区域出现密集光束，而另一部分却未经取样.

像素区域抖动

解决办法：在规则子像素网格上，采用抖动（jitlering）技术，可获得像素区域内光束的较好的近似分布.

抖动：将一个像素区域划（单位正方形）分为16个子区域，在每个子区域内生成随机的抖动位置（jitler position）. 通过将每个子区域的中心坐标抖动一个小分量\(δ_x, δ_y(-0.5<δ_x, δ_y<0.5)\)来获得随机光线位置\((x+δ_x,y+δ_y)\)，将其作为中心坐标为(x,y)的单元内的光线位置.