1. 曲面的定义与性质
1.1. 曲面的数学表达
曲面可以通过参数表达和隐式表达进行建模：
-
参数表达
- 函数域
- 定义为曲面片
$$
\pmb f:\mathbb R^2\rightarrow\mathbb R^3,\quad S_\Omega=\pmb f(\Omega)
$$ -
隐式表达
- 函数核
- 定义为水平集
$$
F:\mathbb R^3\rightarrow \mathbb R, \quad S_c={\pmb p:F(\pmb p)=c}
$$
示例：球的几何表达
-
参数表达：
$$
\pmb f:t\rightarrow \begin{pmatrix}r\cos t\\r\sin t\end{pmatrix},\quad
S=\pmb f([0,2\pi])
$$ -
隐式表达：
$$
F(x,y)=x^2+y^2-r^2,\quad S={(x,y):F(x,y)=0}
$$
1.2. 曲面的性质
-
连续性
- 插值/逼近，用于建立起原始数据采样点之间的连续关系：$\pmb f(u_i,v_i)\approx \pmb p_i$
-
拓扑一致性
- 在图形学应用中，曲面通常是定义为嵌入$\mathbb R^3$中的可定向连续的二维流形
- 直观理解：非退化三维实体的边界表面，其中非退化意味着该实体没有任何无限薄的部分或特征，因此该表面正确地分隔了实体的“内部”和“外部”，有边界的曲面可以通过填充孔延伸到适当的流形曲面中
- 如下图所示，左上角连接顶点为一个退化/非流形顶点，可以通过右上角进行修正；左下角连接边为一个退化/非流形边，可以通过右下角进行修正
-
光滑性
- $C^0$：位置连续，$\pmb f(t_1)=\pmb f(t_2)$
- $C^1$：切线连续，$\pmb f'(t_2)=\pmb f'(t_2)$
- $C^2$：曲率连续
- ……
-
光顺性
-
最小表面积
-
最小曲率
-
最小曲率变化
-
1.3. 逼近误差
在几何处理中常常使用多项式基函数进行曲线和曲面进行建模
-
拟合方程
$$
\pmb p(t)=\sum_{i=0}^p\pmb c_it^i=\sum_{i=0}^p\pmb c_i'\Phi_i(t)
$$ -
泰勒展开
$$
\pmb f(h)=\sum_{i=0}^p\frac{1}{i!}\pmb f^{(i)}(0)h^i+O(h^{p+1})
$$ -
插值误差
$$
\pmb p(t_i)=\pmb f(t_i),\quad t_i\in[0,h]
$$$$
\|\pmb f(t)-\pmb p(t)\|=\frac{1}{(p+1)!}\pmb f^{(p+1)}(t^{\ast})\prod_{i=0}^p(t-t_i)=O(h^{(p+1)})
$$
对于隐式多项式，插值误差为：
$$
\|F(x,y,z)-P(x,y,z)\|=O(h^{(p+1)})
$$
边界误差：
$$
\Delta \pmb p=\lambda \nabla F(\pmb p)
$$
$$
\frac{F(\pmb p+\Delta\pmb p)-F(\pmb p)}{\|\Delta\pmb p\|}\approx \|\nabla F(\pmb p)\|
$$
总结：
-
逼近误差为$O(h^{p+1})$
-
提高逼近质量：
- 增大$\pmb p$，使用更高阶的多项式基函数
- 减小$\pmb h$，使用更小/更多细分片
-
存在的问题：
- 目标数据的光滑性（$\max_tf^{(p+1)}(t)$）
- 处理更高阶的块，如边界条件
1.4. 参数曲面表达
1.4.1. 样条曲面
张量积曲面定义为：
$$
\begin{aligned} \boldsymbol { f } ( u , v ) & = \sum _ { i = 1 } ^ { n } \sum _ { j = 1 } ^ { m } b _ { i } ( u ) b _ { j } ( v ) \boldsymbol { p } _ { i , j } \\ & = \sum _ { i = 1 } ^ { n } b _ { i } ( u ) \sum _ { j = 1 } ^ { m } b _ { j } ( v ) \boldsymbol { p } _ { i , j } \\ & = \sum _ { j = 1 } ^ { n } b _ { j } ( v ) \sum _ { i = 1 } ^ { m } b _ { i } ( u ) \boldsymbol { p } _ { i , j } \end{aligned}
$$
其中，$\pmb p_{ij}$为控制点，$i\in[1,n],j\in[1,m]$
1.4.2. 细分曲面
- 提供几何体的粗略表示
- 获得光滑的表示
- 通过递归进行实现
1.4.3. 三角网格
在几何处理算法中经常使用三角网格进行处理，三角网格$\mathcal M$包含一系列几何和拓扑结构，可以通过一个顶点集合的图结构进行表示：
$$
\mathcal V=\{v_1,\cdots,v_V\}
$$
通过一个面的集合将各个顶点进行连接
$$
\mathcal F=\{f_1,\cdots,f_F\},\quad f_i\in\mathcal V\times\mathcal V\times\mathcal V
$$
有时存储各个边能够方便算法实现：
$$
\mathcal E=\{e_1,\cdots,e_E\},\quad e_i\in\mathcal V\times\mathcal V
$$
三角网格的性质：
- 欧拉公式：$V-E+F=2(1-g)$
- $F\approx V$
- $E\approx 3V$
- 平均顶点价（入射边数）为6
- $V$：顶点数量
- $E$：边数量
- $F$：面数量
- $g$：曲面的亏格，可以理解为曲面上洞眼的数量
1.5. 隐式曲面表达
-
规则体素网格
-
自适应结构
-
三色八叉树
-
自适应采样距离场（ADF）
-
二进制空间分区（BSP）
-
2. 网格数据结构
2.1. 基于面的数据结构
简单的基于面的数据结构有两种表示方式：
-
面集合：将网格表示为三角形构成的元组的集合
-
索引面集合：将所有顶点顺序存储，并将网格表示为三角形顶点索引构成的元组的集合
- 这种方法弥补了面集合方法的顶点复用问题
但以上表示方法缺乏对网格拓扑信息的有效描述
在几何处理中，常有如下数据结构操作：
- 随机访问单独的顶点、边和面
- 面中边的定向遍历，即在面中查找下一条边（或前一条边）
- 访问边所在的面，根据方向，在流形情况下一定为左侧面或右侧面，这样可用于访问相邻边
- 给定一条边，访问它的两个顶点
- 给定一个顶点，必须至少可以访问一个入射面或边，对于流形网格，可以枚举顶点的单环邻域中的所有其他元素，即所有入射面或边以及相邻顶点
为了使得以上操作更加方便，可以在数据结构中添加相关额外信息，如下所示
但是由于基于边的网格结构不存储关于边的信息，在实际使用中还是有很多不方便的地方
2.2. 基于边的数据结构
由于网格连接性与网格的边息息相关，因此基于边的数据结构能够方便我们进行很多操作，著名的边数据结构有winged-edge，相关数据结构如下所示：
在实际使用中，边数据结构在遍历单环邻域时依然不是太方便，因为需要多次判断顶点和面在边上的方向，在各种几何处理算法中，用到最多的还是接下来介绍的半边数据结构。
2.3. 半边数据结构
半边数据结构在基于边的数据结构的基础上将每一条边分裂为两条有方向的半边，能够直接表达任意多边形网格，因为这些网格是可定向（组合）2流形的子集。在半边数据结构中，半边围绕每个面和沿每个边界以逆时针顺序一致定向。
对于每一条半边，我们可以存储引用：
- 指向的顶点
- 邻接的面（边界半边为空）
- 逆时针顺序的下一条半边或边界
- 当前面内的上一条半边
- 反向的半边
如下所示：
2.4. 定向边数据结构
定向边数据结构是专门为三角形网格设计的半边数据结构的一种内存高效的变体，基于引用网格中每个元素（顶点、面或半边）的索引进行设计。
设$f$为面的索引，则该面的三条半边索引为：
$$
\mathrm {halfedge}(f,i)=3f+i,\quad i=0,1,2
$$
设$h$为半边的索引，则它的邻接面索引为：
$$
\mathrm{face}(h)=h/3
$$
该半边在面中的索引为：
$$
\mathrm{face\_index}(h)=h\mod 3
$$
定向边数据结构的优点是内存友好，而缺点则是缺少边的显式表达。
3. 实现
IlumEngine中实现了面网格、边网格和半边网格三种网格数据结构，使用C++17 pmr内存池进行内存的分配与管理，为了节省时间顶点仅存储vec3位置信息，往后考虑使用模板编程方法扩展为泛型库。
