计算机图形学最基本的一个任务就是对一个三维对象进行渲染（rendering）：在二维平面上呈现三维图像。

渲染分为两类：

1. object-order rendering：依次考虑每个对象，并为每个对象找到并更新它影响的所有像素。
2. image-order rendering：依次考虑每个像素，并为每个像素找到影响该像素的所有对象，然后计算像素值。

光线追踪（ray tracing）是一种对3D场景进行渲染的 image-order rendering 类算法。

The Basic Ray-Tracing Algorithm

基本的光线追踪器有三个部分：

1. ray generation（光线生成）：根据相机的几何形状计算每个像素的视线的起始位置和方向。
2. ray intersection（光线相交）：找到与视线相交的最近的物体
3. shading（阴影）：根据光线相交的结果计算像素颜色

基本的光线追踪程序如下：

for each pixel do
	compute viewing ray
    find first object hit by ray and its surface normal n
    set pixel color to value computed from hit point, light, and n

Perspective

用二维图像表示三维物体这个问题被研究了很久，投影可以分为两大类：

1. 中心投影（center projection）
2. 平行投影（parallel projection）

最简单的投影类型就是平行投影，根据投影方向和图像平面的选择，平行投影可以分为两类：

1. orthographic projection（正交投影）

2. oblique projection（斜投影）

平行投影一般用于机械和建筑制图；因为其使平行线保持平行且保留与图像平面平行的平面对象的大小与形状；平行投影的优点也是它的缺点，在日常生活中，我们眼中关于物体的成像都是越远距离越小，这是因为眼睛和相机不会从一个视图方向收集光。如下图所示：

Computing Viewing Rays

为了产生光线，首先需要一个对光线进行表示的数学公式（如下图）： p(t) = e + t(s - e)

所有的产生光线的方法都基于正交坐标系（orthonormal coordiante）也叫做相机框（camera frame），有一个视点 e 和 u v w 三个基向量：

Orthographic Views

对于正交视图而言，结合上图可知，光线的方向为 -w ；其使用4个数字来定义图像尺寸：

1. l 和 r 是图像左右边缘的位置，从 e 沿 u 方向测量（l < 0 < r）
2. b 和 t 是图像上下边缘的位置，从 e 沿 v 方向测量（b < 0 < t）

将 n_x X n_y 像素的图像放入 (r - l) X (t - b)的矩阵中，像素点(i, j)在光栅图像中的位置（m, n）：

m = l + (r - l)(i + 0.5) / n_x

n = b + (t - b)(j + 0.5) / n_y

产生正交视图光线的程序如下：

compute m and n 
ray.direction ⬅ -w
ray.origin ⬅ e + mu + nv

Perspective Views

透视图的图像平面不再位于 e 处，而是 e 前方距离 d 处，这个距离 d 就是图像平面距离，也叫做焦距（facal length）；下图是正交投影和透视投影的对比图：

产生透视视图光线的程序如下：

compute m and n
ray.direction ⬅ -dw + mu + nv
ray.origin ⬅ e

Ray-Object Intersection

一旦我们生成了一条光线 p(t) = e + td，接下来需要做的就是找到与任何对象首次相交的满足 t > 0 的交点

Ray-Sphere Intersection

一个中心点 c = （x_c, y_c, z_c）半径为 R 的球体方程为：(x - x_c)² + (y - y_c)² + (z - z_c)² = R²

结合光线与球体方程，使用向量形式为： (p - c) · (p - c) - R² = 0

➡ (e + td - c) · (e + td - c) - R² = 0

➡ (d · d)t² + 2d · (e - c)t + (e - c) · (e - c) - R² = 0

其实就是一个自变量为 t 的一元二次方程，根据解的形式可以判断光线是否与该球体相交、相切、不接触。

Ray-Triangle Intersection

利用笛卡尔坐标系求解光线与三角形交线：

如果三角形的三个顶点为 a, b, c，那么光线和三角形相交可以表示为：e + td = a + β(b - a) + γ(c- a)

为了得到 t β γ 的值，使用坐标形式表示：

上述形式可以用矩阵表示：

Ray-Polygon Intersection

给定一个 m 个顶点（p₁ … p_m）的平面多边形和它的表面法向量 n， 计算光线和该多边形的交点的公式为： (p - p₁) · n = 0

由于 p = e + td，故而有：

t 有解则表明 交点 p 在多边形内；最简单的判断 p 是否在多边形内的方法就是从 p 点引一条 2D 射线，计算该射线和多边形边的交点个数：交点个数为奇数，那么 p 在多边形内；反之则不在。

Shading

一旦知道了像素的可视化表面，就可以通过评估阴影模型来计算像素值。

Lambertian Shading

Lambertian 模型（表面颜色不依赖于你看的方向）是最简单的阴影模型：来自光源并落在表面区域上的能量的数量取决于表面与光线的夹角。

该模型的像素颜色可以表示为：

k_d 为表面颜色的扩散系数（diffuse coefficient）；I 为光源的密集程度；n 和 l 为 图中的单位向量，可以使用 n · l 来表示夹角 Θ 的余弦值。

Blinn-Phong Shading

在实际生活中，许多表面都有一定的程度的发光、光点和镜面反射光，这取决于你看该平面的方向。Blinn-Phong 模型就在 Lambertian 模型的基础上增加了镜面反射光。

可以通过比较 v 和 l 的半向量 h 与 表面法向量 n 来判断反射光的明暗程度：如果 h 接近 n，那么镜面反射分量（specular component）明亮；反之则暗淡。

Ambient Shading

通常情况下不希望完全不照明的物体被渲染成全黑色；避免黑影的一种粗略但有用的启发式方法就是在阴影模型中添加一个恒定的分量，该分量对像素颜色的作用依赖于对象碰撞，而不依赖于表面几何形状：

k_a 为表面的环境系数（ambient coefficient），I_a 为环境光强度（ambient light intensity）。

Multiple Point Lights

对于多个点光源，其实就是相加即可：

A Ray-Tracing Program

for each pixel do 
	compute viewing ray
    if (ray hits an object with t ∈ [0, ∞)) then
    	compute n
        evaluate shading model and set pixel to that color
    else
    	set pixel color to background color

Exercises

Ex1

由题意可得：3(1 - t)² = 1

解之得：t = 1 ± 1/√3

故而光线和球体的交点为 P₁ = (1 + 1/√3, 1 + 1/√3, 1 + 1/√3)；P₂ = (1 - 1/√3, 1 - 1/√3, 1 - 1/√3)

Ex2

该三角形的重心坐标：(1/3, 1/3, 1/3)

结合光线和三角形三个顶点可得：

1 - t = 1 - β - γ

1 - t = β

1 - t = γ

解之得：t = 2/3, β = 1/3, γ = 1/3

Ex3