0%

GAMES101课堂笔记

个人闲话

开课一年之后我才知道有这样一门课。知道GAMES是CCF牵头办的这件事之后,心里感觉有点怪怪的,像是一个几十年的老傻逼突然干了人事还干得挺好那种感觉。

笔记比较粗糙,是随听随记的,会持续更新,有没有总体整理我不保证。

作业似乎是不允许分享的,我就不贴了。

Lecture 1 Overview of Computer Graphics

  • 什么是图形学?
    • 很多例子
  • 为什么要学习计算机图形学?
  • 课程内容(主要分为四部分)
    • 光栅化
    • 曲线和曲面
    • 光线追踪
    • 动画/仿真

光栅化 Rasterization

把几何实体投影到屏幕上

(CG界认为能够达到30fps可以算实时real-time,低于则为离线offline)

曲线和曲面 Curves and Meshes

如何表现曲线和曲面,偏几何

光线追踪 Ray Tracing

将光线从观察者/照相机向各个像素发射光

Ray Tracing比较慢,但质量好(Trade-off)。

动画与仿真 Animation / Simulation

字面意思

  • 本课不包括
    • OpenGL/DirectX/Vulcan
    • 着色器语法
    • 三维建模/游戏开发
    • Computer Vision / Deep Learning

学习的是图形学,不是图形学API!

  • 课程细节
    • 没有硬件编程

作业网站

有 大 作 业

Lecture 2 Review of Linear Algebra

  • 图形学依赖的内容:
    • 基础的数学
      • 线性代数、微积分、统计学
    • 基础物理
      • 光学、力学
    • 杂项
      • 信号处理、数值分析
    • 一点点美感:-D

向量

  • 向量
  • 单位向量
  • 向量求和(平行四边形、三角形法则)
  • 直角坐标系
  • 点乘
    • 查询向量的夹角/余弦夹角
    • 找一个向量在另一个向量上的投影
      • 如查询\(\mathbf{b}\)\(\mathbf{a}\)上的投影,只需计算\(\frac{\mathbf{a\cdot b}}{\Vert\mathbf{a}\Vert} \hat{\mathbf{a}}\)(也就是\((\mathbf{\hat{a}\cdot b})\mathbf{\hat{a}}\)
    • 对向量进行分解
    • 确定向量的方向(同向、反向)
  • 叉乘
    • 右手坐标系\(\mathbf{x}\times\mathbf{y} = +\mathbf{z}\),否则为左手系。本课中三维坐标系都是右手系。
    • 判定左/右、内/外
      • 如果\(\mathbf{a\times b}\)的z方向为正,则\(\mathbf{a}\)\(\mathbf{b}\)的右侧。
      • 给定三角形ABC(顺序无关),分别考察\(\mathbf{AB\times AP}\)\(\mathbf{BC\times BP}\)\(\mathbf{CA\times CP}\)可以判断P在三角形内/外:三个方向相同(都在左边/都在右边)为内部,否则为外部
  • 正交基
    • 对于三维单位正交基\(\mathbf{u, v,w}\),任意向量\(\mathbf{p}\),恒有\(\mathbf{p} = \mathbf{(p\cdot u)u+(p\cdot v)v+(p\cdot w)w}\)
  • 矩阵
  • 矩阵乘法
    • 矩阵乘法\(\iff\)变换,如关于y轴做反射
  • 转置
  • 单位阵、逆矩阵
  • 叉乘\(\iff\)对偶阵的乘

Lecture 3 Transformation

本节内容:

  • 为什么要学习变换
  • 2D变换:旋转、缩放、裁剪
  • 齐次坐标
  • 组合变换
  • 3D变换(?)

缩放

\[ \begin{bmatrix}s & 0 \\ 0 & s\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}sx \\ sy\end{bmatrix} \\ \begin{bmatrix}s_x & 0 \\ 0 & s_y\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}s_xx \\ s_yy\end{bmatrix} \\ \]

分别表示同比例和不同比例的缩放

反射

关于y轴反射

\[ \begin{bmatrix}-1 & 0 \\ 0 & 1\end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}-x \\ y\end{bmatrix} \]

切变 Shear

特点:

  • 垂直分量无变化
  • 水平分量中y=0时右移0,y=1时右移a

\[ \begin{bmatrix}1 & a \\ 0 & 1\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}x + ay \\ y\end{bmatrix} \]

