GAMES101知识梳理：几何

本节说明

GAMES101 Lecture 12 Geometry 3中最后部分讲的是Shadow Mapping，此部分内容并非几何内容，而是为了后面的光线追踪做铺垫，为了方便查阅故将其内容并入后面的光线追踪里。

Ways to Represent Geometry-几何表示方法

Implicit Geometry-隐式几何

隐式方法给出了点满足的关系，而不是具体位置。
隐式几何一般表示为$f(x,y,z)=0$的形式。
例如

隐式方法很适合求点与几何形体空间关系的问题(在内部、外部还是表面上)，但是有时候不适合表示不太规则的几何形体。

$$f(x_p,y_p,z_p)=\begin{cases} >0 & \text{outside the geometry}\\ =0 & \text{on the geometry}\\ <0 & \text{inside the geometry} \end{cases}$$

Algebraic Surfaces-代数表示方法

不直观，但是对于简单几何表示比较方便。

Constructive Solid Geometry(CSG)-构造立体几何法

通过基本几何的基本运算来组合定义复杂的几何。应用广泛。

Blending Distance Functions-距离函数融合

距离函数表示空间中任意点到几何形体上点的最小距离。距离函数实际上描述的几何形体的边界。

根据几何形体的表面/边界求出几何形体的距离函数然后进行融合，最后恢复出表面(SDF==0)。距离函数融合实际上是进行边界的融合，也可以对不同几何进行融合

例.求移动边界的中间状态

Level Set Methods-水平集方法

距离函数有时不易于表示成解析形式。
水平集方法与距离函数的思想完全一致，只是将距离函数值定义在网格内，只需在网格内找到插值为0的位置就可以将几何表示出来(类似地理上的等高线)。

水平集/距离函数方法可以推广到三维，其应用在医学上有CT、MRI等，在物理模拟上有水花模拟等，

Fractals-分形

自相似，即几何形体中的某个部分和其整体相似，类似程序的递归，如雪花的六边形。

Explicit Geometry-显式几何

显式方法直接给定点的位置或者通过参数映射(参数方程)。
例如

显式方法很直观，但是对于点与几何形体空间关系问题的求解比较麻烦。

Point Cloud-点云

使用空间中一系列点来表示几何形体，将点云变成一系列多边形网格面元。
点需要足够密集，如果点云密度很低就很难绘制出几何形体。

对点云表示的几何形体进行渲染

Polygon Mesh-多边形网格

将几何形体的面拆成许多小的多边形(通常为三角形)。
这是图形学中最常用的显式几何表示方法，使用该方法表示几何形体比较易于进行各种处理，但其面元连接等关系复杂，从而需要更加复杂的数据结构。

补充：Wavefront Object File(.obj)格式
.obj文件本质上是文本文件，文件中将一堆点坐标、纹理坐标、法向量分开表示，最后记录权重用于将分散表示的数据组织起来形成三角形和对应的纹理坐标与法线。
下图文本中，第一部分v定义点的坐标；第二部分vt是纹理坐标；第三部分vn为法向量，其中纹理坐标和法向量的定义有冗余；第四部分f中每一小段定义点/纹理坐标/法向量，一行三个形成一个三角形。

Curves-曲线

曲线可用于定义摄像机、模型的移动，也可以使用曲线定义字体…

Bézier Curves-贝塞尔曲线

贝塞尔曲线用一系列控制点和插值方法定义曲线。$n+1$个控制点定义一条$n$阶贝塞尔曲线。

de Casteljau Algorithm

定义$t$为$\bm{b}_0$到$\bm{b}_1$的时间，$t\isin[0,1]$，使用$t$在$\bm{b}_0\bm{b}_1$上插值找到对应的点$\bm{b}_0^1$。在$\bm{b}_1\bm{b}_2$上同样操作找到$\bm{b}_1^1$，最后在$\bm{b}_0^1\bm{b}_1^1$上找到$\bm{b}_0^2$。
如果画出的点数足够多，就可以由此连出贝塞尔曲线。

贝塞尔曲线使用$t$来定义曲线，是典型的参数方程，因此是显式方法。
使用四个点控制点也可如法炮制。

de Casteljau算法是递归的

de Casteljau Formula

$$\begin{aligned} \bm{b}_0^1(t)&=(1-t)\bm{b}_0+t\bm{b}_1 \\ \bm{b}_1^1(t)&=(1-t)\bm{b}_1+t\bm{b}_2 \\ \\ \bm{b}_0^2(t)&=(1-t)\bm{b}_0^1+t\bm{b}_1^1 \\ \bm{b}_0^2(t)&=(1-t)^2\bm{b}_0+2t(1-t)\bm{b}_1+t^2\bm{b}_2 \end{aligned}$$

