几何
几何的描述
在图形学中几何的描述有两种方式，隐式几何（Implicit Geometry）和显式几何（Explicit Geometry）
隐式几何
隐式几何对点的之间的关系进行描述，不直接给出点的位置。例如，对于一个球面，我们可以使用如下方程描述： \[ x^2 + y^2 + z^2 = 1 \]
几何的隐式表示很难看出其图像，但可以非常轻松地判断一个点是否在曲面上或者在图形内部。隐式几何
- 数学方程表示；
- CSG 表示；
- 距离函数；
- 分形；
数学方程表示
例如，一个球体可以表示为下面的方程： \[ x^2 + y^2 + z^2 = 1 \] 一般地，可以使用方程 \(f\left(x, y, z\right) = 0\) 一个曲面。
使用数学方程表示难以看出其图形，但可以快速判断一个点是否在曲面上，如果是一个封闭的曲面，还可以快速地判断一个点是否在曲面内。
CSG 表示
CSG（Constructive Solid Geometry），通过对几何体进行布尔运算，即交、并、差等运算，用简单的几何集合体组合成复杂的集合体。
下面是一个使用 CSG 得到复杂几何体的例子：
距离函数
距离函数表现了空间内任意一点到物体的最短距离。两个距离函数的加和可以得到两个物体融合的中间态。非常适合在模拟水滴融合中使用，如下图所示：
距离函数中距离为 0 的平面就是物体平面。下图是一个使用距离函数的例子：
距离函数还可以使用水平集（Level Set）来离散的表示：
分形
指的是一个图形的一部分和自己整体相比高度相似，可以理解为一种递归的形式。
显式几何
显示几何有 3 种标识方式：
参数映射（参数方程）；
点云；
多边形面。
参数映射
定义一个映射： \[ f: \R^2 \rightarrow \R^3;\left(u, v\right) \mapsto\left(x, y, z\right) \]
这个映射将 \(\left(u, v\right)\) 映射到 \(\left(x, y, z\right)\). 例如： \[ f\left(u, v\right) = \left((2 + \cos u)\cos v,(2 + \cos u)\sin v, \sin u\right) \] 就是一个参数方程。在例如： \[ f\left(u, v\right) = \left(\cos u \sin v, \sin u \sin v, \cos v\right) \] 表示一个球面。
点云
用一系列空间中三维的坐标来表示物体。点越密集，所形成的模型效果越好。一般会使用点云生成三角形面。
多边形面
一般使用三角形或者四边形来表示。
使用 Wavefront Object File（.obj）格式的文件来存储。在 obj 文件中定义了顶点坐标，法线方向以及纹理坐标还有它们之间的关系，如下所示：
1 | # This is a comment |
曲线
贝塞尔曲线
de Casteljau 算法
先考虑 3 个控制点的情况：使用 3 个控制点画出的贝塞尔曲线称为二次贝塞尔曲线（quadratic Bézier），算法如下：
对于 \(b_0\)、\(b_1\)、\(b_2\) 定义的贝塞尔曲线，我们将求贝塞尔曲线的过程转换成求在 \(t\left(t\in\left[0,1\right]\right)\)时刻，对应贝塞尔曲线上的点。
- 求出线段 \(b_0b_1\) 和线段 \(b_1b_2\) 上对应 \(t\) 时刻的点 \(b_0^1b_1^1\)；
- 将 \(b_0^1b_1^1\) 连接起来后，重复步骤 1 即可。点 \(b_0^2\) 就是我们得到的最终点。
考虑多个点的情况：仿照三个点的情况，每一次都在对应线段上找到对应时刻 \(t\) 所对应的点，并将相邻的点连成线段后重复上面的过程，直到得到最后一个点。
可以看出，de Casteljau 算法是做了多次的线性插值。
贝塞尔曲线的代数公式
贝塞尔曲线的代数公式为： \[ b^n = b^n_0 = \sum ^n _{j = 0}b_jB_j^n(t) \] 其中 \(B^n_j\) 是 Bernstein 多项式，它可视为对 \(\left[1 + \left(1-t\right)\right]\) 的二项展开。 \[ B_j^n(t)=\left(\begin{array}{l} n \\ i \end{array}\right) t^i(1-t)^{n-i} \]
贝塞尔曲线的性质
- Bernstein 所有项的和为 1；
- 贝塞尔曲线必须过起点和终点；
- 对于 3 次贝塞尔曲线来说，起点处的切线为 \(b'(0) = 3(b_1 - b_0)\)，终点处的切线为 \(b'(1) = 3(b_3 - b_2)\)。
- 仿射不变性。贝塞尔曲线做仿射变换生成的曲线等同于对贝塞尔曲线的控制点做仿射变换后再生成的贝塞尔曲线，这个规律不适用于投影变换。
- 凸包性。贝塞尔曲线一定在控制点所形成的凸包内。凸包是能够包围所有点的最小凸多边形。
逐段定义贝塞尔曲线
当我们使用过多的控制点定义一条曲线时，曲线会变得比较平滑，并且不便控制。因此我们一般使用逐段的方式定义贝塞尔曲线。我们每次使用 4 个控制点，把前两个点和后两个点各看作一个控制杆来控制整个曲线。这正是 Photoshop 中的钢笔工具的基本原理。
曲线的连续
\(C^0\) 连续：\(a_n = b_0\).
\(C^1\) 连续：\(a_n = b_0 = \frac{1}{2}(a_{n - 1} + b_1)\).
样条曲线
https://www.bilibili.com/video/av66548502/?from=search&seid=65256805876131485&vd_source=76a5184e318e57fe3ff6a57c443142ad
曲面
可以将贝塞尔曲线拓展到贝塞尔曲面。
贝塞尔曲面
贝塞尔曲面的计算类似于双线性插值的过程。我们使用 \(4 \times 4\) 个点形成贝塞尔曲面。首先，我们在每一行生成 4 条贝塞尔曲线，接下来在 4 条贝塞尔曲线上找到相同时刻对应的 4 个点生成一条新的贝塞尔曲线。这些贝塞尔曲线的集合形成了贝塞尔曲面。
对于贝塞尔曲面，我们需要两个变量 \(u\)、\(v\) 对其进行数学表示。
网格操作
- 表面细分
- 表面简化
- 网格正则化
网格细分
Loop 细分
Loop 细分适用于只有三角形面的模型。首先，将将三角形三条边的中点连接起来，这样 1 个三角形就变成了 4 个三角形。称每条边上的中点为新顶点，三角形原来的三个点为旧顶点。
对于新顶点，采用如下公式更新其位置：
\[ \frac{3}{8}\left(A+ B\right) + \frac{1}{8}\left(C + D\right) \]
对于旧顶点，设其度为 \(n\)，其更新公式为：
\[ (1 - n\times u)\times \text{original\_position} + u\times \text{neighbor\_position\_sum} \]
其中： \[ u =\left\{\begin{array}{lc} \frac{3}{16} & n = 3 \\ \frac{3}{8n} & \text { otherwise } \end{array}\right. \]
Catmull-Clerk 细分
Catmull-Clerk 细分适用于某些面是非三角形的时候进行细分。我们做出以下定义，如果一个面是四边形，那么称为四边形面，反之为非四边形面。任何一个度不是 4 的点都称为奇异点，反之为非奇异点。
每一次细分我们都在每一条边的中点产生新的顶点，并在每一个面上引入一个中点，将面的中点和边上的中点相连，这就是一次细分操作。这样的细分操作满足一下规律：
- 在第一次细分后，所有原本是非四边形内部都会引入奇异点，并且所有的面都变成了四边形面；
- 之后的细分，不会再引入新的奇异点，所有的面都是四边形面。
对于面心的点 \(f\)，计算公式为： \[ f = \frac{v_1 + v_2 + v_3 + v_4}{4} \]
对于边上新生成的中点 \(e\)，计算公式为: \[ e = \frac{v_1 + v_2 + f_1 + f_2}{4} \]
对于旧顶点 \(v\)，计算公式为： \[ v = \frac{f_1 + f_2 + f_3 + f_4 + 2(m_1 + m_2 + m_3 + m_4) + 4p}{16} \]
网格简化
网格简化（Mesh Simplify）通过减少模型的面数简化模型。对于一个模型，我们可以通过构造不同的层级，在不同的情况下选择不同的模型。
我们使用坍缩（Collapsing）的方式进行网格简化。我们将边坍缩变成一个点。我们希望这个点和旧顶点连接后与之前的形状差不多，因此我们引入二次误差度量（Quadric Error Metrics）来度量任意一点与旧顶点连接后与原来的相似程度，并选择最小值作为结果。
在模型中，当我们进行坍缩的时候，我们会对所有可以坍缩的点进行排序，每一次探索误差最小的点后，更新这个点周围的点新的误差值。这里采用堆或者优先队列的方式进行实现。
网格简化是一种贪心算法，我们使用局部的最优解并认为是全局最优的结果。