旋转

  • 默认情况下关于原点,逆时针

\[ \begin{bmatrix}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}x\cos\theta-y\sin\theta \\ x\sin\theta+y\cos\theta\end{bmatrix} \] 另附推导如下: \[ 设旋转前的向量\mathbf{p}=\begin{bmatrix}x \\ y\end{bmatrix}对应的复数为 re^{i\phi} \\ 则有 \left\{\begin{aligned} x = r\cos\phi \\ y = r\sin\phi \end{aligned}\right. \\ 旋转\theta后得到的向量\mathbf{p'}=\begin{bmatrix}x' \\ y'\end{bmatrix}对应的复数为re^{i(\theta+\phi)} \\ 则有 \left\{\begin{aligned} x' = r\cos(\theta+\phi) = r\cos\theta\cos\phi - r\sin\theta\sin\phi=x\cos\theta-y\sin\theta \\ y' = r\sin(\theta+\phi) = r\sin\theta\cos\phi + r\cos\theta\sin\phi=x\sin\theta+y\cos\theta \end{aligned}\right. \\ 从而有\begin{bmatrix}x' \\ y'\end{bmatrix} = \begin{bmatrix}x\cos\theta-y\sin\theta \\ x\sin\theta+y\cos\theta\end{bmatrix} = \begin{bmatrix}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} \] 以上统称——线性变换

齐次坐标

平移不是齐次变换。

\[ \begin{bmatrix}x' \\ y'\end{bmatrix} = \begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} + \begin{bmatrix}t_x \\ t_y\end{bmatrix} \] 不能表示为矩阵乘法,必须要加入一个非齐次项

然而,我们不希望平移成为一个特殊的情况——我们给向量添加第三个分量,表示非齐次的常数 \[ \begin{bmatrix}x' \\ y' \\ 1\end{bmatrix} = \begin{bmatrix}x + t_x\\ y + t_y \\ 1\end{bmatrix} = \begin{bmatrix}1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix}x \\ y \\ 1\end{bmatrix} \] 这种情况下,一个二维的点被表示为 \[ \begin{bmatrix}x \\ y \\ 1\end{bmatrix} \] 而一个二维向量被表示为 \[ \begin{bmatrix}x \\ y\\ 0 \end{bmatrix} \] 考虑点和向量的加法运算:

  • 向量 + 向量 = 向量
  • \(\pm\) 向量 = 点
  • 点 - 点 = 向量
  • 点 + 点 = 这两个点的中点(我们认为二维点\(\begin{bmatrix}x \\ y \\ w\end{bmatrix}(w\neq 0)\)等价于\(\begin{bmatrix}\frac{x}{w} \\ \frac{y}{w} \\ 1\end{bmatrix}\)

仍然符合直觉且自恰。

在引入齐次坐标后,所有的仿射变换都可以表示为齐次坐标意义下的线性变换 \[ \begin{bmatrix}x' \\ y'\end{bmatrix} = \begin{bmatrix}a & b \\ c & d\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix} + \begin{bmatrix}t_x \\ t_y\end{bmatrix} \iff \begin{bmatrix}x' \\ y' \\ 1\end{bmatrix} = \begin{bmatrix}a & b & t_x \\ c & d & t_y \\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix}x \\ y \\ 1\end{bmatrix} \] 引入齐次坐标后,上文的几个变换可以表示为: \[ 缩放\begin{bmatrix}s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1\end{bmatrix} \\ 旋转\begin{bmatrix}\cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1\end{bmatrix} \\ 平移\begin{bmatrix}1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \] 齐次坐标意义下,所有仿射变换对应的矩阵最后一行都是001

其他(如投影)不一定

逆变换

乘逆矩阵即可。

变换的组合

\[ 变换\iff往向量左边乘一个矩阵 \\ 变换的组合 \iff 往向量左边依次乘多个矩阵 \\ 向量的变换不可随意交换顺序 \iff 矩阵乘法不交换 \]

对于点\(\begin{bmatrix}x \\ y \\ 1\end{bmatrix}\),依次应用仿射变换\(A_1, A_2, \cdots, A_n\),则等价于应用一个变换\(A_nA_{n-1}\cdots A_1\)

