Shape Analysis课程笔记05-Smooth and Discrete Surface
这个系列是MIT 6.838: Shape Analysis的同步课程笔记。本课程会介绍几何方法在图形学、机器学习、计算机视觉、医疗图像以及建筑设计等相关领域的原理和应用。本节主要介绍曲面的基本理论。
Theoretical Definition
Embedded Surface
从本节课开始我们会逐步介绍曲面(surface)和流形(manifold)的相关概念。简单来说，我们可以认为曲面是一个二维平面通过(可微)映射\(f\)嵌入到三维空间的结果。
当然这样的定义会引入很多问题，比如说下面的三个映射都满足上面的定义但映射的结果都不符合我们对于曲面的认知。
回忆Jacobian矩阵(Jacobian matrix)给出了映射在局部的线性变化，当\((Df)\)不满秩时会出现曲面退化的情况。因此我们要求曲面的Jacobian矩阵必须满足满秩的条件。
上面提到的曲面本质上是由一个参数平面来定义的，因此也称为参数曲面(parametric surface)。在很多情况下我们并不需要参数平面的存在仍然可以得到定义良好的曲面，即我们只需要满足某些性质的点集就可以去定义曲面。
我们认为尽管曲面本身是三维空间中的对象，但是在曲面上的每一点的局部上仍然可以看做是一个二维的平面。
要严格定义曲面需要涉及到submanifold的概念。对于n维空间中m维的submanifold，其定义如下：
综合上面的内容可以认为曲面的局部都是平面，而这个平面也称为切空间(tangent space)。
Tangent Space
除此之外还可以从曲线来认识切空间。对于曲面上经过\(\mathbf{p}\)点的曲线\(\gamma\)，我们定义\(\mathbf{p}\)点的切空间为满足\(\gamma(0)=\mathbf{p}\)的所有曲线在该处切向量的集合。
如果从微分的角度来考虑，切空间可以认为是局部参数化的像。
实际上切空间的这两种定义是等价的。
Normal Space
在切空间的基础上我们可以进一步定义normal space，它是垂直于切平面法向量的集合。
而利用normal space我们还可以定义曲面(submanifold)是否是可定向的。
Manifold
这里我们正式给出流形的定义：
Discrete Representations
Triangle Mesh
那么如何在计算机中表示曲面呢？最常用的方法是使用三角网格(triangle mesh)，即使用三角形来近似局部的曲面。
三角网格更严格的定义是顶点(vertex)、边(edge)以及面(face)的集合，这些元素也称为单纯复形(simplicial complex)。当然它们还需要满足流形的拓扑性质，显然并不是所有的三角网格都满足曲面的要求。
Mesh Topology vs. Geometry
简单来说这里的拓扑是指依赖于顶点的连接关系而不是具体位置的几何量。
Nonmanifold Edge
尽管本课程中我们主要关注流形的三角网格，但在实际应用中仍然会使用非流形的网格。
Manifold Triangle Mesh
对于流形的三角网格，我们要求网格上的每一条边只能与一个面或两个面相连，而且同一顶点的相邻面需要构成一个封闭或开放的圆盘。
在实际应用中人们可能会出于各种各样的原因主动违背流形的假设，在这种情况下要进行几何分析的话需要额外注意。
Advantages
显然分片线性的三角网格是对曲面的一个合理近似，随着网格面片数的增加我们可以得到更加接近于真实曲面的表达。而三角网格的一些其它好处包括很容易进行渲染、可以表达各种拓扑形式的几何对象以及便于进行细分和修正等。
Mesh Quality
除此之外，即使是满足流形约束的网格本身也有质量的好坏。在大多数情况下我们希望网格的分布是尽可能均匀的。
Valence
我们可以把网格上任意顶点相连的边的数量称为顶点的valence或者degree，利用这个概念就可以描述网格的一些拓扑性质。
Euler Characteristic for Mesh
欧拉示性数(Euler characteristic)\(\chi\)是网格重要的拓扑性质。根据欧拉公式有：
\[V - E + F = \chi\] \[\chi = 2 - 2g\]其中\(g\)称为网格的亏格(genus)，它可以理解为曲面上的孔洞数。上式说明对于任意形式的曲面，只要它们具有相同的亏格数，网格的顶点数、边数以及面数一定满足欧拉公式。
Consequenses for Triangle Meshes
注意到对于没有边界的网格，每条边都对应两个面而每个面都包含三条边，我们可以得到面和边的关系式：
\[2E = 3F\]
带回欧拉公式可以得到：
\[V - \frac{1}{2} F = \chi\] 在大多数情况下网格的亏格数都比较小，因此可以得到近似式：
\[F \approx 2 V\] 此时网格的边和面数都可以近似用顶点数来表示，而且网格顶点的平均valence约为6：
\[E \approx 3 V\] \[F \approx 2 V\]
Orientation
在前面我们介绍过可定向曲面的概念，在连续情况下可定向曲面的法向量场是一个连续场。
而对于离散曲面来说我们则需要在三角网格上定义法向。在三角面片上这不是一个大问题，但对于顶点和边则需要仔细考虑。
对于三角面上的法向量我们可以利用右手法则来进行计算，这样就可以用平面上的法向来近似曲面的法向。不过这里需要注意的是此时三角面片上的顶点是有顺序的，而且此时网格上的法向量场也是不连续的。
Data Structure for Surface
接下来考虑如何在计算机中存储和表示曲面的问题，显然我们希望离散的网格既可以表示曲面的几何信息又可以表示曲面的拓扑性质。
Triangle Soup
最简单的表达方式是直接记录网格上每个面以及每个面上顶点的坐标，早期的一些图形库像OpenGL就使用了这样的方式来存储网格。它的主要缺陷在于我们无法从顶点数据中获得曲面拓扑性质，因此这种表示方法在几何处理中几乎不会使用。
Shared Vertex Structure
另一种常见的表达方式是分别记录每个面上顶点的编号以及顶点的坐标。这种方式可以避免顶点坐标的反复记录，因此常见于各种三维模型的存储格式中。
但遗憾的是这样的表达方式对于几何处理同样不够友好。比如说我们想要对网格进行平滑滤波，即使用相邻顶点坐标的平均值来更新当前顶点的位置，此时如果使用上面提到的表达方式在获取相邻顶点时是非常困难的。
实际上在几何处理中我们经常需要去获取网格的一些局部信息，因此我们需要设计合适的数据结构来方便我们进行查询。
Halfedge Data Structure
半边(halfedge)是网格处理中非常流行的一种数据结构。在这种表达方式中我们会把半边作为数据结构的核心，并且结合网格的顶点和面来查询局部信息。
具体来说半边是网格上边在其对应面上的部分，半边的方向即为该面上的方向。
在每个顶点上需要记录所有以该顶点为起点的半边，每个面上需要记录所有与该面相邻的半边，而每条半边自身还需要记录它的反向半边(flip)、下一条半边(next)以及半边自身的起点和所在面的编号。
利用半边数据结构可以简单地访问任意顶点的所有相邻顶点：
除此之外半边数据结构还可以方便地转换为对偶形式。假设有一个函数\(f\)将曲面上每一点映射为一个实数，对于离散曲面我们可以使用一个数组记录下每个顶点处的函数值来表示\(f\)。
这样的表达形式当然是可以的，但如果我们需要对函数进行积分则会导致一些其它的问题，比如说我们无法在顶点上定义被积元素\(dA\)。
为了解决这个问题我们需要引入dual cell的概念，这样我们就为每个顶点赋予了一定的面积，而函数的积分等于顶点处函数值与dual cell面积的乘积。
实际上利用dual cell我们可以在原始网格的基础上定义一个对偶网格，这样同一个曲面就对应了两个网格：
同样地，对偶网格也可以使用半边数据结构来进行表示。
这两个网格之间的转换可以使用\(\star\)算子来表示，原始网格上的半边通过旋转就得到了对偶网格上的半边。
总结一下，半边数据结构虽然在构造时相对复杂，但可以方便我们实现各种几何处理算法。
Other Representations
最后需要说明的是尽管三角网格是目前最常用的离散曲面表达方式，但在具体应用中还是有非常多的备选。像是机器学习中常见的有向距离场(signed distance field, SDF)、流体仿真中常用的隐式曲面(implicit surface)甚至点云等都可以表示复杂的曲面。
