和乐群

2018 年 12 月 14 日 中国物理学会期刊网

在美国传统文化中，感恩节是亲朋好友合家欢聚的日子。老顾和同事、访问学者、学生们多次聚餐，又参加了朋友的聚会。朋友家住长岛海边的豪宅，真正实现了“面朝大海，春暖花开”的境界。聚会上高朋满座，欢声笑语，美酒佳肴，中西合璧。家庭聚会的主人和来宾都是华尔街的精英，毕业于国内的一流大学和美国的常青藤系列，其专业背景多是数学统计、金融工程。由于聚会的主人毕业于普林斯顿，大家自然地谈起了普林斯顿的著名数学家，“美丽心灵”的原型—约翰纳什（John Nash），证明了费马定理的安德鲁怀尔斯（Andrew Wiles）。怀尔斯躲在阁楼中七年，证明了谷山-志村猜想的一部分，从而解决了费马定理。谷山丰提出的猜想将椭圆曲线和模形式联系起来，开辟了一片新天地，他由于无法证明自己的猜想三十出头蹈海而逝，他的新婚妻子为他殉情，香消玉殒。另一位朋友是摩根金融高管，杜克大学统计博士出身，对陈省身先生、丘成桐无比崇敬。他对老顾用最优传输和蒙日-安培方程来解释深度学习非常有兴趣，深入探讨了理论细节。

依循传统，聚餐的主菜是烤火鸡配蓝莓酱，老顾为聚会带去了家乡风味-东北凉皮。大家开怀畅饮，其乐融融。此情此景，老顾想到了数学中最为恰切的描述—和乐群（holonomy group）。和乐群是陈省身先生翻译成汉语的数学专业词汇，陈先生曾经倡导用和乐群来研究黎曼几何。

近期，老顾和合作者们运用这一抽象概念来理解计算机辅助设计领域的一个基本问题：四边形网格生成。在动漫、游戏界，曲面都是用三角网格（triangle mesh）来表示，但是在计算机辅助设计（CAD）、计算机辅助制造（CAE）领域，几何造型都是用样条曲面（Spline Surface）来表示。在工程实践中，通常对实体进行三维扫描，获取点云数据，然后将点云转换成三角网格，将三角网格转换成四边形网格，最后生成样条曲面，如图1所示。从三角网格到四边形网格的变换是这一过程的关键。这一算法一直受到学术界的关注，并且在工业界每天都在被使用。

Fig1. 三角网格到样条曲面的转换（贺英教授作）。

如此而言，四边形网格生成应该是被充分研究过的成熟问题。并且，将一张曲面转换成四边形网格应该非常符合人类直观。任何一位高中生都可以手工将三角网格变换成四边形网格，三维人脸曲面的四边形网格化是建模师的基本技能之一。但是，在曲面上合理布线，将曲面切割成四边形网格，更多地是一种艺术，而非是一种技术。在目前众多的算法中，几乎所有的算法都需要用户介入进行手工调整，似乎人的“灵性”不可或缺。对于这一问题的深入理解，关键在于和乐群的概念【4】。

测地线（geodesics）

测地线是黎曼几何中的第一个概念，它是直线在流形上的直接推广。我们知道，平面上连接两点的直线段最短，局部来看曲面上连接两点的测地线最短。图2显示了人脸曲面上的一条测地线。

Fig. 2. 人脸曲面上的测地线（贺英、辛士庆教授作）。

测地线算法背后有着一段漫长的故事。老顾的同事Joe Mitchell教授是计算几何领域的领袖人物之一，他早在1980年代就发明了离散曲面上的测地线算法。按理说测地线是黎曼几何的最为基础的概念，工程领域应该很早就采用测地线算法。但是直到20年后，这一算法才被图形学领域采用。数十年来，Mitchell教授坚持在石溪讲授计算几何课程，并将他的算法留为家庭作业培养了上千名学生，其中包括老顾的师弟Pedro Sander教授和老顾与秦宏教授共同指导的学生贺英教授。20年后，Sander向微软研究院的Hughes Hoppe推荐了这个算法，在他们的推动下，Mitchell教授理论算法的工程实现于2005年发表在SIGGRAPH上【1】。贺英教授和他的博士后辛士庆教授一直坚持在这一领域勤奋耕耘【2】，目前成为这一领域的国际权威。由此我们看到几何知识在工程领域的传播的困难，也看到Mitchell教授不忘初心，淡泊名利的学术操守。

