【Games101】-＞计算机图形学

[@toc]

【Games101】-> 计算机图形学

！！！为什么计算机图形学和计算机视觉不一样？有何区别？！！！

模型(Model) -> 图像(Image): 计算机图形学(渲染 3D -> 2D)

图像(Image) -> 模型(Model): 计算机视觉(2D -> 3D)

一. 线性代数基础

向量 Vector

向量 / 矢量 (Vector)：

1. AB = B - A。
1. 两个维度进行比较：方向和长度。
1. 没有绝对的开始位置。

归一化 (Normalization)：

1. 长度维度：模Magnitude |a|
1. 方向维度：单位向量(归一化) a / |a|

点乘(Dot):

向量a = $\bigl(

\begin{matrix} x a \ya \za \end{matrix}

\bigr) $/ (xa,ya,za) , b =

\begin{matrix} x b \\ y b \\ z b \end{matrix}

/ (xb,yb,zb)

1. 运算法则：a · b = |a| |b| cosθ
1. 向量点乘满足交换律，结合律和分配律
1. 坐标运算：a · b = xaxb + yayb + zazb
1. 几何意义：a 在 b 上的投影长度
1. 本质是cosθ 的值决定的方向关系
  
  – 1) 当a和b方向越接近，单位向量点乘结果越接近1
  
  – 2) 当a和b方向越远(趋近相反)，单位向量点乘结果越接近-1
  
  – 3) 当a和b方向垂直时，单位向量点乘结果为0

叉乘(Cross):

向量a = $\bigl(

\begin{matrix} x a \ya \za \end{matrix}

\bigr) $/ (xa,ya,za) , b =

\begin{matrix} x b \\ y b \\ z b \end{matrix}

/ (xb,yb,zb)

1. 运算法则：a · b = |a| |b| sinθ，得到一个向量
1. 右手螺旋定则四指从 a -> b，大拇指指向的方向即为结果方向。
1. 左右手坐标系：当 x × y = z时，使用的是右手坐标系。
1. 叉乘交换律：a × b = -b × a且a × a = 0向量(不是0，是0向量)
1. 叉乘依旧满足分配律和结合律 a × (kb) = k(a × b)
1. 叉乘的实际应用：本质是sinθ 决定的位置关系
  
  – 1) 判断a，b向量的左右关系，a × b > 0 时，b在a的右边，反之,b在a的左边。
  
  – 2) 判断某点在面的内外关系：一个三条向量组成的三角形 A -> B -> C -> A，判断P点是否在三角形内部，分别判断AB,BC,CA三边与AP,BP,CP的左右位置关系，如果都在同一侧，则说明点在三角形内部。

矩阵 Matrices

1. 两个矩阵的相乘，头矩阵的列数必须要与后矩阵的行数相同，否则无法进行乘积。
1. 要计算结果矩阵i行j列的数据，直接找头矩阵i行和后矩阵j列做点乘即可。
1. 矩阵满足结合律和分配律，不满足交换律。

矩阵和向量的混合运算：
当矩阵和向量相乘时，始终将向量写为纵向量并写在后面。
关于矩阵的转置，(AB)^T = B^T A^T。

二. 变换Transformation

2.1. 2D Transformation

尺寸变换Scale

常规缩放

sx ，sy分别为 x，y 方向上的缩放系数。

$\bigl($

\begin{matrix} x p \\ y p \end{matrix}

\bigr)

(x p y p)

=

\begin{matrix} s x & 0 \\ 0 & s y \end{matrix}

\begin{matrix} x \\ y \end{matrix}

变化关系可以表现为: (x,y) -> Ssx,sy => (xp,yp)

Reflection负缩放:

当sx,sy为负数时，在图像效果上表现为对称效果，称为负缩放。

$\bigl($

\begin{matrix} x p \\ y p \end{matrix}

\bigr)

(x p y p)

=

\begin{matrix} - x \\ y \end{matrix}

=

\begin{matrix} - 1 & 0 \\ 0 & 1 \end{matrix}

\begin{matrix} x \\ y \end{matrix}

Shear切变:

x ， y两轴对应为：x = x + ay, y = y。

$\bigl($

\begin{matrix} x p \\ y p \end{matrix}

\bigr)

(x p y p)

=

\begin{matrix} 1 & a \\ 0 & 1 \end{matrix}

\begin{matrix} x \\ y \end{matrix}

旋转变换Rotation

通用旋转：

$\bigl($

\begin{matrix} x p \\ y p \end{matrix}

\bigr)

(x p y p)

=

\begin{matrix} c o s θ & - s i n θ \\ s i n θ & c o s θ \end{matrix}

\begin{matrix} x \\ y \end{matrix}

平移变换Translate

齐次线性变换：

$\bigl($

\begin{matrix} x p \\ y p \end{matrix}

\bigr)

(x p y p)

=

\begin{matrix} a & b \\ c & d \end{matrix}

\begin{matrix} x \\ y \end{matrix}

或者

\begin{matrix} x p \\ y p \end{matrix}

= M

\begin{matrix} x \\ y \end{matrix}

，M为过渡矩阵。

平移变换:

$\bigl($

\begin{matrix} x p \\ y p \end{matrix}

\bigr)

(x p y p)

=

\begin{matrix} a & b \\ c & d \end{matrix}

\begin{matrix} x \\ y \end{matrix}

+

\begin{matrix} t x \\ t y \end{matrix}

由于平移变换并不是传统意义上的线性变换，我们为了能够统一表示所有基础变换，我们可以增加一个维度来表示低维度的变换。

升维表示:

