Games101_9TO16

继续Games101 1-8的内容，从纹理映射开始

纹理映射

三角形内插值：重心坐标

下面提出两个问题：

为什么要做插值
- 因为需要在三角形内得到平滑过渡的一组值
需要插哪些值
- 纹理，颜色，法线等等
如何插值
- 重心坐标（Barycentric Coordinates）

重心坐标

对于一个已知所有顶点的三角形，与该三角形共面的任意一点，都可以表示为这三个顶点的加权和。且满足系数之和等于1。另外，如果三个系数均为非负，则该点位于三角形内部。

则这三个系数组成的坐标为重心坐标。

重心坐标求法

对于三角形内任意一点，我们可以通过连接该点与三角形三个顶点，得到三个三角形，如下图所示：

其中 $A_i$ 表示与角i相对的三角形的面积。那么该点的重心坐标可以通过如下公式结算得到：

\alpha = \frac{A_A}{A_A + A_B + A_C} \\ \beta = \frac{A_B}{A_A + A_B + A_C} \\ \gamma = \frac{A_C}{A_A + A_B + A_C}

因此我们可以得到一个特殊点的重心坐标。即三角形重心的重心坐标。因为三角形重心具有平分三角形面积的性质，故重心的重心坐标为：(1/3,1/3,1/3)

除了使用面积进行计算我们还可以通过如下方式得到更直观的坐标运算来得到重心坐标：

对于上图中三角形内的点(x,y)，我们令其为Ｐ，如果我们把三角形ABC看成坐标系

，A为原点，基为 $\vec{AB}，\vec{AC}$ ，那么对于向量AP我们可以使用如下方式:

$\vec{AP} = u\vec{AB} + b\vec{AC}$

移项得到：

$u\vec{AB} + b\vec{AC} + \vec{PA} = 0$

对于二维三角形，我们可以得到如下形式的式子：

u\vec{AB}_x + v\vec{AC}_x + \vec{PA}_x = 0 \\ u\vec{AB}_y + v\vec{AC}_y + \vec{PA}_y = 0

此外还可以将其写为矩阵形式：

\left( \begin{matrix} u & v & 1 \end{matrix} \right) \left( \begin{matrix} \vec{AB}_x \\ \vec{AC}_x \\ \vec{PA}_x \end{matrix} \right) = 0 \\ \left( \begin{matrix} u & v & 1 \end{matrix} \right) \left( \begin{matrix} \vec{AB}_y \\ \vec{AC}_y \\ \vec{PA}_y \end{matrix} \right) = 0

可见我们需要计算的向量(u,v,1)垂直与上述两个向量，因此可以使用上述两个向量的叉乘得到我们要求的系数。

我们还可以得到如下公式：

\alpha = \frac{-(x-x_B)(y_C - y_B) + (y - y_B)(x_C - x_B)}{-(x_A - x_B)(y_C - y_B) + (y_A - y_B)(x_C - x_B)} \\ \beta = \frac{-(x-x_C)(y_A - y_C) + (y - y_C)(x_A - x_C)}{-(x_B - x_C)(y_A - y_C) + (y_B - y_C)(x_A - x_C)} \\ \gamma = 1 - \alpha - \beta

至此，三角形内部的任意点，都能通过三个点的线性组合来得到该点的位置。

推到：

图形学基础知识：重心坐标（Barycentric Coordinates）_王王王渣渣的博客-CSDN博客_重心坐标

但需要注意的是，重心坐标并不具有投影不变性

对于投影进行插值，应该先进行投影，然后根据投影逆运算计算出该像素点在三维空间中的坐标，然后进行插值，再将结果放回投影后的像素点

注意，重心坐标在映射过程中并非保持不变，所以需要在对应时间计算对应的重心坐标来做插值，不能随意复用！映射过程伪代码如下：

foreach rasterized screen sample(x,y) //通常来说是一个像素的中心
	(u,v) = evaluate texture coordinate at (x,y) //用重心坐标插值
	texcolor = texture,sample(u,v);
	1111set sample's color to texture; //作为漫反射系数

应用纹理

简答纹理映射：漫反射颜色

对于每一个投影屏幕中的采样点，通过插值计算出他的坐标(u,v)
在纹理图上查询纹理值
将该纹理直（例如漫反射系数Kd）应用到模型中。

但是如果使用上述简单的方式进行纹理应用，将存在下文将要讨论的几个问题：

