清华MOOC图形学基础：理论

这个部分是在寒假学习图形学过程中自己整理的图形学知识，后续会进行精简和删改，也方便自己后续查找概念。

色彩模型

色彩视觉（Color Model）

1. 色彩：对不同波长的光的能量感知：不同波长对于不同颜色，人可见光为380-760nm之间。

2. 光的谱分布：光在各个可见波长的分量的强度分布函数称为光的谱分布函数。与光类似，色彩也可以使用谱分布函数描述，但是由于异谱同色现象，导致描述方法特别复杂且不能一一对应。

3. 色彩颜色空间：在所有用于表示色彩的各种颜色空间，以RGB色彩空间最为广泛$存疑$：

   1. 色彩使用三通道的RGB向量表示；

   2. 在RGB色彩空间中，有部分的常用操作可以通过对RGB三通道分别处理而进行；

   3. r,g,b可以用规格化的的float；而使用8bit存储时，取值为[0,255]；

   4. 色彩被表示为三个基本颜色的线性组合（部分的颜色无法表示为正线性组合，$0,0,0$为黑，$1,1,1$为白）：
      $$C=rR+gG+bB$$

4. 其他的颜色空间：

   1. CMY. 青+品红+黄（注意这里和印刷所用的CMYK不一样，K为黑色，这里是颜色空间而不是印刷色彩模式）。其为减色系统，[C,M,T]=[1,1,1]-[R,G,B]，即CMY分别为R,G,B的补色：$0,0,0$为白，$1,1,1$为黑。

   2. HSV. 其为圆锥形的色彩空间，含义如下：

      1. Hue（色调/色相）指的是什么颜色；
      2. Saturation（饱和度/纯度）值越低，颜色越白；
      3. Value of brightness（亮度）——越低越黑。

   3. CIE XYZ-1931：可以感知所有的色彩，色彩基XYZ是色彩基RGB的线性变换。
      $$x=\frac X{(X+Y+Z)},y=\frac Y{(X+Y+Z)},z=1-x-y$$

图像和像素

1. 图像：二维离散函数$f(x,y)$，$f$的定义域为矩阵中的所有格子；
2. 这些格子称之为像素，其值为各个像素的色彩，彩色图像可为$RGB(A)$，而灰度图像的$f$则为单值。

图形学的基本目标

从虚拟的三位场景以及相机的位置信息中生成二维图像——简单图形直接使用参数描述，而复杂模型需要使用参数曲线和曲面或者更一般的网格模型，而网格模型中又以三角网格最为常用

1. 三角网格：由一系列欧式空间中的三维顶点以及连接这些顶点的若干三角面片组成。其中顶点集合记为$V$，面片集合记为$F$。F中的每个$f_i$为$V$中的$V_ai，V_bi，V_ci$顶点构成的空间三角形。

2. 法向量：垂直于平面的直线所表示的向量为该平面的法向量，若朝外为+，朝外为-。对于连续可定向的额三角网格整体而言，相邻三角面片需要具备一致的法向量朝向；

3. 计算法向量的方法：通过三角网格周围的所有三角面片的法向量加权叠加计算（算数平均，面积加权，角度加权等）。

4. 简单绘制方法：每个顶点指定一个色彩属性：

   1. 基于色彩绘制——模型表面的每点的色彩通过其所在三角面片的顶点色彩插值得到（插值可以用来使模型变得更光滑）；
   2. 基于光照绘制——需要指定一个虚拟的光照环境，重点问题是计算光照对色彩的影响。

光照模型（illumination Model）

光照模型用于计算光的强度，其大致分为

1. 局部光照明——物体直接受到光源影响产生的光照效果；
2. 全局光照明——阴影效果和所有不是直接与光源位置相关的光照效果（反射折射等）。

历史

在渲染中加入光照明效果：

1967年：光强与物体到光源距离成反比；

1970年：第一个光反射模型——Lambert漫反射光+环境光；

1971年：漫反射模型+插值的思想（Lambert diffuse + Bicentric interpolation）；

至今：Phong 模型——Diffuse（漫反射）+ ambient（环境光）+ specular（高光）（顶点法向插值）