2D变换的本质：

2D point = (x,y,1) ^ T

2D vector = (x,y,0) ^ T

tx,ty为对应轴偏移量:

得出： $\bigl($

\begin{matrix} x p \\ y p \\ w p \end{matrix}

\bigr)

(x p y p wp)

=

\begin{matrix} 1 & 0 & t x \\ 0 & 1 & t y \\ 0 & 0 & 1 \end{matrix}

\begin{matrix} x \\ y \\ 1 \end{matrix}

=

\begin{matrix} x + t x \\ y + t y \\ 1 \end{matrix}

使用通用的式子表达所有2D基础变换：

$\bigl($

\begin{matrix} x p \\ y p \\ w \end{matrix}

\bigr)

(x p y p w)

=

\begin{matrix} a & b & t x \\ c & d & t y \\ 0 & 0 & 1 \end{matrix}

\begin{matrix} x \\ y \\ 1 \end{matrix}

变换的逆运算，合成与分解

A 通过某种变换到 B ，那么从B 回到 A 既是 逆变换 。在矩阵角度即求矩阵的逆矩阵。

由于2D基础变换的通用表示均是 3 × 3的矩阵，故可以将许多基础变换的3 x 3矩阵依次相乘，最后得到的和变换仍是一个 3 x 3 的矩阵，最后统一对原图形作一个合成变换，即为 变换的合成。

变换的分解为合成的逆运算。

2.2. 3D变换

同样类比2D升维 3D的表示法，可以得出3D空间的点和向量的本质如下：

(x,y,z,w)
:
3D point = (x,y,z,1) ^ T

3D vector = (x,y,z,0) ^ T

通常，当w != 0 时，3D点的真实坐标为：(x / w, y / w, z / w )。

3D基础变换的通式：

Tips: 先进行线性变换再进行平移变换。

$\bigl($

\begin{matrix} x p \\ y p \\ z p \\ 1 \end{matrix}

\bigr)

(x p y p z p 1)

=

\begin{matrix} a & b & c & t x \\ d & e & f & t y \\ g & h & i & t z \\ 0 & 0 & 0 & 1 \end{matrix}

\begin{matrix} x \\ y \\ z \\ 1 \end{matrix}

尺寸变换
S(sx,sy,sz) = $\bigl($

\begin{matrix} s x & 0 & 0 & 0 \\ 0 & s y & 0 & 0 \\ 0 & 0 & s z & 0 \\ 0 & 0 & 0 & 1 \end{matrix}

\bigr)

(s x 000 0 sy 00 00 sz 0 0001)

平移变换
T(tx,ty,tz) = $\bigl($

\begin{matrix} 1 & 0 & 0 & t x \\ 0 & 1 & 0 & t y \\ 0 & 0 & 1 & t z \\ 0 & 0 & 0 & 1 \end{matrix}

\bigr)

(100001000010 t x t y t z 1)

旋转变换
按照右手螺旋定则，可以得到：

xy = z, yz = x, zx = y

Rx(α) = $\bigl($

\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & c o s α & - s i n α & 0 \\ 0 & s i n α & c o s α & 0 \\ 0 & 0 & 0 & 1 \end{matrix}

\bigr)

(1000 0 cos α s in α 0 0 - s in α cos α 0 0001)

Ry(α) = $\bigl($

\begin{matrix} c o s α & 0 & s i n α & 0 \\ 0 & 1 & 0 & 0 \\ - s i n α & 0 & c o s α & 0 \\ 0 & 0 & 0 & 1 \end{matrix}

\bigr)

(cos α 0 - s in α 0 0100 s in α 0 cos α 0 0001)

Rz(α) = $\bigl($

\begin{matrix} c o s α & - s i n α & 0 & 0 \\ s i n α & c o s α & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}

\bigr)

(cos α s in α 00 - s in α cos α 00 00100001)

案例：飞机的三种航行方式(旋转)：Roll Yaw Pitch

Rodrigues(罗德里格斯旋转方程)：

n为旋转轴的向量(根据线性变换的分解可知，任何旋转默认其旋转轴过圆心，故可以使用一个简单的向量表示旋转轴。)，α为绕轴旋转的角度。I是单位矩阵 $\bigl($

\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & 1 \end{matrix}

\bigr)

(10 ⋮ 0 01 ⋮ 0 \dots \dots ⋱ 0 00 ⋮ 1)

R(n,α) = cos(α)I + (1-cosα))n(n^T) + sin(α) $\bigl($

\begin{matrix} 0 & - n z & n y \\ n z & 0 & - n x \\ - n y & n x & 0 \end{matrix}

\bigr)

(0 n z - n y - n z 0 n x n y - n x 0)

2.3. MVP变换

MVP:(model -> view -> projection)

视图变换就是：将场景中所有物体，包括相机，以其自身重心为原点的坐标系转换到以相机为原点的坐标系上。（世界坐标系 -> 相机坐标系）

视图变换:

摄像机的定义：要确定一个摄像机的位置信息，需要确定三个参量：

1. point e:相机所在的位置
1. vector g: 指向相机的前方 (-Z轴)
1. vector t：指向相机的正上方 (Y轴)

已知：旋转矩阵(正交矩阵)的逆就等于其转置矩阵。

有了以上定义，我们可以知道,Model -> View的运算分为以下几步：