纹理放大（Texture Magnification）

即纹理本身过小，分辨率过低。

此处为了区分模型上的像素与纹理上的像素，我们引入一个概念：Texel，指纹理上的像素，即纹理像素或纹素

当查询纹理时候，所给坐标为非整数坐标，因此通常会采取一些方法来得到它的纹理值，常见方法有：

最近邻Nearest
双线性插值Bilinear
双向三次插值Bicubic

纹理放大（Hard Case）

即纹理过大，分辨率过高

当纹理过大时，映射到模型上会产生走样的问题，如下图所示，远处产生了摩尔纹，近处产生了锯齿：

产生摩尔纹的原因是像素不够多，而由于近大远小，远处会有更多的像素被同一纹素的纹理所覆盖，如下图所示：

此处引出一个计算几何中的经典问题：点查询与区域查询（Point Query & Range Query）

其中范围查询又分为很多种，例如平均范围查询，最大最小值范围查询（如线段树）

双线性插值

对于一个非整数点，考虑它的四领域，分别计算你该点到四领域中的Texel的水平与数值距离，并分别进行一次线性插值。

线性插值：对于已知的两个点A、B，如果某一点距离A点的距离为x，则该点的值可以表示为：

$lerp(x,A,B) = A + x(B - A)$

具体过程如图所示：

双向三次插值

与双向线性插值的区别在于去该点的16领域，这16个领域进行水平竖直的三次插值

MipMap

数据结构

允许进行一种快速，近似，正方形(fast,approx,square)的范围查询（Range Query）

范围查询：即给定一个区域，立即可以得到该区域的信息，例如平均值、最大值、最小值，数据结构中的经典算法线段树就可以用来解决区间查询的问题。

Mip来自于拉丁语中的“multum in parvo”，即小空间的多层堆叠

MipMap即将原始图片进行模糊操作，构成类似图像金字塔的结构：

随着层数增加1，图片的长宽缩小一半。

因此层数为Log2(n)（n为分辨率，假设图片为正方形）

可知MipMap是可以提前生成的。

那么使用MipMap算法产生的额外存储是多少呢？

由于每一层的长宽是上一层的一半，因此当前层的存储空间是上一层的1/4，因此每一层占用空间形成一个等比数列。因此总占用空间转化为一个等比数列求和问题：

