分享

《计算共形几何-理论篇》教程简介

 阿里山图书馆 2020-06-01

计算共形几何是一门新兴的跨领域学科,将现基础数学和几何与计算机科学相融合,将现代拓扑和微分几何中的理论推广到离散情形,发展计算方法并广泛应用于计算机图形学、计算机视觉、几何建模、网络、计算力学和医学图像等领域。其基本算法已经被工业界所采用,例如共形虚拟肠镜技术被西门子推广,曲面参数化技术被动漫影视行业所采用,一些核心算法被游戏公司(例如暴雪)所采用。

在过去的十年间,老顾每年暑假都在清华大学丘成桐数学中心教授“计算共形几何”的课程。课程对整个社会完全免费公开,学员来自全国各地,有些学生来自欧美港澳。学员的背景包括计算机、电子、自动化等工程专业,包括数学、物理等理科专业,也包括生物医学等专业;更有很多工程师来自动漫设计、工业检测、计算力学、流体力学,也有放射影像领域的医生。丘成桐先生和老顾将这些年来讲授的内容汇集成书,出版了《计算共形几何-理论篇》,未来我们将会用这本书作为教材。

共形几何植根于基础数学,是很多领域的交叉点:黎曼面理论,复分析,微分几何,代数拓扑,几何偏微分方程,代数曲线等等;计算共形几何和计算机科学中的计算几何,数字几何,数值偏微分方程也有亲缘关系。这门学科的诞生是因为三维技术的蓬勃兴起,特别是三维扫描技术(例如基于结构光的相位平移技术)、计算机图形学技术(例如曲面参数化、纹理贴图技术)、计算机视觉技术(例如曲面注册配准,人脸表情捕捉)的迅猛发展,使得传统的欧几里得几何和线性代数方法无法解决这些领域提出的深刻问题,工程医疗领域必须系统引入现代微分几何和拓扑的思想和方法,发展严密而实用的计算方法。计算共形几何响应了时代的呼唤,从第一性原理出发推动了科学技术的发展。

教材章节梗概

教程的第一部分是代数拓扑和微分拓扑,主要讲解同伦群、同调群的概念,以此为工具讲解了覆盖空间理论、Brouwer和Lefschetz不动点理论,区域不变性原理,特别是微分流形上的微积分,以微分形式和外微分来推广场论,矢量场奇异点的Poincare-Hopf指标定理。特别是微分拓扑中的de Rham上同调理论,和Hodge分解理论。图1显示了曲面上的两个共轭调和微分形式,即无旋无散切向量场,所有这种调和场构成曲面的上同调群。这意味着黎曼流形上椭圆型偏微分方程解空间的维数与流形的拓扑有关,这正是指标定理的要义。

图1. 曲面上的调和形式和全纯微分。

第二部分是复变函数的几何理论,主要是用正规函数族,和几何变分原理来证明黎曼映照定理,曲面共形标准型和单值化定理。如图2所示,所有零亏格曲面可以映射成平面环带,每条边界映成同心圆弧。

图2. 曲面共形标准型。

第三部分是曲面的微分几何,主要讲解黎曼度量,测度线,平行移动,基本形式,特别是活动标架法,高斯-博纳定理,以及几何逼近理论。如图3所示,人脸曲面上两条测地线。

图3. 曲面上的测地线,共轭点概念。

第四部分调和映射理论,主要证明曲面调和映射的存在性、唯一性和微分同胚性,调和映照的奇异点Bochner理论,给出计算方法;如图显示了零亏格封闭曲面到单位球面的调和映射。调和映射的Hopf微分是全纯的二次微分,球面上的全纯二次微分为0,因而这时调和映射必为共形映射。

图4. Stanford兔子到球面的调和映射(温成峰、齐鑫作)。

第五部分是黎曼面理论,主要介绍黎曼面上的亚纯微分,黎曼-罗赫定理;图5显示了亏格为二的黎曼曲面上亚纯四次微分,其水平铅直轨迹生成了四边形网格,其奇异点满足Abel-Jacobi定理。

