GAMES101笔记

Wei Gu 2022年9月

GAMES101：现代计算机图形学入门，是GAMES(Graphics And Mixed Environment Symposium)组织开设的一门线上课。讲师是闫令琪，现在是加州大学圣芭芭拉分校助理教授。既然我校CS3310计算机图形学照搬了GAMES101，我便在九月末两周时间刷完了GAMES101（共22节课），并做了一波整理。虽然这两周经历了一些小麻烦，但是还是顺利做完了这份整理。

目录

01 Overview

课程内容主要包含

• 光栅化（rasterization）：把三维空间的几何形体显示在屏幕上。实时（30fps）是一个重要的挑战。

• 几何表示（geometry）：如何表示曲线、曲面、拓扑结构等

• 光线追踪（ray tracing）：慢但是真实。实时是一个重要的挑战。

• 动画/模拟（animation/simulation）：譬如扔一个球到地上，球如何反弹、挤压、变形等

02 Linear Algebra

自信点，你都会了

点乘可以判断前后，如下图

叉乘可以判断左右和内外，如下图

• 上图左：通过叉乘结果正负，判断左右

• 上图右：通过点是不是在三边的同一侧，判断是否在三角形内外

03~04 Transformation

1. 2D Transformation

1.1 Affine Transformation

仿射变换（affine transformation）= 线性变换（linear transformation）+ 平移（translation）

现在我们用一个二维坐标表示二维平面上的点，故仿射变换有等式：

其中第一项是线性变换，第二项是平移。

二维平面线性变换分类以及对应的线性变换矩阵$\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$$\begin{pmatrix}a&b\\c&d\end{pmatrix}$为：（线性变换的理解可以参见3Blue1Brown）

• 缩放（scale）$s_{\alpha ,\beta }$$s_{\alpha,\beta}$ ：$\left(\begin{array}{cc}\alpha & 0\\ 0& \beta \end{array}\right)$$\begin{pmatrix}\alpha&0\\0&\beta\end{pmatrix}$，参考位置为原点，x轴变为原来$\alpha$$\alpha$倍，y轴变为原来$\beta$$\beta$倍

• 切变（shear）：$\left(\begin{array}{cc}1& a\\ 0& 1\end{array}\right)$$\begin{pmatrix}1&a\\0&1\end{pmatrix}$，参考位置为原点，每个点纵坐标y不变，横坐标x改变

• 旋转（rotate）$R_{\theta }$$R_\theta$：$\left(\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)$$\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}$，逆时针$\theta$$\theta$为正，绕原点逆时针旋转$\theta$$\theta$角度。旋转矩阵是正交矩阵，即$R_{\theta }^T=R_{\theta }^{-1}$$R_\theta^T=R_\theta^{-1}$。旋转矩阵推导使用$(1,0)\to (\cos \theta ,\sin \theta )$$(1,0)\rightarrow(\cos\theta,\sin\theta)$,$(0,1)\to (-\sin \theta ,\cos \theta )$$(0,1)\rightarrow(-\sin\theta,\cos\theta)$两个特殊点容易得到。

1.2 Homogenous Coordinates

之前我们看到仿射变换有等式：

但是后面平移项让人嫌麻烦。引入齐次坐标（homogenous coordinate）便可以扔掉该平移项。所谓齐次坐标就是用n+1维向量表示n维坐标。在2D transformation下就是用3维向量表示2维坐标（在x、y轴外增加了w轴）：

• 2D point = $(x,y,1{)}^T$$(x, y, 1)^T$

• 2D vector = $(x,y,0{)}^T$$(x,y,0)^T$

• $(x,y,w{)}^T(w\ne 0)$$(x,y,w)^T(w\neq0)$扩充定义等价于$(x/w,y/w,1{)}^T$$(x/w,y/w,1)^T$

关于点的$w$$w$轴坐标为1以及向量的为0，这是有道理的。想想向量+向量=向量、点-点=向量、点+向量=点。

于是仿射变换可以写成：（显然先是做线性变换，然后再做平移）

最后来看一个例子——如何绕一个给定的点$\overrightarrow{c}$$\vec{c}$旋转

1. T(-c)：平移到原点

2. R(α)：旋转α角

3. T(c)：平移回点c

于是整个过程可以写成

注意到

• 矩阵没有交换律，矩阵前后顺序很重要

• 矩阵有结合律

2. 3D Transformation

同样的，用齐次坐标可以表示

• 3D point = $(x,y,z,1{)}^T$$(x, y, z,1)^T$

• 3D vector = $(x,y,z,0{)}^T$$(x,y,z,0)^T$

• $(x,y,z,w{)}^T(w\ne 0)$$(x,y,z,w)^T(w\neq 0)$扩充定义等价于$(x/w,y/w,z/w,1{)}^T$$(x/w,y/w,z/w,1)^T$

仿射变换可以写成（仍然是先线性变换再平移）

其中

• 缩放

  $$\begin{array}{c}S(s_x,s_y,s_z)=\left(\begin{array}{cccc}{s}_x& 0& 0& 0\\ 0& s_y& 0& 0\\ 0& 0& s_z& 0\\ 0& 0& 0& 1\end{array}\right)\end{array}$$

• 平移

  $$\begin{array}{c}T(t_x,t_y,t_z)=\left(\begin{array}{cccc}1& 0& 0& t_x\\ 0& 1& 0& t_y\\ 0& 0& 1& t_z\\ 0& 0& 0& 1\end{array}\right)\end{array}$$