1. Mview = Rview Tview, Tview = $\begin{matrix} 1 & 0 & 0 & - x e \\ 0 & 1 & 0 & - y e \\ 0 & 0 & 1 & - z e \\ 0 & 0 & 0 & 1 \end{matrix}$
1. 考虑 g -> -Z, t -> Y , (g × t) -> X的逆运算：Rview^-1 = $\begin{matrix} x (g x t) & x t & x (- g) & 0 \\ y (g x t) & y t & y (- g) & 0 \\ z (g x t) & z t & z (- g) & 0 \\ 0 & 0 & 0 & 1 \end{matrix}$
1. 转置上述矩阵得 Rview = $\begin{matrix} x (g x t) & y (g x t) & z (g x t) & 0 \\ x t & y t & z t & 0 \\ x (- g) & y (- g) & z (- g) & 0 \\ 0 & 0 & 0 & 1 \end{matrix}$

投影变换：

正交投影(Orthographic):
定义：平行光投影，没有“近大远小”的视觉特征。

正交投影的数学原理：
定义原本立方体的六个顶点参数为 f(far),n(near),l(left),r(right),t(top),b(bottom)：

1.将几何体中心点移动到原点。
2.将立方体的尺寸scale扩大为2 * 2 * 2。

M ortho = $\begin{matrix} 2 / (r - l) & 0 & 0 & 0 \\ 0 & 2 / (t - b) & 0 & 0 \\ 0 & 0 & 2 / (n - f) & 0 \\ 0 & 0 & 0 & 1 \end{matrix}$ $\begin{matrix} 1 & 0 & 0 & - (r + l) / 2 \\ 0 & 1 & 0 & - (t + b) / 2 \\ 0 & 0 & 1 & - (n + f) / 2 \\ 0 & 0 & 0 & 1 \end{matrix}$

透视投影(Perspective):

定义：点光源投影(肉眼结构)，存在“近大远小”的视觉特征。
透视投影的数学原理：

1.将平截头体挤压成立方体，即Mpersp -> Mortho。
2.对挤压成的立方体作正交投影即可。（见上）

挤压过程中各坐标的变化为：

yp = (n / z) y , xp = (n / z) x。带入：

M(persp->ortho) $\bigl($

\begin{matrix} x \\ y \\ z \\ 1 \end{matrix}

\bigr)

(x y z 1)

=

\begin{matrix} n x \\ n y \\ ? \\ z \end{matrix}

可推得：M =

\begin{matrix} n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ ? & ? & ? & ? \\ 0 & 0 & 1 & 0 \end{matrix}

根据待定系数法：带入近处点

\begin{matrix} x \\ y \\ n \\ 1 \end{matrix}

=>

\begin{matrix} x \\ y \\ z \\ 1 \end{matrix}

==

\begin{matrix} n x \\ n y \\ n ² \\ n \end{matrix}

。

所以M矩阵的第三行为：

\begin{matrix} 0 & 0 & A & B \end{matrix}

\begin{matrix} x \\ y \\ n \\ 1 \end{matrix}

= n²

带入远处平面的中心点

\begin{matrix} 0 \\ 0 \\ f \\ 1 \end{matrix}

=>

\begin{matrix} 0 \\ 0 \\ f \\ 1 \end{matrix}

==

\begin{matrix} 0 \\ 0 \\ f ² \\ f \end{matrix}

，得出以下结论：

1. An + B = n²
1. Af + B = f²

解得：A = n + f, B = -nf，M(persp->Mortho) = $\bigl($

\begin{matrix} n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ 0 & 0 & n + f & - n f \\ 0 & 0 & 1 & 0 \end{matrix}

\bigr)

(n 000 0 n 00 00 n + f 1 00 - n f 0)

带入 Mpersp = M(persp->Mortho) * Mortho即可。

三. Rasterization光栅化

3.1. 光栅化

垂直可视角(vertical fov):从相机处上中点到下中点所成的夹角。

纵横比(aspect ratio): 投影的宽度 / 高度。

根据图形，可推出以下结论：tan(fovY / 2) = t / |n|, aspect = r / t。

光栅：屏幕！！！

光栅化：在屏幕上绘制出图形即为光栅化。

视口变换：将一块[-1,1]的几何图形转换为 [0,width] x [0,height] ，具体操作如下：
$\bigl($

\begin{matrix} x p \\ y p \\ z p \\ 1 \end{matrix}

\bigr)

(x p y p z p 1)

= M(viewport)

\begin{matrix} x \\ y \\ z \\ 1 \end{matrix}

, M(viewport) =

\begin{matrix} w i d t h / 2 & 0 & 0 & w i d t h / 2 \\ 0 & h e i g h t / 2 & 0 & h e i g h t / 2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}

光栅化的步骤：

1.遍历整个屏幕，对每个像素点中心进行采样，判断其是否在图形内部。
2.可以通过至少三种方法判断中心点是否在图形内：

– a.目标点与三角形三条向量叉乘判断是否都同向。

– b.过目标点作射线判断是否仅有一个交点。

– c.连接三个顶点，所形成的三角形面积和为整个三角形。
3.对存在采样覆盖的像素进行绘制即可。

3.2. 采样瑕疵

Jaggies:抗锯齿，空间采样缺欠。
Moire: 采样缺欠造成的。
Wagon wheel effect: 轮盘效应，时间采样跟不上。

造成以上现象的原因是：

信号频率过高，而采样速率过慢以至于跟不上信号的变化。

如何降低走样率：

1.增加采样率：切换分辨率高的物理设备（硬件层面）。
2.过滤掉高频信号(模糊化处理)后再采样。
– 使用低通滤波器对一块像素点进行卷积操作(收集周围的像素块进行平均化处理)。

