计算机图形学笔记(一)：数学基础与理论根基#

向量加法（Vector Addition）#

数学定义：对于 n 维向量 $u$ 和 $v$，其和定义为： $u + v = \begin{pmatrix} u_1 + v_1 \\ u_2 + v_2 \\ \vdots \\ u_n + v_n \end{pmatrix}$

几何解释：

• 平行四边形法则：$u + v$ 是以 $u$ 和 $v$ 为邻边的平行四边形的对角线
• 三角形法则：将 $v$ 的起点放在 $u$ 的终点，连接 $u$ 的起点和 $v$ 的终点

代数性质：

• 交换律：$u + v = v + u$
• 结合律：$(u + v) + w = u + (v + w)$
• 零元素：$u + 0 = u$
• 逆元素：$u + (-u) = 0$

GAMES101项目实现：

1
// Eigen库中的向量加法
2
Eigen::Vector3f u(1.0f, 2.0f, 3.0f);
3
Eigen::Vector3f v(4.0f, 5.0f, 6.0f);
4
Eigen::Vector3f result = u + v;  // (5, 7, 9)
5

6
// 在光栅化中的应用：顶点位置变换
7
Eigen::Vector3f vertex_position = base_position + displacement;

向量数乘（Scalar Multiplication）#

数学定义：对于标量 $k \in \mathbb{R}$ 和向量 $\vec{v} \in \mathbb{R}^n$： $k\vec{v} = \begin{pmatrix} kv_1 \\ kv_2 \\ \vdots \\ kv_n \end{pmatrix}$

几何效果分析：

• $k > 1$：向量伸长 $k$ 倍，方向不变
• $0 < k < 1$：向量缩短为原长度的 $k$ 倍，方向不变
• $k = 0$：得到零向量
• $k < 0$：向量反向并缩放 $|k|$ 倍

重要应用：

• 单位向量计算：$\hat{v} = \frac{1}{\|\vec{v}\|}\vec{v}$
• 缩放变换：在几何变换中实现物体的放大缩小
• 插值计算：线性插值 $\vec{p}(t) = (1-t)\vec{p_0} + t\vec{p_1}$

点积（内积/数量积）#

数学定义：对于向量 $\vec{u}, \vec{v} \in \mathbb{R}^n$，点积定义为： $\vec{u} \cdot \vec{v} = \sum_{i=1}^{n} u_i v_i = u_1v_1 + u_2v_2 + \cdots + u_nv_n$

几何形式： $\vec{u} \cdot \vec{v} = \|\vec{u}\| \|\vec{v}\| \cos \theta$ 其中 $\theta$ 是两向量间的夹角 $(0 \leq \theta \leq \pi)$

几何意义深度解析：

• 投影解释：$\vec{u} \cdot \vec{v} = \|\vec{u}\| \cdot \text{proj}_{\vec{v}}\vec{u}$
• 标量结果：点积的结果是标量，不是向量
• 角度计算：$\cos \theta = \frac{\vec{u} \cdot \vec{v}}{\|\vec{u}\| \|\vec{v}\|}$

重要代数性质：

• 交换律：$\vec{u} \cdot \vec{v} = \vec{v} \cdot \vec{u}$
• 分配律：$\vec{u} \cdot (\vec{v} + \vec{w}) = \vec{u} \cdot \vec{v} + \vec{u} \cdot \vec{w}$
• 结合律：$(k\vec{u}) \cdot \vec{v} = k(\vec{u} \cdot \vec{v})$
• 正定性：$\vec{u} \cdot \vec{u} = \|\vec{u}\|^2 \geq 0$，等号成立当且仅当 $\vec{u} = \vec{0}$

几何判断准则：

• $\vec{u} \cdot \vec{v} = 0 \iff \vec{u} \perp \vec{v}$（垂直判断）
• $\vec{u} \cdot \vec{v} > 0 \iff \theta < 90°$（锐角）
• $\vec{u} \cdot \vec{v} < 0 \iff \theta > 90°$（钝角）

GAMES101项目中的关键应用：

1
// 1. 计算两向量夹角
2
float dot_product = u.dot(v);
3
float angle = std::acos(std::clamp(dot_product / (u.norm() * v.norm()), -1.0f, 1.0f));
4