图5. 曲面上亚纯四次微分诱导的四边形网格。

第六部分是Teichmuller拟共形映射理论,介绍Teichmuller空间和Teichmuller映射的存在性、唯一性。所有的度量曲面可以由共形等价关系进行分类,所有的等价类构成Teichmuller空间。如图6所示,人脸曲面上有15个洞,可以被共形映射到平面圆盘,每个洞被映成一个圆洞。我们需要45个参数来描述这些圆洞的位置和大小。但是我们可以用莫比乌斯映射来变换右帧,因此这种拓扑曲面对应的Teichmuller空间是42维的。

图6. 黎曼面的Teichmuller坐标。

教材的最后一部分是离散曲面Ricci流理论,用几何变分原理来证明Ricci流解的存在性,唯一性,和离散单值化定理。Ricci流是目前唯一的方法,可以用曲率来设计黎曼度量。几乎所有的几何计算问题都可以归结为计算黎曼度量,因此这种算法具有根本的重要性。Ricci流将黎曼度量形变,使得形变速率和当前曲率成正比,曲率依随扩散-反应方程,如果扩散项压制反应项,则Ricci流图稳定收敛到常曲率度量。图7是曲面单值化的艺术表达,图8是这一定理的算法表达。现实生活中的所有曲面都可以共形变换到常曲率曲面,即球面、欧氏平面和双曲平面。这一定理的高维推广,是微分几何发展的历史主旋律。

图7. Escher的恶魔与天使,艺术地展示了单值化定理。

图8. 封闭曲面的单值化定理,由Ricci流算法得到。

与这些理论相呼应,我们给出相应的计算方法。所有的主要算法和主要定理,我们都有线上演示和视频。学员只需要扫描书中对应章节的二维码即可看到。同时,我们准备了课后作业,学员们基于提供的骨架源代码可以动手实现书中的主要算法,并且用课程提供的数据进行测试。专职的助教会为学员提供必要的帮助。

基本概念和中心定理

图9. 共形变换的保角性质。

共形几何是研究共形变换下不变量的学问。所谓共形变换就是保持角度不变的映射,如图9所示,我们将三维人脸曲面映射到二维平面圆盘,我们在人脸上随意画上两条相交的曲线,曲面上的曲线被映射到平面曲线,但是相交角度不变。

图10. 共形变换与一般的微分同胚。

在曲面的每一个切平面上,共形映射的导映射是相似变换,但是相似比在不同的切平面上彼此不同。如图10所示,我们在平面圆盘上铺满小圆,映回到人脸曲面上之后,如果小圆的形状被保持,那么这一映射是共形的。一般的映射会将平面上的小圆映成椭圆。图11显示了共形映射保持局部形状。

图11. 共形映射保持局部形状。

共形映射保持角度不变,保面积映射保持面元不变。如图12所示,弥勒佛像被映射到平面圆盘,左帧是共形变换,保持局部形状不变;右帧是保面元映射,每个区域的三维面积等于其像的二维面积。

图12. 保角变换与保面积变换(苏科华作)。

共形几何、曲面微分几何中最为深刻而基本的定理就是大一统定理:Poincare-Koebe的单值化定理。如图8所示,封闭带度量的曲面可以周期性地共形映射到三种标准空间中的一种:单位球面、欧氏平面和双曲圆盘。这种周期性的嵌入,用某个对称群来描述,这个对称群反应了曲面的整体性质,即曲面的共形结构。

图13. 带边曲面的单值化定理。

单值化定理对于带边曲面依然成立,如图13所示,所有曲面都可以共形映射到标准空间之中,所有的边界都被映射成测地圆。目前只有离散曲面的Ricci流方法能够计算曲面单值化。

计算共形几何数学方面的核心脉络就是证明单值化定理解的存在性、唯一性、正则性、适定性,特别是如何推广到离散曲面、甚至离散图(graph);计算机科学方面的核心是可计算性,即如何设计算法,计算出单值化定理。人类数百年的积累,得到了理论的精华;到了我们这一代,将理论发展成严密高效的算法;下一代自然是将算法广泛应用于工程医疗,真正造福人类。