– 即根据像素点被占用比例去生成颜色的深浅填入像素块。
3.MSAA:将一块分辨率细分为N x N个小的点，查看每个小点是否被图形覆盖，假设有m个点被覆盖，占比就是m/NxN。(通过增大计算量提高检测覆盖的精度)
4.FXAA：快速近似抗锯齿：图像后处理，使用没有锯齿的图像覆盖原来图像。
5.TAA：时序抗锯齿：相邻两帧的复用，变换够快即可，动态模糊。

四. Shading着色

4.1. 深度缓存算法 Z-Buffer

在光栅化的过程中通过GPU并行运算：

1.初始化zbuffer[x,y] -> ∞
2.进行以下算法：（最小值算法）

for (each Triangle T)
    for (each sample (x,y,z) in T)
        if (z < zbuffer[x,y])
        {
            frameBuffer[x,y] = rgb;
            zbuffer[x,y] = z;
        }
1
2
3
4
5
6
7

4.2. 着色 Shading

定义：给一个物体配置材质的过程叫做着色。

高光: 一个物体上最亮的部分。

漫反射：明暗的交界处变化不是很明显的区域。

环境光照: 间接光照，通过多次漫反射照射到的区域，一般较暗。

Blinn-Phong反射模型

漫反射Diffuse：

光通量：通过着色点的能量多少(沿着色点法线方向射入的光线数量)

在漫反射中，cos θ = I * n, I 着色点指向光源的向量，n是垂直于着色点表面的向量。θ为l和n的夹角。

最终光线表达式: Ld = kd(I / r²) max (0, n*I)，
kd是漫反射系数，与着色面参数有关(颜色，光感等等)，r是着色点距离点光源的距离。I / r² 指有多少光到达了着色点。加上角度即为着色点吸收了多少能量。

镜面反射方案Specularly：

表达式: Ls = ks(I/r²)max(0, n*h)^p

ks指镜面反射系数，h为半程向量，算法为：h = (v + l).normalized，光照方向与视野方向的向量和做归一化。p用来控制高光的大小，一般会取 100数量级左右。

环境光Ambient：

环境光不关心其从哪射出，也不关心距离，仅在计算光照时最后加上这一项即可。

表达式：La = kaIa

Blinn-Phong光照模型：

L = La + Ld + Ls = kaIa + kd(I/r²)max(0,nI) + ks(I/r²)max(0,nh)^p

Shading Mode着色类型

Flat Shading:
通过三角形法线对几何体面上的 每个三角面片 进行着色操作。
Gouraud Shading:
通过三角面片的 每个顶点 的法线方向进行着色，并通过插值运算对三角形内部进行着色。
Phong Shading:
通过三角面片上的 每个像素 进行着色。

4.3. 图形渲染管线 Graphics Pipeline

Shader 着色器：

1. Shader语言编程是运行在硬件上的语言，其对每个渲染单元是通用的。
1. 其通常用来描述对单个顶点 / 片元的操作。

4.4. 纹理映射 Texture Mapping

uv纹理贴图介绍：

1. 每个模型表面都是2D纹理组成的。该2D纹理平铺在坐标系中被叫做uv。uv的取值被规定在[0,1]之间。
1. 将uv纹理的三角形顶点与模型中的顶点一一映射，并通过重心插值运算计算三角形内所有点的图像信息。

4.5. 纹理放大 Texture Magnification

重心坐标：

定义：已知三角形三个顶点A B C, 存在一个点P(x,y)满足 P = αA + βB + γC, α + β + γ = 1时，我们称P点为三角形的重心。
如何快速求解重心参数(奔驰定理)：
分别连接 AP，BP,CP，PBC组成的三角形面积为SA，同理得出SB,SC，则：

α = SA / (SA + SB + SC), β = SB / (SA + SB + SC), γ = SC / (SA + SB + SC)

纹理放大：

当放大后纹理信息不足以支撑显示时，需要对其进行纹理放大，为了处理放大的模糊情况，我们可以采用以下方法进行修复：

线性插值:

表达式： lerp(x, v0, v1) = v0 + x(v1 - v0)

双线性插值 Bilinear:

取其中四个像素块，基于以上线性插值表达式，依次进行二次水平插值与竖直插值即可。
案例：
存在四个像素块u01,u11,u00,u10，对其进行以下操作：

//两次水平插值,s为目标点到 u00 点的水平距离
u0 = lerp(s, u00, u10)
u1 = lerp(s, u01, u11)

//一次竖直插值，t为目标点到 u00 点的竖直距离
(x,y) = lerp(t, u0, u1)
1
2
3
4
5
6

双三次插值 Bicubic:

取其中16个像素块，依次进行线性插值即可。

4.6. 基于Mipmap的范围查询

作用：允许 快速地，近似的，正方形的 范围查询(Range Query)

对于一个宫殿模型来讲：

1.近处的像素单元覆盖的纹理较大，需要许多像素点渲染。远处的像素单元覆盖纹理较小，可能一块像素渲染很多纹理信息，变化是高频的。

Mipmap详解：

1. 当我们拿到一张 r * r(r % 2 == 0) 分辨率的贴图，我们将其本身视为 Level_0 的纹理。
1. 由此可以生成很多分别率为 r / (2 * n) * r / (2 * n) (n = 1,2,3…)的 Level_n 的纹理，直到r / (2 * n) = 1为止。
1. 额外存储量为：1 + 1 / 4 + 1 / 16 + … = 4 / 3 - 1 = 1 / 3。
1. 通过像素点单元距离映射可计算出uv贴图中对应的距离L，L = max(√[(du/dx)² + (dv / dx)²], √[(du/dy)² + (dv/dy)²])，再通过 D = log~2 L计算出 Mipmap层数D。
1. 直接通过层数D去 Mipmap中查询当前区域的颜色平均值。
1. 为了使其层数过度更加平滑，使用三线性插值运算优化表现：
  
  – a.先在Mipmap层中通过距离目标点的距离进行双线性插值
  
  – b.再在Mipmap的两层之间进行线性插值(例子：即得出第1.8层的信息)，使其可视化场景线性平滑过渡。