5
// 2. 光照计算中的Lambert余弦定律
6
float cos_theta = std::max(0.0f, normal.dot(light_direction));
7
Vector3f diffuse_color = albedo * light_color * cos_theta;
8

9
// 3. 视锥体裁剪中的平面测试
10
float distance_to_plane = point.dot(plane_normal) + plane_d;
11
bool is_inside = distance_to_plane >= 0;
12

13
// 4. 背面剔除
14
Vector3f view_direction = camera_position - vertex_position;
15
bool is_front_facing = face_normal.dot(view_direction) > 0;

叉积（外积/向量积）#

数学定义：对于三维向量 $\vec{u}, \vec{v} \in \mathbb{R}^3$，叉积定义为： $\vec{u} \times \vec{v} = \begin{pmatrix} u_2v_3 - u_3v_2 \\ u_3v_1 - u_1v_3 \\ u_1v_2 - u_2v_1 \end{pmatrix}$

行列式表示：

叉积可以表示为形式行列式：

• 第1行：$(\vec{i}, \vec{j}, \vec{k})$ - 单位向量
• 第2行：$(u_1, u_2, u_3)$ - 向量 $\vec{u}$ 的分量
• 第3行：$(v_1, v_2, v_3)$ - 向量 $\vec{v}$ 的分量

$\vec{u} \times \vec{v} = \text{determinant expansion}$

几何意义深度解析：

• 方向：遵循右手定则，垂直于 $\vec{u}$ 和 $\vec{v}$ 构成的平面
• 大小：$\|\vec{u} \times \vec{v}\| = \|\vec{u}\| \|\vec{v}\| \sin \theta$
• 面积解释：$\|\vec{u} \times \vec{v}\|$ 等于以 $\vec{u}$ 和 $\vec{v}$ 为邻边的平行四边形面积

重要代数性质：

• 反交换律：$\vec{u} \times \vec{v} = -\vec{v} \times \vec{u}$
• 分配律：$\vec{u} \times (\vec{v} + \vec{w}) = \vec{u} \times \vec{v} + \vec{u} \times \vec{w}$
• 标量结合律：$(k\vec{u}) \times \vec{v} = k(\vec{u} \times \vec{v}) = \vec{u} \times (k\vec{v})$
• 平行判断：$\vec{u} \times \vec{v} = \vec{0} \iff \vec{u} \parallel \vec{v}$
• 垂直性：$(\vec{u} \times \vec{v}) \cdot \vec{u} = 0$ 且 $(\vec{u} \times \vec{v}) \cdot \vec{v} = 0$

标量三重积：

标量三重积等于三个向量构成的行列式：

• 第1行：$(u_1, u_2, u_3)$ - 向量 $\vec{u}$ 的分量
• 第2行：$(v_1, v_2, v_3)$ - 向量 $\vec{v}$ 的分量
• 第3行：$(w_1, w_2, w_3)$ - 向量 $\vec{w}$ 的分量

$\vec{u} \cdot (\vec{v} \times \vec{w}) = \text{scalar triple product}$

表示以三个向量为邻边的平行六面体的有向体积。

GAMES101项目中的核心应用：

1
// 1. 计算三角形法向量（Assignment 2/3中的关键操作）
2
Eigen::Vector3f edge1 = vertex2 - vertex1;
3
Eigen::Vector3f edge2 = vertex3 - vertex1;
4
Eigen::Vector3f normal = edge1.cross(edge2).normalized();
5

6
// 2. 判断点在三角形内部（重心坐标计算的基础）
7
Vector3f v0 = C - A, v1 = B - A, v2 = P - A;
8
Vector3f cross1 = v0.cross(v1);  // 三角形面积向量
9
Vector3f cross2 = v0.cross(v2);  // 子三角形面积向量
10
float area_ratio = cross2.dot(cross1) / cross1.squaredNorm();
11

12
// 3. 构建坐标系（相机变换中的应用）
13
Vector3f forward = (target - eye).normalized();
14
Vector3f right = forward.cross(up).normalized();
15
Vector3f camera_up = right.cross(forward);
16

17
// 4. 计算三角形面积
18
float triangle_area = 0.5f * edge1.cross(edge2).norm();

单位矩阵（Identity Matrix）#

