GAMES102_note
GAMES102-几何建模与处理 Geometry Modeling and Processing 这个笔记的主要内容分为两部分，一部分是对于课程内容脉络的梳理，整理我最后记住的每个章节的内容；另一部分是我觉得更重要的，是关于一些零散知识点的整理，这里涉及到的知识点结合了自己过往的学习内容，纳入了自己的思考。
数据拟合
基函数的选取与秦九韶算法
在考虑数值逼近（插值或拟合）问题的时候，合适的基函数是非常重要的，按Weierstrass定理，任意闭区间上的连续函数都可以用多项式级数一致逼近。但是在进行插值的过程中，选取什么形式的多项式函数作为基函数值得考虑。
显然，由{ $1, x, x^2, \cdots, x^n$ }是可以张成一个维数为 $n+1$ 的多项式函数空间的，但是为什么我们不用这种方法来计算插值呢？主要原因以下几点
- 计算开销上的困难：虽然求解系数的线性方程组的系数矩阵是Vandermonde矩阵，其本身是非退化的，但是Vandermonde矩阵的条件数增长速度非常快， $n$ 阶的Vandermonde矩阵的条件数至少是 $2^{n-2}$ ，带来的计算开销过大了；
- 高阶多项式插值带来的Runge现象，这其实从根源上限制了 $n$ 必须非常小。
因为这些原因，我们放弃了直接以幂函数作为基函数进行多项式插值的方法，寻求其他办法（Lagrange插值或Newton插值）。
此外，怎么通过计算机计算 $a_0 + a_1x + a_2x^2 + \dots + a_nx^n$ ，答案是秦九韶算法：
\[sum = (((a_nx + a_{n - 1})x + a_{n - 2})x + \dots + a_1)x + a_0\]相比于直接计算，秦九韶算法需要更少的计算次数，用常规方法计算出结果最多需要 $n$ 次加法和 $\frac{n^2+n}{2}$ 次乘法，而秦九韶算法最多只需 $n$ 次加法和 $n$ 次乘法。
从基函数到RBF函数到神经网络
在人工神经网络的数学理论中，通用近似定理（万能近似定理）意味着神经网络可以用来近似任意的复杂函数，并且可以达到任意近似精准度。但它并没有说明要如何选择神经网络参数（权重、神经元数量、神经层层数等）来达到想近似的目标函数。这其实可以看做是Weierstrass定理的一个推广。
常用的用来搭建神经网络的底层函数包括了径向基函数，其中最常用的是Gauss函数。由于其具有可线性组合及局部支撑的性质，因此通过调参可以很好地拟合高维函数。
虽然神经网络是一个比较新颖的领域，但是它的本质就是处理优化问题，和传统的数值逼近在思想上是一致的，但神经网络进行优化的目标与传统逼近的目标是不同的（二者对于精度的要求和保证强度不一样），由此产生了差异。
参数曲线拟合：利用参数化拟合二维空间中的曲线
多元函数拟合
利用在不同维度的基函数，通过张量积的形式就可以拟合在高维空间中的多元函数。
- 优点：定义简单，仅需要表示成多个一元基函数的乘积形式，且每个维度上的一元基函数可以是相同形式的；
- 不足：随着维数的增加，基函数个数急剧增加，导致变量数急剧增加，求解的代价随之增加。
除去一维的基函数作张量积以外，仍然可以通过神经网络的方法来拟合多元函数。
参数曲线拟合
目标是极小化误差：$\min E = \sum_{i = 1}^n |\mathbf{p}(t_i) - \mathbf{p}_i|^2$
重点在于如何进行参数化：
- Equidistant parameterization 均匀参数化
- Chordal parameterization 弦长参数化：比均匀参数化更合理
- Centripetal parameterization 中心参数化：基于物理的观点考虑了归一化
（具体在《计算机辅助几何设计与非均匀有理B样条》一书中有说明）
结论：好的曲线拟合需要好的参数化设计，因为这其实保持了原本形状的某些几何特征。在曲面参数化中，需要利用的就是局部面积或局部角度等，也是从保持局部几何特征这个想法出发的。
三次样条函数
样条函数
构建线性系统可以通过三弯矩方程，也可以通过三转角方程。其优点在于：
- 三对角矩阵使得其为稀疏矩阵
- 对角占优保证其必然有解
- 可以通过追赶法来求解（计算效率？）
几何连续性
引入几何连续性的原因：参数连续性 依赖于参数 的选择，同一条曲线，参数不同，连续阶可能是不同的。
Bezier曲线 B样条曲线
建模的两种形式
- 重建（Reconstruction）：
- 逆向工程：形状已有，要将其“猜”出来；
- 采样->拟合：需要函数空间足够丰富（表达能力够）；
- 代数观点：${a, b, c}$ 作为基函数的组合权系数。
- 设计（Design）
- 自由设计：凭空产生，或从一个简单的形状编辑得到；
- 交互式编辑：几何直观性要好
- 几何观点：基函数 ${t^2, t, 1}$ 作为控制点的组合权系数。
也就是说对于重建数据点是给定的，关键在于选择合适的拟合方案；而对于设计来说，基函数是固定的，关键在于控制点的选取，及设计出什么图案，此时基函数应该尽可能更好地表达几何特性。
NURBS曲线 细分曲线 隐式曲线 NURBS曲面
细分曲线
两个步骤：
- 拓扑规则：加入新点，组成新多边形；
-
几何规则：移动顶点，局部加权平均（加权平均的变换矩阵特征值决定了细分方法能否收敛、结果曲线是否光滑）
- 逼近型细分方法（Chaikin割角法)
- 每条边取中点，生成新点
- 每个点与其相邻点平均
- 迭代生成曲线
- 插值型细分方法（补角法）
- 保留原有定点
- 对每条边，增加一个新顶点
- 不断迭代，生成一条曲线
隐式曲线
- 隐式曲线绘制：Marching Cube，想法是通过计算格点隐式函数值之后作插值，连接插值为0的点
- 隐式曲线拟合：
- 估计法向：利用邻近点来估计切平面；
- 借助各点及其法向，拟合一个二元函数：在型值点上值为0，外部（法向方向的点）为正，内部为负。
NURBS曲面
利用两组NURBS曲线作张量积就可以得到NURBS曲面，其继承了NURBS曲线的性质，“曲线的曲线”。
曲线光顺 离散曲线 三角网格
曲线光顺（fairness）
与曲线各点处曲率有关。工业设计不希望曲线上存在过多拐点（曲率大小为0的点），减少磨损或消耗。但是曲线的光顺性没有一个统一的定义，通过减少曲率的单调区间数量，可以一定程度上提高曲线的光顺性。
离散曲线
曲线的不同表达方法：
- 显示函数曲线
- 参数曲线
- 隐式曲线
- 细分曲线
图形变形
通过改变控制顶点，借助三角形各点的重心坐标（Barycentric）表示进行相应变换，就可以实现图形的变形。
曲面离散（三角网格）
曲面网格的数据结构：
半边数据结构（half-edge data structure）
- 只能表示流形网格
- 数据结构：
- 顶点：包含顶点坐标和出半边的索引；
- 半边：包含起始点、邻接面、下一条半边、上一条半边的索引；
- 面片：包含一条起始边的索引。
考察三角网格曲面的观点：
- 曲面你的离散逼近
- 采样：顶点为从曲面上的采样点
- 本质：分片线性逼近
- 平面图的嵌入
- 平面图的顶点提升至三维空间
- 本质：二维流形
离散微分几何
估计网格上的微分属性的两类方法
- 连续估计(Continuous approximation)
- 先利用网格信息拟合曲面，然后计算拟合曲面上的微分属性
- 离散估计
- 直接近似估计网格上的微分属性
微分坐标（Laplace坐标）
离散形式的Laplacian算子：
$\delta_i = v_i - \sum_{j \in N(i)} \omega_jv_j$
其中权重的选取方案（之后要做归一化处理）：
- 单位权重：$\omega_j = 1$
- 余切权重：$\omega_j = (\cot \alpha + \cot \beta)$
应用：光滑曲面、曲面重建
所谓的能量最小化：顶点到周围点距离的平方和最小
曲面参数化
参数化：将曲面展开成平面，每个3维顶点 $(x, y, z)$ 对应一个2维点 $(u, v)$。
参数化是几何处理中的基本问题：
- 提供了三维曲面每个点的一个二位参数（本征维数参数）；
- 在低维空间处理高维问题，减少复杂度；
- 三维曲面之间的相关问题可以通过参数化空间来处理。
Laplacian Editing
用户通过修改一个点的位置，改变网格的姿态
曲面去噪 采样与剖分
去噪
What is noise? 没有一个严格的数学定义，而且如何区分噪声和特征也值得讨论
- High-frequent tiny parts
- Small bumps on the surface
- High curvature parts
- High fairing energy parts
网格光滑
- 假定：网格顶点的数据及连接关系不变
- 问题转化为：求新顶点的位置，使得“噪声”减少
- 顶点进行适当的扰动或偏移
- 可以基于Laplacian曲率进行光顺，但是涉及到主观的具体的参数设置
滤波
- 卷积：利用权函数，借助原函数各点周边的值对原函数进行加权
- 往往人们会选取高斯函数作为加权函数
- 滤波对象：
- 顶点
- 法向
- 曲率
- 颜色
- 其他物理特征（纹理、反射率等）
保特征的顶点滤波：双边滤波，加权的时候除了点的位置关系还考虑值的大小，如果值差距过大，则权重会变小。
对法向进行滤波：通过求解一套新的法向后，重建网格顶点
采样与剖分
Delaunay三角剖分与Voronoi图
网格生成
- DT只能保证当前采样点的网格是好的，但是修改采样点的位置可以提高网格质量
- Centroidal Voronoi Tessellation(CVT) 使得voronoi图的顶点和每个区域重心重合（迭代）
- Lloyd Algorithm
- ODT