平行移动与和乐群

给定带黎曼度量的曲面，测地线和起点处的一个切向量，和的夹角为。我们平行移动（parallel transport）到处的切向量，满足和的夹角保持为。给定分段测地线（piecewise geodesic），我们可以逐段沿着测地线平行移动切向量，直至平行移动到终点。

对于一般的曲线，平行移动的定义方式比较复杂，将曲线分段，每一段用测地线来代替，如此我们用分段测地线来逼近曲线。然后我们沿着分段测地线来平行移动起点处的切向量。我们将曲线越分越细，分段测地线越来越逼近原始曲线，平行移动到终点处的切向量会收敛到极限位置，我们将这个极限定义为初始切向量，沿着曲线平行移动到终点的结果。

我们考虑曲面上的一个区域，区域的边缘是一条封闭曲线。我们沿着进行平行移动，从起点出发的切向量环绕一周之后回到起点，平行移动之后的切向量和初始切向量之间相差一个旋转，这个旋转角度等于曲面的高斯曲率在上的积分。这一事实被称为是高斯-博纳定理。（Gauss-Bonnet theorem）。

我们固定曲面上的一点，被称为是基点。考虑过基点的一条封闭曲线，。如果我们沿着平行移动，从起点出发的切向量环绕一周之后回到起点，平行移动之后的切向量和初始切向量之间相差一个旋转，这个选择被称为是封闭曲线的和乐(holonomy)，记为。所有过基点的封闭曲线的holonomy成群，被称为是曲面的和乐群（holonomy group）。一般黎曼流形的和乐群也是如此定义，和乐群反映了黎曼度量的内在性质。

四边形网格度量

Fig 3. 四边形网格。

给定带有黎曼度量的曲面，是四边形的网格，如图3所示。如果我们将每个四边形的面视作一个单位正方形，那么诱导了一个新的黎曼度量，我们称之为四边形网格度量，记为。我们力图给出四边形网格度量所要满足的条件。

条件1. 共形等价（conformal equivalence）如图3所示，四面形网格的每个面都接近正方形，大小尽量一致，形状尽量规则。这意味着四边形网格度量和曲面初始黎曼度量彼此共形等价，。

条件2. 高斯-博纳（Gauss-Bonnet）每个面有4个顶点，每个顶点和多个面相邻。我们将和一个顶点相邻的面的数目称为这个顶点的度（degree），度为4的顶点为正常顶点（normal vertx），度不等于4的顶点成为奇异点（singularity）。正常顶点的邻域是平的，其曲率为0；奇异点的邻域是弯曲的，其曲率等于4减去顶点的度乘以。由高斯博纳定理，曲面的总曲率为拓扑不变量，因此我们要求所有奇异点的曲率之和等于，这里是曲面的欧拉示性数。

Fig. 4 面封闭路径（Face Loop）。

条件3. 和乐群（Holonomy Group）如图4所示，我们在四边形网格上定义面路径，就是一系列四边形的面组成的路途，相邻的两个四边形有一条公共边。如果路径封闭，则我们得到一个面封闭路径。如图5所示，我们可以沿着一条面封闭路径平行移动一个标架，回到起点时，标架相差一个旋转。旋转角度为，这里k是整数，即得到此面封闭路径的和乐（holonomy）。

Fig. 5. 标架沿着沿着面路径平行移动。

我们固定一个四边形为基面，考察经过基面的所有面封闭路径，所有这些封闭回路构成了去除奇异点之后曲面的同伦群，记为，这里代表所有奇异点的集合。度量曲面的曲率处处为0，因此同伦的路径诱导相同的holonomy。于是我们得到群同态，这里。这是度量应当满足的和乐群条件。