定义：$n \times n$ 单位矩阵 $I_n$ 定义为对角线元素为1，其他元素为0的矩阵：

$(I_n)_{ij} = \delta_{ij}$

其中 $\delta_{ij}$ 是Kronecker delta函数：

当 $i = j$ 时：$\delta_{ij} = 1$

当 $i \neq j$ 时：$\delta_{ij} = 0$

基本性质：

• 乘法单位元：$AI = IA = A$（当维度匹配时）
• 几何意义：恒等变换，不改变任何向量
• 特征值：所有特征值都是1

转置矩阵（Transpose Matrix）#

定义：矩阵 $A$ 的转置 $A^T$ 定义为： $(A^T)_{ij} = A_{ji}$

重要性质：

• 对合性：$(A^T)^T = A$
• 乘积转置：$(AB)^T = B^T A^T$
• 和的转置：$(A + B)^T = A^T + B^T$
• 标量乘法：$(kA)^T = kA^T$

几何意义：

• 对于旋转矩阵：$R^T = R^{-1}$（正交矩阵性质）
• 反映了线性变换的”逆向”操作

逆矩阵（Inverse Matrix）#

定义：对于方阵 $A \in \mathbb{R}^{n \times n}$，如果存在矩阵 $A^{-1}$ 使得： $AA^{-1} = A^{-1}A = I_n$ 则称 $A^{-1}$ 为 $A$ 的逆矩阵。

存在性条件：

• 行列式非零：$\det(A) \neq 0$
• 满秩条件：$\text{rank}(A) = n$
• 线性无关：$A$ 的列向量线性无关

计算方法：

1. 伴随矩阵法：$A^{-1} = \frac{1}{\det(A)} \text{adj}(A)$
2. 高斯-约旦消元法：$[A|I] \to [I|A^{-1}]$
3. LU分解法：适用于大型矩阵

重要性质：

• $(A^{-1})^{-1} = A$
• $(AB)^{-1} = B^{-1}A^{-1}$
• $(A^T)^{-1} = (A^{-1})^T$
• $\det(A^{-1}) = \frac{1}{\det(A)}$

齐次坐标的数学基础#

引入动机：

1. 统一变换表示：将平移、旋转、缩放等变换统一为矩阵乘法
2. 透视投影简化：用线性代数处理非线性的透视除法
3. 变换复合：多个变换的复合简化为矩阵乘法
4. 无穷远点表示：优雅地处理平行线相交于无穷远点

齐次坐标的数学定义： 对于 $n$ 维欧几里得空间中的点，其齐次坐标是 $(n+1)$ 维向量：

齐次坐标 $(x, y, z, w)$ 对应笛卡尔坐标 $(x/w, y/w, z/w)$，其中 $w \neq 0$

齐次坐标的分类：

• 点的表示：$(x, y, z, 1)$ - 第四个分量为1
• 向量的表示：$(x, y, z, 0)$ - 第四个分量为0
• 无穷远点：$(x, y, z, 0)$ 且 $(x, y, z) \neq (0, 0, 0)$

齐次坐标的等价性： 所有非零标量倍数表示同一个点：

$k(x, y, z, w) \sim (x, y, z, w) \quad (k \neq 0)$

齐次坐标的运算规则#

点与向量的区别：

• 点 + 向量 = 点：$(x_1, y_1, z_1, 1) + (x_2, y_2, z_2, 0) = (x_1+x_2, y_1+y_2, z_1+z_2, 1)$
• 点 - 点 = 向量：$(x_1, y_1, z_1, 1) - (x_2, y_2, z_2, 1) = (x_1-x_2, y_1-y_2, z_1-z_2, 0)$
• 向量 + 向量 = 向量：$(x_1, y_1, z_1, 0) + (x_2, y_2, z_2, 0) = (x_1+x_2, y_1+y_2, z_1+z_2, 0)$

仿射组合： 点的仿射组合（权重和为1）仍为点：

对于点 $P_i = (x_i, y_i, z_i, 1)$，其仿射组合为： $\sum_{i} \alpha_i P_i = \left(\sum_i \alpha_i x_i, \sum_i \alpha_i y_i, \sum_i \alpha_i z_i, \sum_i \alpha_i\right)$

