Fundamentals of Computer Graphics

本文是 《Fundamentals of Computer Graphics》 Reading Review 。

1 Introduction

1.1 Graphics Areas

• Modeling : 将形状与外表存储在计算机中
• Rendering : 从 3D 模型创建 2D 阴影图像
• Animation : 通过 2D 图像序列形成动作
• User Interaction
• Virtual Reality
• Visualization
• Image Processing
• 3D Scanning
• Computational Photography

1.2 API

• API 可以分为两类
  • Graphics APIs : 渲染输出
  • User-interface APIs : 用户输入

1.3 Graphics Pipeline

• 三角形投影
  • z-buffer
• 4D 坐标

1.4 Numerical Issues

• IEEE Floating Point 标准规定了三个特殊值
  • +inf
  • -inf
  • NaN

这三个特殊值能够参与数值运算和布尔运算。

1.5 Graphics Program

• Classes

  • vector2 : 2D 向量
  • vector3 : 3D 向量
  • hvector : 齐次向量
  • rgb : RGB 值
  • transform : 代表变换的 4x4 矩阵
  • image : 二维 RGB 矩阵

• Debugging Methods

  • 假设错误所在的模块，并修改该模块以验证
  • 用图片作为 debug 的输出
  • 使程序有确定的输出，在有 bug 的像素位置设断点，查看该像素的计算过程。同时多设置 assert，在出错时自动定位。
  • 通过可视化 debug

2 Miscellaneous Math

一些数学预备知识

2.1 Sets and Mappings

• 集合(sets)
• 映射(mappings)
• 逆映射(inverse mappings)
• 区间(intervals)
  • 开区间
  • 闭区间
• 对数(logarithms)

2.2 Solving Quadratic Equations

二次方程的解。

2.3 Trigonometry

• 三角学
  • 角度(angles)
  • 三角函数
  • 海伦公式

2.4 Vectors

• 向量
• 向量运算
  • 数乘
  • 点乘
  • 叉乘
• 笛卡尔坐标
• 施密特正交化
• SVD 奇异值分解

2.5 Curves and Surfaces

• 隐式方程
  • 平面、曲面
  • 直线、曲线
• 梯度
• 偏导
• 参数方程

2.6 Linear Interpolation

线性插值
对于给定的两个点 A、B，从 A 到 B 的线性插值为

\[ f(t) = tA + (1-t)B \]

2.7 Triangles

三角形的顶点会存储颜色等信息，渲染时三角形面上的信息由顶点信息线性插值得到，这一插值方式叫 重心坐标(barycentric coordinates) 。

2.7.1 2D Triangles

对于给定的平面三角形，记三个顶点分别是 A、B、C

\[ S = \frac{1}{2} || AB \times AC || \]

在重心坐标系下，平面上任意一点都可以用三角形顶点唯一表示

\[ P = \alpha A + \beta B + \gamma C \quad (\alpha+\beta+\gamma=1) \]

• 重心坐标有一些良好的性质：
  • 平面上一点 P 在三角形内部，当且仅当 \(\alpha, \beta, \gamma \in(0,1)\)
    • 一者为 0 时，P 在三角形边上
    • 二者为 0 时，P 是三角形顶点
  • 三角形重心 G 满足 \(\alpha=\beta=\gamma=\frac{1}{3}\)
  • 记 \(S_{PBC}\) 表示 \(\Delta PBC\) 的有向面积，则 \(\alpha= \frac{S_{PBC}}{S_{ABC}}\) ，其余同理
  • 记 \(f_{BC}(P)\) 表示 P 到 BC 的有向距离，则 \(\alpha = \frac{f_{BC}(P)}{f_{BC}(A)}\) ，其余同理

2.7.2 3D Triangles

2D 三角形的重心坐标可以很好地推广到 3D ，包括有向面积和有向距离的公式。

除了这些，还可以使用外积计算，这可以由有向面积直接推导得来

\[ \begin{align} n_{a} & = (C-B) \times (P-B) \\ \alpha & = \frac{n \cdot n_{a}}{||n||^2} \end{align} \]

这里的关键在于保证采用相同的正方向，例如 ABC 的面积采用 \(AB \times AC\) ，则 PBC 的面积就要用 \(PB \times PC\) ，保证 P 在形内时，PBC 面积符号与 ABC 相同。

3 Raster Images

