GAMES101学习笔记（六）：Geometry 几何（基本表示方法、曲线与曲面、网格处理）

课程资源：GAMES101-现代计算机图形学入门-闫令琪

Lec10 ~ 12 学习笔记：
Lecture 10 ：Geometry 1 (Introduction) ——几何（基本表示方法）
Lecture 11 ：Geometry 2 (Curves and Surfaces) ——几何（曲线与曲面）
Lecture 12 ：Geometry 3 (Mesh)——几何（网格处理）、阴影图

几何的表示方法

• 隐式表示
• 显式表示

隐式几何 通过方程定义，适合判断点位置和布尔运算。
显式几何 通过参数方程定义，适合绘制和采样。

隐式几何 Implicit Geometry

隐式几何通过方程定义形状，通常表示为f(x,y,z)=0。点在曲面上当且仅当满足该方程。

优点：
1）是一种紧凑的表达，可以节省空间
2）很容易查询一个点和表面的内外关系以及点到表面的距离
3）隐式表面比显式表达更容易和光线进行求交（ray-to-surface intersection）
4）对于简单的形状，隐式表达可以准确描述形状，没有采样误差
5）处理拓扑上的变化很容易，例如很方便处理流体

缺点：很难建模复杂的物体（但是显式表达方法可以表示）

代数曲面(Algebraic surface)

并不是直接表示点的位置，而是定义物体上的点满足的关系 f(x,y,z)=0 ，满足这个关系的点就在物体上，通过将点进行归类来获得物体上的点的集合。

构造实体几何CSG(Constructive Solid Geometry)

通过对一些基本的几何形状进行一些运算（Boolean operation）得到复杂的形状，且该方法在各种三维建模工具中应用广泛。

距离函数(Distance Function)