Mipmap的存储空间是相比原来额外的 1/3！

Mipmap仅仅使用了查询与多次插值运算就实现了屏幕的范围快速查找，但它还有以下缺陷：

1. 局限于立方形区域。
2.对于特别远处的区域会过度模糊(Mipmap层数过高)

通过各向异性过滤可以将局限形状扩展为矩形。（相比Mipmap长宽的压缩算法被分开）

4.7. 纹理的应用

纹理的另一种理解： Texture = Memory(存储) + Range Query(范围查询)，本质就是数据。
我们之所以能够看到物体，并且看到物体不同的面，是因为周围有着环境光照，而环境光我们默认其由某一个固定方向的无穷远处射入，但在表达上，我们可以采用球形包围盒，方形包围盒等方式来可视化环境光照，都是为了描述来自不同方向的环境光照。

球形包围盒 Spherical Map:

1. 由于球的半径都相等，球形包围盒可直接利用光射入的角度计算投影位置。
1. 球形包围盒存在一定的问题，类比地球和世界地图平面展开图，在越靠近极点的位置，平面图会出现扭曲。

方形包围盒 Cube Map:

1. 方形包围盒类比游戏引擎中的天空盒 SkyBox,其将一个全景分别投影到立方体的六个面上。很少出现扭曲。
1. 给定一个方向光，根据角度求出光具体射到的位置时，需要额外计算投在哪个面上。

凹凸贴图 Bump Mapping:

1. 通过法线信息表达模型表面的高度或凹凸程度。
1. 法线信息存储相比多边形表达形式更能在低分辨率的情况下存储高分辨率细节。

求某点P法线normal的数学方法：

1. 分别将P点向x,y两个方向移动一个单位，计算出两个切线。
1. 两个切线构成一个平面，将两个切线叉乘即可得到新的法向量。

位移贴图 Displacement Mapping:

1. 实际改变了三角形顶线的位置。
1. 位移贴图的想法是利用一个额外的贴图，称作高度图，它描述了一个表面的凸起和缝隙。换句话说，法线贴图有三个颜色通道来为每个像素产生法线向量 (x, y, z) ，而高度图仅仅由一个颜色通道来为每个像素产生高度值h。

五. Geometry几何

5.1. 几何的隐式表示和显式表示

Implicit(隐式):

1. 基于被归纳的特征点，这些点常常满足某种关系，比如：x² + y² + z² = 1。
1. 对于隐式表示来说，很容易判定某点是否在某几何体内 / 外。
1. 对于隐式表示来说，很困难表达几何体上所有的具体点。

具体实例：

1. 通过算术表达，比如上述球体表达式。
1. 根据基础几何体与基础布尔运算作 ∩，∪ 运算。
1. 距离函数表达，空间中任意一点到几何体中某点的最小距离。SDF(Signed Distance Function)有向距离函数。SDF(d1) blend SDF(d2)。
1. 水平集Level Set Methods，类比地理等高线，将一个平面中某值的点通过平滑曲线连接（双线性插值）。
1. 分形 Fractals，套娃式几何结构，渲染很困难。

Explicit(显式):

1. 存在一个二维uv贴图与三维几何的映射关系，我们可以通过某种对应关系相互转换。
1. 对于显式表示来说，很容易表达几何体上所有具体点（参数映射）。
1. 对于显式表示来说，很困难表达某点与几何体的位置关系。

具体实例：

1. 点云 Point Cloud。
1. 多边形网格 Polygon Mesh，适应性采样，更复杂的数据结构。

5.2. 曲线 Curve

obj文件数据信息：

# 空间中的8个点
v vx vy vz # 1
v vx vy vz # 2
v vx vy vz # 3
...

# 纹理坐标
vt vu vv # 1
...

# 几何体的六个法向量
vn vnx vny vnz # 1
vn vnx vny vnz # 2
...

# 表面映射关系[(顶点索引，纹理坐标，法线)]
f 5/1/1 1/2/1 4/3/1 # 以v5,v1,v4三顶点构成的面，同理规定纹理坐标和法向量
f ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

贝塞尔曲线 Bezier Curve:

一种显示存储的曲线。

定义:
空间中存在四个点 p0,p1,p2,p3，要求一条曲线必须过起点和终点 p0和p3，并且在这两点的切线必须满足 t0 = 3(p1-p0)， t1 = 3(p3 - p2)。

De Casteljau求贝塞尔曲线的算法

1. 对于n个规定的空间中的点，分别连接相邻的两点，形成p0p1,p1p2,p2p3三条线。
1. 取 t ∈ (0,1)，分别取上述三条线上比例为t的位置点，连接所成的n - 1个点。
1. 重复2的操作，直到最后仅得到一个点。
1. 最后在起点，终点与3得到的点作平滑曲线即可得到贝塞尔曲线。

总结：其实该算法也是用了线性插值和递归的思想归纳出曲线必过的某点。

数学推导:

对于3点两段的贝塞尔模型来说：

b0^1(t) = (1 - t)b0 + tb1
b1^1(t) = (1 - t)b1 + tb2
b0^2(t) = (1 - t)b0^1(t) + tb1^1(t) = (1 - t)²b0 + 2t(1 - t)b1 + t²b2
1
2
3