光的传播​

1. 反射定律：

   1. 入射角=反射角入射光线；
   2. 反射光线，反射面的法向量位于同一平面。

2. 折射定律：
   $$\frac {sin{入射角}}{sin{折射角}}=c（c为相对折射系数，记为\frac {n_折}{n_入}）$$

3. 能量守恒定律
   $$I_i=I_d+I_s+I_t+I_v$$
   公式依次为入射光，漫反射光（diffuse），镜面反射光（specular），折射光（refraction）以及介质和物体吸收的能量

4. 光的度量：

   1. 立体角：衡量物体相对于某一视点$P$的视角大小，最大为$4π$；
   2. 光通量（辉度）：单位时间间内通过面元$dS$的光能量，记为$dF$（或$E$）；
   3. 发光强度——单位立体角内的光通量，记为$I$。

5. Phong模型：支持点光源和方向光源，是局部光照模型分解为漫反射光，镜面光和环境光效果的合成。（插入的图片暂时略）具体见下列图片：其中$L$是入射光，$R$是反射光，$V$是视点方向，$N$为物体表面的法向量，$H$是$L$和$V$夹角的角平分线

   1. 漫反射光效果：
      $$I_d=I_iK_dL_N$$
      其中$K_d$：是漫反射系数，分别由$k_{dr}$，$k_{dg}$，$k_{db}$代表R，G，B三个通道的漫反射系数，其与模型自身的色彩紧密相关。

   2. 镜面光效果：
      $$I_s=I_iK_s*(RV)^n$$
      其中：$K_s$是镜面反射系数，与物体表面的光滑程度相关，$n$是反射指数，$n$越大，高光区越集中。

   3. 环境光效果：
      $$I_a=I_iK_a$$
      其中：$K_a$是物体对环境光的反射系数。

   4. 故视角方向的发光强度为漫反射光分量、镜面反射光分量和环境反射光分量之和即：
      $$I= I_iK_dL_N+ I_iK_s*(RV)^n+I_iK_a$$

明暗处理（Shading）

Shading方法

由于物体表面的集合细节往往不规则，为了减缓由模型离散化导致的不光滑的色彩效果而导致的Mach Band效应（一种主观的边缘对比效应：当观察两块亮度不同的区域时，边界处亮度对比加强，使轮廓/边界表现得特别明显）。并且通常除了需要使用光照模型外，还需要使用插值的方法。

1. 一般的处理方式：

   1. Flat shading ：逐面片着色的方式，每个多边形都会被指定一个单一且没有变化的颜色（由于十分不真实，因此仅仅是拿来preview使用）；
   2. Gouraud shading：对所有顶点进行着色的方式，则三角面片上顶点的色彩值按重心坐标（Barycentric Interpolation）结果赋值;
   3. Phong shading：逐像素着色（或者说逐片元fragment）的方式，每个像素的法向量是通过顶点的法向量插值得到的。

2. 重心坐标：重心坐标是由单形顶点定义的坐标，是齐次坐标的一种。平面上的重心坐标可以如下方式表示：
   $$p=\lambda_1 t_1+\lambda_2 t_2+\lambda_3 t_3, \lambda_1+\lambda_2+\lambda_3=1$$
   其中，$t_1,t_2,t_3$分别表示他们的向径，则重心坐标为$(\lambda_1,\lambda_2,\lambda_3)$。

3. 视点变换和视点方向：由几何模型组成的三维场景绘制成高质量的彩色图——通过变换将空间中的点$x$映射为点$x’$的函数。通过变换，可以设置和编辑3D场景光照位置和视点方向（camera）。

4. 简单变换：平移，旋转，均衡缩放（translation，rotate，scale）。

5. 常见变换有：

   1. 刚体变换：保持物质本身的度量变换；
   2. 相似变换：保持角度的变换；
   3. 线性变换：保持线性关系$\vec l+\vec p$，$k\vec l$的变换;
   4. 仿射变换：保持直线即相互平行的直线的变换。