直接应用

图14. 曲面参数化。

图15. 纹理贴图。

共形几何在计算机图形学领域有非常多的应用,最为基本的是曲面参数化纹理贴图,如图14-16所示。所谓曲面参数化就是将曲面映射到平面区域,尽量减少映射带来的畸变;所谓纹理贴图就是将平面的图像经由参数化贴敷到曲面之上。纹理贴图技术是整个影视动漫产业的基础技术之一。最近虚幻引擎5将虚拟几何技术将纹理和几何数据相统一,进一步解放了数字艺术家的创造力。这对于游戏、几何大数据、地理信息系统等领域将带来革命性的影响。

图16. 曲面纹理贴图。

图17. 几何压缩,网格生成。

传统图形学中,曲面都是用三角网格来表示的,如何生成高质量的三角剖分,如何实现几何压缩,用最少的顶点和面来表达尽量精细的几何特征,这些都需要共形几何的算法。如图17所示,我们将原始曲面共形映射到平面区域,然后在平面圆盘上用Delaunay Refinement方法生成三角网格。由于共形映射保角,如此得到的平面Delaunay三角剖分拉回到曲面上,得到曲面的测地三角剖分。改变采样的密度,我们得到不同解析率的曲面三角网格。

图18. 几何图像。

最近,游戏业出现了虚拟几何技术,目的在于支持海量几何数据的实时渲染。这一技术很可能和几何图像技术相关,如图18所示,我们基于图14中的曲面参数化,将米开朗基罗的大卫王雕像映射到平面区域,然后在平面区域均匀采样,得到左上角的图像,图像每个像素的颜色值代表采样点的空间坐标,如此得到几何图像;右上角是法向量贴图,底行显示的是不同采样率几何图像的渲染效果。这种技术将几何数据结构和图像数据结构相统一,可以直接应用虚拟纹理技术来处理海量几何数据,同时简化软件和硬件系统。这很可能成为游戏领域新技术的增长点。

图19. 曲面注册配准(温成峰作)。

在计算机视觉中,曲面注册是一个基本问题,所谓注册,就是寻找两个曲面之间的双射,将主要特征点对应,同时几何畸变最小。图19显示了基于共形几何的计算方法,我们用黎曼映射将3维曲面映射到平面圆盘,然后在平面圆盘之间建立微分同胚,这样就把三维曲面的注册问题转化成平面区域的映射问题。图中所有的特征点被标注成红色的点。仔细观察,我们发现女孩脸上的小圆被映射成男孩脸上的小椭圆,并且所有的椭圆具有同样的偏心率。理论上,这种映射被称为是Teichmuller映射,具有最小的畸变。

图20. 人脸表情动作捕捉。

如图20所示,这种方法也可以建立动态曲面之间的配准,从而实现表情捕捉。这一技术在影视动漫行业用得非常之多。

图21. 曲面上的全纯微分(郑晓朋作)。

Teichmuller理论用于在给定曲面之间寻找畸变最小的微分同胚,如图19所示,而这种最优映射依赖于曲面上的全纯二次微分,图21显示了小猫曲面上的全纯二次微分。这也可以理解为所有给定拓扑曲面上的共形结构形成了一个有限维的流形,所谓的Teichmuller空间,Teichmuller的切空间就是曲面上的所有全纯二次微分。

图22. 曲面规则四边形剖分(郑朋作)。

在计算力学中,有限元计算需要将几何实体规则剖分。例如将曲面表面生成四边形网格,如图22所示。本质上,曲面的四边形网格等价于黎曼面上的亚纯四次微分,其奇异点满足Abel-Jacobi定理,而这一定理实质上是黎曼面上全纯线丛的示性类。历经数十年的实践摸索,这一内在而隐秘的联系终于被揭示。近年来,这方面的研究方兴未艾。

图23. 样条曲面(贺英作)。