推广到通用高阶贝塞尔曲线：

b0^n(t) = Σ ~ (j = 0) ^ (n) bjBj^n(t)

Bi^n(t) = $\bigl($

\begin{matrix} n \\ i \end{matrix}

\bigr)

(n i)

t^(i)(1-t)(n-i)

三维贝塞尔曲线同样适合以上定律。

性质:

1. 起点，终点肯定在曲线上。
1. 起点和终点的切线分别为：b’(0) = 3(b1 - b0), b’(1) = 3(b3 - b2)。
1. 目前仅限于仿射变换。
1. 曲线肯定在控制点所形成的最小多边形(凸包)内。

逐段贝塞尔曲线 Piecewise Bezier Curves:

分段贝塞尔曲线需要处理的问题之一：

如何控制每一段连接过渡平滑，由此引申出下述不同的曲线连续：

C0 continuity: an = b0
C1 continuity: an = b0 = 1/2(a(n - 1) + b1) ，左右切线方向和大小均相等
C2 continuity: 不作详解。

更多类型的曲线 Splines样条

Spline 样条。

B-Splines B样条。

5.3. 曲面 Serface

贝塞尔曲面的计算方法
：

1. 基于贝塞尔曲线的计算逻辑，取坐标系的两个方向，定义采样点(动点)u画出贝塞尔曲线。
1. 重复若干次上述操作，画出n条在该平面方向上的贝塞尔曲线。
1. 定义第二个采样点 v 分别以 u 所在的位置作为控制点计算坐标系第三个方向上的贝塞尔曲线。
1. 最后得出的空间中的贝塞尔曲线交织即为贝塞尔曲面。

5.4. 网格操作 Mesh Operation

网格细分 Mesh Subdivision

三角形网格细分的基础操作:

1. 创建更多的三角面片(顶点)
1. 调优他们的位置。

Loop Subdivision:

将一个三角面片平均分为四个小的三角面片，然后根据 距离权重 分配新的顶点位置。但新形成的顶点与本就存在的顶点更新方式不同。
对于新的顶点来说：Vertex = 3/8 (A + B) + 1/8 (C + D)。
对于旧的顶点来说：(1 - n*u) * origin_position + u * neighbor_position_sum, n是顶点的度(连接着几条边), u = { 3/16,n = 3 ; 3 / 8n , otherwise}。
局限性是:仅可以用作三角面片。

Catmull-Clark Subdivision:

Non-quad: 非四边形面， Extraordinary Vertex 奇异点：度degree != 4。
在每一次细分操作中：在每一个面内增加一个点，在每一条边上加一个中点，连接所有的顶点。
可以用于任意边数的多边形。

网格简化 Mesh Simplification

边坍缩

网格重构 Mesh Regularization

六. 光线追踪 Ray Tracing

6.1. 阴影映射 Shadow Mapping

一种仅能处理点光源形成阴影的方法。
Key：不在阴影中的点必须满足两个条件：

1. 能被摄像机(人眼)所看到的区域。
1. 能被点光源看到的区域。

处理步骤：

1. 从点光源位置看向场景(仿光栅化)，记录各位置的渲染深度 Depth存入Shadow Mapping。
1. 从相机看向场景某点，投影回光源方向，判断该深度与之前记录深度是否相同。
1. 如果2中判断相等，则无阴影，反之，则存在阴影。

存在的问题：

1. 浮点类型深度比较的误差问题。
1. Shadow Mapping模拟光栅化分辨率不好确定。
1. 阴影过度不平滑，我们以下引入软阴影。

软阴影：

6.2. 光线追踪介绍

光线追踪与光栅化：

1. 光栅化实时生成效率较高，但准确度差。
1. 光线追踪精确，但生成效率低，适合离线。

关于光线：

1. 光沿直线传播（实际有波动性）。
1. 光线之间不会发生碰撞。
1. 光线由光源发出经过反射折射等过程传入人眼。
1. 光是可逆的，光路可逆性。

6.3. Recursive(Whitted-Style) Ray Tracing

初步理解：

1. 光线从人眼出发，经过屏幕某像素点处沿直线传播。
1. 当遇到遮挡物时，根据其物理参数计算反射与折射光线，不断重复该步骤，会生成许多递归的光线。
1. 将每次光线与遮挡的碰撞点与光源连接，判断该点是否被光源照射到，如果该点有光线照射，回溯地计算该点的着色。
1. 最后将计算结果返回屏幕上，根据结果做出对应的着色渲染即可。

该初步理解仍旧存在许多细节实现的问题，下面我们将依次解决：

光线与物体的交互算法

光线方程与平面法线方程:

r(t) = o + td, 0 <= t < ∞

光线射线方程，t为某一时刻，o为光线射出点，d为光线方向向量。

平面的点法式： (p - pprime) * N = 0，N是平面的法向量。

光线与物体的交互基础算法:

我们知道一个物体的表面是由许多三角面片组成的，那么我们需要判断光线是否穿过物体即需要判断光线是否穿过物体上的每一个三角形。为了这一目标，我们可以转换思维：

首先，三角形是在一个平面里的。
其次，我们可以判断平面与光线是否存在交点。
最后，我们只需要检测上述交点是否在三角面片内即可。

交互的加速算法:

在大型游戏实际游戏场景中，由成千上万游戏物体，我们如果要计算光线与所有物体的所有三角形的交点，性能极低，于是我们需要使用一些算法来优化该过程：

包围盒Bounding Box