光栅图像(Raster Images) 又称 位图图像(Bitmap Images) ，图像由长方形的像素矩阵构成，每个像素存储一定颜色信息。

这里需要区分 图像像素(Image Pixels) 和 显示像素(Display Pixels)
图像像素是图像文件被存储的形式，而显示像素是显示设备能够调用的像素。由于图片本身可能被缩放或旋转，因此图像像素和显示像素间可能不是一一对应关系。当谈论光栅图像时，这是一个与设备无关的事物。而显示设备是一种近似光栅图像的方式。

3.1 Raster Devices

栅格设备可以分为

• Output
  • Display
    • Transmissive: liquid crystal display (LCD)
      • 像素本身不发光，控制透光量
      • 通过中心晶体的偏振角度控制透光
    • Emissive: light-emitting diode (LED) display
      • 像素本身发光，控制发光量
      • 像素可以分为亚像素(subpixels) ，分别对应不同颜色 RGB
    • 对于显示类输出设备，分辨率(resolution) 是像素的数量
  • Hardcopy
    • Binary: ink-jet printer
    • Continuous tone: dye sublimation printer
    • 对于打印类输出设备，分辨率是像素的密度而非数量
• Input
  • 输入设备需要对每个像素进行光线测量，这通常通过传感器序列实现
  • 2D array sensor: digital camera
    • 传感器构成二维矩阵，每个传感器测量一个像素
    • 传感器只能测量光强不能测量波长
      • Demosaicking : 一个像素只测量一个颜色，不同颜色相间排列，由软件负责填补缺失的部分
      • 每个像素用三个传感器测量 RGB
  • 1D array sensor: flatbed scanner

3.2 Images, Pixels and Geometry

现实图像可以被抽象为二维位置的函数

\[ I(x,y) : R \to V \]

• \(R \subseteq \mathbb{R}^2\) 表示一个图像平面
• \(V\) 表示所有可能的取值
  • 灰度图 \(V=\mathbb{R}^+\)
  • RGB 图 \(V = (\mathbb{R}^+)^3\)

注意现实图像是模拟信号，值是连续的而非离散的。

输入设备，例如相机，对现实图像采样得到离散的像素网格，每个像素的值都是一块现实区域内值的平均，最终得到栅格图像(Raster Images)。
输出设备对栅格图像进行采样和平均，得到显示图像(Display Images)。
图像成为一种采样表示。

在本书中，像素坐标系的原点在图像左下角，水平为 x 轴，竖直为 y 轴，像素坐标是二维非负整数坐标。

\[ P = \{ (i,j) |\ i\in \{ 0, 1, \dots,n_{x}-1 \},j\in \{ 0,1,\dots,n_{y}-1 \} \} \]

每个像素点对应一片以该点为中心的区域

\[ (i,j) \sim [i-0.5,i+0.5] \times [j-0.5,j+0.5] \]

完整的区域为

\[ R = [-0.5, n_{x}-0.5] \times[-0.5,n_{y}-0.5] \]

3.2.1 Pixel Values

• High Dynamic Range, HDR

  • 用浮点存储图像信息
  • 占据空间大

• Low Dynamic Range, LDR (Fixed-range)

  • 用无符号整型存储图像信息，例如 8 位像素的值为 \(\{ 0,1,\dots,255 \}\) ，代表的强度为 \(\left\{ \frac{k}{255} \right\}_{0}^{255}\) 注意这里分母是 255 而非 256，为了能够表示 0 和 1 。

• 几种常见的像素值

  • 1-bit Grayscale
    • 只取 0/1
  • 8-bits LDR RGB
  • 16-bits fixed-range Grayscale
  • 16-bits HDR RGB
  • 32-bits HDR RGB

• 减少存储所使用的空间会导致

  • Clipped : 超过上下界的数值被裁剪
  • Quantization / Banding : 精度减小导致舍入

3.2.2 Monitor Intensity and Gamma

显示器接收一个像素值作为输入，并将其转化为光强输出。

通常输入和输出间遵循以下形式的公式：

\[ I = I_{max}v^\gamma \]

其中，\(I_{max}\) 是最大光强，\(v\) 是输入，\(I\) 是输出光强，\(\gamma\) 是非线性程度。

为了适配显示器的这种非线性，图像信息在编码时会进行 Gamma Correct/Gamma Encoding

