• 参考书籍：Polygon mesh processing，2010
• 大约分8篇，这是第一篇

0. 前言

3D 获取技术

• 计算机断层扫描（computer tomography）
• 核磁共振成像（MR，magnetic resonance imaging）
• 3D 激光扫描 （3D laser scanning）
• 超声 （ultrasound）
• 雷达 （radar）
• 显微成像（microscopy）

Botsch的几何处理管线

输入数据–>移除拓扑和几何错误–>分析表面质量–>表面平滑（噪声去除）–>参数化–>化简–>重网格化以提升网格质量–>自由形式和多分辨建模（Freeform and multiresolution modeling）

1. 表面表示

引言

• 从高层角度，表面可分类为参数化表示（parametric representations）和隐式表示（implicit representations）
  • 参数化表示形式化为：$f:\Omega \to \mathcal{S}$， 其中$\Omega \subset {\mathbb{R}}^2$， $\mathcal{S}=f(\Omega )\subset {\mathbb{R}}^3$
  • 隐式表示形式化为：$F:{\mathbb{R}}^3\to \mathbb{R}$， S={x∈R3∣F(x)=0}\mathcal{S}=\{x\in \mathbb{R}^3|F(x)=0\}S={x∈R3∣F(x)=0}

例：平面中圆的表示

• 参数化表示： $f:[0,2\pi ]\to {\mathbb{R}}^2$, $t\to (\cos t,\sin t{)}^T$
• 隐函数：$F:{\mathbb{R}}^2\to \mathbb{R}$, $(x,y)\to \sqrt{(x^2+y^2)}-1$

• 复杂形状，通常将函数域分为若干子区域，使用独立的函数（surface patch）表示每个子块。这种定义称为分段定义（piecewise）
  • 分段定义中，分段函数只需要局部近似表面
  • 全局近似误差通过子块的大小和数量来控制
  • 分段表示的难点在于如何确保一个块到它相邻块的自然过渡
  • 参数化方法中，通常把表面划分为三角形或四边形（quadrangles）
  • 非参数化方法中，通常把嵌入空间划分为六面体（hexahedral，也就是体素）或四面体单元（tetrahedral cells）
• 对不同的几何操作，两种表示方式各有优劣
  • 常见的几何操作包括：评估（evaluation）、查找（query）、修改（modification）
  • 两种表示在效率（efficiency）和鲁棒性（robustness）上互有取舍

表面的定义和性质

• Surface 在计算机图形学应用中的定义是：一个有向的、连续的2D 流形嵌入进 ${\mathbb{R}}^3$ 空间
  • 一个非退化（non-degenerate）3D 实体的边界面
• 从采样点生成具有连续性质的表面表示
  • 测地线邻接关系，适用于参数化方法。参数化连续表面具有局部流形性（local manifoldness），或者说拓扑等价性（topologically equivalent）。通过插值采样点或者近似，得到连续性的表面
• 除连续性外，表面应该是平滑的（$C^k$连续）
• 表面还应该是光顺的（fairness）

近似能力（逼近能力，approximation power）

• 每个块的函数限制为多项式族，以方便代数运算
• 每个平滑函数应该能被任意精度的多项式逼近（Weierstrass定理）
• 微积分中$C^{\infty }$函数有界时，在一段长度$h$上可以用$p$阶多项式逼近，且误差为$O(h^{p+1})$
  • 通过提升$p$提升精度（p-refinement）
  • 通过减少$h$提升精度（h-refinement）
  • 几何处理应用更喜欢h-refinement，为什么呢？高阶多项式难以保证$C^k$连续；计算机计算困难
• 逼近误差可使用中值定理计算

参数化表面表示

• 参数化表示的好处是函数可以简化许多3D问题
• 但同时，生成参数化表面表示本身十分复杂，盖因参数域需要同时匹配拓扑和度量结构
• 更改参数化表面的拓扑也十分复杂，空间查找也是参数化表面的弱点

样条表面

• NURBS
  • 基于张量积的样条表面，bi-degree $n$，是由若干多项式patch以$C^{n-1}$方式拼接而成

