清华笔记：计算共形几何讲义 （2）代数拓扑

这次课程，我们简单介绍曲面基本群（一维同伦群）的理论梗概。主要概念有基本群的定义，表示，计算。然后我们介绍覆盖空间理论，特别是万有覆盖空间理论，曲线同伦检测算法。【1】给出了课程的视频。

这些理论工具在计算机图形学方面具有巧妙的应用实例，诱导了经典算法。我们仅举两个最为直接的例子：Konrad Polthier首先提出的曲面四边形网格化算法, QuadCover；Yaron Lipman提出的用深度学习来进行曲面的语义分割算法。这些算法的精髓来自于覆盖空间理论。

下一课，我们计算曲面单位切丛的基本群，介绍光滑同伦理论，这是瑟斯顿提出的用于解决“神圣网格”问题的理论基础。

计算机图形学中的应用

曲面四边形网格化

图1. 曲面的四边形网格化。

如图1 所示，曲面的四边形剖分是计算机图形学的一个基本问题，四边形网格化对于计算力学而言非常重要。通常，我们可以计算曲面在每点的主曲率方向（principle direction），这样我们在曲面上定义了一个光滑标架场（Frame Field）。标架场具有一些奇异点。例如在脐点处（ambilical point），标架无法定义。

图2. 分支覆盖（Branch Covering）。

我们可以构造曲面的分支覆盖空间，以奇异点为分支点，然后将曲面上的初始标架场“提升”到覆盖空间上的一个矢量场。然后，我们将覆盖空间的矢量场进行分解，求得调和分量，在投影回原来曲面，得到两组光滑矢量场。矢量场的积分曲线诱导了曲面的四边形网格。具体细节可以在【2】中找到。这种方法的关键思想是覆盖空间的概念，提升的概念，和矢量场的分解。

深度学习和曲面的结合

图3. 曲面参数化，将曲面映射到平面长方形区域，生成“几何图像”。

目前，计算机图形学领域的一个研究热点是将神经网络和曲面结合，用深度学习的方法来进行几何处理，例如对曲面进行语义分割（symantic segmentation）。传统的卷积神经网的输入是二维图像，因此我们需要将曲面转换成“几何图像”，如图3所示。我们将曲面映射到平面区域，然后在平面上重新采样，得到二维点阵。

图4. 用平环覆盖拓扑球面。

几何图像的一个缺陷是边界的不连续性。为了使边界光滑，我们采用分支覆盖。覆盖空间是拓扑环面，拓扑环面的覆盖空间是整个二维平面，可以作为神经网络的输入。如图4所示，大卫头曲面是拓扑球面，我们选择三个奇异点，构造4重分支覆盖，形成一个拓扑环面。拓扑环面的覆盖空间是二维平面。在【3】中，我们可以找到实现的细节。

基本群的概念和表示

图3. 曲面上的蚂蚁。

代数拓扑由庞加莱创立。基本群的想法比较直观：假如我们是生活在曲面上的蚂蚁，一辈子没有跳离过曲面，因此没有三维的概念。那么，我们如何判断我们生活的曲面是否有“洞”？

图4. 拓扑球面和拓扑轮胎面。

如图4所示，拓扑球面没有环柄，小猫曲面具有一个环柄，具有三维的“洞”。那么，这个“洞”是因为曲面嵌入在三维欧式空间中所产生的吗？换言之，这个“洞”是曲面和三维空间的相对关系，还是曲面自身内蕴的特性？

图5. 拓扑轮胎曲面上，存在无法缩成点的圈。

如果蚂蚁比较智慧，它会追踪曲面上的封闭路径。拓扑球面上，所有的圈都能够缩成一个点；拓扑轮胎上，存在一些圈无法缩成点，如图5所示。“圈是否能够缩成点”的思想成为了同伦伦的源头。

图6. 道路同伦。

基本概念

我们考察曲面上的道路，如果两条道路具有相同的起点和终点，并且一条道路能够在曲面上渐变成另外一条道路，则我们说它们彼此同伦，如图6。

如果道路的起点和终点重合，则我们称之为环路。我们在曲面上选定一个基点p。考察所有从基点出发，又回到基点的有向环路，将它们进行同伦分类。

• 定义有向环路的乘法：两条环路首尾相接，构成一条更长的环路，则更长的环路为原来两条环路之积，如图7。

• 能够缩成基点的环路被视作单位元。

• 一条有向环路方向取反，所得的逆向环路被视为原来环路的逆元，如图8。

图7. 环路乘积。红色的环路是两个黑色环路的乘积。

可以直接验证，所有过基点的有向环路同伦等价类，在连接操作（乘法）下成群。这个群被称为是曲面的基本群，或一维同伦群，记为；

图8. 环路取逆。红色的环路是黑色环路的逆。

表示

拓扑空间的同伦群的概念虽然直接，但是依然抽象，我们需要更为具体实际的表示方法。一般的方法是用同构的一个群，所谓的“词群”，来表示。

