论文部分内容阅读
计算共形几何是计算机科学和纯粹数学之间的交叉学科,其目的是将现代几何、经典几何的概念和定理转化为计算机算法,为工程实践服务.计算机算法在某种程度上促进和传播了数学,同时也拉近了数学和工程应用之间的距离.全纯二次微分作为共形几何中的重要概念.在Teichmuller空间的研究中具有重要的意义,它和曲面上的叶状结构有着直接的关联,全纯二次微分的水平轨线和竖直轨线都构成了曲面上的叶状结构.但由于全纯二次微分的艰深晦涩,少有人能领略其美感,更无法想象其在工程领域能有什么样的应用.本文首次实现了高亏格黎曼曲面到图(graph)的广义调和映照算法.得到曲面上的叶状结构,并进行了可视化,同时,由于黎曼曲面到图(graph)的广义调和映照诱导的Hopf微分就是全纯二次微分(Strebel微分),于是算法可以进一步计算全纯二次微分.算法通过输入不同的曲面上的环路和高度参数,可以控制叶状结构的拓扑同伦类和几何属性,因而得到的全纯二次微分也是可控的.本文首次对高亏格曲面上的叶状结构和全纯二次微分进行了全面丰富的可视化.使得我们能够更加直观理解这些概念,进而将之应用到工程领域.在六面体网格生成中.本文首次阐述了可染色四边形网格、有限可测叶状结构和Strebel微分三个概念之间的等价关系,为六面体网格生成算法提供了坚实的理论基础;并且基于曲面上的叶状结构和Strebel微分,提出并实现了全自动的六面体网格生成算法,对六面体网格自动生成这一所谓的“圣杯”问题实现了重大突破.此外,基于曲面上的叶状结构,我们提出一种新的曲面配准算法,可以进行高亏格、大形变非等距变换下的曲面配准.另外,本文还介绍了Birkhoff插值中,在任意单项序下具有相同极小单项基的一类问题,提出了这类问题的判别标准,使得我们可以使用字典序下的极小单项基快速算法来计算其他单项序下的问题.曲面上的叶状结构和Strebel微分.所谓叶状结构(foliation),就是将n维流形分解成(n-1)维子流形,其分解方式局部上具有直积结构,如图1中(a)所示,我们将亏格为2的曲面分解成一族曲线,每条曲线被称为一片叶子.曲面上三条叶子交汇的点被称为奇异点.图1 亏格为2的曲面上的叶状结构和Strebel微分.为得到曲面上的叶状结构,我们考虑曲面到图(graph)的广义调和映照.如图1(a)中三条橙色曲线所示,我们在曲面上指定了一组环路(封闭曲线){γ1,γ2,γ3},并相应配以高度参数这组环路将曲面分割成2条裤子(带有三条边界的亏格为零的曲面).这种分解方式可以定义出一个图(graph),如图1(b),每条裤子对应一个节点,每条环路对应一条边,边的长度即为对应的高度参数;如果环路连接两条裤子(可以相同),那么此环路对应的边连接这两条裤子对应的节点.Gromov和Schoen[20]定义了图(graph)的双曲性质,证明了从曲面到图的广义调和映照的存在性和唯一性.我们的算法使用非线性热流方法求解曲面到图的广义调和映照,并得到曲面上的叶状结构.如图1所示,(b)中图(graph)的节点的原像是(a)中标识红色的曲线;(b)中图(graph)中边上的点的原像是(a)中曲面上的叶子.曲面上叶状结构的叶子可以是环路(封闭曲线),也可以是无限延伸的螺旋线,所有叶子均是环路的叶状结构称为有限可测叶状结构.我们算法通过广义调和映照算得的叶状结构是有限可测叶状结构.经典的Hubbard-Masure理论[25]证明了可测叶状结构和全纯二次微分之间的等价关系,即任给一个可测叶状结构,如图1(a),则存在一个全纯二次微分如图1(c),其水平轨道诱导的叶状结构恰好是所给的叶状结构.具有有限可测叶状结构的全纯二次微分叫做Strebel微分.我们在计算出叶状结构后,对其进行Hodge星算子操作,就可以计算Strebel微分.六面体网格生成.本文首次阐述和证明了下面这三个概念的等价关系:{可染色四边形网格}(?){有限可测叶状结构}(?){Strebel微分}定理0.0.1(三位一体)设S是亏格大于1的封闭黎曼曲面.给定曲面上可染色四边形网格Q,则存在Q诱导的有限可测叶状结构(FQ,μQ),同时存在唯一的Strebel微分Φ.使得Φ诱导的水平有限可测叶状结构(FΦ,μΦ)恰好等于(FQ,μQ).相反地.给定Strebel微分Φ,可构造有限可测叶状结构(FΦ,μΦ).诱导可染色四边形网格Q.此三位一体理论框架使得我们可以使用Strebel微分来构造可染色四边形网格,然后拓展生成曲面内部实体的六面体网格.算法流程为:输入亏格为g>1的封闭曲面,曲面的内部空间构成高亏格的实体.(1),用户在输入曲面上设定一组不相交的简单环路,并对每个环路指定一个高度参数;(2),计算出唯一的Strebel微分;(3),Strebel微分将输入曲面分割成圆柱面,并生成可染色四边形网格;(4),根据曲面的圆柱面分割,向曲面内部空间延伸,生成体的圆柱体分割;(5),计算分割出的每个拓扑圆柱体到标准圆柱体的微分同胚映射;(6),将标准圆柱体上的六面体网格拉回映射到原拓扑圆柱体上,即完成了各个分割圆柱体上的六面体网格生成,最后将其拼接,得到整体的六面体网格.高亏格曲面配准.基于曲面上的叶状结构,我们提出一种新的曲面配准方法.叶状结构将曲面分解为一组封闭曲线,这种分解具有局部张量积结构.并且对应一个图(graph).对于两个具有相同拓扑的叶状结构的同胚曲面.我们首先对它们的图进行配准,然后配准对应的叶子.图2展示了我们曲面配准算法的流程.给定两个亏格为g= 4的曲面,我们自动计算出能将曲面分解为2g-2条裤子的3g-3条环路,进而诱导裤子分解图.两个曲面上拓扑相同的裤子分解,诱导相同的裤子分解图.我们为图(graph)中的边赋予长度.计算曲面到图的广义调和映照,进而得到曲面的叶状结构.图上的一个点对应着源曲面上的一片叶子,也对应着目标曲面上的一片叶子.这给出了叶子之间的对应关系,进而保证了圆柱面和奇异轨线之间的对应关系.如图2所示,两个曲面上对应的圆柱面用相同的颜色进行渲染.最后调整相应叶子之间的映射,得到曲面整体之间的微分同胚映射.图2 亏格为4的曲面配准.Birkhoff插值的极小单项基问题.本文另外研究了多元Birkhoff插值中,在任意单项序下具有相同极小单项基的一类问题,得出如下结论:若在所有消去序下,某—Birkhoff插值问题存在唯一的极小插值单项基B,则该插值问题在任意单项序下的极小插值单项基都是B.我们结合任意非插值基中的单项对应的向量都与严格小于该单项的单项对应向量线性相关这一结论,利用归纳法.证明了该定理的正确性.这一定理使得我们可以使用字典序下的极小单项基快速算法来计算其他单项序下的问题.