$$\begin{gathered} f:[u_n,u_m]\times [v_n,v_m]\to {\mathbb{R}}^3 \\ (u,v)\to \sum _{i=0}^m\sum _{j=0}^k{c}_{ij}{N}_i^n(u)N_j^n(v) \end{gathered}$$

• $c_{ij}$是网格控制点，每个表面点$f(u,v)$可以看做控制点的凸集组合
• 由于基函数的局部支撑性，每个控制点只有局部影响
• 局限性
  • CAD中，模型除拓扑约束（topological constraints）外，还需要几何约束（geometric constraints），十分复杂
  • 添加控制点，影响范围较大

细分表面

• 与样条的区别在于，通过连续精化控制网格，可以表示任意拓扑的表面
• 细分表面不受拓扑或几何约束的限制
• 但细分表面对生成的网格有要求，细分连续性（subdivision connectivity）

三角网格

• 每个三角形可通过重心参数化表示

$$\begin{gathered} p=\alpha a+\beta b+\gamma c \\ \alpha +\beta +\gamma =1,\alpha ,\beta ,\gamma \ge 0 \end{gathered}$$

• 欧拉方程

$$V-E+F=2(1-g)$$

• $g$是亏格（genus）
• 网格统计性
  • 三角形数是顶点数的约两倍
  • 边数是顶点数的约三倍
  • 平均顶点价（入射边数）为6

隐式表面表示

• 很多隐函数的选择
• 只要隐函数是连续的，隐式表面就没有空洞；此外，隐式表面是势函数的一个水平集，几何自交也不会发生
• 通过更改隐函数的值（减少=扩张；增加=收缩）可以使表面变形
• 使用符号距离场可以很方便查询、距离计算等
• 隐式表面表示对生成采样点、寻找测地线邻居、表面渲染等任务十分困难；此外，缺乏参数化方法，进行纹理贴图也很难

规则网格（Grids）

• 在目标的包围盒内离散化致密网格
• 每个网格得到标量，形成一个统一的（uniform）的标量场（scalar grid）；体素内的函数值通过三线性插值求得，因此提供了二次逼近阶
• 缺陷：内存消耗立方体地上升

自适应数据结构

• 层次八叉树（hierarchical octree）
  • Three-color octree，将空间划分为白色（outside）、黑色（inside）与灰色（surface），只精化灰色单元（cell）
  • Adaptive sampled distance fields（ADF），只在曲率变化大的区域精化，进一步减少存储复杂度
  • Binary space-decomposition，类似的逼近能力，稍微好一点的内存效率

转换方法（Conversion Methods）

• 因为两种表示方式都是有限采样（例如三角网格之于参数化；统一/自适应网格之于隐式表示），转换一定是有损的

参数化到隐式

• 参数化到隐式变换相当于计算或逼近它的符号距离场
  • 使用体素化或3D扫描转换技术可以高效做到，但得到的解决是分段同质（piecewise constant）的，实际上表面的富豪距离应该不是处处平滑的，而是分段线性或分段三线性逼近
  • 因此，需要平衡逼近的效率和计算效率
• 对多边形网格来说，就是计算3D网格结点到三角网格的符号距离
  • 如何计算网格结点到最近三角形的距离？kd-trees
  • 还需要确定符号，是inside还是outside
  • 对全局来说，可以使用fast marching方法加速

隐式到参数化

• 隐式或体积表示到三角网格的转换，也可称为等值面提取（isosurface extraction），经典算法是marching cubes
  • marching cubes的改进
  • 其他方法，dual contouring，cubical marching squares algorithm
• 另一类方法是精化和滤波一个3D Delaunay 三角剖分（triangulation）

小结

• 两类surface representations，parametric VS. implicit

  • 参数化的优势：采样、细节、直接修改；不足：距离查询、拓扑更改
  • 隐式表面的优势：拓扑更改、距离查询；不足：采样、形状编辑、细节（分辨率）

• 混合表示（如自适应八叉树）兼具二者优点

• 二者的转换方法（conversion techniques）

• 其他表示方法——径向基函数、基于点的表示等等