GAMES 101 现代计算机图形学基础 笔记(上篇).

  • 变换与齐次坐标
  • 光栅化(反走样与深度缓冲)
  • 着色(Blinn-Phong 着色模型,图形管线,纹理映射,凹凸贴图)
  • 几何(曲线与曲面,贝塞尔曲线)

变换 Transformation

为什么要学习变换?

变换分为模型变换和视图变换。

模型变换的例子:

  • 跳舞机器人的运动
  • PIXAR 的开场动画

视图变换:

  • 3D 空间到 2D 的投影

二维变换

缩放变换(Scale)

反射变换(Reflection)

切变变换(Shear)

旋转(Rotation)

About (0,0), CCW(Counter clockwise) by default.

线性变换(Linear)

齐次坐标 (Homogeneous Coordinates)

平移不能有上述的矩阵表示。

但是我们希望使用简单的表示方法。有无能将上述变换统一的表示方式?

增加坐标的第三维度!(w-coordinate)

  • 2D Point: $(x,y,1)^T$
  • 2D Vector: $(x, y, 0)^T$
  • Valid Operations on w-coordinate
    • Vec + Vec = Vec
    • Point - Point = Vec
    • Point + Vec = Point
    • Point + Point = ?
      • Let $(x,y,w)^T := (\frac x w, \frac y w, 1), w\ne 0$
      • 几何意义是 n 等分点

这样我们就能将仿射变换转换成统一的矩阵表示了。

逆变换(Inverse Transform)

$M^{-1}$ is the inverse of transform $M$ in both a matrix and geometric sense.

变换的合成(Composing Transforms)

复杂的变换可以通过简单的变换得到;在变换的复合过程中,先后次序很重要.

三维变换

可按照上述的思路,构造出 4x4 矩阵表示的三维空间中的齐次坐标。

特别的,三维空间中的旋转需要固定旋转轴。

欧拉角 $R_{xyz}(\alpha, \beta,\gamma)=R_x(\alpha)R_y(\beta)R_z(\gamma)$​

观测变换(Viewing Transformation)

视图变换(View/Camera Transformation)

什么是视图变换?我们可以与拍照过程进行类比。拍照的第一步是模型变换,也就是把模型放在合适的位置上。第二步是找好角度放相机(View Transformation),也就是本节要介绍的视图变换。第三步是做投影变换,将照片定格。

如何执行视图变换?首先要定义相机的概念:

  • 位置 $\vec e$
  • 看向 $\hat g$
  • 相机的向上方向 $\hat t$

约定俗成地,我们在视图变换时令 $\vec e = \vec 0, \hat g = -\hat z, \hat t = \hat y \ (*)$。

定义 $M_{view}$ 变换相机,使得经过该变换满足上述 $(*)$。

  • Translates $\vec e$ to origin.
  • Rotate $\hat g$ to $-\hat z$.
  • Rotate $\hat t$ to $\hat y$.
  • Then naturally $\hat g \times \hat y = \hat x$.

Then the calculation process:

我们要做的,是把所有物体都应用这个变换,保证相机与物体的相对运动性质不变。

视图变换也被称为 ModelView Transformation.

投影变换(Projection Transformation)

计算机图形学中的投影:是将 3D 模型形成二维图像,有两种投影方式,正交投影与透视投影。正交投影(Orthographic projection)原来平行的线仍然平行;透视投影(Perspective projection)平行线不再平行,会有近大远小的现象。

正交投影

首先我们需要将相机摆在合适的位置(具体来说是满足上述 $(*)$​ 的条件),然后我们可以直接无视掉 Z 坐标,将剩余的物体直接平移并缩放到 $[-1, 1]^2$​​。

正交变换实际上是把空间立方体 $[l, r] \times [b,t] \times [f,n]$ 映射到标准正方体 $[-1,1]^3$​ 的过程。

image-20211106214250684

正交投影的过程

具体来说,我们有:

透视投影

透视投影的特性是平行线相交于一点,近大远小。

回忆:$(x,y,z,1), (kx,ky,kz,k\ne0), (xz,yz,z^2,z\ne0)$​ 都代表同一点

  • 做透视投影的步骤:
    • 首先将视锥压成正方体 $M_{persp\rightarrow ortho}$
    • 然后进行正交投影 $M_{ortho}$

image-20211016010006341

做透视投影的步骤

