课程链接：GAMES102几何建模与处理
课程讲师：刘利刚
微信公众号：AlbertLiDesign
Github实现（C#）：https://github.com/AlbertLiDesign/ALDGP
三角网格的理解
三角网格有两个观点，第一个观点是说，点是从曲面上采样的，我们把曲面上相邻的点连成三角形，就构成一张水密的分片线性的表达，所以它是对原曲面的逼近，每个三角形都是一张平面，所以它是一种分片线性的表达。所以从曲面的逼近来看，网格是一个更简单的，低次的曲面，只有连续，它是用一个分片线性逼近函数去逼近一个光滑曲面，如果从泰勒展开的角度也可以看作是网格点处的一阶展开，用局部的平面片去逼近了原来的曲面，也可以把它叫做离散曲面。
另一个观点是认为，网格本质上是一个图（Graph），它只是有一些线和点构成的一张图，就如同我们在数据结构中学到的图结构。我们先从平面上得到一个平面图，然后再把点映射到空间中的某个位置，在拓扑学中叫提升（lifting），即拓扑结构不变，只是把顶点的位置从二维平面变到三维空间，只要有一个函数能把这些点映射到空间，就能形成一张复杂的曲面，所以网格本质上是二维图的空间映射，因此它本质上是二维流形，可以看作是拓扑学中从低维到高维的嵌入（提升），二维平面图可以看作是一个参数域，通过参数化变到空间中的曲面。
网格的数据结构
要想理解三角网格的结构，要理解什么是图结构。图结构由顶点和边组成，生活中有很多的用处，比如我们可以把城市道路看作是边，把十字路口看作是节点，那么就能得到一个城市地图的抽象，去找从一个节点到另外一个节点的最短路径就可以利用图中的算法，这也就是生活中经常使用的导航。
网格的表示可以写成，这里
是顶点集合，
是边集合，
是多边形集合，对于三角网格，
表达的就是三角形集合，任意多边形网格都可以转化成三角网格。需要注意的是，已知顶点集合和边集合（或面集合）可以推出另一个集合，OBJ是最简单的网格表示格式，其表示方法如下
v 1.0 0.0 0.0
v 0.0 1.0 0.0
v 0.0 -1.0 0.0
v 0.0 0.0 1.0
f 1 2 3
f 1 4 2
f 3 2 4
f 1 3 4
只存储了顶点信息和面的信息，表示顶点，后面的三个浮点数为三维空间中的坐标，
表示面，后面的三个正数表示由第几号顶点构成的三角形。例如
表示由第1、2、3号顶点构成了一张三角面片。由顶点信息和面信息我们就可以推出边的信息，只需要对去除重复的边即可。给定顶点坐标和边的连接关系，也可以推出面的信息，只需要去访问与一条边相邻的边即可，如此循环下去最后会找回到自身，一张面也就得到了。给定边集合和面集合无法推出顶点信息，因为它们都是拓扑信息，缺乏几何信息。
非流形结构
对于一个曲面上的任意一点，它的无穷小邻域拓扑同胚于一个小平面，如果不是一个小平面，那么它就是非流形。例如图2(b)，如果我们沿着中间的顶点画一个圈会发现交于两个小平面，因此这个点是一个非流形顶点，其他同理。非流形结构很麻烦，在大多数的几何处理都不讨论非流形结构，微分几何讨论的是流形结构，故非流形结构不在本课程的讨论范围中。
三角网格编程初步
一些对三角网格复杂的操作离不开图的数据结构，在这里我们介绍一种常用的数据结构——半边数据结构（Half-edge data structure）。半边数据结构的思想是把一条边变成两条半边，它是以边为中心的存储，半边会存储它的末顶点、它的下一条半边以及它的面，网上能找到很多关于半边数据结构的介绍。半边数据结构的目的是提高点线面的查询或增删改操作的效率。
下面是一个半边数据结构，一条半边（图3中的红色半边）存储了一个顶点（半边指向的末顶点），它的另外一条半边（方向相反的opposite halfedge），它所指向的面（指向的incident facet）以及它的下一条半边(next halfedge)；一个顶点只需要存储它的顶点以及它所在的半边即可；一张面仅需要存储一条半边。
struct HE_edge
{
HE_vert* vert;
HE_edge* pair;
HE_face* face;
HE_edge* next;
};
struct HE_vert
{
float x;
float y;
float z;
HE_edge* edge;
};
struct HE_face
{
HE_edge8 edge;
};
那么对于这样的结构，我们是否能够很快速地找到所需要的信息呢？答案是肯定的。
- 由一条半边找两个顶点：半边已存储末顶点可以直接访问，而它的相反半边的末顶点其实就是它自身的始顶点，因此查找始顶点只需要访问该半边的相反半边（pair）的末顶点即可。
- 由一条半边找两邻面：半边已存储它所在的面，同理，要想找到它的另一个邻面，可以直接访问它的相反半边存储的邻面即可。
- 由一张面找所有半边：面已经存储一条半边，我们只需要不断地寻找这条半边的下一条半边，直到回到它自身，即可找到面内所有半边。
- 由顶点找所有半边：顶点已存储一条半边，我们找它的相反半边的next即可找到所有经过该顶点的半边。
代码如下：
// 由边找两顶点及两邻面
HE_vert* vert1 = edge->vert; // 末顶点
HE_vert* vert2 = edge->pair->vert; // 始顶点
HE_face* face1 = edge->face; //半边所在的面
HE_face* face2 = edge->pair->face; // 半边相邻的面
// 由面找其所有半边
HE_edge* edge = face->edge // 找到一张面的半边
do
{
// do something with edge
edge = edge->next;
}
while(edge != face->edge)
// 由顶点找其所有半边
HE_edge* edge = vert->edge;
do
{
edge = edge->pair->next;
}
while(edge != vert->edge)
常用的几何处理库有：CGAL、Libigl、Meshlab、OpenMesh、PCL(Point Cloud Library)、TriMesh、DGtal等等。
曲线曲面的微分几何
曲线的微分几何
如图4，给定一条曲线，上面有一个点
，这里的曲线是一条光滑的参数型曲线，例如我们前面学过的贝塞尔曲线。
那么能得到下面的表达式（三维情况），
那么在这个点处求导，
我们知道对向量的求导、求积都是对分量的求导、求积，然后就变成了一个向量，可以证明这个向量与曲线相切，切点为
。
在微分几何里面我们还定义了关于
的导数
（即二阶导数），可以证明
与
不是同向的，把它们两个做叉积就可以得到另外一个方向
，
被称为从法，将
与
再做叉乘，就能得到法向
。由于
就是切向所以我们记为
，这里我们会发现，
、
和
构成了一个互相垂直的直角坐标系，并且遵循右手系，在微分几何里成为Frent frame。我们说，如果一个点非退化，那么这个点处的切线、从法和法相就构成了一个正交的Frent标架。法相就是垂直于切线方向，从法则是指向屏幕里面，如果是空间曲线，我们可以通过找法向与切向构成的平面，再求该平面的法向即是从法。
微分几何中还有一个概念叫曲率，曲率是曲线在该点处弯曲程度的度量，是它的密切圆（osculating circle，也叫曲率圆）的半径的倒数。曲率越大，曲率圆越小，表示它弯的很厉害，直线的曲率为0，曲率半径无穷大。
曲率可以通过一些推导来计算，如下图所示
需要注意的是，曲率与参数化是无关的，也就是说它是曲线的本身属性，即曲线的形状由每个点的曲率所唯一确定，但是相差一个刚性变换，即弯曲的方向可能不同。所以曲率是刻画曲线的几何本身不变量。
曲面的微分几何
曲面的微分几何会稍微复杂一点，如图9给出的一张曲面，给定点，在三维中的曲面是二维流形，因此
的坐标是双参数的，这里用
表示。由于它有两个参数，因此要对两个分量进行偏导，有
分别对进行偏导后得到两个向量，这两个向量一定是不共线的，因此就可以张成一张平面，叫做切平面，切平面上过p点的任何一条线都与曲面有唯一交点，且都是曲面的切线。切平面上有无数条切线，因此切线只有在给定的方向下才有意义。
有了切平面，我们就能求出点的法向，即
与
的叉积，这就得到了曲面在
点处的法向。需要注意的是求得的法向要做归一化处理，即
。
我们以和某一切向
够成一个平面，该平面会与曲面有一条交线，即图12中的黑色曲线，这条曲线就是一条平面曲线，有了平面曲线就可以定义它的一些参数，例如曲率，这个曲率就叫做方向曲率，它是随着方向变化而变化的。可以想象，如果这个
和
构成的平面，以
为转轴旋转，那么就能得到无穷多条交线，那么就会有无穷多个曲率，所以在空间中讨论切向和曲率都是要指定方向的。
主曲率、高斯曲率与平均曲率
可以证明的是，在过曲面上一点的无穷多的曲率中，有两个方向的曲率至关重要，一个是最大曲率，一个是最小曲率
，并且这两个曲率的方向是相互垂直的，对任意曲面都成立，它们成为主曲率。找到了两个主曲率了，根据欧拉公式，其他方向的曲率可以表示为这两个主曲率的线性组合，并且组合系数相加刚好为
，即
是该方向曲率与
所构成的夹角。
图13展示了最小曲率和最大曲率的可视化，可以看到这两个曲率是相互正交的。
由这两个主曲率也可以定义其他的曲率，其中比较重要的曲率是高斯曲率，高斯曲率就是两个主曲率的乘积，
高斯曲率也用来度量曲面的弯曲程度，它是一个等距变换不变量，即当曲面发生变形时，只要两点间的距离不发生改变，那么它就不会变。例如用一张纸，把它卷成一个圆柱或圆锥，这个纸上的度量都不会变化，仅做了弯曲。一个平面的高斯曲率，任何方向都是直线，所以高斯曲率为，除此之外，圆柱和圆锥可以由平面卷起来而成，并没有发生撕裂和挤压，因此可以证明，圆锥和圆柱上的每个点的高斯曲率一定为0。反过来我们说，处处高斯曲率为
的曲面，即通过等距变换可以变成一个平面，那么它就被称为可展曲面。可展曲面可以被展成平面，并过程中不发生任何撕裂、挤压、变形。值得注意的是，还有一种可展曲面叫切线面，即一条空间曲线所有的切线所构造出的曲面，如图14所示。
还有另外一个曲率是平均曲率，即两个曲率的算术平均，
它也有一种特殊的性质，处处平均曲率为的曲面叫做
，极小曲面的面积最小，例如生活中的肥皂泡。
在微分几何中还有一些概念，例如椭球点（elliptic），抛物点（parabolic）和双曲点（也叫马鞍点，hyperbolic）。椭球点的两个主曲率都大于，抛物点是指最大主曲率大于
，最小主曲率等于
的点，双曲点的最大主曲率大于
，最小主曲率小于
，极小曲面上的所有点都是马鞍点。除此之外，对于球上一点，它的两个主曲率都相等且均大于
，平面上的两个主曲率都为
。
离散微分几何
微分几何是研究光滑曲面上一个无穷小邻域的微分属性，例如导数、曲率等性质。那么如何研究三角网格曲面呢？三角网格是分段的平面，即分片平面，对于一个三角网格上的顶点，它的邻域三角形不一定共面，那么曲面在这一点只有连续，不光滑就不可微，不可微就没法去讨论它的微分属性，但是我们又知道，这些点是从一个光滑曲面上采样过来的点，那么它原本的曲面一定有它的微分属性，我们希望从采样点去估计出原曲面的微分属性。
法向估计
对于三角网格上一点，有若干个三角面与该点相邻，每张网格面都是平面且有各自的法向，那么该点的法向该如何定义的？一个简单的想法是直接将相邻面片的法向平均来得到，即顶点法向等于于它相邻的三角面的法向的平均（离散逼近）。当然也可以通过相邻的网格面来拟合出一张光滑曲面，再用光滑曲面的法向来近似它（连续逼近）。因此就有了两种方法论。
连续逼近在早点有很多paper做过相关研究，我们更关心的是能否用离散方法来逼近它。上面说到可以用这个点周围的面片的法向来平均，但是每个三角形都不一样，因此需要加权平均，于是衍生出了各种加权的方法，例如面积权和顶点夹角权。
曲率估计
我们最关心的是曲率计算，这里主要给出结论，在计算曲率时我们使用Laplace-Beltrami定理来计算一个点的曲率，即对于顶点的1-邻域（1-ring，即与该点相邻的一圈网格面），取过该点的某一边相对的两个三角形的夹角与
的余切和作为权重，最后再除以一邻域的Voronoi面积的两倍，即可近似出这个点的平均曲率。
同样，高斯曲率也可以有Gauss-Bonnet定理推导出，即一个点的高斯曲率等于减去三角形在过该点的角的和再除以Voronoi面积。
图20展示了高斯曲率的可视化，可以看到突出的部位高斯曲率会很大，接近平面的部位高斯曲率就会很小，越平的地方高斯曲率越小。
极小曲面
前面提到，极小曲面就是平均曲率处处为的曲面，它的每个点都是马鞍点，即两个主曲率一正一负。在实际应用中，建筑学中会用的比较多，屋顶使用极小曲面，由于它的面积最小，因此能够起到省材料的作用，其次，由于每个点都是马鞍点，即一个方向是向下弯另一个方向是向上翘，当下雨下雪时，水会顺着凹的方向流出，就不容易形成积水。因此有很多建筑的屋顶采用了极小曲面设计。
上文我们提到了极小曲面的近似求解，即网格点与它1-邻域的重心。单独把1-邻域拿出来看，如图27所示，我们构造一个由点出发指向它的1-邻域重心的向量
，我们让点
沿着
运动，对于任意开放网格，让每个点沿着各自的
运动迭代，即可得到一张极小曲面（注意要迭代地移动，每次移动
即可，不能直接移过去，不然很难收敛）。
因此可以归纳出离散极小曲面的局部迭代法，如图29所示
前提是输入的曲面必须是开放的曲面，边界点保持固定，如果是封闭曲面那么该曲面会坍缩。另外，上述使用的拉普拉斯算子是均匀拉普拉斯算子，这可能会造成网格面自交，使用余切拉普拉斯算子能够避免这一情况。