可见，$n$阶贝塞尔曲线上的点$\bm{b}^n(t)$实际上是其$n+1$个控制点的线性组合，而组合系数$B_j^n(t)$是伯恩斯坦多项式(Bernstein Polynomial)，类似二项分布多项式。

$$\begin{aligned} \bm{b}^n(t)&=\bm{b}_0^n(t)=\sum_{j=0}^{n}\bm{b}_jB_j^n(t) \\ B_i^n(t)&=\begin{pmatrix} n \\ i \end{pmatrix} t^i(1-t)^{n-i} \end{aligned}$$

推广至三维很容易，将点表示为三维坐标，仍然用伯恩斯坦多项式进行插值即可。

贝塞尔曲线的特性

• $t=0,t=1$时，$\bm{b}(t)$分别是首尾两个控制点，$\bm{b}^{\prime}(t)$分别是曲线进和出的方向；
• 贝塞尔曲线的仿射变换等同于对其控制点进行仿射变换然后再画出曲线(仅对仿射变换)；
• 凸包性质：贝塞尔曲线一定在其控制点形成的凸包(Convex Hull)内。

Piecewise Bézier Curves-分段贝塞尔曲线

高阶贝塞尔曲线控制点很多，不太容易控制。因此使用分段贝塞尔曲线，即每次用较少的控制点定义一段曲线，最后将各段曲线连在一起。

最常用的是Piecewise Cubic Bézier(三阶贝塞尔曲线，四个控制点)

如果分段连接处导数连续则曲线是光滑的，反映在控制点上就是前一段的2,3控制点(即后一段的控制点0)和后一段的控制点1，三点共线且两段线段等长。

分段贝塞尔曲线的连续性

• C0 Continuity: $\bm{a}_n=\bm{b}_0$，曲线连续
• C1 Continuity: $\bm{a}_n=\bm{b}_0=1/2(\bm{a}_{n-1}+\bm{b}_1)$，一阶导数连续
  类似还有C2连续…，于曲面有G0,G1,G2…连续。

其他曲线

• Spline-样条
• B-Spline
• …

Surfaces-曲面

Bézier Surface-贝塞尔曲面

由贝塞尔曲线可以得到贝塞尔曲面。
如下图中贝塞尔曲面由16个控制点定义，相当于在两个方向上求贝塞尔曲线。首先定义16个控制点为$4\times4$布局，先对四行分别求贝塞尔曲线，对于相同横坐标，四条贝塞尔曲线上各有一个点，将这四个点当作贝塞尔曲线的控制点再求一条曲线，随着横坐标变化我们就得到一个移动的贝塞尔曲线，这个移动贝塞尔曲线就构成了贝塞尔曲面。

图中表示的是Bicubic Bezier Surface，由"Bicubic"一词可见，这与我们在着色一节中所说的双三次插值是一样的。

由上所述，我们需要水平和竖直两个方向的时间$t$，我们可将其命名为$(u,v)$ in $[0,1]^2$

Geometry Processing-几何处理

Mesh Subdivision-网格细分

Loop Subdivision

网格细分实际上进行两步操作，先增加三角形数量，再调整三角形位置。

增加三角形

更新位置
对于新产生的顶点，其位置就是周围旧的顶点的加权平均。

对于旧的顶点，其位置是周围旧的顶点与自己的加权平均，$n$为节点的度。

Catmull-Clark Subdivision

如果不是三角形网格，可以使用Catmull-Clark Subdivision。
该方法首先定义非四边形面(Non-Quad Face)和奇异点(Extraodinary Vertex，即度不为4的点)。
取边的中点并分别与其面的中点相连，这个操作会引入新的奇异点，因为非四边形面的中心与其各边中点相连，由于边数不为4，则原面的中点会变成奇异点。这个操作会让非四边形面全部消失，而后续的细分不会再增加奇异点。其中，第一次细分增加的奇异点数等于非四边形面个数。

点位置的更新方式如下

Mesh Simplification-网格简化

Edge Collapsing-边坍缩

对于一条边，将其两端顶点捏到一起。

Quadric Error Metrics-二次误差度量
二次误差度量可以确定边坍缩生成的新顶点位置，相比使用求平均方法,其生成的新图形面积与原先比较接近。
新顶点的位置是使得该点到与其关联的各面(边坍缩前)的距离的平方和最小的位置，该平方和就是其二次误差度量，类似MSE的概念。
其具体做法就是，对于各边求出其单独坍缩的最小二次误差度量记为该边的值，然后先坍缩值最小的边，坍缩后更新各边的值，再次坍缩最小值边…以此类推。这种算法是一种贪心算法，具体实现需要用到优先队列。