6. 投影变换的表示：M和$\vec t$：$\vec {p’}=$M$\vec p+\vec t$（M为二维矩阵），若使用齐次坐标：则$\vec {p’}=$M$\vec p$(由于渲染插件原因M表示的是矩阵）。

7. 复合变换一般不能交换顺序。

8. 在法向量（与曲面正交的单位向量）交换中，我们要通过变换切平面，再计算法向量。$\vec {v_{OS}}$变换为$\vec {v_{WS}}$，则$\vec {v_{WS}}=$M$\vec{v_{OS}}$，转换为切平面后为$\vec {v_{WS}}=（M^{-1}）^{T}\vec {v_{OS}}$，即法向量的变换矩阵是原变换矩阵的逆的转置。

9. 视点和投影模式.

   1. 视点变换与camera位置及朝向有关；
   2. 投影模式，3D变换为2D，常用正交投影（直接把第三维变0）和透视投影（使用透视投影矩阵）。

材质反射属性模型——双向反射分布函数（BRDF：Bidirectional Reflectance Distribution Function）

BRDF是描述物体表面对光的反射性质。

基础知识

1. 光照/照明（illumination）：分为局部光照和全局光照（见光的传播的Phong模型中的叙述）；

2. 球面坐标：利用球坐标$(r,\theta,\phi)$表示一个点 $p$ 在三维空间的位置的三维正交坐标系。球坐标的几何意义：原点到 $p$点的距离 $r$ ，原点到点 $p$ 的连线与正 z-轴之间的天顶角$\theta$以及原点到点$p$的连线，在$xy$平面的投影线，与正轴之间的方位角$\phi$；

3. 立体角：见前文；

4. 投影面积：$A’=Acosa$

5. 光能：光子能量总和；

6. 光通量：和磁通量类似；

7. 辉度E（见P1）：单位面积上的光通量；

8. 光强：单位立体角的光通量；

9. 光亮度：单位投影面积和单位立体角上的光通量；

10. 辉度和光亮度的关系：$E=\int_\Omega{L({\omega}){cos{\theta}} d{\omega}}$。其中$\Omega$是入射角形成的半球（Hemisphere），而$L({\omega})$是沿着$\omega$方向的光亮度。

BRDF

1. 定义：描述物体表面将光能从任意入射方向反射到任意视点方向的反射特性，是关于入射光方向和反射光方向的四维实函数，其等于反射方向的光亮度和沿入射方向的入射光辉度之比（或入射光的光亮度）：
   $$f({\omega}_i-{\omega}_r)=\frac {d{L_r}({\omega}_r)}{d{E_i}}=\frac {d{L_r}({\omega}_r)}{L_i(\omega_i)cos\omega_id{\omega}_i}$$

2. 性质：

   1. 可逆性：由于光路可逆，故$\omega_i$和$\omega_r$不变；

   2. 能量守恒：$Q_{in}=Q_{re}+Q_{ab}+Q_{trans}$，即有：
      $$\int_\Omega{f(\omega_i\rightarrow\omega_r)L(\omega_i)cos\omega_id\omega_i}\leq1$$

3. 用于计算环境光照下的反射光亮度可以写为：
   $$L_r=\int_\Omega{f(\omega_i\rightarrow\omega_r)L(\omega_i)cos\omega_id\omega_i}$$

4. 模型：经验模型，基于物理表达，基于数据表达

   1. 经验模型：
      1. Lambertain漫反射模型是最基本的反射模型：入射光线被均匀地反射到各个方向，不同方向的BRDF是一个常数。反射率是反射光的辉度和入射光的辉度之比；
      2. Phong模型，在Lambert漫反射模型基础上，添加了镜面反射项，以表达镜面反射效果，但是其不具备可逆性，不准确但是简洁高效；
      3. Blinn-Phong模型，引入入射方向和反射方向的角平分线h，使用h和法向量n的点积替代原Phong模型的$\vec r \cdot \vec v$，以简化运算。
   2. 物理模型中：
      1. 建立在表面粗糙度的细节几何结构上，通过微平面法向量的统计分布表达；
      2. 同时在实际应用中，单向反射性存在擦地角附近增大的性质，且入射光的反射光是由麦克斯韦方程组中得到的菲涅尔公式（Fresnel）得到；
      3. Cook-Torrance模型，假设微平面为镜面反射，且假定为V，然后结合Lambertian漫反射项与微平面项结合同时采取Bechmannn分布来描述微平面法向的分布函数。
   3. 数据模型（略）

5. BRDF的动机：为了对未知反射属性的材料进行建模，并生产具有高度真实感的结果，恢复BRDF和其他场景属性的过程称之为逆渲染（inverse rendering）。

6. BRDF的度量和评价：由于BRDF是关于光线和视角的函数，其度量通过对2D光照空间和2D视角空间进行采样获取。故需要sample，source和detector，固定材料、固定光源或固定材料（用于已知凸几何体）和光源而移动其他的方式，

光线追踪

思路和框架：将显示缓存区看成是由空间中的像素组成的矩阵阵列，人眼透过这些像素看到场景中的物体。对于每个像素$P$计算其色彩值：计算视点链接像素$P$中心的光线演唱后所碰到的第一个物体交点，然后使用局部光照模型计算交点处的颜色值，然后沿交点处的反射和折射方向队光线进行跟踪。通过光线跟踪，可以很容易的表现出阴影反射折射之类的视觉效果，且更容易适用于复杂的物体表示方法。

光线求交

1. 光线的表示：
   $$P(t)=R_o+t*R_d$$
   其中${R_O}$是光线的原点，$\vec {R_d}$为向量，代表朝向，一般为单位向量，$t$为光线到达的位置，均为正数。

2. 平面的表示：显式表示为$P$为平面一点和n为平面的法向量，隐式表示为
   $$H(P)=Ax+By+Cz+D=\vec n\cdot P+D=0$$

3. 点到平面的距离：$\vec n$为单位法向量时，$P$到$H$的距离就是$H(P)$；

4. 光线和平面求交：联立 $\vec nP+ D=0$，$P(t)=\vec R_O+tR_d$得到
   $$t=-\frac {D+nR_o}{\vec n \cdot \vec{R_d} }$$
   最后需要验算$t$是否大于0即可。

5. 光线和三角形求交：先验证是否在平面，再验证是否在三角形内，其作用有纹理映射，法向插值，颜色插值。转化为解线性方程组（通过Cramer法则直接求解）。

6. 光线和多边形求交：首先计算光线与多边形所在的平面交点，若交点存在，判断是否在多边形内部——为了进行这一判断，我们将交点以及多边形的所有顶点投影到XY-,YZ-,ZX-平面中一个。

   1. 法一（在不进行预处理的情况下最快）：二维情况下采用交点检测算法，基于Jordan曲线定理：平面上一个点位于一个多边形的内部，当且仅当由该点出发任何一条射线与多边形边界有奇数个交点（奇偶检测算法）。我们可以将检测点作为远点，然后用X轴正半轴作为检测焦点的射线，然后逐一比对（多边形某条边两端点同号则无交点，否则若交点在X正半轴则是交点，反之不是交点）;
   2. 法二（稳定但慢）：计算带符号的角，即转化为带符号的弧长，为0则在外，为2$π$则在内部，若为$π$则在边界;
   3. 法三（最快的方法）：以顶点符号为基础的弧长累加，将坐标原点移到被测点，各象限内点的符号对应标准象限，若顶点$p_I$的某个坐标为0，则记为+，若$x，y$均为0，则顶点为被测点，然后定义符号变化转化为弧长变化，若穿越相对（13或24）象限的时候，为$±π$，通过$f=y_{i+1}x_i-x_{i+1} y_i$若为0则穿过原点，大于0为正，小于零为负，判断点在直线的上方还是下方。

7. 光线和球面相交——代数法（存在误差和计算量）

   1. 通过球面的表示：$f(P)=||P-P_C ||-r=0$，即解决$||P(t)-P_C ||-r=0$的根，解得$t=-b±\sqrt {b^2-c}$；
   2. 优化方法：
      1. 首先计算光源指向球心的向量$\vec l =P_c-R_0$，若$\vec l ^2<r^2$则在球的内部，$\vec l ^2>r^2$则在球的外部，$\vec l ^2=r^2$则在球面上（注意光源在球面上的时候退化情况）；
      2. 然后计算球心到光线所在直线的距离，若$d^2=\vec l ^2-t_p^2，d>r$，则光线与球面不相交。

光线追踪加速

1. 原因：时空复杂度高，主要消耗在于可见性判断和求交测试；

2. 方法：空间数据结构，比如层次包围体，均匀格点，四叉树八叉树空间二分树；

3. 包围盒：（比如把一个兔子包到一个长方体里）

   1. 多种包围方法：比如平行于坐标轴，非平行与坐标盒，OBB；
   2. 判断方法：除非交于长方体，否则不会与兔子相交；
   3. 后续由Kay和Kajiya 提出，根据景物的实际形状选取$n$组不同方向的平行平面包裹一个景物或者一组景物来做为层次包围盒——定义一任意平面方程$Ax+By+Cz-d=0$，则可以得到一个法向量$\vec N$，且与原点距离为$d$的平面，令$d$为自由向量，则定义了一组平面（流形？），故对于任意给定景物，必然存在两平面将景物夹在中间，记为$d_i^{near}$ 和$d_i^{far}$，用几组平面可以构成一个紧致包围盒，取若干统一方向为平面法向，并取n小于5；
   4. 而对于$d_i^{near}$ 和$d_i^{far} ：
      1. 显式曲面我们可以将多面体的所有顶点投影到法向量方向，并计算与原点的最大值最小值；
      2. 隐式曲面体，用条件极值的极大极小值——拉格朗日乘数法。

4. 包围球：一个包围球仅包含两组参数，球心和半径。物体转包围盒不转一般极度理想的包围球比较难，采用$n$个点的近似最优包围球（计算几何相关），一把比理想包围球大5%。方法：遍历所有点找到最大最小的$x/y/z$的三组六个点，然后计算三组距离，选取最大值，然后作为包围球直径，作为算法的初始值；然后遍历所有的点，若当前点在包围球外，则修改直径（以当前在球外的点与球心相连接，反向延长到之前的交点）。

5. 层次包围体：给定场景的所有物体的包围体，可以将这些包围体作为叶子节点，构建一个包围体树-HBV，每个内部节点的所有子孙节点对应的包围体并集。从根节点往下层次遍历，计有$n$个包围盒，则由$n$降维为$logn$。

6. 均匀格点：存到一个三维格点整列，有相交的则记录到一个list。然后用DDDA算法类似，光线与$x$和$y$的交点成规律排布（$\frac {dy}{dx}$不变）。此方法容易建立，但物体分布不均匀可能会浪费资源，因此最好为非均匀空间分布。

7. 四叉/八叉树：

   1. 四叉树为二叉树而为推广，每个节点为正方形，递归的将每个正方形分为四个等大的小正方形，叶子节点面片数足够简单时停止扫描；
   2. 八叉树为四叉树的三维推广，和四叉类似，但是每个节点为立方体，且遍历更复杂，但对非均匀场景更适合；
   3. 八叉树的构建：将场景用一个最小的平行于坐标轴放置的立方体包围，使用自顶向下的递归划分直到边界条件（深度，面片数之类的）前，将节点划分为八个等大的小立方体。注意到可能会有同一面片存储在不同的叶节点，可能会导致效率下降，可以采用将面片分为多个，也可以采用Octree-R方法——通过启发式算法，更为自由的划分面片，从而提速4%-47%。
   4. 节点寻址：指针或者编号（使用该节点的编号加上1到8作为其suffix）。
   5. 光线的遍历，每与八叉树的一个内部节点相交，都有可能与至多四个节点相交，因此需要使用空间八叉树剖分技术。

8. 空间八叉树剖分技术：一个空间非均匀网格剖分算法

   1. 方法：将含有整个场景的空间立方体按三个方向中剖面分割成八个子立方体网格，组织成一棵八叉树，若某一子立方体网格中所含景物面片数大于给定的阈值，则为该子立方体作进一步的剖分，直到面片数目小于阈值；然后利用空间连贯性加速光线追踪。

   2. 八叉树的最大深度：表示空间分割所能达到的层次，称为空间分配率;

   3. 编码方式：计八叉树深度为N，则编码为$q_1q_2…q_iFF…F,（q_i\in[0,7])$的整数序列，$F$为不同于$[0,7]$的符号），则可以通过节点编码方式很容易找到任一点所在网格。

   4. 性质：$P(x,y,z)$为空间一点，则

      1. 坐标为整数表示为
         $$x=i_1i_2…i_nB，y=j_1j_2…j_nB，z=k_1k_2…k_n，i_l,j_l,k_l∈[0,1]，l\in I$$

      2. $P$所在的单位立方格编码为$q_l=i_l+2j_l+4k_l,$ $l$见上面的公式；

      3. $P$位于一编码为$q_1q_2…q_iFF…F$的空间网格内，则网格的前左下角坐标为
         $$x’=i_1 i_2…i_i 0…0$$
         $y,z$则改为对应的$j,k$；

