计算机图形学的一个基本操作是渲染3D物体，例如由很多个几何物体组成的场景或模型，然后再从某一个角度观察3D模型并生成对应的2D图片。从根本上来讲，渲染是输入一些物体并输出一个矩阵的像素，因此渲染要考虑每一个物体是如何影响每一个像素的。通常有两种顺序，分别是以物体为序的渲染(object-order rendering)与以图片为序的渲染(image-order rendering)。其中物体为序指的是遍历每一个物体，考虑每一个物体对所有像素的影响。图片为序指的是遍历每一个像素，考虑每一个像素受所有物体的影响。这两种方法产生的最后结果是类似的，但是他们有一些不同的优点与缺陷，会在第八章进行更多讨论。就一个前瞻而言，图片为序的渲染更容易实现与更改适用范围来产生不同的效果，但是需要消耗更多的运行时间。我们在这里先介绍图片为序渲染的光线追踪算法，相比起物体为序的渲染来讲需要更少的数学工具。
1. 基础的光线追踪算法
可见此文的3.2部分。流程为根据摄像机的几何属性来计算每个像素光线的起始点和方向，其次寻找在该光线上第一个相交（最近）的物体，最后根据该物体的颜色、法向量和光照等信息计算出像素的颜色。
2. 透视
摄影与计算机图形学很多时候都在处理将三维物体转为二维图片的过程，其中除了会造成扭曲或变形的特殊方法外，我们通常使用线形透视的方法来直接处理。常用的有两种，分别是
-平行投影，即所有点到屏幕的投影方向是一致的,可以保持原物体的大小比例等信息，常用于工程图等
-透视投影，即所有点都投影至一个视点(View Point)，中间取屏幕的一个截面，原理接近于照相机的小孔成像。这个方法的结果与近大远小的人眼观察效果类似.
就透视方法而言可以见各类美术科普，本链接有一个较为直观简单的初步介绍。此外，投影方向和被投影的屏幕之间存在正交的(Orthographic)或者斜的(Oblique)关系。相较美术复杂严谨的透视构图而言，计算机图形学只要在算法上维持透视的正确性就可以很轻松的生成正确透视的二维图像。
3. 计算视线
可以简单讲射线表示为参数向量的形式，即\(p(t)=e+t(s-e)\)，具体如下。
其中\(e\)为相机的点位置，相机的坐标系可利用上右后的右手坐标系来进行表示\(\{u,v,w\}\)并如后文方法计算出\(s\)。
3.1 平行正交投影
可以简单让所有视线方向为摄像机的正面方向，即\(-w=s-e\)。接下来在摄像机处构成一个\((u,v)\)垂直于\(-w\)的一个平面，将物体投影至平面上。本文使用\(l<0<r,b<0<t\)的横向与纵向位移为限制，位移单位为\(u,v\)的单位向量。我们的目的是将最终成像的大小\((n_x,n_y)\)点阵图像素\((i,j)\)转换到这个投影平面坐标\((a,b)\)上。如果将像素点放在对应小方格的中间而不是左下角，则可得\(a=l+(r-l)/n_x*(i+0.5),b=(t-b)/n_y*(j+0.5)\),其中\(0.5\)是像素点在方格中间导致的位移，而\((r-l)/n_x\)则是横向的单位方格长。在计算出平面坐标\((a,b)\)后，可以得到投影点坐标为\(e+au+bv\)，注意这里的\(u,v\)默认为单位向量。
3.2 透视投影
透视平面在摄像机前构成一个投影平面，其中摄像机到投影平面的距离为\(d\)，被称为图片平面距离(Image Plane Distance)或者焦距(Focal Length)。与之前一样通过像素位置\((i,j)\)计算投影平面坐标\((a,b)\)，则视线方向为\((e-dw+au+bv)-e=-dw+au+bv\)，视线原点为\(e\)。
4. 视线与物体相交
我们从上一节已经得到了视线的公式\(e+td\),其中\(e\)是起始点，\(d\)是方向向量。我们通常认为\(t\in[0,+\infty)\)，考虑相交问题时需要考虑是否存在最小的\(t\)使得射线接触物体。虽然很多操作时我们通常考虑与三角形进行接触，但是在此部分也会讨论一些特殊图形的特殊处理方法。
4.1 与球体相交
笼统来讲如果有三维隐式函数表示的Surface\(f(p)=0\)，我们可以解方程\(f(p(t))=f(e+td)=0\)。就球体来讲我们有\(f(p)=(x-x_c)^2+(y-y_c)^2+(z-z_c)^2-R^2=0\)或\((p-c)\cdot(p-c)-R^2=0\)，代入视线函数\(p(t)=e+td\)得到\((e+td-c)\cdot(e+td-c)-R^2=(d\cdot d)t^2+2d\cdot(e-c)t+(e-c)\cdot(e-c)-R^2=0\)，可以解\(t\)的二元一次方程得解。
4.2 与三角形相交
视线与三角形相交问题(Ray-Triangle Intersection)有很多方法，这里使用基于重心坐标(Barycentric coordinate)的Möller-Trumbore(MT)算法，主要因为其需要的内存空间较小且速度较快。此链接附带另外两个方法，
首先我们将三角形写作两个向量的参数平面即\(f(u,v)\)，可得相交点为\(e+td=f(u,v)\)。因为\(x,y,z\)三个方向的相等带来了三个公式，以及我们拥有\(u,v,t\)三个未知数，存在利用计算方法直接求解的可能。假设三角形三点为\(a,b,c\)，则可有\(e+td=\alpha+\beta(b-a)+\gamma(c-a)\)。如果\(\beta,\gamma>0，\beta+\gamma<1\)则可得交点在三角形内，否则在三角形外。如果无解可能是三角形三点共线(degenerate)或者射线与三角形平面平行且不重合。MT算法通过利用线性代数中的克莱姆法则（Cramer Rule）来直接得解。克莱姆法则计算上可以理解为行列式的比率，分母是原线性变换矩阵的行列式，分子是将参数所对应的列改为结果向量。例如\(\beta\)是对应第一列，则将第一列改为结果的\([x_a-x_e,y_a-y_e,z_a-z_e]\)。几何上稍显复杂，建议观看此视频。其方法是对于向量\((\beta,\gamma,t)\)来讲，可以将\(\gamma\)值看做\((\beta,\gamma,t),j,k\)三个向量组成的平行六面体体积。经过\(A\)的矩阵变换后\((\beta,\gamma,t)\)变成了结果向量的\((x_a-x_e,y_a-y_e,z_a-z_e)\)，另外两个\(j,k\)则分别变为变换矩阵的第二列和第三列（线性变换的基础）。通过行列式代表体积变换比率的原则，可得“原体积=变换后体积/体积改变比率”。其中\(\beta\)的值为原体积，\(|A|\)为变换矩阵的行列式即体积改变比率，公式就讲清楚了。这里需要注意的是，如果\(|A|=0\)，这代表视线方向与三角形的两个向量组成的行列式值为0，几何意义上表示由\((i,j,k)\)组成的单位立方体体积经过矩阵\(A\)变换后的体积缩小到了\(0\)，进而代表视线与三角形共面甚至共线，此情况下直接判断为不相交即可（即使相交也不看不到，三角形厚度为0）。
MT算法在计算时使用克莱姆法则而不是更快的高斯消元主要是因为通常我们不需要知道全部三个\(\beta,\gamma,t\)值就能判定三角形与视线是否相交。就实际操作时，我们会判定\(t\)是否在视线限制范围内的\([t_0,t_1]\)种，检测\(\gamma\)是否在\([0,1]\)之间，最后再检测\(\beta>0,\beta+\gamma<=1\)。因为提前筛选的原因，很有可能在第一步和第二步克莱姆法则就已经停止运算返回结果，不需要全部的高斯消元来计算三个值。具体见下图。
4.3 与多边形相交
对于一个包含点\(p_1,p_2,\cdots,p_n\)以及法向量\(n\)的多边形来讲，有隐式函数\((p-p_1)\cdot n=0\)。连立视线函数\(p=e+td\)可得\(t=\frac{(p_1-e)\cdot n}{d\cdot n}\)。通过\(t\)可以计算出点\(p=e+td\)，其次检查\(P\)是否在多边形内。一个检查方法是将多边形投影至\(xy,yz,xz\)平面的任何一个上，然后自点\(P\)创造一个任意射线（通常是沿着标准xyz方向中的一个），如果射线交多边形的投影个数为奇数则点\(P\)在多边形内。选取三个平面中的较好的一个是为了避免多边形在某个单一平面的投影为一条线的情况。另外一个方法则是将多边形切割为三角形再进行判定，更接近实际操作的方法。
4.4 与多个物体相交
一个简单的方法是依次检测每一个物体，并选取\(t\)值最小，即距离最近的物体。
5. 着色(Shading)
在找到视线与物体的交点后，像素值会依据不同的着色模型来被计算出来。此处记录两个常用的着色模型，更多的模型会在第十单元进行讨论。大部分的着色模型设计是模仿光的反射过程，即被光源照射的表面将一部分的光反射至照相机的过程。通常使用三个关键参数，分别是朝向光源的向量\(l\)，朝向相机的向量\(v\)与表面法向量\(n\)。就不同模型而言可能还有一些其他参数，例如表面的颜色、光泽度等。
5.1 Lambertian Shading
Lambertian Shading仅与光源方向及表面法方向(\(l,n\))相关，两者之间的cos夹角决定了反射光的强度。公式为\(L=k_d I max(0,n\cdot l)\)，意义上为"像素值=漫反射系数光线强度夹角光强保留系数"。这个方法采取了简单的漫反射方法，也被称为Diffuse Shading。
5.2 Blinn-Phong Shading
Lambertian Shading的结果与视线方向无关，但是在现实生活中不同的观察角度会有不同的光照效果，球体也有镜面式反射的位置随着视角移动而变化的效果（Specular reflection）。因此很多着色模型会在Lambertian shading的漫反射部分（Diffuse Component）外额外增加一个镜面反射部分（Specular Component）。
Blinn-Phong Shading是由两人前后提出的着色模型，主要增加当光线和视线围绕法线越接近对称则拥有更高亮度的特性，这一特性是符合常识的（对称则光反射后直接进入人眼或相机）。实现的方法是从光线与视线两个向量\(v,l\)中取中间方向向量\(h\)。如果中间向量\(h\)与法向量\(n\)更为接近，则说明视线与光线越对称。公式与示意图分别如下,此处\(k_s\)为镜面反射系数，\(p\)被称为Phong exponent,主要让镜面反射部分的值下降得更快，使得对称部分呈高光的白色，其他部分则快速降低镜面反射部分的像素值。如果\(p\)值很小，则很有可能出现镜面反射部分大于漫反射部分的情况，导致整个物体呈白色。
5.3 Ambient Shading（环境光照）
为了避免没有被光照或者角度极差的表面在成像时完全为黑色，实际操作时可能会对所有表面增加一个固定值的环境光照。因此上文的Blinn-Phong Shading可以被修改为以下情况。需要注意的是\(k_a,k_d,k_s\)为三个系数，但是都是以颜色或者其他属性表示的。
5.4 多点光源
在处理多点光源的时候有很多模型，一个可用的模型是简单的将各个光源的值相加得解，具体如下。
6. 光线追踪程序
在刚才的章节内已经介绍了如何计算出视线，如何检测视线与物体相交，以及如何基于Blinn-Phong着色模型计算交点对像素的影响。在这三者之下，可以写出以下的简单光线追踪程序的伪代码。
6.1 OOP设计的光线追踪程序
在实际操作的时候，可以设计一个abstract class称为surface，然后各类几何物体\(triangle, sphere, polygon, group\)等设置为子类。这样大部分通用的计算方法都可以在surface类编写，减少冗余。一些可用的method包括检查视线是否接触surface的hit函数以及得到表面外围最大碰撞箱的boudning-box函数。还有一些可以使用的大类包括Material或者Texture等，具体设计与使用可以参考其他章节以及一些现实的项目。
7. 阴影（Shadows）
光线追踪程序的阴影较为容易计算。如果检测点\(P\)是否在阴影，只需要自点\(P\)向光源处作一条射线进行物体碰撞检测即可。如果碰到了物体则说明无法从点\(P\)行至光源，反向说明\(P\)在阴影中。我们常将该射线称为shadow rays（阴影线）。这里简单使用全局光造成的阴影作为例子，即假设光源（比如太阳）在极远处，则所有点的光照来源都一致。具体算法如下。注意这个算法\(e+td\)形容的是从照相机来的视线，而\(p+sl\)说的是阴影线。其中\(s\)取一个小的正\(\epsilon\)为起始范围是为了避免因为计算精度问题导致计算阴影线碰撞时把起始点点\(P\)平面自己算了进去。
理想镜面反射（Ideal Specular Reflection）
对于镜面地板或者简单镜面反射的水面来讲，光线追踪都能很简单的添加理想镜面反射的功能。第一步是计算视线与反射面的反射角度\(r=d-2(d\cdot n)n\)，示意图如下
其次，我们使用一个递归函数\(raycolor(p+sr,\epsilon,\infty)\)去寻找反射线的颜色，具体实现方法多种多样，一个简单的方法可以是在有限次数的反射内加权计算反射线碰撞到的表面颜色，并注意每次折射之后光线的能量损失。这么一来反射导致的光强则为如下。
最终的效果见下图