这里我们略去透视投影矩阵的推导,直接给出透视投影转换为正交投影矩阵的表示形式。具体的推导可以通过考虑以下特殊点,代入特殊值来决定矩阵的元素。

  • 近平面的坐标不改变
  • 远平面的 $x,y$ 坐标被压缩至与近平面相同
  • 近平面中心点与远平面中心点的位置不变

值得注意的是,在我们平常的应用中,我们并不是直接使用 $l, r, b,t$ 来描述一个近平面的位置,而是更倾向于使用 $fovY$​(field-of-view, 垂直视角) 和 aspect ratio 这两个量来描述一个近平面。

使用这两个量我们可以轻松地计算出 $l,r,b,t$ 四个近平面参数。

image-20211106214646265

光栅化 Rasterization

准备

在我们进行完 MVP(模型变换,视图变换,投影变换)之后,我们将三维的模型转化成了 $[-1,1]^3$​​ 上的正规立方体。在那之后,我们就要将这个立方体投影到我们的屏幕上,绘出图像了。而这图像的绘制过程,我们便将其称为光栅化

在此之前,我们必须先给出屏幕的定义:

我们可以将屏幕视为是像素点的二维数组,其中每个像素点由 R, G, B 三种颜色构成。像素点的维数与分辨率相同。进行坐标表示时我们使用 $(x,y)$ 表示 $[x, x+1]\times[y,y+1]$ 这一个像素点,这里 x,y 是整数。

要将正规立方体绘制到屏幕上,这个过程与 z 是无关的,我们需要首先对 xOy 平面做变换 $[-1,1]^2\rightarrow [0, width] \times [0, height]$,这个过程我们称为视口变换。而这里用到的变换矩阵是:

该怎么把 $[0, width] \times [0, height]$​ 中的内容画到屏幕上呢?这就要用到光栅化了。

三角形的光栅化

我们接下来要考虑如何将三维空间中的一个三角形光栅化成像素。

为什么选择三角形?因为三角形是最基础的多边形,任何其它多边形都可以用三角形来表示。同时,三角形的三个顶点一定在同一个平面内。三角形的内部和外部区分的十分清楚,而且可以用叉积来判断点是否在三角形中。

那么,如果我们得到了三角形的三个顶点在二维平面中的表示 $(x_1, y_1), (x_2, y_2), (x_3, y_3)$​ 之后,我们该如何估计这个三角形所包围的像素点的集合呢?也就是说,该如何判断一个像素(的中心点)和一个三角形的位置关系呢?

我们可以通过采样(Sampling)的方法来实现。采样,实际是将一个函数离散化的过程,这是图形学中的一个核心概念。

我们再明确一下我们的采样目标:判断某个像素的中心点是否在给定的三角形 $(x_1, y_1), (x_2, y_2), (x_3, y_3)$​​ 内部。即我们要尝试去实现如下的函数:

// Sampling
for(int x = 0; x < xmax; ++x) {
    for(int y = 0; y < ymax; ++y) {
        image[x][y] = inside(t, x+0.5, y+0.5);
    }
}

那么该如何实现 inside(t, x, y) 函数呢?

image-20211106223216259

我们考虑如下的三个叉积。$\overrightarrow {P_0P_1} \times \overrightarrow {P_0Q}$, $\overrightarrow {P_1P_2} \times \overrightarrow {P_1Q}$, $\overrightarrow {P_2P_0} \times \overrightarrow {P_2Q}$ 如果 z 坐标的符号相同,那么点 Q 就一定在三角形内。如果点正好落在边界上,可自行定义解决方案。

image-20211106225745932

光栅化加速:包围盒

但是,如果对屏幕的所有元素采样,造成了没有必要的资源浪费。我们使用包围盒(Bounding Box)的概念,取三角形边界点的 x, y 坐标分别的最小值或最大值,作为包围盒 x, y 坐标的最小值与最大值。这样我们就能得到一张带锯齿的图像了。

image-20211106232712939

带锯齿的图像

图像之所以带锯齿(Jaggies)是因为,我们的采样率并不够高,并不足以描述原来的信号,因此就发生了走样(Aliasing)的问题。

反走样

首先我们简单介绍一下采样理论。采样瑕疵(Sampling Artifacts)包括多种,在图形学中包括锯齿,摩尔纹等等。采样瑕疵背后都是因为信号的变化太快,以至于采样的速度跟不上信号的变化。而解决办法,便是通过首先对原图进行模糊(滤波, pre-filtering then sampling),然后再对其进行采样。

