games101 三、几何
表示几何的不同方式
隐式几何（Implicit Geometry）和显式几何（Explicit Geometry）
隐式几何不显式指出顶点的位置，只给出点之间的关系，例如用一个方程来表示一个球。
缺点是不够直观，好处是很容易判断一个点是否在几何体表面或者内外。
显式几何给出几何体的每个顶点坐标。
另一种显式几何是用参数映射的方式给出每个点，可以将二维平面映射到三维空间中，得到一个曲面，例如，点是以(u, v)参数的形式给出，然后将(u, v)映射到三维空间中，得到(x, y, z)。
显式几何的缺点是不太容易判断一个点是在几何体的表面上还是内外。
隐式几何
隐式几何的好处
- 描述简洁
- 容易查询一个点和几何体的关系（在表面上、在内部还是在外部）
- 容易做光线求交
- 对于简单的形状，描述精确，不存在采样错误
- 容易描述拓扑结构的改变
隐式几何的问题
很难对复杂形状建模。
代数曲面（Algebraic Surface）
用 \(x^2 + y^2 + z^2 = 1\) 表示球面。
用 \((R-\sqrt{x^2 + y^2})^2 + z^2 = r^2\) 表示甜甜圈，环形圆管（Torus）。
构造实体几何（Constructive Solid Geometry, CSG）
用基本几何体做布尔运算（Boolean Operation）得到复杂几何体。
距离函数（Distance Function）
不直接描述表面，而是去描述点到表面的最近距离。
距离函数或者有向距离函数（Signed Distance Function, SDF）适合处理几何体的融合操作。
水平集方法（Level Set Method）
是一种距离函数的表示方法，他将距离函数的值存储在一个网格中，如果把所有\(f(x)=0\)的点找出来，就能得到图中所示的曲线，如果把\(f(x)=2\)的点找出来，就能得到另外一条曲线，有点类似于等高线。
水平集还可以定义在三维空间的格子上。
还可以用于物理模拟，描述一个流体的边界。
分形（Fractals）
分形用来描述自相似的现象，即同样的结构在不同的尺度上重复出现。
显式几何
点云（Point Cloud）
就是一系列点，不构成任何表面，只要点足够多足够密集，就能表示一个物体。
点云经常会被转换为多边形面（Polygon Mesh）。
多边形网格（Polygon Mesh）
由顶点和多边形组成的网格，通常用三角形或四边形。
obj文件格式
obj文件格式是一种常见的多边形网格文件格式。
v表示顶点坐标，vn表示顶点法线，vt表示纹理坐标，f表示一个多边形。
f的格式是这样的，它由三组12/34/55这样的数字组成，每组数字表示一个顶点，一组数字对应的其实是三个序号，分别是顶点序号、顶点法线序号、纹理坐标序号。
vn 0.713667 0.093012 -0.694283
vt 0.854030 0.663650
v 0.348799 -0.334989 -0.083233
vn 0.742238 0.092067 0.663782
vt 0.724960 0.675077
v 0.313132 -0.399051 0.881192
...
f 739/739/739 735/735/735 736/736/736
f 189/189/189 736/736/736 735/735/735
f 192/192/192 738/738/738 737/737/737
f 739/739/739 737/737/737 738/738/738
f 190/190/190 741/741/741 740/740/740
...
曲线（Curve）
曲线能用在哪，比如说控制相机的移动路径，或者用来描述字体。
曲线（Curve）
贝塞尔曲线（Bezier Curve）
贝塞尔曲线由四个点P0, P1, P2, P3定义，P0和P3分别是曲线的起点和终点，P0和P1构成了P0的切线方向，P2和P3构成了P3的切线方向。
De Casteljau算法
用任意数量个点来定义贝塞尔曲线。
原理是这样的，给定一个范围在0到1之间的参数t，通过一定的规则找到贝塞尔曲线上对应t的点，然后我们枚举0到1之间所有的t值，就能得到贝塞尔曲线。
怎么找对应t的点呢？
考虑初始只有三个控制点的情况，这种情况也叫二次贝塞尔曲线（Quadratic Bezier），有三个点B0、B1、B2，B0和B1构成一个线段，B1和B2构成另一个线段，我们将每个线段看作一个0到1的范围，取t值对应的点，得到两个新点，然后再将两个新点连成一条线段，再取t值对应的点，这个点就是t值对应的贝塞尔曲线上的点。
如此，我们通过枚举所有的t，就能找到贝塞尔曲线上的所有点。
这个过程是一个递归插值的过程。
贝塞尔曲线代数方程（Bezier Curve Algebraic Formula）
给定n+1个控制点，每个点需要找n轮，可以写出一个n阶贝塞尔表达式，如下：
\(b_j\)表示控制点，\(B_{j}^{n}(t)\)是伯恩斯坦多项式，定义如下：
这里的 \(\binom{n}{i}\) 是个组合数 \(C_{n}^{i}\)。
其实就是一个二项分布多项式。
注意，贝塞尔方程是一个最终的展开式，并不涉及中间得到的临时点。
贝塞尔曲线有以下性质：
- 贝塞尔曲线起点是\(b_0\)，终点是\(b_n\)，因此，\(b^{n}(0) = b_0\)，\(b^{n}(1) = b_n\)。
- 在四个控制点（三阶贝塞尔曲线）的情况下，起始位置的切线和结束位置的切线分别是，\(b^{'}(0) = 3(b_1-b_0)\)，\(b^{'}(1) = 3(b_3-b_2)\)
- 在仿射变换时，可以直接对控制点进行变换，利用变换后的控制点生成的贝塞尔曲线和对原始贝塞尔曲线上的每个点进行变换是一样的（只有仿射不变性，投影变换是不行的，因为投影变换的最后一步是做透视除法，即对x、y、z坐标分别除以齐次坐标w，这个过程是非线性的）。
- 凸包性质：贝塞尔曲线总是位于控制点形成的凸包内。
分段贝塞尔曲线（Piecewise Bezier Curves）
逐段贝塞尔曲线。
为了解决高阶贝塞尔曲线（由很多点定义的贝塞尔曲线）不易控制的问题，可以用多段低阶贝塞尔曲线来连接成高阶贝塞尔曲线，前一段的终点同时作为后一段的起点。
一般使用三阶贝塞尔曲线（四个控制点）（Piecewise cubic Bezier）来连接。
如何使得两段贝塞尔曲线之间的连接是光滑的呢？我们利用上面的三阶贝塞尔曲线的性质，让前一段的终点和后一段的起点重合，并且让前一段的终点切线和后一段的起点切线方向相反，切线长度一致。
这里给出几种连续的定义：
- \(C^0\)连续：两段曲线的连接点重合，在几何上连续。
- \(C^1\)连续：两段曲线的连接点重合，并且切线方向相反，切线长度相同，并且一阶导数连续。
可以使用https://math.hws.edu/eck/cs424/notes2013/canvas/bezier.html这个网站来交互式地绘制贝塞尔曲线。
样条（Spline）
简单来讲，一个利用多个控制点控制的曲线就是样条。
B样条（B-Spline）
B样条是基函数样条（Basis Spline）的缩写，它的大概思路是将伯恩斯坦多项式视为不同的基函数，然后通过线性组合这些基函数来得到曲线。
B样条是对贝塞尔曲线的一个推广。
B样条具有局部性，贝塞尔曲线是全局控制的，即一个控制点的移动会影响整条曲线，而B样条是局部控制的，一个控制点的移动只会影响曲线的一部分。
曲面
贝塞尔曲面（Bezier Surface）
贝塞尔曲面是贝塞尔曲线的推广。
下图是由16个控制点（4x4）定义的一个三阶贝塞尔曲面。
它的原理是这样的，在原本的二维平面上，先用四个控制点画出一条贝塞尔曲线，然后沿着新增的维度方向，再其他三个平面上继续画出三条贝塞尔曲线，这样就得到了四条贝塞尔曲线，选择任意一个t，我们分别能在这四条贝塞尔曲线上找到对应的点，然后将这四个点作为新的控制点，再画一条贝塞尔曲线，枚举所有的t值，就能得到整个贝塞尔曲面。
下图中蓝色的线扫过的地方就是贝塞尔曲面。
由此可见，我们需要两个t参数，我们把这个二维的参数叫做(u, v)。
这也是为什么贝塞尔曲面被归类到显式几何的原因，因为它是通过参数映射的方式来定义曲面的，给定(u, v)，就能找到曲面上的点。
网格（Mesh）操作：几何处理
- Mesh subdivision（曲面细分）：让三角形更密
- Mesh simplification（曲面简化）：让三角形更少
- Mesh regularization（曲面规整化）：让三角形大小形状都差不多。
曲面细分（Mesh Subdivision）
分两步：
- 生成更多三角形
- 调整三角形顶点的位置，使表面更光滑
Loop Subdivision
（这个细分的发明人的名字叫Loop）
这个算法只能细分三角形。
该算法把一个三角形分成四个三角形，如下图所示，
如何调整三角形顶点的位置呢？
首先考虑新增顶点的位置，如下图所示，新增顶点位于一条边上，它被两个三角形共享，这个点的新位置由四个原有的点A, B, C, D加权平均得到。
对于原有的顶点，它的新位置由它本身和它的邻居顶点加权平均得到。
其中，\(n\) 是顶点的度（degree），也就是连接了几条边。
\(u\) 的计算公式如下：
Catmull-Clark细分（Catmull-Clark Subdivision）
他可以细分任意多边形。
这个算法把面分为四边形面和非四边形面（Non-quad face）
奇异点（Extraordinary Vertex）：度不等于4的顶点
如何细分呢？
对于任意一个面，取每条边的中点作为新的点，取每个面的中心作为新的点，把面中心点和每个边中心点连起来。
这个细分算法有以下性质：
- 只要一个面是非四边形面，它的中心点一定是奇异点。
- 经过一次细分之后，所有的非四边形面全部消失
这相当于，一次细分之后，所有非四边形面全部转化为相同数量的奇异点，再细分，奇异点不再增加（因为已经全是四边形面了）。
每次细分后，要调整顶点位置。
面中心点、边中心点和原有顶点的位置调整公式如下：
曲面简化（Mesh Simplification）
边坍缩（Edge Collapse），把一条边的两个顶点合并成一个顶点，从而减少三角形的数量。
二次误差度量（Quadric Error Metric, QEM），是新点到原本连接的面的距离平方和，我们的目的是找到一个新点，让这个距离平方和最小，将这个新点作为边坍缩后的新顶点。
如何选择要坍缩的边呢？
为每个边计算出二次误差度量，然后选择误差最小的边进行坍缩，这里面存在问题，坍缩一条边后，其他边的二次误差度量也会变，所以需要重新计算。用优先队列或堆来保存所有已经计算出的二次误差度量，每次选择误差最小的边进行坍缩，如果发现它需要更新，就将它弹出队列，更新它的二次误差度量，再放入堆中。