在工业设计、机械设计、数字制造领域,曲面被样条曲面所表达, 构造样条本质上是计算曲面的仿射结构,最终归结为共形几何的算法。如图23所示,黄色点为曲面的奇异点,我们构造一个黎曼度量,将所有曲率集中在奇异点处,如此得到的度量诱导曲面的一个仿射图册,从而我们可以构造样条曲面。这一特殊的黎曼度量可以用曲面的Ricci流方法来获得。

图24. 图的嵌入。

几年来,图网络发展迅猛,图的嵌入问题引发人们极大的兴趣。应用共形几何的方法,我们可以计算图的嵌入,则对于网络路由算法设计至关重要。图24显示了一个抽象图在球面上的嵌入,这种嵌入可以被视为共形单值化定理在图上的推广。

图25. 超材料设计(陈士魁作)。

图25显示了增材制造中的超材料设计,(d)帧显示了用负泊松比材料设计的面罩。传统的超材料设计只能在平面区域上实行,利用共形几何,我们可以在任意曲面上进行设计和模拟。

图26. 共形脑图。

图26显示的是大脑皮层曲面共形映射到平面区域,大脑上的沟回映成平面上的圆形边界。这样,我们可以比较不同的大脑皮层曲面,监控神经疾病的进展,例如奥兹海默症等等。

图27.虚拟肠镜。

图27显示的是虚拟肠镜技术。我们将直肠曲面平铺到平面之上,从而展开所有的皱褶,暴露出所有的直肠息肉,监控息肉生长情况,预防癌变的发生。

教程总结

计算共形几何为广大工程技术背景的年轻人提供了系统学习现代拓扑和几何理论的大好机会,真正将抽象的数学理论和切实的高新科技结合起来。几乎所有的基本概念,重要定理都有计算机算法相对应。我们对大量的工程关键问题进行详尽剖析,揭示出背后的拓扑和几何本质。

我们发现,在工程领域,有很多基本问题被研究了数十年,虽然工程上不断地有所提高,但是问题本质并没有被明晰阐释,很多时候工程技术人员有非常好的直觉,积累了各种诀窍,但是无法上升到理论层面,无法世代积累。例如,在机械设计领域,大量的CAD模型需要被表示成样条曲面,但是如何设计光滑覆盖整个曲面的样条、去除奇异点,这一直是无法解决的问题。我们发现传统样条曲面的构造是依赖于仿射不变量,因此需要流形的仿射结构。但是一般流形上没有仿射结构,我们必须引入奇异点。又如,四边形网格生成的关键是奇异点设计,如何指定奇异点的位置才能保证生成的四边形网格与原曲面共形。这方面的研究长达数十年,但是一直没有令人满意的解答。虽然大量商业软件声称解决了这一问题,但是它们的解决方案中都需要手工介入。其实,这个问题最后归结为全纯线丛的示性类理论。再如,游戏引擎如何支撑海量复杂几何数据的实时渲染,这一直是这一领域的关键问题。一种很有希望的解决方案是将三角网格转换成纹理表示,用虚拟纹理的技术动态在硬盘和GPU显存之间动态调度活动页面。这种技术的瓶颈在于几何大数据的全局参数化,这依赖于共形几何算法。或许虚幻引擎5的横空出世,能够推动虚拟几何技术的爆发。将工程积累的直觉升华到严密自洽的理论体系,这正是这本书的目的所在。

我们希望这本教程可以激发学员们通过动脑和动手两条途径来体悟自然真理,实现下一代几何算法,在各自的领域做出实质性的贡献。依随科技的发展,绝大多数的计算机教材很快被时代所淘汰。这本书中的几何概念和理论是自然界的一部分,独立于人类社会。因此我们希望这本书能够陪伴读者一生,书中讲解的几何原理融入到读者的血液之中,书中的几何拓扑理论结构成为读者知识结构的一部分。希望这本书成为广大工程技术人员的常备工具书,可以随时查找工程中常见的拓扑几何概念,查找到常见定理的证明脉络,查找到实用的拓扑几何算法;经常翻看,可以找到艺术设计的灵感,找到工程技术的突破点。我们希望计算共形几何的理论和算法能够经得起时间的检验,在历史的长河中历久弥新!

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 全屏 打印 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多