频域的概念

频率的概念我们已经熟知,如 $\cos 2\pi fx$ 中频率为 $f$​。用频率可以定义函数周期性变化的快慢。

我们可以使用傅里叶级数将一个函数(从它的时域)表示成正弦函数和余弦函数的加权和的形式(转换到频域),也可以使用逆傅里叶变换将其从频域转化回时域。

image-20211106235002520

傅里叶变换和逆傅里叶变换

走样是指,使用同样的采样方式,在高频信号和低频信号两个不同的信号上,得到了相同的采样结果。如下图所示:

image-20211108153046165

走样的例子

滤波 Filtering

滤波是指对于某个特定的信号,仅保留其特定频率的信息。以图像为例,一个图的低通滤波等价于对这个图作用模糊效果,而一个图的高通滤波等价于描绘出这个图像的细节边界。

我们接下来要说明,对一张图做滤波,等价于对这张图做卷积(分 Box 加权平均)。

image-20211108155427029

卷积定理

卷积定理是说,对时域的卷积,等价于对频域的乘积;在时域上的乘积,等价于在频域上的卷积。也就是说,如果我们想得到一张图像的滤波,有以下两种选择:

  • 在时域中对图像做卷积
  • 先使用傅里叶变换将图像转化到频域,将其与 Box Filter 的频域相乘之后再做逆傅里叶变换

事实上,这里的 Box Function 就相当于是一个低通滤波器,可以用来将图像模糊化。而这里 Box 越宽,所接受的频率就越低,所得到的图像也就越模糊。

采样:重复频域上的内容

image-20211108160150741

卷积定理指出,在时域上的乘积,等价于在频域上的卷积。我们将原函数 $X_a(t)$​ 与冲激函数 $P_\delta(t)$ 做乘积,也就等价于将二者都使用 FFT 化归到频域后,将二者做卷积。而这结果表明,采样就是在重复一个原始信号的频谱。

image-20211108160830500

对走样的解释

而为什么会发生走样呢?采样的不同间隔,会引起频谱以不同的间隔去移动。如果我们采样的不够快,那么信号在频域上就产生了混叠现象。

反走样的方法

该怎么才能减少走样错误呢?

  • 增大采样率 (But very costly & may need high resolution)
  • 进行反走样操作:让图像的频谱的频宽变窄!如何做到?在采样前去掉高频信号!

回到我们的问题上来,我们要解决现在存在的锯齿问题,也就是要先对原三角形进行模糊,然后再对其采样。那么该怎么对原来的三角形进行模糊呢?我们使用一个低通滤波器对其进行卷积即可。

image-20211108161654357

通过计算像素点落在三角形中的平均面积来做滤波

而在我们具体解决问题的时候,我们选择 Supersampling 的方式,也就是将某个像素分为 $N\times N$ 个采样点,然后对这些采样点的像素值取平均。

image-20211110134128999

image-20211110134145650

深度缓冲

本节我们主要立足于解决可见性/遮挡问题,解决方法就是深度缓存/深度缓冲(Z-Buffering)。

只有将模型按照一定的顺序放在屏幕上,才能达到正确的效果。直观的想法是,先画远处的,再画近处的,这样才能让近处的物体覆盖远处的物体。这样的算法叫做画家算法。而如果假设有 $n$ 个物体,进行 $O(n \log n)$​ 的排序后便可将其画出。但是这种算法的缺陷是,如何定义“远近”,即定义物体离相机所在处的深度,并不容易。

image-20211110135626091

相互遮挡的例子

为了解决这个问题,图形学引入了深度缓存的概念。想法就是对屏幕的所有像素额外记录其当前显示物体的最浅深度(深度取正值,表示距离相机的远近)。这样类似于动态规划的算法最终复杂度是 $O(n)$ 的。而且如果我们假设在同一深度处不会出现两个模型,那么不同模型的着色顺序对结果是没有影响的。

image-20211110140334554

深度缓存算法

Shading 着色

Blinn-Phong 着色模型

着色是指引入明暗和颜色不同的过程,但在这里我们定义为对物体应用不同材质的过程。

于是我们在这里介绍一个简单的着色模型,Blinn-Phong Reflectance Model,其中包括高光,漫反射以及环境光照三部分。值得注意的是这个模型是 OpenGL 和 Direct3D 的默认着色模型。具体来说,其定义的参数如下:

image-20211110141545558

概念的定义

着色是具有局部性的,即每次只考虑单个点,不考虑其他物体的存在。这样是无法表现阴影的。

漫反射 Diffuse Reflection

光线的接收:单位面积上接收到的光照强度为 $\cos \theta = I \cdot n$。

光线的反射:$I’ = \frac I {r^2}$​

漫反射后:$L_d = k_d(I/r^2)\max(0,\vec n \cdot \vec l)$​,其中 $k_d$ 是三维的 (R,G,B),表示漫反射系数。

高光 Specular Term

基于如果 $v$ 视线方向和镜面方向相近,那么半程向量就跟平面法向相近的事实,我们定义半程向量 $h := bisector(v,l) = \frac {v+l} {||v+l||}$。

然后令 $L_s = k_s (I/r^2)max(0, \cos \alpha)^p=k_s (I/r^2)max(0, n \cdot h)^p$ 即可,其中 $k_s$ 为高光反射系数。

为什么要带有 $p$ 次方呢?这是因为我们想让产生高光的夹角处于一个相对较小的范围。

image-20211110200642332

环境光照 Ambientbu Term

环境光照的强度不取决于物体,我们在这里大胆假设每个地方、每个方向的环境光照的大小都相同。也就是说,这一项会填充图中的黑色区域,将图像整体提升某个光照强度。$L_a := k_aI_a$。

着色频率

不同的着色单位会有不同的着色效果,具体来说,可分为以下几种:

  • 逐三角形着色(Flat shading):将每个三角形视作一个平面,但着色效果不够光滑。

  • 逐顶点着色(Gourand shading):使用插值的方法计算三角形内部的颜色值,但问题在于如何求顶点的法向。

  • 逐像素着色(Phong shading):对每个像素点进行模型计算。

image-20211110202506874

值得注意的是,着色频率越低并不一定代表着效果越差。若几何体足够复杂,则可能区别甚小。

接下来就侧重于解决上述着色频率留下的问题:

image-20211110202753142

定义逐顶点的法线

image-20211110202853817

定义逐像素法线

图形管线 Graphic Pipeline

从图形到场景的过程描述为图形管线。

image-20211110203343148

纹理映射 Texture Mapping

纹理映射,事实上是为每个三角形分配一个材质平面的坐标 $(u, v)$。

image-20211111231357192

其中那种拼接起来可以无限重复的材质我们称为 tiled texture.

重心坐标插值

当我们知道了三角形的三个顶点的属性的时候,如果我们想要实现在三角形内部属性的平滑过渡,就要引入重心坐标的概念。

image-20211111231532132

对于一个三角形 ABC 来说,其中 $(x,y) = \alpha A + \beta B + \gamma C$,若 $\alpha + \beta + \gamma = 1$,则称 $(\alpha, \beta, \gamma)$ 为该三角形内的 $(x,y)$ 点的重心坐标,其中 $\alpha, \beta, \gamma \ge 0$。

image-20211111231732485

而由此推导下去,在 $xOy$ 平面中我们有:

使用重心坐标可以方便我们做插值。具体来说,对于三角形 ABC,对于其内部点 $(x,y)=(\alpha, \beta, \gamma)$​,有 $V = \alpha V_A + \beta V_B + \gamma V_C$​。

但是值得注意的是,重心坐标在投影操作中可能会变化。这就会导致一些插值操作只能在三维空间中计算,比如计算深度插值,应该使用原始的三角形三维坐标来计算,而不应使用投影后的平面坐标。

纹理应用 Applying Texture

我们可以将纹理的颜色值设置为模型对应位置的漫反射系数,从而达到应用纹理的效果。

而一个像素对应的纹理的颜色值,则可以通过插值的方式计算得出。

这里我们可能遇到问题:

  • 如果材质对应的图像过小怎么办?
  • 如果材质对应的图像过大怎么办?

对于前者,我们可以使用双线性插值的方法来缓解。

image-20211115164939643

而对于后者,我们可以使用 Mipmap / 各向异性过滤的方法来解决。

事实上,我们可以将纹理视为是内存中的一个数据结构,提供了便捷的查询接口,而非将纹理视为是一张图片。

用纹理做环境光反射效果

纹理可以用来做环境光反射的效果。实际上,如果我们将来自环境的光照组织成纹理:

image-20211127173639430

犹他茶壶