在3维几何中能够完全包裹住几何物体的立方体小盒。特殊的可以使用 Axis-Aligned BoundingBox(轴对齐包围盒)。
根据AABB包围盒我们可以得知：

在2D中，判断光线是否进入平面需要判断在X,Y两个维度都满足光线进入了对面，并且暂时都没有射出平面的部分。
在3D中同理，我们可以推断以下结论：
以3D包围盒为例，我们计算光线进入的时间t只需要关注三个维度时间最大的进入点，同理，出的时间只需要关注三个维度时间最小的出点。即 t(enter) = max{tx,ty,tz} 与t(exit) = min{tx,ty,tz}。

以上思维会出现几个疑问：

1. 光线是射线而不是直线。
1. 当t(exit) < 0时，代表盒子在光线后面，即没有交点。
1. 当t(exit) >= 0 且 t(enter) < 0，光源在盒子的内部，有交点。

总结下来，当且仅当 t(enter) < t(exit) && t(exit) >= 0时，光线才和盒子存在交点。
普通的包围盒：

解方程解出交点： t = [(pprime - o) · N] / (d · N)
轴对齐包围盒：

解方程解出单个维度的交点： t = [pxprime - ox] / dx

加速结构 Accelerate

空间划分：

八叉树(四叉树) Oct-Tree ,K维的二叉树 KD-Tree，二叉空间分区树 BSP-Tree

KD Tree设计思路：

空间维度的划分

数据结构:

划分轴，x，y，z轴？
划分位置，不一定是正中间，根据实际情况
数据结点都被存储在叶子结点中，不会存在中间结点中。

存在的问题:

1. 如果空间划分不合理在树的叶子节点中会重复计算包围盒中的三角形，导致性能的大幅度浪费。
1. KDTree的建立并不简单，同样要考虑与三角形的求交。

Bounding Volume Hierarchy(BVH)

物体维度上的划分

在KD Tree的空间分块基础上，采用BVH划分物体的思想（完全不考虑空间上的覆盖关系），可以避开KD Tree重复计算三角形的问题。

BVH的大致步骤：

1.找到总的包围盒，通过递归地对物体进行二分(划分方法随意).
2.再计算子物体的包围盒，必要时停止。
3.存储每一个叶子节点中的对象。

如何高效的划分物体：

1. 选择多种不同的划分维度(x,y,z…)。
1. 通常可以选择节点中最长的轴并且始终划分物体维度的中点(保证划分两边的三角形数量近似)

BVH的数据结构与算法:

DataStruct:

内部结点存储包围盒和子结点，子结点指针。
叶子节点存储包围盒和物体列表。

Algorithm:

伪代码：