n*n + (n*n)/4 + (n*n)/16 + ... \\ S = n*n \frac {(1 - (1/4)^{log_2(n)})}{1-1/4} \\ S = n*n \frac {1-(1/2)^{2log_2(n)}}{3/4} \\ S = n*n \frac {1-(1/(2^{log_2(n^2)})}{3/4} \\ S = n*n \frac {1- 1/n^2}{3/4} = n^2 \frac {\frac{n^2 - 1}{n^2}}{3/4} \\ S = \frac {n^2 - 1}{3/4} \\ S = 4/3 (n^2 - 1)

因此该算法的空间复杂度为 $O((4/3)n^2)$ ，即只需比原空间多出1/3的空间即可。

查询

那么给出一个像素点该如何查询该像素点对应的纹素平均值呢？

对于一个像素点，我们计算他在像素平面内与他相邻的两个像素的距离，记为x，y。然后通过微分的方法计算其在纹素域的距离。计算公式如下：

$L = max(\sqrt{(\frac{du}{dx})^2 + (\frac{dv}{dx})^2}, \sqrt{(\frac{du}{dy})^2 + (\frac{dv}{dy})^2})$

然后选取其中的最大者作为近似正方形的边长，然后通过取对数计算要取的层级：

$D = log_2(L)$

将该算法用于渲染后可以得到如下结果：

其中越暖的颜色代表使用了越低层的贴图。

Trilinear Interpolation

由于MipMap提供了多层级，相当于提升了一个维度，因此我们可以进行三线性插值，例如下图中描述的情况：

我们可以在相邻两层之间进行双线性插值，然后再对两层的插值结果再进行一次线性插值。

使用三线性插值后得到的贴图如下所示：

使用三线性插值的MipMap得到的结果如下：

可见远处会产生过模糊（OverBlur）的效果。原因在于MipMap值适用于正方形区域的查询，且只是近似，因此远处由于视角拉伸产生的非正方形区域的纹理产生了过模糊，下面介绍一个新的方法，能过部分解决这种问题：各向异性过滤（Anisotropic Filtering）

Anisotropic Filtering

各向异性过滤的思路事实上与Mipmap相同，都是通过预先计算不同尺寸的贴图来进行近似，只不过使用各向异性生成的贴图如下所示：

这组贴图我们称为Ripmaps，可以见该方法生成的贴图集合是Mipmap的超集，取该图中的对角线上的所有图片，就得到了Mipmap，因此又该图可知Ripmaps的开销将是原本的4倍。其中各项异性指考虑各个方向上的差异性。

该方法在Mipmap的基础上增加了单独的长宽变化，每一行上的图片长不变，宽变窄；每一列上的图片宽不变，高变窄。

为什么各向异性的效果会比单纯的Mipmap好？

对于如下图中的纹理映射，由于视线的问题，并不是所有纹理都是方方正正的被映射到物体上的：

因此对于矩形区域，各向异性过滤会得到更好的近似结果。

此外还有一些类似的方法能解决别的形状的纹理映射问题，比如EWA filtering

EWA filtering

该算法使用不同的圆形来覆盖不规则图像，使用多次查询达到近似的效果：

各种贴图

学完纹理映射之后，我们来思考一下什么是纹理。

在现代GPU中，纹理事实上就是内存中的一块数据（memory）+ 对于这块数据的查询方法（range query(filtering)）

环境光照（Environment Map）

假设光源无限远，只记录光照的方向信息，这种贴图被称作环境光贴图

例如

Utah Teaport 犹他茶壶；Stanford Bunny 斯坦福兔子

球面环境映射 Spherical Environment Map

球心为世界中心。类比地球仪展开铺平，存在纹理的拉升扭曲问题，例如将地球仪展开后南极洲在视觉上很小，解决方法：Cube Map
立方体贴图 Cube Map

将环境光照信息记录在一个立方体表面上，但会需要额外判断某一方向上的光照应该记录在立方体的哪个面上，计算量更大

凹凸贴图

记录了纹理的高度移动，并不改变原来模型的集合信息，通过法线扰动，得到模拟出来的着色效果，以假乱真

计算法线的方法

Bump Mapping
- 对于每个像素，记录该店的扰动
- 在贴图中，每个像素定义一个高度差
- shading时根据该高度差调整法线的方向
计算方法
- 设原本表面的某像素点p的法线n(p) = (0,1)
- 那么该点的梯度为： $dp = c * \frac{h(p+1) - h(p)}{1}$ ，其中h为高度函数，c为影响常量
- 那么受到扰动后的法线为 $n(p) = (-dp,1).normalized()$ 即原法线旋转90°
UV下的法线算法：

局部坐标下， $n = (-\frac{dp}{du}, -\frac{dp}{dv}, 1).normalized$

位移贴图

与凹凸贴图类似，但位移贴图是真的改变了几何信息，去对模型的顶点做位移，会比凹凸贴图更加逼真，但对模型的精度（三角面数量）要求更高，并且运算量也会随之上升

DirectX有Dynamic的插值法，根据需要对模型做插值，看情况决定模型的细致程度（动态曲面细分）

凹凸贴图vs.位移贴图

程序纹理

三维的纹理，并非真正生成了纹理的图，而是定义控件中任意点的颜色，定义三维空间中的噪声函数，再通过映射，得到预想的效果

预计算着色

将环境光进行预计算处理，再附在原先纹理上做一层遮蔽，再将纹理贴到模型上

三维渲染

广泛应用于物体渲染，如核磁共振等扫描后得到体积信息，通过这些信息进行渲染

程序纹理	预计算着色	三维渲染

几何

几何的表达方式

隐式几何

用空间中的满足一定条件的点的集合来表示面，隐式几何不会表示点的具体位置信息，而是告诉我们这些点满足的函数关系

我们很难看出隐式想表达的形状是什么，但对于判断点的位置关系（在内，在外还是在表面）会很方便

代数曲面
CSG构造实体几何
- 通过布尔运算将多个隐式几何进行结合
$\aleph$ 距离函数表示法
- 对于任意几何，不直接描述表面，而是描述空间中任何一个点到这个表面的最近距离（可正可负）
- 该方法在做blending（融合）时能达到很好的效果：
- 距离函数：SDF(Signed Distance Functions)
- - 上图中第一行是直接使用隐式函数表示平面AB后进行融合的结果
  - 第二行使用SDF表示平面AB后进行融合的结果
  - 本例中融合被定义为对于位置的点的函数值相加
  - 第二行中函数值为0的地方就是表面。
水平集（Level Set）
- 与距离函数的思想类似，在地理上类似等高线的定义
- 水平集与纹理的结合应用：CT扫描
分形几何（Fractals）
- 自相似几何，类似于递归，但由于变化频率过高，渲染时会产生强烈的走样，很难控制形状
- 中间的蔬菜中文名为：宝塔花菜

显式几何

直接给出点的位置，或者可以进行参数映射；然而想要判断内外时，显式的表达就很难进行表示

点云（Point Cloud）

用空间中一堆点的集合来表示物体，只要点足够密集，就看不到点与点之间的空隙，理论上可以表示任何几何，通常三维扫描得到的结果就是点云（点云可以转变为三角形）

多边形面（Polygon Mesh）

或许是目前最为广为流传的三维几何表达方式

$\aleph$ The Wavefront Object File(.obj)Format

一种文本格式，用于记录一些特殊的点、法线、纹理坐标、和连接关系

例子中的文件描述了一个立方体，其中v开头的八行描述了立方体的八个顶点

其次一个立方体有六个面，即六个不同的朝向，也就是六个法线，vn开头的八行描述了该立方体的六条法线，由于自动建模，产生了冗余的行，实际只有6条法线，例如29和30行是一回事

一个面有4个点，总共24个，但涉及到点的共用最终只需要12个纹理坐标，（也可以将立方体展开理解），我们需要定义12个纹理坐标，vt开头的14行描述了12个纹理坐标（同样有冗余）

然后定义点的连接关系，f表示的12行定义了点的连接关系，即哪三个点会形成一个三角形格式为：f v/vt/vn，其中每一位的数字代表了对于集合中的第几个点/纹理坐标/法线

曲线Curves

贝塞尔曲线（Bezier Curves）

使用一系列的控制点来定义曲线

绘制方法：德卡斯特里奥（de Castelijau）算法生成二次贝塞尔曲线（quadratic Bezier）

对于三个点的贝塞尔曲线生成，过程如下：

定义三个点
根据任意t值插值出点
不断重复t在[0,1]间取值
得到曲线

二次贝塞尔曲线：递归

贝塞尔曲线代数表示

在每两个之间找一个时间t，相当于每两个之间线性插值

把算法过程携程代数形式：

不难发现该式形式符合一个二项分布多项式，推广到n阶可得：

三次贝塞尔曲线的代数表示：

贝塞尔曲线的性质

必过起点终点，起始切线方向为前两个点连接的方向，终止切线方向为结尾两个点连接的方向
对于三次贝塞尔曲线，其起始位置的切线一定是 $b'(0) = 3(b_1 - b_0);b'(1) = 3(b_3-b_2)$
在仿射变换下，只需要对控制点做仿射变换再对变换后的控制点绘制贝塞尔曲线，就能得到这个贝塞尔曲线在仿射变换下的结果（但对投影不行）
凸包性质：贝塞尔曲线始终会在包含了所有控制点的最小凸多边形中, 而不是按照控制点的顺序围成的最小多边形
- 凸包：能包裹所有点的最小凸多边形

逐段贝塞尔曲线

控制点多了以后，贝塞尔曲线并不直观，很难控制，于是我们想到可以每次定义一段贝塞尔曲线，然后连起来普遍习惯每四个控制点定义一段，并略去中间两点间的连线

连续性

$C_0$ 连续：点相同	$C_1$ 连续：切线向同

样子条曲线

样条：连续的曲线，由一系列控制点控制，满足一定的连续性，即可控的曲线

B样条曲线有关信息可以参考：

https://zhuanlan.zhihu.com/p/50626506

https://www.bilibili.com/video/BV13441127CH?p=13

胡事民老师的课

曲面

贝塞尔曲面

u方向上画出四条贝塞尔曲线后，在这四个线上再取四个点，并认为这是个点是一组新的贝塞尔曲线的控制点，这些点在空间内向v方向扫描，便形成了贝塞尔曲面

几何处理

曲面细分（Mesh subdivision）

Loop细分（Loop subdivision）

以三角形面为例：

增多三角形数量
调整三角形的位置（即调整顶点的位置）
1. 将顶点区分为新的顶点与旧的顶点

该算法规定，一般情况下（不考虑边缘情况），对于新顶点，位置由下左图规定，而对于旧顶点，需要由旧顶点和新顶点位置共同确定

下右图中，n为该顶点的度（依附于某个顶点的边的条数），u为一个和n有关的数

新顶点	旧顶点

Ctamull-Clark细分

loop细分有一个前提，即只适用于三角形网格，而对于非三角形网格的细分，就需要借助catmull-clark算法该算法定义面分为两种——四边面和非四边面，并定义度为4的顶点为非奇异点，其余点均为奇异点

具体做法是，对每个非四边面都取其中的一个点（重心或者其他点），将其与该面的其他顶点分别连接，在这个过程中，会引入一个新的奇异点，并且在一次细分后，所有非四边面都变为了四边面，在后续的细分中，将不会引入新的奇异点

对于细分后顶点位置的调整，先将顶点分为三大类

①新的在面上的点；

②新的在边上的点；

③旧的点如下计算

loop细分与catmull-clark细分不同的处理效果：

具体推导过程可以参考： https://blog.csdn.net/McQueen_LT/article/details/10610260

网格简化（Mesh simplification）

边坍缩

如何保证坍缩前后轮廓基本保持一致？ ——二次误差

二次误差度量：坍缩后的点和原本几个边（面）的距离的平方和最小

对每一条边都先计算一下二次误差，随后从二次误差最小的开始坍缩，由小到大

但这么做会引入一些问题：做一次坍缩后，其他边也跟着变了，他们的二次误差必须被重新计算

所以需要从二次度量误差中选最小的，取完最小的之后，我们要对它们的二次误差做一次更新，于是我们就要用到优先队列 / 堆这种数据结构，这种数据结构能让我们能取得二次误差最小值的同时也能动态更新其他受影响的元素

另外，这种通过对局部计算最优解，试图找到全局的最优解，是一个典型的贪心算法

网格正规化（Mesh regularization）

光线追踪

光栅化的着色是一种局部的现象，在其着色的过程中只会考虑着色点自己的信息，而不会考虑其他物体，甚至不会考虑物资自身的其他部分对着色点的影响。事实上这些都是会有遮挡的关系的，是会产生阴影的，为了解决这个问题，就有了光线追踪

引入

Shadow Mapping 阴影贴图

核心思想：如果一个点不在阴影里，那么这个点可以被摄像机和光源都看到

局限：硬阴影，走样，只能处理点光源

具体实现细节：

① 先从光源看向场景，做一遍光栅化，不进行着色，只记录深度

② 再从摄像机看向场景，再做一遍光栅化，记录深度

③ 比较两次深度值，如果不相等，则说明该点在阴影中

问题1：渲染出来的阴影比较脏

原因：深度值的比较位浮点数比较，而判断浮点数相等势必会产生误差，虽然处理精度的方法有很多种，但并不能从本质上解决问题

问题2：走样

原因：本身储存的深度图存在分辨率限制，与渲染时的分辨率搭配不好的话，就会产生走样

关于硬软阴影：本质是本影和半影的问题，只要存在软阴影，那么光源一定具有一定的体积

Why Ray-Tracing？

由上可知，光栅化并做不好全局的效果，如软阴影，反射，环境光照

光栅化很快速，但渲染的质量不高；光纤追踪的处理速度慢，但渲染的很准确

光栅化很容易做到实时，而光线追踪更多的应用于离线渲染（现在的实时光线追踪，这位更是重量级！）

首先定义光线——沿直线传播，不会发生碰撞，从光源到人眼

由光路的可逆性，在光线追踪的具体应用中，采用从人眼（认为是一个针孔摄像机）到光源的方法

光线投射：人眼，成像平面，光源，物体

Ray Casting

从相机出发投射一条光线，穿过成像平面，与着色点相连，如果光源能看见着色点（着色点不在阴影中），那么就生成一条有效光路，计算能量并着色（我们很容易知道这个着色点的法线，入射方向等信息，这时候可以用各种各样的着色模型（如Blinn Phong））

对于场景中的物体，我们假设光打到它之后会发生完美的折射与反射，而对于着色点，我们取光路与物体最近的交点（涉及深度测试）

总的来说，光线投射其实就是每个像素投射出去一条光线，求到和场景内物体的最近交点，通过该交点和光源连线来判定是否可见，然后算着色，写回像素的值

这个方法依旧只是弹射一次，但事实上光线是能在物体间弹射很多次，这时候就需要用到whitted光线追踪