我们对几种基本变换提供记号:\(\mathbf{T(p)}\)为平移向量\(\mathbf{p}\)\(\mathbf{R}(\alpha)\)为绕原点逆时针旋转角\(\alpha\)

如何绕给定点c旋转?

\[ \mathbf{T}(c)\cdot\mathbf{R}(\alpha)\cdot\mathbf{T(-c)} \]

3D变换

类似二维,我们也提供齐次坐标:

点表示为\(\begin{bmatrix}x \\ y \\ z \\ 1\end{bmatrix}\),向量表示为\(\begin{bmatrix}x \\ y \\ z \\ 0\end{bmatrix}\),而且规定\(\begin{bmatrix}x \\ y \\ z \\ w\end{bmatrix}(w\neq 0) = \begin{bmatrix}\frac{x}{w} \\ \frac{y}{w} \\ \frac{z}{w} \\ 1\end{bmatrix}\)

三位仿射变换表示为 \[ \begin{bmatrix}x' \\ y' \\ z' \\ 1\end{bmatrix} = \begin{bmatrix}a & b & c & t_x \\ d & e & f & t_y \\ g & h & i & t_z \\ 0 & 0 & 0 & 1\end{bmatrix}\begin{bmatrix}x \\ y \\ z \\ 1\end{bmatrix} \] 由于 \[ \begin{bmatrix}a & b & c & t_x \\ d & e & f & t_y \\ g & h & i & t_z \\ 0 & 0 & 0 & 1\end{bmatrix} = \begin{bmatrix}1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1\end{bmatrix}\begin{bmatrix}a & b & c & 0 \\ d & e & f & 0 \\ g & h & i & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \] 所以它表示”先线性变换,后平移“

Lecture 4 Transformation Cont.

今日内容:

  • 3D变换
  • 观测变换
    • 视图/相机变换
    • 投影变换
      • 正交投影
      • 透视投影

3D变换

类似二维,三维变换中有: \[ 缩放S(s_x, s_y, s_z) = \begin{bmatrix}s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & s_z & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \\ 平移T(t_x, t_y, t_z) = \begin{bmatrix}1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1\end{bmatrix} \\ \] 对于旋转则比较复杂…… \[ R_x(\alpha) = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & \cos\alpha & -\sin\alpha & 0 \\ 0 & \sin\alpha & \cos\alpha & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \\ R_y(\alpha) = \begin{bmatrix}\cos\alpha & 0 & \sin\alpha & 0 \\ 0 & 1 & 0 & 0 \\ -\sin\alpha & 0 & \cos\alpha & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \\ R_z(\alpha) = \begin{bmatrix}\cos\alpha & -\sin\alpha & 0 & 0 \\ \sin\alpha & \cos\alpha & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \\ \] 任意三维旋转则可表示为 \[ R_{xyz}(\alpha,\beta,\gamma) = R_x(\alpha)R_y(\beta)R_z(\gamma) \] 罗德里格旋转公式 \[ \mathbf{R}(\mathbf{n}, \alpha) = \cos\alpha\cdot\mathbf{I} + (1 - \cos\alpha)\mathbf{n}\mathbf{n}^T + \sin\alpha\begin{bmatrix}0 & -n_z & n_y \\ n_z & 0 & -n_x \\ -n_y & n_x & 0 \end{bmatrix}\\ (注意这个矩阵是\mathbf{n}的对偶阵,用于叉乘) \]

Q:为什么这里是一个三阶矩阵?在齐次坐标系下不应该是四阶矩阵吗?

A:这是四阶矩阵的左上角那三阶。

视图变换

什么是视图变换?

思考如何照一张照片:

  • 找到一个地方,把人安排进去(模型变换 / 把场景建好、模型搭好)
  • 找一个好的角度,放好相机(视图变换)
  • 茄子(投影变换,3D→2D)

首先,定义相机:

  • 相机位置Position \(\mathbf{e}\)
  • 镜头方向Look-at direction \(\hat g\)
  • 上方向Up direction \(\hat t\)(与镜头方向垂直)

注意到相机和物体进行同样的变换时,得到的照片完全相同

因此我们可以做变换:

  • 相机位置固定在原点

  • 镜头方向固定在-Z

  • 上方向固定在Y

    (为什么那个方向是-Z呢,因为这门课约定所有坐标系都是右手系)

如何做这样的变换?

  1. 平移到原点

  2. \(\hat g\)转到-Z

  3. \(\hat t\)转到Y

    这样\(\hat g \times \hat t\)自然就是X

平移变换为: \[ T_{view} = \begin{bmatrix}1 & 0 & 0 & -x_e \\ 0 & 1 & 0 & -y_e \\ 0 & 0 & 1 & -z_e \\ 0 & 0 & 0 & 1\end{bmatrix} \\ \] 希望构造一个旋转阵,把\(\hat g\)转到-Z,把\(\hat t\)转到Y,把\(\hat g \times \hat t\)转到X,这是不容易的。

但是我们可以构造它的逆矩阵:把Y转到\(\hat t\),把Z转到\(-\hat g\) ,旋转阵的逆矩阵如下: \[ R_{view}^{-1} = \begin{bmatrix} x_{\hat g\times\hat t} & x_t & x_{-g} & 0 \\ y_{\hat g\times\hat t} & y_t & y_{-g} & 0 \\ z_{\hat g\times\hat t} & z_t & z_{-g} & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

结合旋转阵都是正交矩阵: \[ R_{view} = \begin{bmatrix} x_{\hat g\times\hat t} & y_{\hat g\times\hat t} & z_{\hat g\times\hat t} & 0 \\ x_t & y_t & z_t & 0 \\ x_{-g} & y_{-g} & z_{-g} & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \] 因此视图变换阵 \[ M_{view} = R_{view}T_{view} = \begin{bmatrix} x_{\hat g\times\hat t} & y_{\hat g\times\hat t} & z_{\hat g\times\hat t} & -x_e \\ x_t & y_t & z_t & -y_e \\ x_{-g} & y_{-g} & z_{-g} & -z_e \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

投影变换

左:透视投影;右:正交投影

正交投影

最简单的做法:

  • 把相机摆在原点,镜头方向-Z,上方向Y
  • 把Z坐标扔掉
  • 把物体放缩并平移到\([-1,1]^2\)

更本质的讨论:

我们希望把空间立方体\([l,r]\times[b,t]\times[f,n]\)映射到\([-1,1]^3\)的规范立方体上去

(注意:离我们越近,z轴的坐标越大)

  • 首先把立方体中心平移到原点(\(T(-\frac{l+r}{2}, -\frac{b+t}{2}, -\frac{f+n}{2})\)
  • 然后做缩放(\(S(\frac{2}{r-l}, \frac{2}{t-b},\frac{2}{n-f})\)

\[ M_{ortho} = \begin{bmatrix}\frac{2}{r-l} & 0 & 0 & -\frac{r+l}{2} \\ 0 & \frac{2}{t - b} & 0 & -\frac{t+b}{2} \\ 0 & 0 & \frac{2}{n-f} & -\frac{f+n}{2} \\ 0 & 0 & 0 & 1\end{bmatrix} \\ \]

透视投影

近大远小、平行线投影后不一定再平行,而会收敛于一点

  • 回忆一下点的定义

    \(\begin{bmatrix}x \\ y \\ z \\ 1\end{bmatrix} = \begin{bmatrix}xz \\ yz \\ z^2 \\ z\end{bmatrix}(若z\neq 0)\)

如何做透视投影?

  • 首先把视锥frustum“挤压”成一个立方体cuboid
  • 然后做正交投影

这个挤压过程类似上文的Shear,有以下性质:

  • 近平面永远不变
  • 远平面的z值不变
  • 远平面的中心不变

怎么做这个挤压?(也就是求变换矩阵\(M_{persp\to ortho}\)

对于原来的点\((x,y,z)\),假设变换后的点是\((x',y',z')\)

因为要压缩到cuboid上去,任意一个点的y和近平面上对应点的y有一个确定关系

我们已经知道\(y'=\frac{n}{z}y, x' = \frac{n}{z}x\) \[ \begin{bmatrix}x \\ y \\ z \\ 1\end{bmatrix} \mathop\Rightarrow\limits_{\text{变换}} \begin{bmatrix}\frac{nx}{z} \\ \frac{ny}{z} \\ ? \\ 1\end{bmatrix} = \begin{bmatrix}nx \\ ny \\ ?? \\ z\end{bmatrix} \] 也就是说, \[ M_{persp\to ortho}\begin{bmatrix}x \\ y \\ z \\ 1\end{bmatrix} = \begin{bmatrix}nx \\ ny \\ ?? \\ z\end{bmatrix} \] 这已经可以确定\(M_{persp\to ortho}\)的很多分量了 \[ M_{persp\to ortho} = \begin{bmatrix}n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ ? & ? & ? & ? \\ 0 & 0 & 1 & 0\end{bmatrix} \\ \begin{bmatrix}n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ ? & ? & ? & ? \\ 0 & 0 & 1 & 0\end{bmatrix}\begin{bmatrix}x \\ y \\ z \\ 1\end{bmatrix} = \begin{bmatrix}nx \\ ny \\ ?? \\ z\end{bmatrix} \] 结合上面的几条性质我们推测出第三行的值:

近平面上的点不变,用n代替z,可以知道第三行前两列都是0,设为\(\begin{bmatrix}0 & 0 & A & B\end{bmatrix}\),有\(An+B=n^2\)

原平面上的点z值不变,有\(Af+B=f^2\)

从而\(n, f\)为方程\(x^2-Ax-B=0\)的两个根,我们可以知道\(A = n+f, B = -nf\)

从而: \[ M_{persp\to ortho} = \begin{bmatrix}n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ 0 & 0 & n+f & -nf \\ 0 & 0 & 1 & 0\end{bmatrix} \\ \] 结合刚刚的正交投影,透视投影变换就是 \[ M_{persp} = M_{ortho} M_{persp\to ortho} \]

Lecture 5 Rasterization 1 (Triangles)

这节课Pretty Easy

在上节课中,我们通过视图变换投影变换把任意的三维场景都变到了\([-1,1]^3\)这个标准立方体上去,接下来我们希望能在屏幕上将里面的内容绘制出来

但什么是屏幕呢?

  • 一个pixel矩阵
  • 矩阵的尺寸称为分辨率
  • 是一种典型的光栅成像设备

Raster == Screen (German)

Rasterize == To draw onto the screen

那么什么是像素呢?

  • 本课中认为:一个pixel是一个有确定颜色的小方块
  • 颜色是RGB的混合

给出屏幕空间的定义(与虎书存在不同)

  • 左下角为原点
  • 向右为x轴,向上为y轴
  • 每个像素的坐标为\((x,y)\),其中x和y都是整数(从0开始)。
    • 像素\((x,y)\)的中心是\((x + 0.5, y+0.5)\)
    • 分辨率为\((\text{width}, \text{height})\)的屏幕,其显示范围从\((0,0)\)\((\text{width}, \text{height})\)

光栅化过程,就是把物体从\([-1,1]^3\)映射到\([0,\text{width}]\times[0,\text{height}]\)的过程

这太简单了(不考虑遮挡)

光栅化:

  • 与z坐标无关
  • \([-1,1]^2\)变形到\([0,\text{width}]\times[0,\text{height}]\)
    • 先平移\(T(\frac{\text{width}}{2}, \frac{\text{height}}{2})\)
    • 再缩放\(S(\frac{\text{width}}{2},\frac{\text{height}}{2})\)

\[ M_{viewport} = \begin{bmatrix} \frac{\text{width}}{2} & 0 & 0 & \frac{\text{width}}{2} \\ 0 & \frac{\text{height}}{2} & 0 & \frac{\text{height}}{2} \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

为什么用三角网格?

  • 三角形是最基本的多边形
    • 多边形可以三角剖分
  • 三角形有独特性质
    • 一定共面,而四边形、多边形不保证在同一平面上
    • 内外定义明确,而更多边的图形都有凹凸性
    • 插值方便

对于一个三角形,我们需要确定显示时哪些像素显色——完全覆盖的肯定有色,完全不触及的肯定没有颜色,部分则比较复杂

方法一:采样

在若干点计算函数的值,可以把函数离散化

定义函数(注意xy不一定是整数) \[ \text{inside}(t,x,y) = \left\{\begin{aligned} &1, 点(x,y)在三角形t内部 \\ &0, otherwise \end{aligned}\right. \] 要采样这个三角形,只需要

1
2
3
for (int x = 0; x < x_max; x++)
for (int y = 0; y < y_max; y++)
image[x][y] = inside(triangle, x + 0.5, y + 0.5);

那么如何计算inside函数呢?

叉乘

如何加速?

可以只检测轴向包围盒内的pixel。

或者用ITT来做

预告:下节课抗锯齿