当 $\sum_i \alpha_i = 1$ 时，结果是有效的点。

GAMES101项目中的实际应用#

变换矩阵的统一表示：

1
// 不使用齐次坐标的变换（需要分别处理）
2
Vector3f transformed_point = rotation_matrix * point + translation_vector;
3
Vector3f transformed_vector = rotation_matrix * vector;  // 向量不受平移影响
4

5
// 使用齐次坐标的统一变换
6
Matrix4f transformation = translation * rotation * scaling;
7
Vector4f homogeneous_point(point.x, point.y, point.z, 1.0f);
8
Vector4f homogeneous_vector(vector.x, vector.y, vector.z, 0.0f);
9

10
Vector4f transformed_point = transformation * homogeneous_point;
11
Vector4f transformed_vector = transformation * homogeneous_vector;
12

13
// 转换回笛卡尔坐标
14
Vector3f result_point = transformed_point.head<3>() / transformed_point.w();
15
Vector3f result_vector = transformed_vector.head<3>();  // w分量为0，不需要除法

MVP变换链的实现：

1
// Assignment 1中的核心变换
2
Matrix4f mvp = projection * view * model;
3
for (auto& vertex : vertices) {
4
    Vector4f clip_coord = mvp * Vector4f(vertex.x, vertex.y, vertex.z, 1.0f);
5

6
    // 透视除法（齐次坐标到NDC）
7
    Vector3f ndc_coord = clip_coord.head<3>() / clip_coord.w();
8

9
    // 视口变换
10
    Vector3f screen_coord = viewport_transform * ndc_coord;
11
}

算法背景与动机#

问题描述：给定两个端点 $(x_0, y_0)$ 和 $(x_1, y_1)$，在离散的像素网格上绘制连接这两点的直线。

核心挑战：

• 像素网格是离散的，而数学直线是连续的
• 需要选择最接近理想直线的像素点
• 算法必须高效，避免浮点运算和除法

数学原理推导#

直线方程： $y = mx + b, \quad m = \frac{y_1 - y_0}{x_1 - x_0}$

决策变量的引入： 对于当前像素 $(x_i, y_i)$，下一个像素可能是 $(x_i+1, y_i)$ 或 $(x_i+1, y_i+1)$。

定义决策变量： $d_i = 2(y_i - y_{ideal}) \cdot (x_1 - x_0)$

其中 $y_{ideal} = y_0 + m(x_i + 1 - x_0)$ 是理想直线在 $x = x_i + 1$ 处的y值。

决策规则：

• 如果 $d_i < 0$，选择 $(x_i+1, y_i)$
• 如果 $d_i \geq 0$，选择 $(x_i+1, y_i+1)$

递推关系：

当 $d_i < 0$ 时： $d_{i+1} = d_i + 2(y_1 - y_0)$

当 $d_i \geq 0$ 时： $d_{i+1} = d_i + 2(y_1 - y_0) - 2(x_1 - x_0)$

初始值： $d_0 = 2(y_1 - y_0) - (x_1 - x_0)$

GAMES101项目实现分析#

1
// Assignment 1中的Bresenham算法实现
2
void rst::rasterizer::draw_line(Eigen::Vector3f begin, Eigen::Vector3f end) {
3
    auto x1 = begin.x(), y1 = begin.y();
4
    auto x2 = end.x(), y2 = end.y();
5

6
    Eigen::Vector3f line_color = {255, 255, 255};
7

8
    int x, y, dx, dy, dx1, dy1, px, py, xe, ye, i;
9

10
    // 计算增量
11
    dx = x2 - x1;  // $\Delta x$
12
    dy = y2 - y1;  // $\Delta y$
13
    dx1 = fabs(dx);  // $|\Delta x|$
14
    dy1 = fabs(dy);  // $|\Delta y|$
15

16
    // 初始决策变量
17
    px = 2 * dy1 - dx1;  // 对应水平主导情况
18
    py = 2 * dx1 - dy1;  // 对应垂直主导情况
19

20
    // 根据斜率选择主导方向
21
    if (dy1 <= dx1) {  // |斜率| ≤ 1，水平主导
22
        // 确保从左到右绘制
23
        if (dx >= 0) { x = x1; y = y1; xe = x2; }
24
        else { x = x2; y = y2; xe = x1; }
25

26
        set_pixel(Eigen::Vector3f(x, y, 1.0f), line_color);
27

28
        for (i = 0; x < xe; i++) {
29
            x = x + 1;
30
            if (px < 0) {
31
                px = px + 2 * dy1;  // 选择水平像素
32
            } else {
33
                // 选择对角像素，y坐标需要根据方向调整
34
                if ((dx < 0 && dy < 0) || (dx > 0 && dy > 0)) {
35
                    y = y + 1;
36
                } else {
37
                    y = y - 1;
38
                }
39
                px = px + 2 * (dy1 - dx1);
40
            }
41
            set_pixel(Eigen::Vector3f(x, y, 1.0f), line_color);
42
        }
43
    } else {  // |斜率| > 1，垂直主导
44
        // 类似处理，但以y为主导方向
45
        // ... 垂直主导的实现
46
    }
47
}