首先，假设我们给定一组“字母”，例如所有的英文字母，字母组成了词。两个词拼接成一个更长的词，这定义了词的乘法。显然，“空词”是这个乘法的单位元。同时，每个字母可以求逆，例如互为逆元，它们之积为空词，即单位元。这样，所有的词在拼接的乘法下构成了一个群。这个群是由所有英文字母所自由生成的。

假设，存在一组特殊的词，“关系"，它们等价于空词。给定一个词，我们可以对其进行如下基本操作：

1. 在任何位置插入一个关系词，或关系词的逆，

2. 如果在词中，存在一个子词等于某个关系词，或关系词的逆，去掉这一子词。
   

给定两个词，如果我们能够将其中的一个经过有限个基本操作变成另外一个，则我们说这两个词彼此等价。

所有词的等价类，在拼接操作的乘法下成群，被称为“词群”。一个词群的符号表示为 {生成元，关系词} 。

典范表示

在可定向的紧曲面上，存在基本群的生成元:

满足如下条件：

这里a.b代表环路a和环路b的代数相交数。所谓代数相交数可以如下理解。如果环路a和环路b横截相交于一点q, 并且a的切向量叉积b的切向量和曲面在q点的法向量一致，则q的指标为+1，如果相反，则指标为-1。如果环路a和环路b在点q相切，则q点的指标为0. 环路a和环路b的代数相交数等于所有交点的指标之和。

这种基本群的生成元被称为是基本群的典范基底。我们可以将曲面沿着一族典范基底切开，得到单连通的4g边形，所得的区域被称为是曲面的一个基本域，如图7所示。基本域的边界是

边界可以缩成一个点。

图9. 基本群的典范基底。

曲面上任何一条环路可以经同伦变换，使得它和典范基底只相交于基点。然后，将此环路最终分解为多个子环路的乘积，每个子环路只经过基点一次。在基本域上，每个子环路是连接两个角点的道路。道路可以同伦变换到基本域的一段边界上，由此子环路可以由，及其逆生成。这证明了是基本群的生成元。因此，曲面基本群的典范表示是:

.这里，g被称为是曲面的亏格，其直观意义是曲面上“环柄”的个数。每个环柄上有一对经度环路和纬度环路，如图9所示。

基本群的计算方法

图的基本群

首先，我们考虑最为简单的情形：拓扑空间为一个图（Graph），记为G(V,E)，这里V是顶点集合，E是边的集合。图中任何非平庸的环路都无法缩成一个点，因此图的基本群是自由生成的，其关系式为空集。首先，我们计算G的一个生成树（Spanning Tree）T，即T是G的一个不含任何环路的子图，同时T包含所有顶点。那么G\T由一些边组成，我们称之为“余边”：

一般拓扑空间

一般拓扑空间的基本群计算主要是基于CW-胞腔分解。所谓k维CW-胞腔，就是k维拓扑圆盘。例如0维胞腔是点，1维胞腔是线段，2维胞腔是拓扑圆盘，3维胞腔是实心球体，等等。我们用

图12.亏格为1的曲面的CW-胞腔分解。

理论证明

这里介绍的同伦群的组合算法是基于Seifert-van Kampen定理，这个定理的实质是分而治之的策略。就是将原来流形分解成子流形，分别计算每个子流形的基本群，然后将子流形的基本群拼成原来流形的基本群。

基本概念

直观而言，覆盖映射局部是拓扑同胚，但全局是多对一的映射。

我们将许多基本域的拷贝沿着相应的边界逐片粘和起来，粘和过程中保证所得曲面一直是单联通的。

最终我们所得的曲面被称为是原来曲面的万有覆盖空间。

如图1所示，对于亏格为1的曲面，其万有覆盖空间可以配上一个平直黎曼度量，从而铺满整个欧式平面；对于亏格为2的曲面，其万有覆盖空间可以配上一个双曲度量，从而铺满整个双曲平面（欧式单位圆盘）。

图13. 亏格为1曲面的万有覆盖空间。

提升和升腾

图14. 环路提升。

如图2所示，我们在楼下找一族开覆盖

拓扑,代数关系

直接应用

同伦检测 在计算拓扑中，判定两个复杂环路是否同伦是一个饶有兴味的问题。

图15. 同伦检测。

我们可以将底流形上的环路提升到万有覆盖空间的道路， 然后判断这些道路是否起止于同样的点。

不动点类问题

---

【1】http://m.iqiyi.com/w_19rtqmw8mp.html?msrc=10_107_192&u1=qyid1424935073&wx_uid2=wxidoG0a9jh7lM1t3z2B8P3BDI9fbOwM

【2】F. Kalberer, M. Nieser and Konrad Polthier, "QuadCover - Surface Parameterization using Branched Coverings", Computer Graphics Forum, 2017.

 

【3】H. Maron, M. Galun, N. Aigerman, M. Trope, N. Dym, E. Yumer, V. Kim, Y. Lipman, Convolutional Neural Networks on Surfaces via Seamless Toric Covers, SIGGRAPH 2017.

---