这个条件比较微妙，远离日常经验。在拓扑复杂的曲面上面，我们可以找到平直黎曼度量带有锥奇异点，奇异点处的曲率为，但是去除奇异点的曲面和乐群不是的子群。这种现象在亏格为0的曲面上不会发生，但是在高亏格的曲面上却很常见。

Fig 6. 不满足和乐群条件的黎曼度量。

如图6所示，我们设计亏格为2的曲面上的一个平直度量，带有唯一的奇异点，奇异点处的曲率为，其他各点曲率为0。图中红色曲线为过奇异点的测地封闭曲线。这个度量的和乐群不是的子群。详细讨论请见【3】

Fig 7. 阿贝尔微分的水平轨迹和内边界平行。

条件4. 如果度量满足以上3个条件，则我们可以在曲面上存在一个阿贝尔微分（Abel Differential），其零极点给出的奇异点，其诱导的度量为。更多的，的水平和铅直轨迹诱导了四边形网格，因此的水平和铅直轨迹是有限封闭环路，同时和边界曲线平行或者垂直。如图7所示，给定平面长方形，有两个圆洞。我们设计一个黎曼度量，有两个奇异点，曲率各为。从奇异点出发的测地线如图所示，阿贝尔微分的水平轨迹为蓝色封闭回路，和内外边界平行。

Fig 8. 阿贝尔微分的水平轨迹和内边界相截。

图8显示了不满足阿贝尔微分条件的平直度量。我们改变了奇异点的位置，阿贝尔微分的水平轨迹不再和内边界平行。

如上四个条件中，和乐群的条件最为关键。满足所有条件的度量取决于奇异点的位置。从计算角度而言，我们的离散曲面Ricci流理论可以保证带有奇异点的平直度量的存在性，即满足前两个条件；目前，尚未有系统性的算法保证满足和乐群条件和阿贝尔微分条件，这正是算法需要人为手工干预的核心原因。

Fig. 9 四边形网格，具有1个，2个，4个和12个奇异点

（大连理工罗钟铉及团队作）。

通过以上的理论理解，我们可以根据奇异点的个数要求设计不同的黎曼度量，从而得到不同的四边形网格。如图9所示，我们设计的度量具有不同数目的奇异点：从上而下，1个，2个，4个和12个奇异点。图10显示了亏格为2曲面上的两个四边形网格，带有8个和两个奇异点。

Fig. 10 亏格为2曲面上的两个四边形网格，8个和4个奇异点。

（大连理工雷娜教授团队作）

小结

这里，我们讨论了四边形网格度量应该满足的条件【4】。四边形网格生成是工程界的基本问题，但是其理论刻画的语言完全来自黎曼几何和共形几何。黎曼度量、测地线、平行移动、和乐群、共形等价、阿贝尔微分，这些概念不会在目前的计算机科学课程中提及，但是工程问题的实质就是应用这些概念其相应的定理，特别是和乐群的概念在这里起到至关重要的作用。这又一次彰显现代几何对于工程技术的指导推动作用。

References

Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, Hugues Hoppe. "Fast Exact and Approximate Geodesics on Meshes". SIGGRAPH 2005.
Xiang Ying, Shi-Qing Xin, Ying He. "Parallel chen-han (PCH) algorithm for discrete geodesics". ACM Trans. Graph. 33(1):9:1-9:11 (2014).
Yu-KunLain， Miao Jin, Xuexiang Xie, Ying He, Jonathan Palacios, Eugene Zhang, Shi-Min Hu, Xianfeng Gu. "Metric-Driven RoSy Design and Remeshing", IEEE VIs, Volume: 16 ,Issue 1, Pages 95-108， 2010.
Wei Chen , Xiaopeng Zheng , Jingyao Ke , Na Lei , Zhongxuan Luo, Xianfeng Gu, "Metric Based Quadrilateral Mesh Generation", http://arxiv.org/abs/1811.12604

请长按下方二维码，选择 “识别图中二维码”，即可关注。