9. 通过八叉树的光线跟踪加速：

   1. 利用性质2求光线起点$P_0$所在的立方网格编码$Q$，然后位于边界上的起点根据光线前进方向$R$辨别光线是否射出场景，如果射出，算法结束。其查找结果为是否匹配成功的$Bool$以及没有匹配的位数$B$；
      1. 若$Q$为$q_1q_2…q_i$，则八叉树中节点含有$q_1q_2…q_iFF…F$时取$True$，$B$则定义为八叉树叶节点表中与$Q$获得最大程度匹配的节点其编码suffix不匹配的位数。
      2. $Bool$决定是否包含面片，$Q$和$B$决定立方体的空间位置和大小。若$Bool$量为$True$，则光线与该立方体中所含三角形面片求交，若交返回交点；若$Bool$为$False$，则继续搜索；
      3. 包含起点且不包含任何景物面片的最大空间网格为$q_1q_2…q_iq_{i+1}FF…F$，$F$为$B-1$个；若求交失败为假，应该跨过当前立方体网格；
      4. 而新的网格前左下角坐标由性质3决定，跨越网格后，先求出当前空间网格上的出口点坐标，重置光线起点，然后让光线和六面求交，且预先计算光线在各个坐标平面上投影线的结局和斜率，快速求解。通过新出发点重复跟踪过程，直至光线射出场景或者求到交点。