• 绕x-,y-,z-axis旋转

  $$\begin{array}{c}{R}_x(\alpha )=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& \cos \alpha & -\sin \alpha & 0\\ 0& \sin \alpha & \cos \alpha & 0\\ 0& 0& 0& 1\end{array}\right)\\ R_y(\alpha )=\left(\begin{array}{cccc}\cos \alpha & 0& \sin \alpha & 0\\ 0& 1& 0& 0\\ -\sin \alpha & 0& \cos \alpha & 0\\ 0& 0& 0& 1\end{array}\right)\\ R_z(\alpha )=\left(\begin{array}{cccc}\cos \alpha & -\sin \alpha & 0& 0\\ \sin \alpha & \cos \alpha & 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\end{array}$$

旋转的正方向如图，推导过程和2维旋转类似。

可以将3D旋转分解成绕x-,y-,z-axis旋转，即：

其中α、β、γ称作欧拉角（Euler angle）。

罗德里格斯旋转公式（Rodrigues' Rotation Formula）

三维空间的一个向量$\overrightarrow{v}$$\vec{v}$，绕任意轴$\overrightarrow{n}=(n_x,n_y,n_z)$$\vec{n}=(n_x,n_y,n_z)$旋转$\alpha$$\alpha$角度，得到的向量为$R(\overrightarrow{n},\alpha )\overrightarrow{v}$$R(\vec{n},\alpha)\vec{v}$，其中旋转矩阵为：（式中I为单位矩阵）

证明略

3. Viewing Transformation

观测变换（viewing transformation）

• 视图变换（view transformation）或称为相机变换（camera transformation）

• 投影变换（projection transformation）

  • 正交投影（orthographic projection）

  • 透视投影（perspective projection）

3.1 View Transformation

相机有三个参数

这么理解参数$\hat{t}$$\hat{t}$：相当于一张照片调整旋转。并且我们假设了$\hat{g}\perp \hat{t}$$\hat{g}\perp\hat{t}$，其实相机的向上方向是人为规定的，规定正交的话可以避免在做视图变换时，产生图像的变形。

如果我们保持相机和物体的相对位置不变，并同时移动它们，相机看到的物体样子是没有改变的。自然会想让相机移动到一个固定的位置，也就是让相机移动到原点，look-at direction $\hat{g}$$\hat{g}$和Z轴负方向同向，up direction $\hat{t}$$\hat{t}$和Y轴同方向。这便是视图变换（view transformation）或称为相机变换（camera transformation），记作$M_{view}$$M_{view}$，且

其中先做平移变换（$\overrightarrow{e}=(x_e,y_e,z_e)$$\vec{e}=(x_e,y_e,z_e)$，t、g等下角标意义类似）

再做旋转变换，即将$\hat{g},\hat{t},\hat{g}\times \hat{t}$$\hat{g},\hat{t},\hat{g}\times\hat{t}$分别旋转到-Z、Y和X轴。逆旋转$R_{view}^{-1}$$R_{view}^{-1}$容易写出：

由于旋转矩阵是正交阵，故

带入即得相机变换$M_{view}$$M_{view}$

3.2 Projection Transformation

现在摄像机和物体都摆好了，物体需要从3D投影到2D平面。有正交投影（orthographic projection）和透视投影（perspective projection）两种。不过下面介绍的投影变换实际上是把长方体投影到$[-1,1{]}^3$$[-1,1]^3$的空间中。

3.2.1 Orthographic Projection

正交投影简单理解：

• 相机在坐标原点，向-Z轴看，up direction为Y

• 物体Z轴扔掉

• 平移缩放物体到$[-1,1{]}^2$$[-1,1]^2$范围（即x和y轴范围在-1和1之间）

通常做法：

考虑将$[l,r]\times [b,t]\times [f,n]$$[l,r]\times [b,t]\times[f,n]$范围的长方体cuboid，平移缩放到$[-1,1{]}^3$$[-1,1]^3$canonical cube。即：

注意到，采用右手坐标系的时候，左边比右边x小，下边比上边y小，但是前面比后面z大。这就是为什么OpenGL采取左手坐标系。

3.2.2 Perspective Projection

透视投影步骤：

• $M_{persp\to ortho}$$M_{persp\rightarrow ortho}$：把视锥体（frustum）“挤压”成立方体，并保证近平面上任意一点不变，远平面上z坐标不变（但是之间的平面z坐标会改变）

• $M_{ortho}$$M_{ortho}$：正交投影。同3.2.1节

• 最后$M_{persp}=M_{ortho}{M}_{persp\to ortho}$$M_{persp}=M_{ortho}M_{persp\rightarrow ortho}$即为答案

下面推导$M_{persp\to ortho}$$M_{persp\rightarrow ortho}$

设视锥体中任意一点(x,y,z)，通过$M_{persp\to ortho}$$M_{persp\rightarrow ortho}$挤压成(nx/z, ny/z, unknown) （由相似三角形可知），即

故$M_{persp\to ortho}$$M_{persp\rightarrow ortho}$形如

又因为近平面上任意一点不变，远平面上z坐标不变，有

解得

通过fovY和aspect得到l,r,b,t

之前使用l（左边沿的x坐标）,r（右边沿的x坐标）,b（下边沿的y坐标）,t（上边沿的y坐标）来表示近平面，此外我们还可以用垂直可视角度（field-of-view）fovY和宽高比aspect ratio来表示。

显然有

• $t=|n|\tan \frac{fovY}{2}$$t=|n|\tan\frac{fovY}{2}$

• $r=t\cdot aspect$$r=t\cdot aspect$

• $b=-t,k=-r$$b=-t,k=-r$

05~06 Rasterization

经过投影变换，物体已经被平移压缩在[-1,1]³之中。现在要让物体画到屏幕上，这称为光栅化（rasterize）。

1. Defining the screen space

• 屏幕范围：(0,0)到(width,height)

• 用整数(x,y)表示一个像素，譬如红圈中的(2,1)

• 像素范围：(0,0)到(width-1,height-1)

• 像素(x,y)的中心点为(x+0.5, y+0.5)

2. Viewport Transformation

已知物体已经被平移压缩在[-1,1]³之中，现在想让物体平移伸缩到屏幕范围——[0,width]X[0,height]里（扔掉物体z轴）。这便是viewport transformation（视口变换）。变换矩阵易得：

3. Rasterization

triangle mesh是表示物体的一个普遍有效的方法，选取三角形的优势在于

• 最基本的多边形，可以表示其他多边形

• 一定是个平面

• 内外定义清楚

• 有很好的插值方法，实现渐变等效果

那如何用像素来表示一个三角形呢？

方法是：sample (采样) if each pixel center is inside the triangle.

用c描述为：

1
for (int x = 0; x < xmax; x++)
2
    for (int y = 0; y < ymax; y++)
3
        image[x][y] = inside(tri,x+0.5,y+0.5)
4
        //inside函数：如果在三角形内返回1，否则0

注意：

• 如何判断是不是在三角形内外？用叉乘（第二章）

• 中心点在边界上怎么办？自行定义

• 加速？可以不用遍历整个屏幕上的像素的。譬如使用bounding box围出三角形，之外的像素无需遍历

4. Sampling Artifacts

采样瑕疵（sampling artifact）包含

• 锯齿（jaggie）

• 摩尔纹（Moire pattern）：图中照片删去了奇数行列，然后重新拼接而成

• 车轮效应（wagon wheel effect）

• 等

这也称为走样（aliasing）。这是因为信号变化太快，而采样太慢而导致的。

5. Anti-aliasing

既然有走样，那就要想办法反走样（anti-aliasing，AA）。这里介绍SSAA（supersample anti-aliasing，超采样抗锯齿）方法。

普通采样和超采样分别如下图左和右所示：

然后对超采样的计算平均值即可：

MSAA（multisample anti-aliasing，多重采样抗锯齿）是对SSAA的优化。但是课程上直接把SSAA称为MSAA了，也并没有详细讲清楚。这里也不再展开。

事实上，上述方法体现了模糊（blur）后再采样的思想。课程也花费了大量经历利用信号系统相关知识解释这一点。这里就简单一提：

• 可以将图片做傅里叶变换，会发现低频信息多，高频信息少

  • 去除低频信息（高通滤波），发现原始图像只剩下边界

  • 去除高频信息（低通滤波），发现原始图像变模糊，边界不清晰

• 模糊操作等于做了个低通滤波，即去掉了高频的信号，减少了信号重叠的情况。从而在采样的时候可以实现反走样

• 对原始图像在空间域上的卷积实现了频域上的滤波

07~09 Shading

1. Visibility/Occlusion

在光栅一章中，我们只考虑画一个物体。当有多个物体时，就会产生可见/遮挡（visibility/occlusion）的问题。我们将介绍画家算法（painter‘s algorithm）和z-buffer两种算法。

虽然遮挡问题还是属于光栅化问题，但是我遵从课程设计将其放在此处

1.1 Painter's Algorithm

想法很简单：先给物体排序；先画远的，再画近的，画近的会遮挡远的。

但是有问题——有的物体之间无法确定谁深谁近，如

可见画家算法有局限性。

1.2 Z-Buffer

z-buffer又称深度缓冲（depth buffer）。想法是：最终的像素是所有物体中具有最小z值的对应像素（为方便讨论，这里假设z恒正，z越小越近）。需要维护两个缓冲：

• frame buffer stores color values，也就是最后的结果

• depth buffer (z-buffer) stores depth

用伪代码描述为：

xxxxxxxxxx
9
1
initial depth buffer to inf;
2
during rasterization:
3
    for (each triangle T)
4
        for (each sample (x,y,z) in T)
5
            if (z < zbuffer[x,y])  //closest pixel so far
6
                framebuffer[x,y] = rgb; //update color
7
                zbuffer[x,y = z; //update depth
8
            else
9
                ;

例子为：（图中R表示无穷远）

分析：

• 复杂度：假设每个三角形O(1)，n个三角形，故O(n)

• 没有排序

• 画物体的顺序改变，不影响最终结果

1.5 CS3310's New Stuffs

学校图形学在GAMES101的基础上有如下额外内容。

Gooch Shading Model

一种不真实的着色效果。主要想法是：法向量越指向光源，越暖色调；否则冷色调。下图是一种方案，其中c代表rgb颜色。

Light Sources

• Directional Lights(方向光) ：平行光（光源无穷远处），譬如阳光

• Punctual Lights(精确光) ：光源有自己的位置。可以引入1/r²或1/r的衰减，也可以不引入。

  • Point/Omni Lights(点/泛光源)

  • Spotlights(聚光灯) ：光源发出的光线有角度范围，且随着角度增大而衰减，中间亮，两边暗

• Area Lights (区域光)

Transparency

只需要掌握alpha通道即可，可以理解为透明度，在[0,1]之间，0是完全透明，1是完全不透明。物体通过filter射到眼睛里的光的颜色可以计算为：

2. Blinn-Phong Reflectance Model

shading（着色）在Merriam-Webster Dictionary定义为：

The darkening or coloring of an illustration or diagram with parallel lines or a block of color.

在本课程中，着色指给物体应用材质的过程。本节我们介绍Blinn-Phong反射模型。这是一个简单理想化的模型。

物体表面发出的光包括：

• 镜面高光（specular highlights）

• 漫反射（diffuse reflection）

• 环境光照（ambient lighting）

入射方向l、入射点法线方向n、观察方向v如图所示：

2.1 Diffuse Term

漫反射把部分入射光均匀的分散发射出去。

Diffuse shading（Lambertian shading）有公式：

其中漫反射系数$k_d$$k_d$在[0,1]之间，表示亮度和颜色；I/r²表示光源到达入射点时的光强；max是为了扔掉从表面下入射的情况；漫反射光强$L_d$$L_d$与观察者距着色点（shading point）距离无关。

随着kd的变大，着色效果变化如下：

2.2 Specular Term

镜面反射项有公式：

其中$\overrightarrow{h}$$\vec{h}$称为半程向量（half vector），满足

注意：

• 指数p使得离R角度大的v的镜面反射项小

• 之所以没有$max(0,\overrightarrow{n}\cdot \overrightarrow{l})$$\max(0,\vec{n}\cdot\vec{l})$项，因为这原来就是一个简单理想化的模型

$k_s$$k_s$与p大小改变，效果如下：

2.3 Ambient Term

假设物体各处接收到来自环境的光$I_a$$I_a$是一致的，环境光照有公式：

2.4 Put Together

Blinn-Phong Reflection Model即：

3. Shading Frequencies

着色频率（shading frequency）包含三种：

• flat shading：每个三角形有一个法向量，进行着色，三角形内部各处着色相同

• Gouraud shading：每个顶点有一个法向量，进行着色，三角形内部颜色通过插值计算出

• Phong shading：每个顶点有一个法向量，通过插值计算出三角形内每个像素的法向量，再对每个像素进行着色

效果如图：

相关问题：

• 如何确定顶点法线方向？如果由几何性质能直接得出就最好了，不然就对顶点周围的面的法向量进行加权平均。

• 有了顶点法向量，如何插值得到像素的法向量？通过重心坐标（Barycentric interpolation），见本章第6节。

4. Graphics (Real-time Rendering) Pipeline

图形管线（graphics pipeline），或者称为实时渲染管线（real-time rendering pipeline），是指通过给定虚拟相机，3D场景物体，光源等要素来生产或者渲染一副2D 图像的过程。如图：

其中着色器（shader）是可编程的。譬如我们可以使用OpenGL Shading Language （GLSL）来定制物体着色方案。这里的fragment（片元）可以理解为像素，如果用MSAA的话，一个像素包括多个fragment。

4.5 CS3310: Texture Compositing

学校课还介绍了纹理合成（texture composting），即通过一个特定的样本来合成一个大的纹理。有pixel-based和patch-based两种方法。

pixel-based texture compositing

后面还有很多东西，但是sb说：“细节我们就不讲了。”

5. Texture Mapping

纹理映射（texture mapping）就是把一张2维的图像贴（映射）到一个三维物体表面。三维物体上每个三角形顶点对应二维纹理的一个坐标(u,v)。

至于怎么映射、以及纹理如何设计，我们不关心。

6. Barycentric Coordinate

对于三角形ABC所在平面上的任意一点$(x,y)$$(x,y)$，都可以表示为（易证）

且满足$\alpha +\beta +\gamma =1$$\alpha+\beta+\gamma=1$

故平面上任意一点都可以用$(\alpha ,\beta ,\gamma )$$(\alpha,\beta,\gamma)$来表示，该表示方法称为重心坐标（barycentric coordinate）。当且仅当$\alpha ,\beta ,\gamma$$\alpha,\beta,\gamma$非负，$(x,y)$$(x,y)$在三角形ABC内。

已知A,B,C三点坐标，如何求$\alpha ,\beta ,\gamma$$\alpha,\beta,\gamma$？

• 公式

  

• 面积

  

插值

通过重心坐标$(\alpha ,\beta ,\gamma )$$(\alpha,\beta,\gamma)$可以做线性插值

其中$V_{A/B/C}$$V_{A/B/C}$可以是顶点的位置、材质坐标、颜色、法向量等等属性。

注意到，三维空间内三角形的重心坐标在投影后，不一定是二维投影的重心坐标。所以应该在三维空间做插值，再投影到二维上去；而不是先投影到二维，再做插值。

7. Applying Texture

把纹理应用到物体过程为：

• 对于每个采样点（像素中心），可以通过重心坐标插值得到纹理对应$(u,v)$$(u,v)$坐标。原来我们只知道顶点对应的$(u,v)$$(u,v)$坐标，现在通过插值得到所有采样点的了。

• 获取材质$(u,v)$$(u,v)$坐标的颜色，并设置该采样点的漫反射系数Kd即可

8. Texture Magnification/Minification

应用纹理时产生的问题包含

• 纹理放大（texture magnification）：当纹理图片分辨率过低，就会出现多个像素点仍然对应一个(u,v)坐标，并将该(u,v)坐标下颜色信息复制给该像素点，这样形成的图片边界过渡就会非常不自然，形成一个个的小格子（见8.1节图Nearest）。

• 纹理缩小（texture minification）：纹理分辨率过高，就会出现一个像素点对应多个(u,v)坐标，便会导致走样的问题（见8.2节图）。

8.1 Texture Magnification

下图中有三种做法：

nearest就是像素点选取最近的纹理元素（texel, i.e. a pixel on a texture）

下面介绍双线性插值（bilinear）。

选取最近的四个texel，做两波线性插值。

事实上，在纹理被放大和缩小时都可以使用nearest、bilinear或bicubic的做法。这称为纹理滤波（texture filtering）。

8.2 Texture Minification

可以使用超采样（supersampling）解决，但是计算昂贵。下面介绍Mipmap概念，可以实现快、近似、正方形的范围查询（range query）——可以立刻得到一个区域内的平均值（或最大值、最小值等）。

利用原始纹理，预处理生成mipmap。额外存储其实只有原图的三分之一，不占多少空间。

屏幕像素只需要选取对应等级的纹素即可。但是如何计算等级D呢？下面是一种近似方法：（可参考3brown1blue关于雅可比矩阵的介绍）

假设我算出来是1.8层，还需要使用三线性插值（trilinear interpolation）（两次双线性插值后，再做一次线性插值）来得到屏幕像素的最终值：

然而由于mipmap只实现正方形内的范围查找，于是会产生overblur的问题：（屏幕像素对应材质的长方形甚至斜长的区域，在做mipmap时，自然会取过大的正方形，从而导致模糊的情况）

解决方法有各向异性过滤（anisotropic filter）和EWA过滤等。它们生成不同的材质图，支持正方形之外的范围查找。

9. Applications of Textures

纹理不仅仅可以给物体表面贴个图，还有其他的应用。

Environment Map

可以使用纹理来表示环境光，如图：

Bump Mapping

凹凸贴图（bump mapping）可以记录物体表面相对高度，从而影响物体表面法线，进而影响阴影，给人凹凸感觉。不过物体表面实际上还是光滑的，凹凸只是纹理带来的错觉。

位移贴图（displacement mapping）则真正移动了3Dmesh的顶点，从而有更真实的阴影效果。但是要求物体的3D mesh要足够细，才能支持这个操作。

3D Procedural Noise

似乎是引入噪声，来生成3维纹理（譬如大理石纹路之类的）。

Provide Precomputed Shading

就是在纹理上已经做好shading了

3D Textures

纹理可以不只是二维表面的，也可以是三维空间的。还可以做体渲染（volume rendering）。譬如CT扫描的结果。

10~12 Geometry

1. Representation

1.1 Implicit

包括

• algebraic surface: 用$f(x,y,z)=0$$f(x,y,z)=0$表示一个平面。判断内外容易，得到表面上的点困难。

• constructive solid geometry (CSG)：用交并差等运算表示

• distance function：空间任何一点到物体表面距离的最小值（可以是带符号的）

• level set（水平集）：store a grid of values approximating function; surface is found where interpolated values equal zero。譬如用密度做体渲染，找密度为一个定值的表面

• fractal（分型）

隐式表示的优劣

Pros

• compact description (e.g., a function)

• certain queries easy (inside object, distance to surface)

• good for ray-to-surface intersection (more later)

• for simple shapes, exact description / no sampling error

• easy to handle changes in topology (e.g., fluid)

Cons

• difficult to model complex shape

1.2 Explicit

• $f:{\mathbb{R}}^2\to {\mathbb{R}}^3;(u,v)\to (x,y,z)$$f:\mathbb{R}^2\rightarrow \mathbb{R}^3;(u,v)\rightarrow(x,y,z)$。得到表面上的点容易，判断点在表面内外困难。

• point cloud（点云）

• mesh，使用.obj文件描述mesh

2. Curve

这里着重介绍贝塞尔曲线（Bézier Curves）。下图有三个控制点（control point）$b_0,b_1,b_2$$b_0,b_1,b_2$，取所有[0,1]之间的t，便可以画出该曲线。当然四个甚至更多的控制点都是可行的。特别的四个控制点的称为cubic Bézier curve

代数形式：

更一般的，n+1个控制点下，曲线可以表示为：

贝塞尔曲线性质（n个控制点）：

• $b(0)=b_0;b(1)=b_{n-1}$$b(0) = b_0; b(1) = b_{n-1}$

• 端点切线斜率：$b^{\prime }(0)=(n-1)(b_1-b_0);b^{\prime }(1)=(n-1)(b_{n-1}-b_{n-2})$$b'(0)=(n-1)(b_1-b_0);b'(1)=(n-1)(b_{n-1}-b_{n-2})$

• 仿射变换后做贝塞尔曲线，与先做贝塞尔曲线再仿射变换，结果一致

• 凸包性质：贝塞尔曲线一定在凸包（最小围住控制点的多边形）内

分段贝塞尔曲线（Piecewise Bézier Curve）

也就是一根曲线由多个贝塞尔曲线组成。连接点的连续性可以定义：

• C⁰ continuity：第一段终点和第二段起点相同，$a_n=b_0$$a_n=b_0$

• C¹ continuity：还要求切线斜率一致，$a_n=b_0=\frac{1}{2}(a_{n-1}+b_1)$$a_n=b_0=\frac{1}{2}(a_{n-1}+b_1)$

3. Surface

3.1 Bézier Surface

考虑$4\times 4$$4\times4$的控制点阵，先用每列四个控制点画出四条贝塞尔曲线（图中灰色，参数u控制），再利用这四条曲线在相同参数u上的点，画出一条贝塞尔曲线（图中蓝色，参数v控制）。诸多这样蓝色的曲线就可以组成贝塞尔曲面。

3.2 Mesh

这里介绍对网格的细分（subdivision）、简化（simplification）和正则（regularization）操作。

3.2.1 Subdivision

网格细分的思路是：

1. 创建更多的三角形（顶点）

2. 调整所有顶点的位置

下面介绍两种细分方法。

1）Loop Subdivision（注意到Loop是人名）

首先，将每个三角形分成四份：

然后，调整顶点位置：

• 新顶点

• 旧顶点，可以看到如果度越大，相邻顶点对原始顶点的影响越小

2）Catmull-Clark Subdivision

Loop细分只能解决三角形网格的细分问题，对于一般的情况可以采用Catmull-Clark细分。

基本概念

• 非四边形面（Non-quad face）：顾名思义。

• 奇异点（Extraordinary vertex）：度数不为4的点。

首先，添加新点

• 取每个面的一个点（比如重心），取每个边的中点，将所有新添加的点做连接

• 经过一次细分，所有非四边形面会消失，变成一个奇异点

然后，调整位置

3.2.2 Simplification

我们采取边坍缩（edge collapsing）的方法来简化曲面。

先要介绍二次误差（quadric error），即新的点应该使与它相关联的面的平方和达到最小。

于是简化的步骤如下：（贪心算法）

1. 假设坍缩每一条边，然后分别得到它们的二次误差。 做为各自的分数

2. 每次都坍缩分数最小的边，然后更新被影响边的分数

3. 重复步骤1

另. Shadow Mapping

不属于几何这一部分，但是somehow就在lecture12介绍了，应该还是属于光栅这一块的

这里提供一个生成物体影子的办法，其核心想法是：不在影子中的点必须同时被光源和照相机看到。

1. 首先记录光源能看到点的深度信息

2. 从眼睛看向物体，将所看到的点，投射回记录深度信息的那张图。在对应像素位置，找到当时的深度信息，与现在该点到光源的距离进行比较。如果当前距离比之前的深度大，说明中间有物体遮挡，即在阴影之中（如点2）；如果相等，则不在阴影中（如点1）。

Shadow Mapping的优点：快

Shadow Mapping 的问题

• 理论上只能硬阴影（适用于点光源）

• 依赖贴图的分辨率，走样问题

• 浮点精度误差，浮点数判断相等

所谓的硬阴影和软阴影，其实可以理解为本影（umbra）和半影（penumbra）。

CS3310还补充了阴影体（shadow volume）和平面阴影（planar shadow）来计算阴影的方法。

planar shadow

思想很简单，根据光源和投影面位置推导一个投影矩阵，通过这个矩阵能把模型上所有顶点投射到投影面（比如地面）上，也就是将渲染物体压扁到一个平面上。

shadow volume

上图中红色点是进入阴影体，紫色点是出阴影体。只需判断观察点进出阴影体数目是否相同（可以使用stencil buffer来计数）。相同的话就不在阴影体中。该算法性能不好，且理论上也只能生成硬阴影，不过不会因采样和分辨率而产生的问题。

13~16 Ray Tracing

华为云 上的整理看上去很不错，本章就拿来了，做了一些删减工作和一点点补充：)。由于遵循了课程顺序，本章分节有待商榷。

光栅化是把场景中的物体独立出来，并且再将物体独立成一个个的三角形面片进行渲染，通常 GPU 绘制三角形面片是并行的，所以对于物体来说，它是不知道自己周围的物体，同样的，对于三角形面片来说，它也是不知道自己周围的三角形。所以光栅化无法处理一类需要全局信息进行渲染的效果，如：软阴影、Glossy 反射以及间接照明。

相比较光栅化，光线追踪是从相机出发，计算相机发出的光线（视线）与场景产生的结果，这里的光线可能会与场景中的物体碰撞后生成另外一些光线，然后生成的光线也需要继续做计算。所以对于光线追踪来说，相机产生的光线是知道整个场景信息的。

光栅化与光线追踪的对比：

1. 光栅化快，实时，是一种近似算法

2. 光线追踪慢，离线，是一种准确的算法

1. Recursive (Whitted-Style) Ray Tracing

先来学习一种传统的光线追踪算法，称为Whitted风格。

该方法有几点不同于常规的着色方案：

1. 光源：光线不同，这里假设光线在碰撞到物体后还会产生折射和反射。

2. 着色过程：每发生一次折射或者反射（弹射点）都计算一次着色，前提是该点不在阴影内。

如图所示，该算法的过程如下：

1. 从视点从成像平面发出光线，检测是否与物体碰撞

2. 碰撞后生成折射和反射部分

3. 递归计算生成的光线

4. 所有弹射点都与光源计算一次着色，前提是该弹射点能被光源看见

5. 将所有着色通过某种加权叠加起来，得到最终成像平面上的像素的颜色

为了后续说明方便，课程定义了一些概念：

• 从视角出发第一次打到物体的光线叫做：primary ray

• 弹射之后的光线叫做：secondary rays

• 判断可见性的光线叫做：shadow rays

1.1 Ray-Surface Intersection

Recursive (Whitted-Style) Ray Tracing涉及到光线与物体的碰撞问题，所以这里介绍一下如何判断光线-表面相交问题。

1.1.1 Ray Equation

光线可以一个点o和方向向量d定义：

1.1.2 Ray Intersection With Implicit Surface

如图解t即可：

1.1.3 Ray Intersection With Triangle

计算步骤：先求光线和平面的交点 → 再判断点是否在三角形内

光线与平面交点求解：

Moller Trumbore Alogrithm（MT算法）

一种快速计算光线是否在三角形内以及与平面交点的算法，其核心出发点是用重心坐标表示平面。

具体步骤：

1. 求解t，b1，b2（三个式子，三个未知数——求解方法：克莱姆法则）

2. 解出来之后，看是否合理：①沿着这个方向（t非负）②在三角形内（b1，b2非负）

1.2 Accelerating Ray-Surface Intersection

加速原理：不再判断光线与每个三角形的相交情况，而是判断光线与包围物体表面的盒子来粗略判定光线是否与物体相交。如果与包围盒（bounding volume）相交，再判断光线是否与物体相交。

1.2.1 Bounding Volume

这里主要介绍了 AABB 包围盒（Axis-Aligned Bounding Box），它是轴对齐的，也就是其平面与xOy、yOz或zOx平面平行。通常在判断物体相交情况的时候，可以先检测物体是否与 AABB 包围盒是否相交，如果相交再进一步做判断（更精细的相交判断）。

1.2.2 Ray Intersection with Axis-Aligned Box

这里给了一个 2D 的例子进行解释：

需要记住的关键概念是：

1. 光进入了所有对面（slab，一对平行的平面），才算进入Box

2. 光离开任意一对面，就算离开了包围盒

3. 什么时候有交点：$t_{enter}<t_{exit}$$t_{enter}<t_{exit}$时有交点

4. 考虑负的情况：$t_{exit}<0$$t_{exit}<0$ 说明Box在光背后

5. $t_{exit}\ge 0\mathrm{\&}\mathrm{\&}{t}_{enter}<0$$t_{exit}≥0\ \&\&\ t_{enter}< 0$ 说明光线起点在Box内 → 有交点

6. 对于三维包围盒来说，有如下公式成立：$t_{enter}=max\left\{t_{min}\right\},t_{exit}=min\{t_{max}\}$$t_{enter}=\max \left\{t_{\min }\right\}, t_{exit}=\min \{t_{max}\}$

总之，当且仅当$t_{enter}<t_{exit}\mathrm{\&}\mathrm{\&}{t}_{exit}\ge 0$$t_{enter}<t_{exit}\ \&\&\ t_{exit}\ge 0$时，光线与AABB相交。（该算法背后是Liang-Barsky算法）

2. Using AABBs to Accelerate Ray Tracing

lecture14继续介绍加速光线追踪的内容。是1.2节的延续。

本节我们将介绍Uniform grids，Spatial partitions和Object partitions三种场景划分方式。

2.1 Uniform Grid

Uniform grids 简单来说就是将场景划分成一个个规整的格子，通过格子来判断光线与物体的相交情况。

构建Uniform grids 的步骤如下：

1. 找到包围盒

2. 创建格子

3. 存储每个对象至格子中

那么此时判定光线与物体相交就转换成光线与格子相交问题，当光线与格子相交后，再去考虑它与格子内物体的相交情况：

这种方式有一些问题：

1. 格子的分辨率问题，如果格子的分辨率设置太小就失去了划分的意义；如果分辨率太大就要做好多次和格子求交，效率不高。

2. 格子通常只适用于规整的场景，相反，物体位置较为稀疏的场景就不适用这种划分方案，因为此时很多格子都不存储物体，大量时间被浪费在了光线与格子的求交上

2.2 Spatial Partition

通常有 Oct-Tree（八叉树） 、KD-Tree 以及 BSP-Tree 三种划分方案：

• Oct-Tree：每次迭代都将区域重新切分为均匀四块，按一定规则停止切分（如切分得到的四块区域中，三块都没有物体；或四块区域都还有物体，但是此时的区域已经较小）

• KD-Tree：总是沿某个轴进行切分，每次划分总会在原来的区域上生成两块新的区域（这里沿轴的次序是由交替进行的，如二维中总是按着x y的次序进行交替切分）

• BSP-Tree：每次都是沿着一定方向进行切分（非水平或竖直）

下面着重介绍KD-tree。

1）Pre-Processing

假设空间 A 被划分为如图所示 KD-Tree，那么它的结构等同于其中树结构所所描述：

2）Data Structure for KD-Trees

中间节点（A，B，C，D）存储了：

1. 划分后的轴

2. 划分后的切分平面

3. 子节点的指针

叶子节点（1，2，3，4，5）存储了：区域中包含的物体的列表（obj只会存在于叶子节点）

3）Traverse

1. 发射光线从根节点出发，分别判断光线与左右节点是否相交，若相交则进入2；否则，则与节点不相交

2. 递归判断相交直至叶子节点，若与叶子节点相交，进入3

3. 挨个判断叶子节点存储物体与光线的相交情况

4）Problem

1. 三角形mesh与盒子的交点不好判断

2. 物体可能与多个包围盒相交

2.3 Object Partition & Bounding Volume Hierarchy (BVH)

为了解决上述问题，人们提出了另外一种划分方案，即在场景中对物体进行划分，此时就不用考虑三角形与包围盒的求交问题

它本质是将一个场景用一个包围盒包住，然后按照一定划分方案将盒子划分成不同的子区域，不同子区域都需要包含三角形，最终划分到叶子节点时，每个叶子节点就包含了一些三角形，即包含了对应的一些物体：

1）Building BVHs

三种想法

• 按轴的次序进行划分

• 按最长轴继续进行划分

• 在物体三角形数目的最中间对物体进行划分（这里的最中间指的是划分后，两边的三角形数目基本一致）

Visualizing the Boundary Volume Hierarchy algorithm — Harold Serrano - Game Engine Developer提供了第三种的具体画法（事实上也包含了第二种）。

何时停止？当包围盒中物体个数小于一个定值时停止。

2）Data Structure

• 中间节点（Internal nodes）：该节点对应的包围盒和子节点的指针

• 叶子节点（Leaf nodes）：该节点对应的包围盒和包围盒里面的物体列表

3）BVH Traversal

4）Spatial vs Object Partitions

3. Radiometry

为了对物理世界的光做更加真实的描述，我们需要介绍辐射度量学（radiometry）。

• 辐射通量（radiant flux）：$\mathrm{\Phi }\equiv dQ/dt[W]$$\Phi\equiv dQ/dt\ [W]$. 单位时间的辐射能量，亦作辐射功率

• 辐射强度（radiant intensity）：$I(\omega )\equiv d\mathrm{\Phi }/d\omega$$I(\omega)\equiv d\Phi/d\omega$. 单位立体角的辐射通量

• 辐照度（irradiance）：$E(x)\equiv d\mathrm{\Phi }/dA$$E(x)\equiv d\Phi/dA$. 单位表面的辐射通量

• 辐射率（radiance）：单位立体角和垂直此方向的单位表面的辐射通量。如图

4. Bidirectional Reflectance Distribution Function (BRDF)

BRDF 解决了从某个方向辐射到表面的能量，它所辐射到其他方向的能量分布问题。BRDF公式如下：

对$d{\omega }_i$$d\omega_i$做积分，得到反射方程（reflection equation）：（图中H²表示上半球面）

渲染方程（rendering equation）就是物体自发光加上反射方程：（图中${\mathrm{\Omega }}^{+}$$\Omega^+$表示上半球面，p是着色点）

接下来我们换一个角度来理解上述公式，来看看L到底包含了什么。下面的ppt包含了积分方程、矩阵泰勒展开等等数学知识。最后导出了漂亮的结果，可以看到物体发出来的辐射率包含了自发光、一次反射、二次反射等等。

5. Monte Carlo Integration

求定积分的一种估计方法

6. Path Tracing

6.1 Whitted-Style Ray Tracing‘s Problem

• 在处理光照反射时总是沿着镜面反射方向进行，这适用于镜面材质，但不适用于 Glossy 之类的材质

• 不考虑物体表面漫反射会进一步反射，但实际上漫反射物体仍会继续反射光线

6.2 A Monte Carlo Solution

相较于这些问题，第四节介绍的渲染方程仍然是对的，所以我们只需要按照渲染方程来求解物体表面的着色问题即可。由蒙特卡洛方法有：（式中pdf是概率密度函数（probability density function））

算法：

上述算法的问题：

• 光线数量会爆炸，因为一个着色点会反射多个光线（选$w_i$$w_i$时）。我们可以将反射的光线数目设为1（即路径追踪path tracing的概念），于是shade函数变为：

  

  但是这样噪声很大，于是我们在每个像素处打入多条光线来解决这个问题。

  

  

• 递归无法停止。使用Russian Roulette（俄罗斯轮盘赌）解决。

  

至此一个正确的路径追踪算法实现了，但效率不高。要求有高采样率，即一个像素要发出很多条光线进行采样。我们希望通过低采样率也能获得高采样率的效果。

这里的做法就是将物体表面接收到的 radiance 分解为两部分：来自光源和来自其他反射物体。

• 对于来自光源的部分，直接在光源上进行采样即可，采样过程就是换积分域的过程

• 对于来自其他反射的光源，仍然按照RR算法求解

换积分域如图：

最终的伪代码如下：

上述路径追踪算法效果相当相当的好。当然辐射率并不是颜色，还需要γ校正等操作。

17 Materials and Appearances

1. Material == BRDF

在图形学中材质就是BRDF。

1.1 Diffuse/Lambertian Material

漫反射材质（diffuse/Lambertian material）会向着色点表面半球的各个方向进行均匀反射：

现在假设一个漫反射材质着色点接收到均匀的光（$L_i(w_i)$$L_i(w_i)$为常数），并向各个方向均匀反射（$f_r(w_i,w_o)$$f_r(w_i,w_o)$为常数）。则由渲染方程有：

由能量守恒（$L_o=L_i$$L_o=L_i$）得：

其中$\rho$$\rho$称为albedo，在零一之间，可以来表示颜色。

1.2 Glossy Material

这是一种更加粗糙的材质，表面会产生沿一个方向的散射：

1.3 Ideal Reflective/Refractive Material

这种材质会产生反射和折射：

关于反射和折射公式想必都会了

1.4 Fresnel Reflection/Term

菲涅尔公式解释反射光的强度、折射光的强度、相位与入射光的角度的关系。菲涅尔效应指：视线垂直于表面时，反射较弱；而当视线非垂直表面时，夹角越小，反射越明显。譬如看脚底游泳池的水是透明的，但是远处的水面反射强烈。

定性分析

绝缘体和导体的菲涅尔项不同

定量分析

精确公式和近似公式如下：

2. Microfacet Material

微平面（microfacet）理论假设物体表面由不同法向量的微小平面组成。

它引入了三个函数：D、G、F

• D：是法线分布函数，它解释了在观看者角度反射光的微平面的比例。法线分布函数描述了在这个表面周围的法线分布情况，当输入向量h时，如果微平面中有35%与向量h取向一致，则法线分布函数就会返回0.35

• G：是几何衰减函数，它解释了微平面彼此之间的阴影和遮挡。

• F：是菲涅尔函数，它解释了菲涅耳效应，该效应使得与表面成较高的入射角的光线会以更高的镜面反射率进行反射。

可以根据物体微表面是否具有方向性将物体分类

• Isotropic(各项同性)：法线分布均匀

• Anisotropic(各项异性)：法线分布有明确的方向性

3. Properties of BRDFs

BRDF性质有：

• 非负

  $$f_r(w_i\to w_r)\ge 0$$

• 线性可加

• 可逆

  $$f_r(w_i\to w_r)=f_r(w_r\to w_i)$$

• 能量守恒

  $${\int }_{H^2}{f}_r(w_i\to w_r)\cos {\theta }_i\mathrm{d}{w}_i\le 1$$

• 各向同性/各向异性：如果满足各向同性，BRDF可以从4维降低到3维。即

  $$f_r({\theta }_i,{\varphi }_i;{\theta }_r,{\varphi }_r)=f_r({\theta }_i,{\theta }_r,{\varphi }_r-{\varphi }_i)$$

18 Advanced Topics in Rendering

本章介绍了渲染中的一些现代方法。属于介绍内容，不再整理。思维导图如下：

19 Cameras, Lenses and Light Fields

本章被弹幕戏称为“现代摄影入门”，属于科普性质。简单整理。

1. Cameras

• Aperture size（光圈大小）：光圈越大，进光量就越多，照出的照片越亮，背景越虚化。F值为镜头的焦距除以镜头口径的直径。F值越小，光圈越大。

• Shutter speed（快门速度）：快门速度越大，运动物体不易模糊，同时照片越暗

• ISO感光度：Multiply signal before analog-to-digital conversion；Linear effect (ISO 200 needs half the light as ISO 100)。ISO越大，照片越亮，底噪越大

• Exposure（曝光）：曝光时间乘以irradiance

2. Lens

折射公式想必会了

2.1 CoC（Circle of Confusion）

当物体远离Focal Plane，原本的一个点落在sensor plane上就会变成一个圆，这个圆就被称为circle of confusion，如下图，它和光圈大小有比例关系

回忆到，光圈N=焦距f/直径A。故有

即，CoC 和 N成反比，更大的光圈使得远处物体成像模糊。

2.2 Depth of Field

景深二图以蔽之

2.3 Rendering with Lens Focus

怎么渲染出景深的效果呢？

1）定义属性：

定义sensor的大小，透镜的属性（焦距，光圈大小），物距z_0

2）渲染

• 对于sensor上的每个点x’

• 在透镜上随机取样点x’’

• 将上面两点连线后，根据透镜性质得知光线可以传播到x’’’

• 估计x‘’‘到x’的radiance

3. Light Field / Lumigraph

光场（light field或称为lumigraph），即是空间中任意点发出的任意方向的光的集合。

七维全光函数（plenoptic function）$L(x,y,x,\theta ,\varphi ,\lambda ,t)$$L(x,y,x,θ,ϕ,λ,t)$描述了空间中的光场，$(x,y,x)$$(x,y,x)$表示光线的空间位置，$(\theta ,\varphi )$$(θ,ϕ)$表示光线的角度，$(\lambda ,t)$$(λ,t)$表示光线的波长和时间。

可以用两个平面上的点$(u,v),(s,t)$$(u,v),(s,t)$来描述光场。

这样参数化有两种理解方式

• a. 一种是固定(u,v), 所有的(s,t)组成一张图，也就是从(u,v)点看到的外部世界的样子

• b. 另一种是固定(s,t), 所有的(u,v)组成一张图，也就是显示从不同方向看同一个点的样子

20 Color and Perception

本章更是科普性质，懒惰的我就不做整理了

21~22 Animation

又是很简单的整理

1. Mass Spring System

胡克定律和简谐振动都学过了。我们这里引入弹簧内部的相对运动消耗施展在弹簧两端的力：

质点们通过弹簧连接可以生成不同的拓扑结构，从而进行物体的模拟。譬如可以模拟布料。

2. Particle System

粒子系统指的是模拟大量粒子集合的运动，在其中每个粒子的运动又会受到不同力的影响，如碰撞、引力等，我们只需要把这些力正确的模拟出来即可。譬如可以模拟水流、星系、鸟群。

3. Kinematics

• 正向运动学（forward kinematics）：已知初始的关键点位置和相对旋转，计算最终的关键点位置。唯一解

• 反向运动学（inverse kinematics）：根据初始的关键点位置和最终关键点位置，计算相对旋转的数学过程。无解或无穷多解（ill-posed problem）。

绑定蒙皮和动捕不想整理了

4. Single Particle Simulation

模拟单个粒子在速度场中的运动情况（速度场指的就是一种函数，在任意时刻t和位置x，都有对应的速度取值v(x,t)）。即解ODE

接下来介绍了欧拉方法等数值求解ODE的解法，不再展开。

5. Rigid Body Simulation

刚体模拟（Rigid body simulation）不会发生形变，即刚体的内部都会以一种方式（趋势）进行运动，所以也可以把刚体模拟看成是粒子的扩充进行模拟：

6. Fluid Simulation

关键想法：

• 水是由无数小的刚体球体组成

• 水无法被压缩，即任意处水的密度相等

• 当某处的密度改变了，需要其他位置的球来补充

• 需要知道各处的密度梯度，使用梯度下降更新

流体动力学里有拉格朗日法和欧拉法