不直接描述物体的表面，该方法使用函数表示空间中的点到物体的表面的最小距离(并且这个距离是有符号，如果点在物体之外，距离的符号为正；如果点在物体的内部，距离的符号为负），距离函数的值为0的点都在物体的表面上，这样的距离函数表示又称为有符号距离场(SDF)

SDF适合做基于距离函数的融合来实现两个物体的融合: 对两个物体的SDF做融合实际上是对两个物体的边界做融合

水平集方法(Level Set Methods)

Level Set方法中使用一个网格来近似距离函数，每个网格中都有一个值表示距离, 通过双线性插值可以求解距离等于0的位置，连接这些点就是表面。

水平集不仅可定义在二维空间中的格子上，也可定义三维空间中的网格上，此时对于对一个每个点表示密度的三维纹理来说，让密度等于某个值得到的水平集就是物体的表面。

分型几何(Fractal)

表示子相似性：自身的一个部分和整体的相似性（形状本身可能是递归生成的, 比如雪花）。
当形状本身是递归生成时，在渲染过程中会因为形状的变化频率太高而产生走样。

显式几何 Explicit Geometry

与隐式几何相对的就有显式几何，显式的方法有直接给出点的位置，或者用参数映射（定义一个函数，将二维平面上一个区域中的二维坐标点映射到三维空间的表面上去）

显式几何通过参数方程直接表示形状，通常形式为 p(u,v)=(x(u,v),y(u,v),z(u,v))，其中 u 和 v 是参数。

优点： 易于绘制和采样，适合渲染和建模。
缺点： 判断点是否在曲面上较复杂，布尔运算和求交困难。

点云(Point Cloud)

不考虑物体是一个表面，而是表面为一堆点，只要点足够密集，就看不到点与点之间的缝隙。理论上可以表示任何几何。通常三维扫描等得到的结果就是点云。

点云经常被转换成多边形网格（polygon mesh）形式的数据。

多边形网格(Polygon Mesh)

图形学中应用最广泛的表达形式，表示四边形或三角形组成的面，更易于进行处理/模拟、自适应采样(adaptive sampling)

可用Wavefront Object File(.obj) 形式的文件的去存储mesh形式的数据: 在text文件中记录所有顶点坐标、法线、纹理坐标和顶点之间的连接关系，通过定义一个face(三角形的三个顶点各自的坐标索引,纹理坐标索引,法线索引)来表示顶点之间的连接关系。

曲线和曲面

Bezier surface，subdivision surface，NURBS(非均匀有理B样条曲线） 等。

曲线 Curves

贝塞尔曲线 Bézier Curves

贝塞尔曲线是需要一系列的控制点去定义某一个曲线（通过参数t来定义，显式表示）

三次贝塞尔曲线(Cubic Bezier Curve)使用四个控制点 P0, P1, P2, P3 来定义曲线, 曲线的起始点和终止点必须是 P0 和 P3，并且这四个点确定了曲线的两条切线：曲线在起点处的切线t0 , 在终点处的切线t1。

绘制贝塞尔曲线——De Casteljau Algorithm

通过De Casteljau算法生成贝塞尔曲线，实现的是使用任意多的点来绘制一条Bezier曲线，例如但当只有两个点时为一条线段，三个点时生成的是二次贝塞尔曲线(quadratic Bezier curve)，四个控制点生成的是三次贝塞尔曲线(Cubic Bezier Curve)。

几何形式

三个控制点生成二次贝塞尔曲线(quadratic Bézier curve):

四个控制点生成三次贝塞尔曲线(Cubic Bézier Curve)：
同样是对控制点进行递归线性插值的过程

代数形式

在计算三次贝塞尔曲线的过程中，我们是在每两个之间找一个时间t，相当于每两个之间线性插值。

推广到n阶：给定n+1个控制点，可得到n阶的贝塞尔曲线，任意时刻t下曲线上的点是n+1个控制点的线性组合，组合的系数是和时刻t相关的多项式(成为Bernstein polynomial)，所有系数多项式的和为1，每一项系数可以看做是(t+1-t)^n
的展开项。

贝塞尔曲线性质

• 仿射变换性质：
  对贝塞尔曲线做仿射变换，不需要对曲线上的每一个点做仿射变换，只需要对控制点做仿射变换，然后利用变换后的控制点来生成曲线, 该曲线就是变换后的贝塞尔曲线。(在其他的变换(eg:投影变换)下这样做不行）

• 凸包性质(Convex hull property)：
  凸包是能够包围给定的几何形体的最小的凸多边形.
  生成的贝塞尔曲线是在控制点形成的凸包内的，eg:如果四个控制点在一条直线上，则生成的贝塞尔曲线一定是连接起点和终点的线段。

贝塞尔曲线的缺点：

1. 当控制点多时，不容易通过控制点来控制曲线的形状
2. 改变一个控制点的位置，整条贝塞尔曲线上的点的位置都会变化。实际应用时，期望曲线具有"局部性"：改变一个控制点，只会影响部分范围内的点。

分段贝塞尔曲线 Piecewise Bézier Curve

分段贝塞尔曲线通过分段解决了贝塞尔曲线的两个缺点：

1. 分段后可很容易地通过控制点位置来控制曲线的形状。
2. 改变一个控制点后，最多影响两段贝塞尔曲线中的点。

分段贝塞尔曲线：给定很多控制点时，不是使用所有控制点来生成一条贝塞尔曲线，而是将这些控制点按顺序分成若干个部分(通常一个部分中包含4个控制点,并且相邻部分的控制点集合中有公共点)，每一个部分的控制点生成的是低阶(通常是三阶的)的贝塞尔曲线，然后将这些贝塞尔曲线连接起来就组成了分段贝塞尔曲线。

分段贝塞尔曲线的三种连续性：（前后两段的贝塞尔曲线可分别使用两个函数表示）

• C0连续性(几何连续性)：前一段的终点和后一段的起点是同一个点，所以这是分段贝塞尔曲线固有的连续性(实际上两个函数在公共点处的值连续)
• C1连续性(切线连续性)：在定义的基础上需要满足： an = b0，使得前一段的终点处的切线和后一段的起点的切线在方向和大小上都相同, 该连续性可使得两段曲线在连接点处的光滑过渡。(实际上是两个函数在公共点处的一阶导数连续)
• C2连续性(曲率连续性): 实际上是两个函数在公共点处的二阶导数连续。

优点: 可以通过控制每一段贝赛尔曲线的四个控制点的中间两个控制点的位置来控制这一段贝塞尔曲线的形状。

样条曲线 Spline Curve

定义：可用一系列的控制点控制的连续曲线，在曲线上的任意一个点都满足一定的连续性

基函数：前面的Bezier Curve的代数表达中的Bernstein polynomial就可看做是基函数，通过控制点的坐标来对基函数进行加权求和得到曲线的函数

B样条曲线(B-splines/Basis splines)：基函数样条曲线 。该曲线比贝塞尔曲线的能力更强：因为B样条曲线具有局部性，在使用较多的控制点来生成曲线时，改变其中一个控制点，只会影响部分范围内的点，并且B样条曲线也不用像分段贝塞尔曲线那样使用分段操作才能实现局部性。

非均匀有理B样条曲线(NURBS): 比B样条曲线更加复杂

深入了解：https://www.bilibili.com/video/BV13441127CH

曲面 Surfaces

贝塞尔曲面 Bézier Surfaces

将贝塞尔曲线拓展到曲面上得到的曲面: 使用4x4个控制点（压平就是4x4的网格），然后在两个方向上分别应用贝塞尔曲线：先在水平方向上利用每条水平线上的四个控制点计算得到四条贝塞尔曲线，然后在四条贝塞尔曲线上采样得到竖直方向上相同时刻的四个点，最后基于这四个点计算贝塞尔曲线。

绘制贝塞尔曲面 Evaluating Bézier Surfaces

通过参数映射把 u v 分别映射成 t

几何处理/网格处理

• 网格细分 mesh subdivision (upsampling)
  使用更多的三角形来表示物体表面，细分后的得到的表面会更加光滑

• 网格简化 mesh simplification (downsampling)
  网格细分的逆过程，在能够控制损失和保持基本形状的情况下，使用更少的三角形表示，可以减少存储占用。

• 网格正则化 mesh regularization
  避免长尖的三角形(这种三角形会对渲染过程造成不便)，通过正则化在不丢失细节情况下让三角形变得和正三角形相似且三角形之间大小相近

网格细分 Mesh subdivision

具体的过程主要分为两步：
1.先分出更多的三角形。
2.使得这些分出的三角形的位置发生一点变化，使得细分后得到的物体表面更加光滑。

两种细分的算法：

• Loop Subdivision （只能用于细分三角形网格）
• Catmull-Clark Subdivision （可以用于一般的网格的细分）

网格简化 Mesh simplification

应用场景：当物体模型距离视点距离很远时，减少面的数量不会影响视觉效果。(可以根据物体模型和视点的距离来选用不同具有不同数量的面的模型,越近使用更多的面，这是几何的层次结构，较难处理，而前面提到的纹理图像的层次结构很容易处理，例如使用Mipmap)

一种网格简化的方法：边坍缩算法(Edge Collapsing Algorithm)

完整过程：先选择边来进行坍缩，然后通过优化的方法来确定坍缩后的点的位置
坍缩过程：就是将一条边的两个顶点合并成一个顶点并删除掉这条边，从而实现三角形数量的减少。

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

坍缩后的点的位置的确定：可以通过最小化二次误差来确定坍缩后的点的位置使得坍缩前后的轮廓形状基本一致，这个二次误差是坍缩后的点到与该点关联的面的距离的平方和。(下图是原始的五个顶点abcde坍缩成afe三个顶点的情况)

坍缩的边的选择：不重要的边进行坍缩，重要的边不进行坍缩。算法中基于二次误差度量(Quadric Error Metrics)这个指标来选择边进行坍缩，具体过程：

1. 计算当前模型中所有边的最小二次误差：对于每一条边，我们假设对每条边进行坍缩并使用优化的方法确定坍缩后的点的位置后，然后计算出坍缩每条边的最小二次误差
2. 选择最小二次误差最小的边进行坍缩，坍缩了一条边之后，和这条边原始两个顶点相连的边的最小二次误差会变化，需要更新这些边的最小二次误差(使用优先队列，可以方便地取最小值，并且方便动态更新相邻边的值)
3. 重复步骤2，再选择当前边的最小二次误差最小的边进行坍缩，如此迭代下去指导达到终止的条件。

属于贪心算法，通过不断求解局部最优解来寻找全局最优解