Intersect(Ray ray, BVH node)
{
    if (ray misses node.boundingbox) return;
    
    if (node is a leaf node)
    {
        test intersection with all objs;
        return closest intersection
    }
    
    hit1 = Interaction(ray, node.child1);
    hit2 = Interaction(ray, node.child2);
    
    return the closer of hit1,hit2;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.4. 辐射度量学 Radiometry

核心物理量描述

核心问题：如何描述光照？

Radiant flux: 辐射通量
Irradiance: 辐照度
Radiance: 辐亮度

以及以下物理量的介绍：

Radiant Energy:

定义: 理解为能量，单位是焦耳(J)，表示为Q。

Radiant Flux:

定义: 单位时间的能量(功率), 单位是瓦特(W) | 刘明(lm)，表示为 Φ = dQ / dt
Radiant Intensity

定义: 单位立体角的能量，单位是坎德拉(cd), 表示为 I(ω) = dΦ / dω

Solid Angles 立体角:

要了解立体角，我们要先了解2维平面中的弧度制：

θ = l / r, l是θ角对应的一段弧，r是圆的半径。

根据二维推出三维空间中，立体角中：

Ω = A / r², A是Ω角对应的弧面面积，r是圆的半径。

[在均匀点光源中，Intensity和方向无关。I = Φ / 4Π ]

经过推导，立体角的相比天顶角 θ 和方位角 Φ 的变化公式为：

dω = dA / r² = sinθ dθ dΦ

Irradiance 辐照度

定义: 单位面积上对应的能量，单位是 W / m² = lm / m² = lux 。

公式: E(x) = dΦ(x) / dA

对点光源模型来说，Intensity是不变的，而Irradiance是变化的。

Intensity : 辐射通量 / 立体角，距离越远立体角和辐射通量都会增大，整体表示为不变。
Irradiance: 能量功率 / 面积，功率是发光体固有属性，保持不变，而照射面积随距离会变化。

Radiance 辐亮度

定义: 单位立体角，单位照射面积下的功率，单位是 lm / srm² = cd / m² = nit。

从理解方面上想，Radiance即为Irradiance从某个方向射入的能量。

BRDF

Bidirectional Reflectance Distribution Function(BRDF): 中文名为 双向反射分布函数

引入概念的目的：

已知入射光能量和角度，射到物体表面会向多个方向辐射，辐射出去的能量跟角度不一样，求得给定方向辐射的能量是多少。

【总结下来：BRDF就是某一单位面积吸收能量后往某个方向反射出去的比例(能量分布)公式。】

物理意义：

物体表面和光线是如何作用的。

公式：

Lr = ∫H² fr Li(p,ωi)cosθi dωi， fr是BRDF的比例，后面是这块面积接收到的纬度相同的入射光的能量,H²是指描述光线传播的半球模型。

The Rendering Equation 渲染方程

Reflection Equation

首先从反射方程角度入手：

Lr(x,ωr) = Le(x,ωr) + Li(x,ωi)f(x,ωi,ωr)(ωi,n),x是目标点，ωi是入射角，ωr是出射角

对于单个点光源模型来说，反射光应为自己的光(右边第一项) + 入射光(光源) * BRDF比例 * 入射光夹角

对多个点光源来说，只需要再上述公式基础上做累加：

Lr(x,ωr) = Le(x,ωr) + ∑Li(x,ωi)f(x,ωi,ωr)(ωi,n)

而对于面光源来说，可以将其看作多个点光源集合，上述式子变为：

Lr(x,ωr) = Le(x,ωr) + ∫Ω Li(x,ωi)f(x,ωi,ωr)cosθi dωi

由于某点真实光照是由一次直接光照(自身发光)和若干次间接光照求和产生的效果，我们可以将渲染方程简化为：

l(u) = e(u) + ∫l(v) K(u,v)dv还可以简化为↓
L = E + KL，该方程是一个递归方程，求解出L为：

L = E + KE + K²E + …,由此我们引入全局光照 概念：
全局光照：某光源经过N次弹射后最终产生的效果。

6.5 蒙特卡洛积分方程

概率论提要:

所需知识： PDF(Probability Density Functions) 概率密度分布方程。

p(x)满足条件：p(x) >= 0 and ∫p(x)dx = 1

X的数学期望：E[X] = ∫ xp(x) dx

Monte Carlo Intergration:

基础蒙特卡洛积分方程：
FN = (b - a) / N Σ(1->N) f(Xi)

蒙特卡洛积分方程：
∫f(x) dx = 1 / N Σ(1->N) f(Xi) / p(Xi)

基于以上方程，可以得知下述性质：

采样点N越多，误差越小

6.6 Path Tracing 路径追踪

复习 Whitted-style ray tracing:

1. 总是执行镜面反射 / 折射
1. 直到弹射到光滑平面停止
1. 局限：黑暗的面未计算反射现象，存在仅考虑直接光照的情况

使用 Monte Carlo积分方程解渲染方程：

得到 Lo(p, ω) ≈ 1 / N Σ(1->N) Li(p,ωi)fr(p,ωi,ωo)(n·ωi) / pdf(ωi)

即得到一个渲染算法：shade(p,ωo) ↓↓↓

//仅考虑直接光照的情况
shade(p, ωo) - p是采样点坐标，ωo是入射方向
    //随机在PDF中选择N个方向ωi
    Lo = 0.0
    foreach ωi
        Trace a ray r(p,ωi) //跟踪射线
        if ray hit the light  //如果射线达到了光源
            Lo += (1 / N) * Li * fr * cos / pdf(ωi) //效果叠加
   return Lo;
1
2
3
4
5
6
7
8
9

算法改进：

shade(p, ωo) - p是采样点坐标，ωo是入射方向
    //随机在PDF中选择N个方向ωi
    Lo = 0.0
    foreach ωi
        Trace a ray r(p,ωi) //跟踪射线
        if ray hit the light  //如果射线达到了光源
            Lo += (1 / N) * Li * fr * cos / pdf(ωi) //效果叠加
        else if ray hit an object at Q
            Lo += (1 / N) * shade(q,-ωi) * fr * cos / pdf(ωi)
   return Lo;
1
2
3
4
5
6
7
8
9
10

根据以上改进，我们发现当射入100跟光线时，后续递归深度2层以上即会造成计算量爆炸，所以我们使用蒙氏进行路径追踪时，仅考虑一条光线射入。

改进：

    shade(p, ωo) - p是采样点坐标，ωo是入射方向
        //随机在PDF中选择1个方向ωi
        Trace a ray r(p,ωi) //跟踪射线
        if ray hit the light  //如果射线达到了光源
            return (1 / N) * Li * fr * cos / pdf(ωi) //效果叠加
        else if ray hit an object at Q
            return (1 / N) * shade(q,-ωi) * fr * cos / pdf(ωi)
1
2
3
4
5
6
7

我们再引入如果尽可能还原现实中光线是无限次弹射的，使用俄罗斯轮盘赌思维改进算法：
离散型随机变量数学期望： E = P * (Lo / P) + (1 - P)*0 = Lo

shade(p,ωo)
    //规定一个概率值
    P_RR = ？
    ksi = Random.Range(0,1)
    if (ksi > P_RR) return 0.0
    
    Trace a ray r(p,ωi) //跟踪射线
        if ray hit the light  //如果射线达到了光源
            return (1 / N) * Li * fr * cos / pdf(ωi) / P_RR
        else if ray hit an object at Q
            return (1 / N) * shade(q,-ωi) * fr * cos / pdf(ωi) / P_RR
1
2
3
4
5
6
7
8
9
10
11

这种算法已经没问题了，但效率方面较低。对于面积较小的光源来讲，光线打到光源的概率几乎为0，我们需要采用直接再光源采样去优化算法。

相关阅读:
分布式锁redisson
Python机器学习016：pytorch张量与数据类型
Python3《机器学习实战》学习笔记（四）：朴素贝叶斯实战篇之新浪新闻分类
动态内存管理(malloc free calloc realloc)
python链表_递归求和_递归求最大小值
【双链表增删查改接口的实现】
Spring-AOP
以前编写好能够正常运行的 SAP UI5 代码，几个月后忽然不能运行了该怎么办？
计算机毕业设计-长途汽车售票系统SSM+JSP【代码讲解+安装调试+文档指导】
【信号处理】Matlab实现语音变速变调

原文地址：https://blog.csdn.net/qq_55071342/article/details/130843123

【Games101】-＞ 计算机图形学