10. 空间二叉树（BSP）：一种空间划分结构，起初用于解决图形学中隐藏表面为题，为二分查找树的高维推广，主要有axis-aligned类型和polygon-aligned类型。

    1. polygon-aligned BSP：每次选取一个多边形面片所在的平面，作为空间的划分平面，通常来说，当由多边形组成才是用polygon-aligned BSP。
    2. axis-aligned总是沿着某个坐标轴垂直方向划分平面，且划分平面总是把节点按照空间大小划分为两个相等的子节点（也有部分认为随意划分也可），其大大减少了光线和划分平面间的计算量（33%），建树过程差不多。
    3. 而在过程中，我们可以根据深度进行规则轮换，这样的话是的层次结构的划分更加规则regular。

11. KD树（任意一个BSP都是KD，但是KD不是BSP）：其与BSP区别在于划分平面，KD任意，BSP二分划分。

12. BSD的遍历：第一次调用函数时，$min$和$max$初始化为BSP根节点对应立方体的两个焦点到光线原点的距离。若光线从根节点立方体内部发出，则$min$为负数。BSP遍历一般比八叉快10%。由于BSP总是从终点开始划分，因此也存在面片跨越多个节点导致遍历变慢。而KD树就是为了解决这个问题。

13. 分布式光线跟踪（随机光线跟踪）；光束追踪（线变锥形，首先将初始光束投向可视空间，由近及远监测光束与场景中物体的交，交点处产生新的反射折射光束，也可以使用光束树）；具选择性的光线跟踪结合插值（选择部分，剩余插值）；RPU（可编程光线处理单元）。

补充，由于清华的光栅图形学为自读内容，因此无整理。下一个part主要是几何造型相关。