算法优化与变种#

整数优化：

• 所有计算都使用整数运算
• 避免浮点数和除法运算
• 时间复杂度：$O(max(|x_1-x_0|, |y_1-y_0|))$

对称性处理：

• 通过交换坐标处理不同象限的直线
• 统一处理各种斜率情况

抗锯齿扩展：

• Wu’s算法：考虑像素覆盖面积
• 超采样：提高采样率后下采样

缩放变换（Scaling Transform）#

数学定义： 缩放变换是一种线性变换，将向量的各个分量分别乘以对应的缩放因子： $S(s_x, s_y, s_z): \begin{pmatrix} x \\ y \\ z \end{pmatrix} \mapsto \begin{pmatrix} s_x \cdot x \\ s_y \cdot y \\ s_z \cdot z \end{pmatrix}$

齐次坐标矩阵表示：

缩放变换矩阵 $S(s_x, s_y, s_z)$ 是一个 $4 \times 4$ 对角矩阵：

• 对角线元素：$(s_x, s_y, s_z, 1)$
• 其他元素均为0

$S(s_x, s_y, s_z) = \text{diag}(s_x, s_y, s_z, 1)$

几何效果分析：

• 均匀缩放：$s_x = s_y = s_z = s$
  • $s > 1$：物体放大 $s$ 倍
  • $0 < s < 1$：物体缩小为原来的 $s$ 倍
  • $s = 1$：恒等变换
• 非均匀缩放：$s_x, s_y, s_z$ 不全相等
  • 改变物体的长宽高比例
  • 可能导致圆变椭圆等形变
• 反射缩放：某个 $s_i < 0$
  • $s_i = -1$：沿第 $i$ 轴反射
  • $s_i < -1$：反射并放大
  • $-1 < s_i < 0$：反射并缩小

重要性质：

• 可逆性：当所有 $s_i \neq 0$ 时，$S^{-1}(s_x, s_y, s_z) = S(1/s_x, 1/s_y, 1/s_z)$
• 行列式：$\det(S) = s_x \cdot s_y \cdot s_z$（体积缩放因子）
• 特征值：对角元素 $s_x, s_y, s_z$ 就是特征值
• 交换性：缩放矩阵之间满足交换律

GAMES101项目实现：

1
Eigen::Matrix4f create_scaling_matrix(float sx, float sy, float sz) {
2
    Eigen::Matrix4f scaling = Eigen::Matrix4f::Identity();
3
    scaling(0, 0) = sx;
4
    scaling(1, 1) = sy;
5
    scaling(2, 2) = sz;
6
    return scaling;
7
}
8

9
// 应用示例：在Assignment 1中缩放三角形
10
Matrix4f model = create_scaling_matrix(1.5f, 1.5f, 1.5f);  // 放大1.5倍
11
for (auto& vertex : triangle_vertices) {
12
    Vector4f scaled_vertex = model * Vector4f(vertex.x, vertex.y, vertex.z, 1.0f);
13
    vertex = scaled_vertex.head<3>();
14
}

特殊缩放变换：

• 各向同性缩放：$S(s, s, s)$ - 保持形状，只改变大小
• 沿轴缩放：$S(s, 1, 1)$ - 只沿x轴缩放
• 镜像变换：$S(-1, 1, 1)$ - 沿x轴镜像

旋转变换（Rotation Transform）#

仿射变换的严格定义#