环境光可以通过记录在球面上,然后将球面展开,就可以得到环境光照对应的纹理。但是这样做在纹理上下会有明显的扭曲现象。

image-20211127174058860

为了解决这个扭曲的问题,我们使用如下的方案:

image-20211127174158530

将球面上的每个点映射到恰好包围球的包围盒的表面上(沿球面法向)。然后将包围盒展开成六个表面。

用纹理做凹凸贴图

事实上,我们的纹理不只是可以用来替换 Blinn-Phong 反射模型中的 $k_d$ 值。我们可以用纹理来描述表面的“属性”,比如待渲染表面的凹凸感,便可以用纹理来记录表面的相对高度。

其实我们可以用足够多的三角形来模拟出凹凸效果,但是这样势必会导致性能上的衰减。使用纹理来做凹凸贴图可以在不改变原模型的几何复杂程度的情况之下,达到渲染出带有凹凸感的图像的目的。

凹凸贴图的推导

计算过程:修改高度值 -> 重新计算法向量值 -> 着色。

image-20211201185543817

Local Coordinate : 换基

位移贴图

凹凸贴图并没有改变自己的几何,所以在边缘上看不出凹凸感。同时在阴影上也体现不出来凹凸感。而位移贴图实际上改变了模型几何的位置。但我们需要要求模型足够细致。

Geometry 几何

几何的表示

几何的分类:Implicit 的几何和 Explicit 的几何。

Implicit 的几何是说,满足某些特定关系的点构成的几何,即 $f(x,y,z)=0$;Implicit 对于找出集合中的所有点很困难,但是要想判断某个点在不在其中很容易。

Explicit 的表示是说,通过参数映射的方法来定义表面,即将平面上的点 $(u,v)$ 映射到三维坐标 $(x,y,z)$​​​. 想找出几何体表面集合中的所有点,只需变化 $u,v$ 的值即可。但是不容易判断某个点在不在其中。

不同的表示方法,需要根据需要来选择。

此外,隐式表示还可以用 CSG(Constructive Solid Geometry) 的方法来构造,如 $A \cup B, A\cap B, A\backslash B$.

image-20211201192043523

CSG 的例子

隐式表示还可以用距离函数、水平集、分形等等方法来定义。

显式表示可以用点云,多边形面(obj 文件)等等表示。

曲线

贝塞尔曲线

用一系列的控制点定义出满足某些性质的曲线。

曲线的起点为控制点的起点,终点为控制点的终点,起始点处与终点处的切线分别为 $\overrightarrow {P_0P_1}, \overrightarrow{P_{n-1}P_n}$.

如何画贝塞尔曲线:de Casteljau Algorithm

(1)先考虑三个控制点,生成二次贝塞尔曲线。

image-20211201194418429

(2)再考虑四个控制点,生成三次贝塞尔曲线。

image-20211201194528603

(3) 代数形式:插值!

image-20211201194639946

给定 $n+1$ 个控制点,有贝塞尔曲线如下:

贝塞尔曲线的性质:

(3) 在仿射变换下不变;

(4) 曲线包含在控制点的凸包(包含所有控制点的最小凸多边形)内。

逐段形成贝塞尔曲线:每四个控制点形成一段贝塞尔曲线,并将其连接。

保证切线光滑?导数连续!保证性质(2)成立即可。

两段贝塞尔曲线的连续: $C^0$ 连续指点重合,$C^1$ 连续指导数连续,以此类推。

其它曲线

样条(Spline),B-样条(basis splines),具有好的局部性。

曲面

贝塞尔曲面

image-20211201201257424

面上的操作

  • Subdivision
  • Simplification
  • Regularization
细分

(1) 分出更多三角形 (2) 将新的三角形的位置改变,使得原模型更加光滑

Loop Subdivision

image-20211201202358001

image-20211201202518340

Catmull-Clark Subdivision

针对于一般的曲面,而非三角形作为图源。

定义:非四边形面,奇异点(度不为 4 的点)

细分的方式:引入点的操作十分简单,取每面的中点和该面的边的中点,并将其连接。

调整位置的方法:分为三种。

image-20211201204717217

简化

边坍缩 Edge Collapse

Quadric Error Metrics 二次误差度量 寻找去 Collapse 某条边后新顶点的位置。

image-20211201205342215

将所有边按二次误差测量排序,坍缩最小值所在边,更新受影响的其他边的权重。用堆来维护!