\[ v' = v^{1/\gamma} \]

输入与输出间的非线性关系最初并不是认为设计的，而是 CRT 显示器的物理特性。现代 LCD、OLED 虽然原理不同，但为兼容已有标准，也会模拟 Gamma 特性。
另一方面，人眼对光强的感知也是非线性的，对暗部的感知比亮部更精细，采用非线性存储能够增加暗部信息精度。

3.3 RGB Color

RGB 颜色通过红、绿、蓝三种颜色来组合任意颜色

• red + green = yellow
• green + blue = cyan
• blue + red = magenta,
• red + green + blue = white

RGB 空间 \(\{ (r,g,b)|\ r, g, b \in [0,1] \}\) 。

RGB 值同样进行 Gamma Encoding 。

3.4 Alpha Compositing

不透明的图像覆盖另一张图像，可以直接覆写像素值。但半透明的图像叠加到另一张图像上，需要混合两张图像的像素值。另一种情况是两个物体都是不透明的，但是同一像素内同时出现两个物体，若只取一个物体的像素值，则容易出现边缘锯齿。

混合公式是

\[ c = \alpha c_{1} + (1-\alpha)c_{2} \]

• 半透明物体混合，\(\alpha\) 表示物体1的透明度
• 不透明物体混合，\(\alpha\) 表示物体1在像素中的占比

图像像素的 \(\alpha\) 值可以单独用一张灰度图存储，被称为 Alpha Mask 或 Transparency Mask ，或作为 RGB 的第四个维度，被称为 Alpha Channel 。

4 Ray Tracing

渲染(Rendering) 输入一组三维物体，输出一组二维像素。
- Object-order Rendering : 依次考虑各个物体，计算对每个像素的贡献
- Image-order Rendering : 依次考虑每个像素，计算各个物体对其贡献
后者更加常见也更加灵活。

光线追踪(Ray Tracing) 是一种 Image-order Rendering 算法。

4.1 The Basic Ray-Tracing Algorithm

当视角和场景确定后，决定某个像素的光线就被确定了。从视点（相机）出发，向像素点引一条射线，这就是决定该像素的光线，称为该像素的 视线(Viewing Ray) 。与这条视线相交的所有物体，就是对该像素有贡献的物体。

1. Ray Generation : 根据相机位置和成像平面计算每个像素的 Viewing Ray
2. Ray Intersection : 确定与视线相交的物体
3. Shading : 计算物体对像素的贡献

4.2 Perspective

三维场景有很多投影到二维平面的方法，这对应了不同透视方式。

• 平行投影(Parallel Projection) ：三维物体上的所有点向投影平面作平行线，垂足即投影点
  • 平行线方向称为 投影角度(Projection Direction)
  • 若投影线与投影平面正交，则称为 正交投影(Orthographic) ，否则称 斜射投影(Oblique)
  • 平行投影能够保持平行线投影后平行，且平行于投影面的物体形状不变
  • 缺少近大远小的深度感
• 直线透视(Linear Perspective)/透视投影(Perspective Projection) ：通过让平行线相交于一点来制造深度的感觉
  • 现实中的人眼和相机接收的并不是平行光，而是过视点的光线
  • 从视点出发，向物体上的点引直线，与成像平面的交点就是投影点
  • 根据射影定理，平行线的投影会交与一点，称为 消失点(Vanishing Point)

4.3 Computing Viewing Rays

从视点 \(\mathbf{e}\) 向像素点 \(\mathbf{s}\) 引的射线的参数方程为

\[ \mathbf{p}(t) = \mathbf{e} + t(\mathbf{s}-\mathbf{e}) \]

• 相机坐标系(Camera Frame)
  • 记相机所朝方向作为前方 \(-\mathbf{w}\)
  • 选取大致的上方 \(\mathbf{v'}\) ，这不一定与 \(\mathbf{w}\) 垂直，需要施密特正交化
  • 求 \(\mathbf{u} = \mathbf{v}' \times \mathbf{w}\) 作为右方
  • 求 \(\mathbf{v} = \mathbf{w}\times \mathbf{u}\) 作为上方
  • \(\mathbf{u}, \mathbf{v}, \mathbf{w}\) 构成右手坐标系的正交基，分别代表右方，上方，后方

4.3.1 Orthographic View

在正交投影中，物体上的所有点通过平行线投影到平面上，因此所有 Viewing Ray 都具有相同的方向。虽然这里没有相机的概念，但是我们仍用 \(-\mathbf{w}\) 表示 Viewing Ray 的方向。

不是一般性的，成像平面可以认为过视点 \(\mathbf{e}\) 且以 \(\mathbf{e}\) 为原点，即 \(\mathbf{u},\mathbf{v}\) 张成的平面。在这一平面上，可以用 \(\mathbf{u},\mathbf{v}\) 作为基向量建立二维坐标。

• 用 \((l,r,b,t)\) 分别表示图像的四条边在成像平面上的位置：
  • 左边：\(\mathbf{e}+l\mathbf{u}\)
  • 右边：\(\mathbf{e}+r\mathbf{u}\)
  • 上边：\(\mathbf{e}+b\mathbf{v}\)
  • 下边：\(\mathbf{e}+t\mathbf{v}\)

接下来建立 \(n_{x}\times n_{y}\) 的像素网格坐标到相机坐标系坐标的对应，坐标 \((i, j)\) 的像素应该有相机坐标系下的坐标 \((u, v)\) ：

\[ \begin{align} u & = l + \frac{r-l}{n_{x}} (i+0.5) \\ v & = b + \frac{t-b}{n_{y}}(j+0.5) \end{align} \]

![[Pasted image 20260912142330.png]]

在正交投影中， Viewing Ray 的起点可以简单的认为是像素点。

• 综上 Viewing Ray：
  • Origin : \(\mathbf{e} + u\mathbf{u}+v\mathbf{v}\)
  • Direction : \(-\mathbf{w}\)

非正交的平行投影可以很自然的从正交情形推广得到，只需要区分投影方向 \(\mathbf{d}\) 和 \(\mathbf{w}\) 。

4.3.2 Perspective Views

在透视投影中，成像平面与视点具有一定距离，称为 成像平面距离(Image Plane Distance) 或 焦距(Focal Length) ，记为 \(d\) 。

• Viewing Ray :
  • Origin : \(\mathbf{e}\)
  • Direction : \(- d\mathbf{w} +u\mathbf{u} + v\mathbf{v}\)

4.4 Ray-Object Intersection

得到 Viewing Ray \(\mathbf{p}(t) = \mathbf{e} + t \mathbf{d}\) 后，计算第一个相交的物体。

对于一个曲面 \(f(\mathbf{p})=0\) ，计算与 Viewing Ray 的交相当于解方程

\[ f(\mathbf{e}+ t \mathbf{d}) =0 \]

4.4.1 Ray-Sphere Intersection

给定球面

\[ (\mathbf{p}-\mathbf{c})^2 = R^2 \]

代入 Viewing Ray 方程得到

\[ (\mathbf{e}+t\mathbf{d})^2 = R^2 \]

这是关于 \(t\) 的一元二次方程，可以解得 \(t\) 。

4.4.2 Ray-Triangle Intersection

设三角形三个顶点为 \(\mathbf{a},\mathbf{b},\mathbf{c}\) 。借助三角形重心坐标系建立方程

\[ \begin{cases} \mathbf{e} + t\mathbf{d} = \alpha \mathbf{a}+\beta \mathbf{b}+\gamma \mathbf{c} \\ \alpha + \beta + \gamma = 1 \\ 0 < \alpha,\beta, \gamma <1 \end{cases} \]

消元 \(\alpha\) ，可以得到标准线性系统

\[ \begin{bmatrix} x_{a}-x_{b} & x_{a}-x_{c} & x_{d} \\ y_{a}-y_{b} & y_{a}-y_{c} & y_{d} \\ z_{a}-z_{b} & z_{a}-z_{c} & z_{d} \end{bmatrix} \begin{bmatrix} \beta \\ \gamma \\ t \end{bmatrix} = \begin{bmatrix} x_{a}-x_{e} \\ y_{a}-y_{e} \\ z_{a}-z_{e} \end{bmatrix} \]

4.4.3 Ray-Polygon Intersection

给定平面多边形，设其有 \(m\) 个顶点，依次为 \(\mathbf{p}_{1},\mathbf{p}_{2},\dots,\mathbf{p}_{m}\) ，记平面法线为 \(\mathbf{n}\) 。

首先求 Viewing Ray 和平面的交点 \(\mathbf{p}=\mathbf{e}+t\mathbf{d}\)，这可以通过解下述方程得到：

\[ (\mathbf{e}+t\mathbf{d}-\mathbf{p_{1}})\cdot \mathbf{n} = 0 \]

再判断 \(\mathbf{p}\) 是否在多边形内。

首先注意到平行投影不会改变 \(\mathbf{p}\) 在形内还是形外，因此可以先将多边形投影到 xy-平面或别的平面上简化计算。接着以 \(\mathbf{p}\) 的投影点为原点向任意方向引射线，若射线与多边形的边有奇数个交点，则 \(\mathbf{p}\) 在形内，否则在形外。

这里需要注意投影可能导致平面坍缩成线。可以考虑多边形法向量 \(\mathbf{n}=(x_{n},y_{n},z_{n})\) 。选取其中绝对值最大的分量作为投影方向，例如 \(|x_{n}|\) 最大则投影到 yz-平面。

另一种处理多边形的方法是将其切分为多个三角形。

4.4.4 Intersecting a Group of Object

对于一组物体，可以分开单独考虑。

4.5 Shading

在决定像素的表面被确定后，像素值会根据 着色模型(Shading Model) 被计算。本节介绍两种简单的着色模型。

大部分着色模型的原理是计算光线的反射，光从光源出发，经表面反射，抵达相机。

4.5.1 Lambertian Shading

表面反射的光强与入射角的余弦值成正比。

\[ L = k_{d}I \max(0,\mathbf{n}\cdot \mathbf{l}) \]

• \(L\) : 像素值
• \(k_{d}\) : 漫反射系数(Diffuse Coefficient)
• \(I\) : 光源强度
• \(\mathbf{n}\) : 表面单位法向量
• \(\mathbf{l}\) : 光源单位方向向量

注意，每个颜色通道可能有单独的 \(k_{d}\) 和 \(I\) ，需要分开计算，或作为向量计算。

\[ \mathbf{L} = \mathbf{k_{d}} \odot \mathbf{I} \cdot \max(0,\mathbf{n}\cdot \mathbf{l}) \]

4.5.2 Blinn-Phong Shading

Lambertian Shading 只与光源、表面材质有关，与观察角度无关。但真实的表面会产生高光，这是因为光线比较集中的向某个方向反射，即镜面反射。

根据镜面反射，当入射光线和视线关于法线对称时，观察到的光线最强，因此可以用视线 \(\mathbf{v}\) 和镜面反射方向 \(\mathbf{r}\) 的夹角余弦值来衡量观察到的反射强度，这就是 Phong 提出的镜面反射分量。

\[ C_{s} = k_{s}I \max(0, \mathbf{r}\cdot \mathbf{v})^p \]

其中 \(p\) 是高光指数，\(k_{s}\) 是高光系数。

Blinn 对该公式做了改进，记半程向量 \(\mathbf{h}= \frac{\mathbf{l}+\mathbf{v}}{||\mathbf{l}+\mathbf{v}||}\) 表示入射光线 \(\mathbf{l}\) 和视线 \(\mathbf{v}\) 的角平分方向，则镜面反射分量可以写作

\[ C_{s} = k_{s}I \max(0, \mathbf{n}\cdot \mathbf{h})^p \]

• 完整的着色模型由两项构成
  • 漫反射分量(Diffuse Component)，即 Lambertian Shading
  • 高光分量(Specular Component)

\[ L=k_d I \max(0,\mathbf n\cdot\mathbf l)+k_s I \max(0,\mathbf n\cdot\mathbf h)^p \]

4.5.3 Ambient Shading

设定一定的环境光分量(Ambient Component)，在没有光源照射的情况下也不会是纯黑的。

\[ C_{a} = k_{a}I_{a} \]

• \(k_{a}\) : 表面环境光系数，由表面材质决定
• \(I_{a}\) : 环境光强度，由环境决定

4.5.4 Multiple Point Lights

多光源情形可以分解为单光源情形的简单叠加

\[ L = k_{a}I_{a} + \sum_{i=1}^N [k_{d}I_{i}\max(0,\mathbf{n}\cdot \mathbf{l}_{i})+k_{s}I_{i}\max(0,\mathbf{n}\cdot \mathbf{h}_{i})^p] \]

4.6 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  # 背景色

4.6.1 Object-Oriented Ray-Tracing Program

OOP 的思想将事物组织为类，例如 Surface 类派生 Triangle、Sphere、Group 类等。

所有可以与 Viewing Ray 相交的事物都可以被抽象为 Surface 类，这一类的公共方法 hit 判断是否与 Viewing Ray 碰撞，并返回碰撞记录。

class Surface{
    /** 
    求 Viewing Ray 和 Surface 的交点，参数范围 [t0, t1)
    Args:
        r(Ray): Viewing Ray，用 e+td 参数方程表示
        t0(float): 从 t0 开始寻找
        t1(float): 到 t1 寻找结束
    Returns:
        hit(bool): 是否相交
        rec(HitRecord): 碰撞记录，包括材质、法线、视线等信息
    */
    virtual auto hit(Ray r, float t0, float t1) -> [bool, HitRecord];

    /** 返回 Surface 的 bounding box */
    virtual auto bounding_box() -> Box;

    /** 表面材质 */
    Material* material;  
}

class HitRecord{
    float t;  // 交点参数
    Vector3 n;  // 表面法向量
    float ka;   // 环境光系数
    float kd;   // 漫反射系数
    float ks;   // 高光系数
    float p;    // 高光指数
}

class Ray{
    Vector3 origin;
    Vector3 direction;
}

Box 类是边与坐标轴平行的立方体，通过对角顶点可以唯一确定一个 axis-aligned bounding box 。

球面实现 bounding_box()

Box Sphere::bounding_box(){
    Vector3 min = center - Vector3(radius, radius, radius);
    Vector3 max = center + Cector3(radius, radius, radius);
    return Box(min, max)
}

Material 类封装材质，包括漫反射系数、镜面反射系数等等。

class Material{
    float ka;   // 环境光系数
    float kd;   // 漫反射系数
    float ks;   // 高光系数
    float p;    // 高光指数
}

4.7 Shadows

求出像素点 Viewing Ray 与表面的交点后，需要判断这些交点的阴影。其余表面点的阴影并不会反映到像素上。

阴影与着色类似。从表面点 \(\mathbf{p}\) 出发，向光源方向 \(\mathbf{l}\) 引射线 \(\mathbf{p}+t\mathbf{l}\) ，这被称为 Shadow Ray 。若 Shadow Ray 在到达光源前与别的表面相交，则该点有阴影。

• 与 Viewing Ray 的区别

  • Viewing Ray 从相机出发，指向像素点
  • Shadow Ray 从表面点出发，指向光源

• 自相交阴影

  • 若从 \(t=0\) 开始判断，可能由于浮点数误差将 \(\mathbf{p}\) 所在表面判断为相交表面
  • 因此通常从小数 \(t=\epsilon\) 开始判断

Blinn-Phong Lighting + Shadow Ray

def raycolor(r: Ray, t0: float, t1: float):
    rec: HitRecord             # viewing ray hit record
    shadow_rec: HitRecord            # shadow ray hit record

    hit, rec = scene.hit(r, t0, t1)

    if hit:                 
        p = e + rec.t * r.direction      # 交点
        color = rec.ka * scene.Ia        # 着色，背景色

        shadow_ray = Ray(p, l)
        shadow_hit, shadow_rec = scene.hit(shadow_ray, EPSILON, INF)
        if not shadow_hit:
            # 未被遮蔽
            h = normalize(normalize(l) + normalize(-r.d))  # 半程向量
            c = c
                + rec.kd * scene.I * max(0, rec.n @ l)
                + rec.ks * scene.I * max(0, (rec.n @ h)^(rec.p))
        return c
    else:
        return background-color

• scene 指整个场景，scene.hit(r) 会遍历场景中的所有物体，并返回第一个碰撞点
• normalize() 用于单位化向量
• r.d 从相机指向像素
• l 是光源方向
• 只要有物体，无论是否被遮蔽，都至少有环境光分量
• 这一算法只考虑表面直接接收光源光线，而未考虑反射后的光线。考虑后者的光追算法被称为 全局光照(Global Illumination)

4.8 Ideal Specular Reflection

上一节中的算法只考虑了光源对物体表面的直接着色，但物体表面反射的光线同样能对别的表面着色，这被称为 间接光照(Indirect Illumination)。因此引入理想镜面反射。

Viewing Ray 方向 \(\mathbf{d}\) 从相机指向像素，也指向表面交点 \(\mathbf{p}\) 。光线在表面反射可以逆向考虑为 Viewing Ray 在表面反射，这一反射视线方向为

\[ \mathbf{r} = \mathbf{d} - 2(\mathbf{d}\cdot \mathbf{n})\mathbf{d} \]

其中 \(\mathbf{n}\) 是表面法线。

反射视线参数方程为 \(\mathbf{p}+s\mathbf{r}\) 。这一反射视线若与物体碰撞，则贡献颜色，计算方法可以直接沿用 raycolor() 。每一次反射光强会衰减，不同颜色的衰减系数不同，记为 \(k_{m}\) 。

加入新的贡献：

\[ C = C + \mathrm{raycolor}(\mathbf{p}+s\mathbf{r},\epsilon,\infty) \]

注意这一公式是递归的，每一次反射视线的计算都可能引入新的反射视线，递归终点是反射视线不与物体发生碰撞。

通常设置最大递归深度，以避免无限反射。

5 Linear Algebra

本章回顾一些线性代数知识。采用列主序向量。

5.1 Determinants

给定二维向量 \(\mathbf{a}, \mathbf{b}\) ，行列式 \(|\mathbf{a}\ \mathbf{b}|\) 可以表示 \(\mathbf{a}\) 和 \(\mathbf{b}\) 张成的三角形面积。这是有向面积，若 \(\mathbf{a}\) 到 \(\mathbf{b}\) 为逆时针，则符号为正，否则为负。

给定三维向量 \(\mathbf{a},\mathbf{b},\mathbf{c}\) ，行列式 \(|\mathbf{a}\ \mathbf{b}\ \mathbf{c}|\) 表示平行六面体体积。若 \(\mathbf{a},\mathbf{b},\mathbf{c}\) 遵循右手序，则符号为正，否则为负。

5.2 Matrices

• 矩阵运算
  • 加法
  • 数乘
  • 矩阵乘法
    • 结合律
    • 分配律
  • 转置
  • 逆
  • 行列式
• 特殊矩阵
  • 对角矩阵
  • 对称矩阵
  • 正交矩阵
• 行列式展开

5.3 Computing with Matrices and Determinants

三维向量 \(\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}\) 共面等价于

\[ \begin{vmatrix} \mathbf{a}-\mathbf{d} & \mathbf{b}-\mathbf{d} & \mathbf{c}-\mathbf{d} \end{vmatrix}=0 \]

• 计算行列式

  • Laplace 展开
  • 代数余子式(cofactor)

• 伴随矩阵(adjoint matrix)

• 伴随矩阵求逆
• 线性系统(Linear System)

5.4 Eigenvalues and Matrix Diagonalization

特征值(Eigenvalues) 与特征向量(Eigenvectors)

\[ A \mathbf{v} = \lambda \mathbf{v} \]

• 对称矩阵（厄米矩阵）必然可以对角化，且有一组正交特征向量
• 特征值分解
• 奇异值分解(Singular Value Decomposition, SVD)

6 Transformation Matrices

• Scaling 缩放
  • 通常是对角矩阵，对角线上是各轴缩放倍数。
• Shearing 切变
  • 主对角线全是 1，某个非对角位置有切变系数 k
• Rotation 旋转
  • 正交矩阵
  • 行列式值 +1
• Reflection 反射
  • 正交矩阵
  • 行列式值 -1

6.1 Composition and Decomposition of Transformation

• Composition of Transformation

  • 左乘矩阵代表一次变换
  • 对于连乘，从右侧开始变换

• Decomposition of Transformation

  • 对称阵的特征值分解
    • 旋转-缩放-逆旋转
  • 方阵的奇异值分解
    • 旋转-缩放-旋转
  • 根据 SVD ，任意方阵代表的变换都可以被理解为：旋转-缩放-旋转
  • 旋转矩阵的 Paeth Decomposition
    • 将旋转矩阵分解为切变矩阵
    • 有时切变比旋转更方便，这是因为在舍入后， shear 对每一整行（或每一整列）做的是同一个整数位移，所以不会把这一行内部的像素拉开，也就不会产生“洞” 。而应用旋转矩阵后的数值在舍入后可能不均匀。

旋转矩阵

\[ R(\theta)=\begin{bmatrix}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{bmatrix} \]

可以分解成：

\[ R(\theta)=\begin{bmatrix}1 & -\tan(\theta/2)\\0 & 1\end{bmatrix}\begin{bmatrix}1 & 0\\\sin\theta & 1\end{bmatrix}\begin{bmatrix}1 & -\tan(\theta/2)\\0 & 1\end{bmatrix} \]