数学定义：仿射变换是线性变换与平移的复合，对于向量空间 $\mathbb{R}^n$，仿射变换 $T: \mathbb{R}^n \to \mathbb{R}^n$ 定义为： $T(\vec{v}) = A\vec{v} + \vec{b}$ 其中 $A \in \mathbb{R}^{n \times n}$ 是线性变换矩阵，$\vec{b} \in \mathbb{R}^n$ 是平移向量。

仿射空间的概念： 仿射空间是没有固定原点的几何空间，仿射变换在仿射空间中具有特殊意义：

• 点的变换：$P' = AP + \vec{b}$
• 向量的变换：$\vec{v}' = A\vec{v}$（向量不受平移影响）

仿射变换的几何性质#

保持性质（不变量）：

1. 直线性保持：直线 $L: \vec{p}(t) = \vec{p_0} + t\vec{d}$ 变换后仍为直线 $L': \vec{p}'(t) = A\vec{p_0} + \vec{b} + tA\vec{d}$

2. 平行性保持：平行直线变换后仍平行

   • 证明：平行线具有相同方向向量，$A\vec{d}$ 保持方向关系

3. 比例保持：线段上的比例关系保持不变

   • 若 $\vec{p} = (1-t)\vec{p_1} + t\vec{p_2}$，则 $\vec{p}' = (1-t)\vec{p_1}' + t\vec{p_2}'$

4. 重心保持：点集的重心变换后仍为变换后点集的重心

不保持的性质：

• 长度：$\|\vec{v}'\| \neq \|\vec{v}\|$（除非 $A$ 是正交矩阵）
• 角度：$\angle(\vec{u}, \vec{v}) \neq \angle(\vec{u}', \vec{v}')$（除非 $A$ 是相似变换）
• 面积/体积：缩放因子为 $|\det(A)|$

仿射变换的分类#

按几何效果分类：

1. 刚体变换（Rigid Transform）：$A$ 是正交矩阵，$\det(A) = 1$

   • 保持长度、角度、面积
   • 只包含旋转和平移

2. 相似变换（Similarity Transform）：$A = sR$，$s > 0$，$R$ 是正交矩阵

   • 保持角度和形状
   • 包含均匀缩放、旋转、平移

3. 一般仿射变换：任意可逆矩阵 $A$

   • 可能包含剪切、非均匀缩放等

按变换分解分类： 任何仿射变换都可以分解为基本变换的复合： $T = T_{trans} \circ T_{rot} \circ T_{scale} \circ T_{shear}$

平移变换的数学本质#

为什么平移不是线性变换： 线性变换必须满足：

1. $T(\vec{0}) = \vec{0}$（零向量保持）
2. $T(\alpha\vec{u} + \beta\vec{v}) = \alpha T(\vec{u}) + \beta T(\vec{v})$（线性性）

但平移变换 $T(\vec{v}) = \vec{v} + \vec{t}$ 不满足第一个条件： $T(\vec{0}) = \vec{0} + \vec{t} = \vec{t} \neq \vec{0} \quad (\text{当} \vec{t} \neq \vec{0})$

仿射变换的引入： 为了统一处理线性变换和平移，引入仿射变换： $T(\vec{v}) = A\vec{v} + \vec{t}$

齐次坐标中的平移表示#

齐次坐标矩阵：

平移变换矩阵 $T(t_x, t_y, t_z)$ 的结构：

• 左上角 $3 \times 3$ 子矩阵为单位矩阵
• 第4列前三个元素为平移向量 $(t_x, t_y, t_z)$
• 第4行为 $(0, 0, 0, 1)$

$T(t_x, t_y, t_z) = \text{translation matrix}$

变换过程的数学验证：

对于点 $(x, y, z, 1)$，平移变换的结果为： $(x, y, z, 1) \xrightarrow{T(t_x, t_y, t_z)} (x + t_x, y + t_y, z + t_z, 1)$

向量与点的区别：

• 点的平移：$(x, y, z, 1) \to (x+t_x, y+t_y, z+t_z, 1)$
• 向量的平移：$(x, y, z, 0) \to (x, y, z, 0)$（向量不受平移影响）

这正确反映了几何直觉：向量表示方向和大小，与位置无关。

平移变换的性质#