Note:ThisismostlycopiedortranslatedfromthepapersofProf.XianfengGu(http://www.cs.sunysb.edu/~gu/).
计算共形几何
张威应用数学11006059
1引言
共形几何是纯数学中很多学科的交叉领域,比如黎曼曲面理论、微分几何、代数曲线、代数拓扑、偏微分方程、复分析等等.它有很长的历史,至今在现代几何与现代物理中仍然非常活跃.比如超弦理论中的共形场和理论物理中的模空间理论都是当今快速发展的研究领域.
近些年来,随着三维数字扫描仪、计算机辅助几何设计、生物信息和医学成像的快速发展,出现了越来越多的三维数字模型.因此迫切需要有效的算法来表示、处理和使用这些模型.计算共形几何在数字几何处理中扮演了一个重要角色.它已经应用在很多重要的领域,比如曲面修复、光顺、去噪、分片、特征提取、注册、重新网格化、网格样条转换、动画和纹理合成.特别地,共形几何奠定了曲面参数化的理论基础,同时也提供了严格的算法.计算共形几何还应用于计算机视觉中的人脸跟踪、识别和表情转换,医学成像中的脑电图、虚拟结肠镜和数据融合,几何建模中的具有任意拓扑流形上的样条构造.
共形几何之所以如此有用是基于以下一些事实:•共形几何研究的是共形结构.日常生活中的所有曲面都有一个自然的共形结构,因
此共形几何算法非常普遍.
•共形结构比黎曼度量结构更灵活、比拓扑结构更具有刚性.它能处理大量黎曼几何不能有效处理的变换,这些变换还能保持很多拓扑方法会丢失的几何信息.
•共形映射比较容易控制.比如,两个单连通封闭曲面之间的共形映射构成一个6维空间,因此只要固定3个点,这个映射就是唯一的.这个事实使得共形几何方法在曲面匹配和比较中非常有价值.
•共形映射保持局部形状,因此在可视化方面有很好的应用.
•所有的曲面都可以根据共形结构进行分类,而且所有的共形等价类形成一个有限维流形.这个流形有丰富的几何结构,容易对其分析和研究.与之相反,曲面的等距类形成一个难以分析处理的无穷维流形.
计算共形几何
•计算共形几何算法是以椭圆偏微分方程为基础的,而椭圆偏微分方程又是容易求解而且稳定的,因此计算共形几何方法对于实际工程应用非常有用.
•共形几何中,所有单连通曲面都能共形变换成某种标准空间:球面、平面、双曲空间.也就是说,任何曲面都具有三种标准几何(球几何、欧式几何、双曲几何)中的一种.这样大部分三维数字几何处理任务都能转化成二维标准空间中的任务.历史上,计算共形几何方法已经广泛应用于许多工程领域,然而绝大部分应用都基
于平面区域的共形映射.最近,随着数学理论的发展和计算能力的提升,计算共形几何方法已经从平面区域推广到具有任意拓扑的曲面.
1.1共形变换和共形结构
图1:共形映射保持角度
(a)Circlepacking
(b)Checkboard
图2:共形映射根据FleixKlein的Erlangen纲领,几何就是研究在特定的变换群下保持不变的空间性质.共形几何就是研究保角变换群下的不变量.它介乎于拓扑和黎曼几何之间.
计算共形几何
共形映射就是保角映射,如图1所示.在无穷小邻域,共形映射就是放缩变换.它保持局部形状,比如它将无穷小圆周映成无穷小圆周.如图2所示,这个bunny曲面通过一个共形映射映到平面.如果平面有一个circlepacking,则通过拉回得到bunny曲面上的一个circlepacking.如果给平面铺上棋盘格,则同样得到bunny曲面的棋盘格修饰,其中直角和正方形都是保持的.
曲面上的两个黎曼度量是共形的,如果它们定义的角度是相同的.共形结构就是指曲面上度量的共形等价类,而黎曼曲面就是带有共形结构的光滑曲面.因此在黎曼曲面上,我们可以度量角度,但不能度量长度.每一个带有度量的曲面都自动成为一个黎曼曲面.
如果两个黎曼曲面之间存在共形映射,则称它们是共形等价的.显然,共形等价是黎曼曲面间的一个自然的等价关系.共形几何的目的就是在共形等价意义下对黎曼曲面进行分类,这就是所谓的模空间问题.给定一张光滑曲面,考察它上面的所有共形结构在共形等价下的模,这个集合被称为曲面的模空间.对于具有正亏格的封闭曲面,模空间是正维数的有限维空间.
1.2基本任务
下面的问题是计算共形几何最基本的一些任务.这些问题是相互依赖的:
1.共形结构给定一张带有黎曼度量的曲面,计算它的内蕴共形结构的不同表示.一种方法是计算它的Abelian微分群,另一种方法是计算标准的黎曼度量.
2.共形模完全共形不变量称为黎曼曲面的共形模.正如前面所讲的,理论上存在一组有限的数完全决定了黎曼曲面,这些称为黎曼曲面的共形模.一个比较难的问题是显式计算任意给定曲面的共形模.
3.标准黎曼度量黎曼曲面的uniformization定理揭示了每一个黎曼度量都共形等价于一个常Gauss曲率度量.除了球面和环面外,这个度量是唯一的.计算这个度量在计算共形几何中具有基本的重要性.
4.共形映射 计算共形几何 计算两个共形等价的曲面之间的共形映射可以简化为计算它们到标准形状空间(球面、平面、双曲空间中的圆域)之间的共形映射.
5.拟共形映射大部分微分同胚都不是共形的,它们将无穷小圆周映成无穷小椭圆.如果这些椭圆的长短轴比一致有界,那么就称为拟共形映射.拟共形映射的微分是由所谓的Beltrami微分刻画的,Beltrami微分记录了长轴方向和长短轴比.有一个基本定理是说通过Beltrami微分可以恢复拟共形映射.而至于怎样通过Beltrami微分计算拟共形映射,则是一个具有很多应用价值的重要问题.
6.共形镶嵌粘合带边黎曼曲面并研究缝曲线形状和粘合样式之间的关系.这与拟共形映射问题紧密相关. 1.3共形几何在工程应用中的优点 计算共形几何已经被证实在许多工程领域中有重要应用.下面是一些主要理由:
1.标准区域所有带度量的曲面都能共形地映成球面、平面或双曲圆盘中的标准区域.这可以帮助我们将三维几何处理问题转化为二维问题.
2.通过曲率设计度量每一个共形结构都有一个常Gauss曲率的标准度量,这个度量在很多几何应用中非常有价值.例如在双曲度量下,每一个非平凡同伦类都有一个闭测地线代表元.此外,我们可以根据预先给定的曲率设计黎曼度量,这在几何建模中非常有用.
3.一般几何结构共形几何方法能够用来构造其他几何结构,比如仿射结构、射影结构等等.这些结构在几何建模应用中是关键的.
4.微分同胚的构造共形映照和拟共形映照可以被用来构造曲面间的微分同胚.可以应用于曲面注册和比较这些计算机视觉和医学图像中最基本的问题. 计算共形几何
5.等温坐标共形结构可以被当作曲面上的等温坐标图册.在这种坐标下,度量的表达式最简单,因此所有的微分算子,比如Laplace-Beltrami算子,具有很简洁的表达式.这可以用来简化偏微分方程.等温坐标保持局部形状,对于可视化和纹理映射是非常完美的. 2已有工作 图3:基本群的多边形表示 图4:四种类型的图.(a)Acutgraph但不是systemofloops.(b)Asystemofloops.(c)基本群的基但不是systemofloops.(d)同调基,但既不是同伦基也不是cutgraph. 计算共形几何已经有比较长的历史了,起初大部分共形几何方法都是针对平面区域或拓扑圆盘的.直到近些年来才推广到具有复杂拓扑的曲面上,这与当前研究热点计算拓扑的发展是紧密相关的.有相当一部分计算共形算法是依赖于计算拓扑算法的. 计算共形几何 图5:从左到右:输入模型,handle(绿)和tunnel(红)环,handle特征 2.1计算拓扑 计算拓扑的研究对象主要是单纯复形,比如三角网格曲面就是一种二维单纯复形.计算拓扑的一些基本问题就是计算曲面单纯复形的cutgraph,同调群和基本群.知道了cutgraph,就能将曲面剪开成拓扑圆盘,这对于参数化和纹理映照是非常有用的.知道了基本群,就能完全确定封闭曲面的拓扑分类.通常基本群是用多边形表示的,其中有约化多边形表示、标准多边形表示等一些特殊的多边形表示,见图
3. Vegter和Yap[1]给出了计算标准多边形表示的算法,Lazarus等[2]简化了Vegter和Yap的算法,复杂度为O(gn),其中n,g分别为曲面的大小和亏格.标准多边形表示由2g个具有公共点的环组成,令人不满意的是它们可能具有公共边.在大部分应用中,标准多边形表示不是必须的,只需要知道cutgraph就足够了.cutgraph是指三角网格曲面上的一族边集使得曲面去掉这些边后变成拓扑圆盘,如图4所示.Dey和Schipper[3]使用cutgraph得到了检验曲线是否可缩或两曲线是否同伦的快速算法.2002年,Erickson等[4]第一次提出了最优cutgraph的问题:给每一条边赋一个权,求权最小的cutgraph.这篇文章证明了最小cutgraph问题是NP难的,并给出了计算近似最小cutgraph的贪婪算法,该算法复杂度为O(g2nlogn),精度为O(log2g).deVerdière和Lazarus[5]研究了一种称为"systermofloops"的特殊cutgraph,每一个systermofloops都由具有公共基点的2g个环组成,如图4所示.Erickson等[6]给出了一个简单的贪婪算法来计算基本群和第一同调群的生成元,这同时也解决了deVerdière和Lazarus提出了最短systermofloops问题. 计算共形几何 曲面上一些与特征紧密相关的环,比如handles和tunnels,在诸如拓扑修复、曲面参数化和特征识别等应用中非常有用,如图5所示.Dey等[7--9]给出了计算handles和tunnels的算法.Yin等[10]提出了使用universalcoveringspace来计算最短非平凡环的算法.deVerdière[11]使用最优pants分解来找同伦类中的最短环.Xin等[12]研究了高亏格曲面上的测地环.关于曲面上的非平凡环,还有许多文章[13--19],目前仍是一个热点问题. (a)调和1形式 (b)共轭的调和1形式 图6:调和1形式 2.2平面区域 传统的数值复分析方法集中在平面区域的共形映射.[20--25]作了详尽总结.Schwarz-Christoffel映射已经被广泛应用于计算共形映射[26,27].[28--30]研究了多连通区域的Schwarz-Christoffel映射.[31]给出了一种基于交比和Delaunay三角化的鲁棒算法.最近,Marshall等[32]引进了基于迭代简单映射的geodesiczippper算法,Bishop[33]提出了基于双曲几何的线性复杂度的共形映射算法. 2.3亏格为0的曲面 [34]利用余切公式构造了离散调和映射,Lévy等[35]引进了Cauchy-Riemann方程的一阶有限元逼近.2002年,Desbrun等[36]最小化Dirichlet能量得到了离散内蕴参数化.Floater[37]引进平均值坐标来计算广义调和映射.[38,39]对拓扑球面的共形映射进行了研究.在CG领域,[40,41]对拓扑圆盘和球面上的共形映射进行了详尽地总结. 计算共形几何 2.4高亏格曲面 高亏格曲面上共形结构的计算有两个主要方法:全纯微分方法和离散曲率流方法. 图7:全纯1形式 2.4.1全纯微分 离散全纯微分方法是由Gu和Yau[42,43]提出的,用来计算高亏格曲面上的共形结构.这个方法基于Hodge理论,使用热扩散方法来计算每一个上同调类中的调和形式,见图6(a)和6(b).然后利用Hodge星算子构造全纯形式,见图
7.所有计算都是在离散多边形曲面上进行的.Pinkall等[34]定义了一种不同的离散Hodge星算子来计算极小曲面.Mercat[44]通过离散Cauchy-Riemann方程来构造离散全纯映射,不过这个方法要求曲面是四边形网格.2003年,Hirani在他的博士论文[45]中详细介绍了离散外微分方法. Gortler等[46,47]使用离散1形式来对亏格为1的曲面进行参数化.Tong等[48]推广到带有锥奇点的1形式方法,并用来进行remeshing和tiling.2009年,Zeng等[49,50]将全纯微分方法应用于计算带多个边界的亏格为0的曲面上的共形映射,以及拟共形映射. 2.4.2iFlow i流是由Hamilton[51]在Princeton的讨论班上引进的.i流对曲面和三维流形的几何研究产生了革命性的影响,是当前几何研究中极为活跃的方向.特别地, 计算共形几何 它导致了三维Poincaré猜测的证明.Hamilton[52]使用2维i流给出了正亏格曲面uniformization定理的证明.这表明了它在CG领域中有极大的潜在应用价值. 图8:Circlepacking存在很多方法离散光滑曲面,其中与共形映射离散特别相关的是由Thurston[53]引进的circlepacking度量.circlepacking这个概念首先是由Koebe提出的,Thurston猜测平面Jordan区域的circlepacking离散序列收敛于Riemann映射,见图
8.这个猜测被Rodin和Sullivan[54]所证明.ColindeVerdière[55]建立了circlepacking的第一变分原理,然后证明了Thurston的circlepacking度量存在性.这为实现计算circlepacking度量的快速算法铺平了道路,比如Collins和Stephenson[56]就给出了一个算法.Chow和Luo[57]推广了ColindeVerdière的工作,并引进了曲面上的离散i流和离散i能量.它们证明了离散i流的一般存在性和收敛性定理,同时证明了i能量的凸的.基于此,Jin[58]在2008年给出了离散i流的算法实现.另外一个相关的离散方法是circlepattern,它同时考虑网格曲面的组合与几何信息,可以看成是circlepacking的变种.Circlepattern是由Bowers和Hurdal[59]提出的,已经被证明是Bobenko和Springborn[60]提出的凸能量的极小元.2006年,Kharevych等[61]给出了一个有效的circlepattern算法. 2.4.3YamabeFlow Yamabe问题目的是为紧Riemann流形找到具有常标量曲率的共形度量.Yamabe[62]给出了第一个带有漏洞的证明,之后被一些包括Trudinger[63],Aubin[64]和Schoen[65]在内的研究者所更正.关于这个问题的详细总结可以参看Lee和Parker的文章[66]. 2004年,Luo[67]研究了曲面上的离散Yamabe流.他引进了多边形度量的离散共形 计算共形几何 变换概念,这在研究离散Yamabe流和相应的变分原理方面具有关键性的作用.基于离散共形类和几何方面的考虑,Luo定义离散Yamabe能量为微分1形式的积分,然后证明了这个能量是一个局部凸函数.他还从这得出Yamabe流下的曲率发展是一个热方程. 最近,Springborn等[68]的一个非常漂亮的工作表明可以将Yamabe能量和MilnorLobachevsky函数等同起来,将曲率发展的热方程和余切Laplace方程等同起来.近期Gu等[69]使用离散Yamabe能量构造了一个计算离散共形度量的有效算法.Bobenko等[70]讨论了离散双曲Yamabe流,它被Zeng等[71]用来计算双曲结构和标准同伦群生成元. 图9:全局共形的纹理映照 图10:使用特殊的平坦度量设计向量场 2.5应用2.5.1图形学 共形几何方法广泛应用于CG中.等温坐标对于全局共形参数化来说是很自然的[42].因为共形映照不会扭曲局部形状,所以它对于纹理映照来说是非常理想的.图9显示了一个使用全纯微分进行纹理映照的例子.特殊的平坦度量对于设计曲面上的向量场是非常有价值的,图10显示了使用曲率流方法设计的向量场. 计算共形几何 图11:流形样条框架 2.5.2几何建模 几何建模中的一个最基本的问题就是将传统的欧式区域上的样条系统地推广到流形区域上,这与曲面上的一般几何结构关系紧密,见图11和12. 传统的样条方案是建立在仿射不变量上的,如果流形具有仿射结构,那么传统的样条也能直接推广到流形上.然而由于拓扑障碍,一般的流形不具有仿射结构.但是删去一些奇点后,曲面上允许存在仿射结构.详细的讨论请参考Gu等[72]. 仿射结构可以通过共形几何方法显式计算.比如可以通过曲率流和全纯微分方法来计算仿射结构,图13显示的是用曲率流方法构造的仿射结构.与其他的方法比较起来,比如基于平凡联络的方法[73],这些方法的优点是它能给出样条曲面的全局共形参数化,即等温坐标.在这种坐标下,微分算子,比如梯度算子和Laplace-Beltrami算子,具有最简单的形式. 2.5.3医学成像 共形几何在医学成像的很多领域都有应用.比如在脑电图中,不同部分的大脑皮层曲面片的注册是关键性的.大脑表面高度卷曲,而且不同的人的大脑有不同的解剖结构, 计算共形几何 图12:流形样条 图13:仿射结构因此在大脑皮层曲面片之间找到好的匹配是非常有挑战性的任务.图14演示了一个解决方案[39],先通过用标准方式将大脑表面映到球面,然后找到球面的自同构,这样曲面片的注册就很容易建立了. 2.5.4视觉 曲面匹配在计算机视觉中是一个基本问题.图15演示了曲面匹配的基本框架.图16演示了同一个人的不同表情的人脸匹配的例子,细节可参考[74--76].Teichmüller理论可以应用于曲面分类[77,78].通过使用i曲率流,我们可以计算双曲uniformization度量.然后我们使用测地线进行pants分解并计算Fenchel-Nielsen坐标.图17演示了万有覆盖空间在双曲空间中的一个有限部分的计算,图18演示了计算Teichmüller坐标的流程. 计算共形几何 图14:大脑表面的共形映照 图15:曲面匹配框架 2.5.5计算几何 在计算几何中,同伦检测是一个重要的问题.可以使用i流计算双曲uniformization度量[71].根据定理,每一个同伦类中有唯一的闭测地线.给定一个环,我们可以计算这个环的同伦类对应的Möbius变换,这个变换的轴就是双曲度量下的闭测地线.如图19所示,同伦的环的标准代表元是相同的. 计算共形几何 图16:不同表情的人脸匹配 图17:万有覆盖空间在双曲空间中的有限部分 3总结 计算共形几何是一门数学和计算机科学的交叉学科,它对数学理论的掌握要求比较高.很多算法都依赖于拓扑算法,与计算拓扑紧密相关.本文介绍了这个方向的一些基本问题、算法以及应用.目前仍然有很多基本问题没有解决,它们需要更深刻的理解和更强大精确的计算方法.下面列举一些对理论和应用都非常重要的问题.
1.Teichmüller映射给定两个度量曲面和映射同伦类,计算唯一的angledistortion最小的映射,也就是Teichmüller映射. 计算共形几何 图18:Teichmüller空间中的Fenchel-Nielsen坐标 图19:使用双曲度量进行同伦检测
2.Abel微分 计算不同类型的Abel微分群,特别是全纯的二次微分.3.组合结构和共形结构之间的关系 给定一个拓扑曲面,每一个三角化都有一个由circlepacking决定的自然的共形结构,讨论这两个结构之间的关系.4.逼近理论尽管计算共形不变量的算法已经有了,但是逼近的理论结果仍没有建立.对于平面区域的共形映射,不同离散方法的收敛性都已经建立了.但是对于一般曲面而言,收敛性分析仍然是开放的.5.精度和稳定性双曲几何计算对于数值误差是非常敏感的.要提高计算精度是非常具有挑战性的.计算几何中的精确计算方法给出了解决这个问题的方向.在逆距离circlepacking 计算共形几何 方法和组合Yamabe流方法中,可接受曲率空间的非凸性造成了算法的不稳定.因此,曲面需要高精度的三角化.在实际应用中,提高三角化精度对这些算法是非常重要的.交角为锐角的circlepacking算法更加稳定,全纯微分方法最稳定. 计算共形几何 参考文献 [1]Vegter,
G.,Yap,
C.K.,1990.plexitybinatorialsurfaces.In:ProceedingsofthesixthannualsymposiumonComputationalgeometry.NewYork:ACM,102-111. [2]Lazarus,
F.,hiola,
M.,Vegter,
G.,etal,2001.Computingacanonicalpolygonalschemaofanorientabletriangulatedsurface.In:SCG'01:ProceedingsoftheseventeenthannualsymposiumonComputationalgeometry.NewYork:ACM,80-89. [3]Dey,
T.K.,1994.Anewtechniqueputepolygonalschemafor2-manifoldswithapplicationtoydetection.In:ProceedingsofthetenthannualsymposiumonComputationalgeometry.NewYork:ACM,277-284. [4]Erickson,
J.,Har-Peled,
S.,2002.Optimallycuttingasurfaceintoadisk.In:SCG'02:ProceedingsoftheeighteenthannualsymposiumonComputationalgeometry.NewYork:ACM,244-253. [5]deVerdière,
E.C.,Lazarus,
F.,2002.Optimalsystemofloopsonanorientablesurface.In:Proc.43rdAnnualIEEESymp.FoundationsofComputerScience.Springer-Verlag627-636. [6]Erickson,
J.,Whittlesey,
K.,2005.Greedyoptimalyandhomologygenerators.In:SODA'05:ProceedingsofthesixteenthannualACM-SIAMsymposiumonDiscretealgorithms.Philadelphia,PA,USA:SocietyforIndustrialandAppliedMathematics,1038-1046. [7]Dey,
T.K.,Li,
K.,Sun,
J.,2007.putinghandleandtunnelloops.In:CW'07:Proceedingsofthe2007InternationalConferenceonCyberworlds.Washington,DC,USA:IEEEComputerSociety,357-366. [8]Dey,
T.K.,Li,
K.,Sun,
J.,etal,2008.Computinggeometry-awarehandleandtunnelloopsin3dmodels.In:SIGGRAPH'08:ACMSIGGRAPH2008papers.NewYork:ACM,1-
9. [9]Dey,
T.K.,Li,
K.,Sun,
J.,2009.Computinghandleandtunnelloopswithknotlinking.Comput.AidedDes.,41(10):730-738. [10]Yin,
X.,Jin,
M.,Gu,
X.,2007.Computingshortestcyclesusinguniversalcoveringspace.Vis.Comput.,23(12):999-1004. [11]Verdière,
E.C.D.,Lazarus,
F.,2007.Optimalpantspositionsandshortesticcyclesonanorientablesurface.J.ACM,54
(4):18. [12]Xin,
S.Q.,He,
Y.,Fu,
C.W.,etal,2011.Euclideangeodesicloopsonhigh-genussurfacesappliedtothemorphometryofvestibularsystems.In:MICCAI'11:Proceedingsofthe14thinternationalconferenceonMedicalputingputer-assistedintervention.Berlin,Heidelberg:Springer-Verlag,384-392. [13]Chambers,
E.W.,Erickson,
J.,Worah,
P.,2008.Testingcontractibilityinplanarplexes.In:SCG'08:Proceedingsofthetwenty-fourthannualsymposiumonComputationalgeometry.NewYork:ACM,251-259. [14]Chambers,
E.W.,Erickson,
J.,Nayyeri,
A.,2009.Minimumcutsandshortesthomologouscycles.In:SCG'09:Proceedingsofthe25thannualsymposiumonComputationalgeometry.NewYork:ACM,377-385. [15]Chambers,
E.W.,Erickson,
J.,Nayyeri,
A.,2009.Homologyflows,cohomologycuts.In:STOC 计算共形几何 '09:Proceedingsofthe41stannualACMsymposiumonTheoryputing.NewYork:ACM,273-282.[16]Erickson,
J.,2010.Maximumflowsandparametricshortestpathsinplanargraphs.In:SODA'10:ProceedingsoftheTwenty-FirstAnnualACM-SIAMSymposiumonDiscreteAlgorithms.Philadelphia,PA,USA:SocietyforIndustrialandAppliedMathematics,794-804.[17]Erickson,
J.,Worah,
P.,2010.Computingtheshortestessentialcycle.DiscreteComput.Geom.,44
(4):912-930.[18]Dey,
T.K.,Hirani,
A.N.,Krishnamoorthy,
B.,2010.Optimalhomologouscycles,totalunimodularity,andlinearprogramming.In:STOC'10:Proceedingsofthe42ndACMsymposiumonTheoryputing.NewYork:ACM,221-230.[19]Erickson,
J.,2011.Shortestnon-trivialcyclesindirectedsurfacegraphs.In:SoCG'11:Proceedingsofthe27thannualACMsymposiumonComputationalgeometry.NewYork:ACM,236-243.[20]Delillo,
T.K.,1994.Theuracyofnumericalconformalmappingmethods:Asurveyofexamplesandresults.SIAMJournalonNumericalAnalysis,31
(3):pp.788-812.[21]Ivanov,
M.,V.T,1995.Handbookofconformalmappingputer-aidedvisualization.BocaRaton:CRCPress.[22]Binder,
I.,Braverman,
M.,Yampolsky,
M.,2007.Onplexityoftheriemannmapping.ARKIVFORMATEMATIK,45
(2):221-239.[23]Trefethen,
L.,1986.Numericalconformalmapping.Amsterdam:North-HollandPublishingCo.[24]Wegmann,
R.,2005.HandbookofComplexAnalysis:GeometricFunctionTheory.vol2.Amsterdam:Elsevier,351-477.[25]Henrici,,1993.DiscreteFourierAnalysis,CauchyIntegrals,ConstructionofConformalMaps,UnivalentFunctions.vol3.London:Wiley.[26]Driscoll,
T.A.,Trefethen,
L.N.2002.Schwarz-ChristoffelMapping.CambridgePress.[27]Banjai,
L.,Trefethen,
L.N.,2003.Amultipolemethodforschwarz--christoffelmappingofpolygonswiththousandsofsides.SIAMJ.Sci.Comput.,25
(3):1042-1065.[28]DeLillo,
T.K.,Elcrat,
A.R.,Pfaltzgraff,
J.A.,2001.Schwarz-christoffelmappingoftheannulus.SIAMReview,43
(3):pp.469-477.[29]Delillo,
T.,Elcrat,
A.,Pfaltzgraff,
J.,2004.Schwarz-christoffelmappingofmultiplyconnecteddomains.Journald'AnalyseMathématique,94:17-47.[30]Crowdy,
D.,2005.Theschwarz-christoffelmappingtoboundedmultiplyconnectedpolygonaldomains.Proceedings:Mathematical,PhysicalandEngineeringSciences,461(2061):pp.26532678.[31]Driscoll,
T.A.,Vavasis,
S.A.,1998.Numericalconformalmappingusingcross-ratiosanddelaunaytriangulation.SIAMJ.Sci.Comput.,19:1783-1803.[32]Marshall,
D.E.,Rohde,
S.,2007.Convergenceofavariantofthezipperalgorithmforconformalmapping.SIAMJ.Numer.Anal.,45:2577-2609. 计算共形几何 [33]Bishop,
C.J.,2010.Conformalmappinginlineartime.DiscreteComput.Geom.,44:330-428. [34]Pinkall,
U.,Polthier,
K.,1993.Computingdiscreteminimalsurfacesandtheirconjugates.ExperimentalMathematics,2:15-36. [35]Lévy,
B.,Petitjean,
S.,Ray,
N.,etal,2002.Leastsquaresconformalmapsforautomatictextureatlasgeneration.In:Proceedingsofthe29thannualconferenceonComputergraphicsandinteractivetechniques.NewYork:ACM,362-371. [36]Desbrun,
M.,Meyer,
M.,Alliez,
P.,2002.Intrinsicparameterizationsofsurfacemeshes.ComputerGraphicsForum,21
(3):209-218. [37]Floater,
M.S.,2003.Meanvaluecoordinates.Comput.AidedGeom.Des.,20:19-27. [38]Gotsman,
C.,Gu,
X.,Sheffer,
A.,2003.Fundamentalsofsphericalparameterizationfor3dmeshes.In:SIGGRAPH'03:ACMSIGGRAPH2003Papers.NewYork:ACM,358-363. [39]Gu,
X.,Wang,
Y.,Chan,
T.F.,etal,2004.Genuszerosurfaceconformalmappinganditsapplicationtobrainsurfacemapping.IEEETransactionsonMedicalImaging,23:949-958. [40]Floater,
M.S.,Hormann,
K.,2005.Surfaceparameterization:atutorialandsurvey.In:Dodgson,
N.A.,Floater,
M.S.,Sabin,
M.A..Advancesinmultiresolutionforgeometricmodelling.SpringerVerlag,157-186. [41]Sheffer,
A.,Praun,
E.,Rose,
K.,2006.Meshparameterizationmethodsandtheirapplications.Found.Trends.Comput.Graph.Vis.,2:105-171. [42]Gu,
X.,Yau,
S.T.,2003.Globalconformalsurfaceparameterization.In:SGP'03:Proceedingsofthe2003Eurographics/ACMSIGGRAPHsymposiumonGeometryprocessing.Aire-la-Ville,Switzerland,Switzerland:EurographicsAssociation,127-137. [43]Jin,
M.,Wang,
Y.,Yau,
S.T.,etal,2004.Optimalglobalconformalsurfaceparameterization.In:VIS'04:ProceedingsoftheconferenceonVisualization'04.Washington,DC,USA:IEEEComputerSociety,267-274. [44]Mercat,
C.,2001.Discreteriemannsurfacesandtheisingmodel.CommunicationsinMathematicalPhysics,218:177-216. [45]Hirani,
A.N.,2003.Discreteexteriorcalculus.PhDthesis.Pasadena,CA,USA:CaliforniaInstituteofTechnology. [46]Gortler,
S.J.,Gotsman,
C.,Thurston,
D.,2006.Discreteone-formsonmeshesandapplicationsto3dmeshparameterization.Comput.AidedGeom.Des.,23:83-112. [47]Tewari,
G.,Gotsman,
C.,Gortler,
S.J.,2006.Meshinggenus-1pointcloudsusingdiscreteoneforms.ComputersandGraphics,30:917-926. [48]Tong,
Y.,Alliez,
P.,Cohen-Steiner,
D.,etal,2006.Designingquadrangulationswithdiscreteharmonicforms.In:ProceedingsofthefourthEurographicssymposiumonGeometryprocessing.Aire-la-Ville,Switzerland,Switzerland:EurographicsAssociation,201-210. [49]Zeng,
W.,Yin,
X.,Zhang,
M.,etal,2009.Generalizedkoebe'smethodforconformalmappingmultiplyconnecteddomains.In:SPM'09:2009SIAM/ACMJointConferenceonGeometricand 计算共形几何 PhysicalModeling.NewYork:ACM,89-100.[50]Zeng,
W.,Luo,
F.,Yau,
S.T.,etal,2009.Surfacequasi-conformalmappingbysolvingbeltrami equations.In:Proceedingsofthe13thIMAInternationalConferenceonMathematicsofSurfacesXIII.Berlin,Heidelberg:Springer-Verlag,391-408.[51]Hamilton,
R.,1982.Threemanifoldswithpositiveicurvature.J.Differ.Geom.,17:255-306.[52]Hamilton,
R.,1988.MathematicsandGeneralRelativity.vol71.AmericanMathematicalSociety.[53]Thurston,
W.,1980.GeometryandTopologyofThree-Manifolds.PrincetonUniversityPress.[54]Rodin,
B.,Sullivan,
D.,1987.Theconvergenceofcirclepackingstotheriemannmapping.J.Differ.Geom.,26
(2):349-360.[55]ColindeVerdière,
Y.,1991.Unprinciplevariationnelpourlesempilementsdecercles.Invent.Math.,104
(3):655-669.[56]Collins,
C.R.,Stephenson,
K.,2003.Acirclepackingalgorithm.Comput.Geom.TheoryAppl.,25:233-256.[57]Chow,
B.,Luo,
F.,2003.Combinatorialiflowsonsurfaces.J.Differ.Geom.,63
(1):97-129.[58]Jin,
M.,Kim,
J.,Luo,
F.,etal,2008.Discretesurfaceiflow.IEEETransactionsonVisualizationandComputerGraphics,14
(5):1030-1043.[59]Bowers,
P.L.,Hurdal,
M.K.,2003.Planarconformalmappingsofpiecewiseflatsurfaces.In:InVisualizationandMathematicsIII,
H.-C.HegeandK.Polthier,Eds.MathematicsandVisualization.Springer-Verlag3-34.[60]Bobenko,
A.I.,Springborn,
B.A.,2004.Variantionalprinciplesforcirclepatternsandkoebe'stheorem.Trans.Am.Math.Soc.,356:659-689.[61]Kharevych,
L.,Springborn,
B.,Schröder,
P.,2006.Discreteconformalmappingsviacirclepatterns.ACMTrans.Graph.,25:412-438.[62]Yamabe,
H.,1960.Theyamabeproblem.OsakaMath.J.,12
(1):21-37.[63]Trudinger,
N.,1968.Remarksconcerningtheconformaldeformationofriemannianstructurespactmanifolds.Ann.ScuolaNorm.Sup.Pisa,22
(2):265-274.[64]Aubin,
T.,1976.équationsdiffréntiellesnonlinéairesetproblèmedeyamabeconcernantlacourburescalaire.J.Math.PureAppl.,55
(3):269-296.[65]Schoen,
R.,1984.Conformaldeformationofariemannmetrictoconstantscalarcurvature.J.Differ.Geom.,20
(2):479-495.[66]Lee,
J.M.,Parker,
T.H.,1987.Theyamabeproblem.Bull.Am.Math.Soc.,17
(1):39-71.[67]Luo,
F.,Khan,
L.,Bastani,
F.,etal,2004.Adynamicallygrowinganizingtree(dgsot)forhierarchicalclusteringgeneexpressionprofiles.Bioinformatics,20(16):2605-2617.[68]Springborn,
B.,Schröder,
P.,Pinkall,
U.,2008.Conformalequivalenceoftrianglemeshes.In:SIGGRAPHAsia'08:ACMSIGGRAPHASIA2008courses.NewYork:ACM,1-11.[69]Yin,
X.,Jin,
M.,Luo,
F.,etal,2009.Emergingtrendsinputing.In:.Berlin,Heidelberg: 计算共形几何 Springer-Verlag,38-74.[70]Bobenko,
A.,Springborn,
B.,Pinkall,
U.,2010.Discreteconformalmapsandidealhyperbolic polyhedra.arXiv:1005.2698.[71]Zeng,
W.,Jin,
M.,Luo,
F.,etal,2009.Canonicalyclassrepresentativeusinghyperbolic structure.In:Proc.IEEEInt.Conf.ShapeModelingandApplicationsSMI2009.171-178.[72]Gu,
X.,He,
Y.,Qin,
H.,2006.Manifoldsplines.Graph.Models,68
(3):237-254.[73]Crane,
K.,Desbrun,
M.,Schröder,
P.,2010.Trivalconnectionsondiscretesurfaces.Comput. Graph.Forum,29
(5):1525-1533.[74]Wang,
S.,Wang,
Y.,Jin,
M.,etal,2007.Conformalgeometryanditsapplicationson3dshape matching,recognition,andstitching.IEEETrans.PatternAnal.Mach.Intell.,29
(7):1209-1220.[75]Zeng,
W.,Zeng,
Y.,Wang,
Y.,etal,2008.3dnon-rigidsurfacematchingandregistrationbased onholomorphicdifferentials.In:ECCV'08:Proceedingsofthe10thEuropeanConferenceonComputerVision.Berlin,Heidelberg:Springer-Verlag,1-14.[76]Zeng,
W.,Samaras,
D.,Gu,
D.,2010.iflowfor3dshapeanalysis.IEEETrans.PatternAnal.Mach.Intell.,32
(4):662-677.[77]Zeng,
W.,Lui,
L.M.,Gu,
X.,Yau,
S.T.,2008.Shapeanalysisbyconformalmodules.MethodsAppl.Anal.,15
(4):539-556.[78]Jin,
M.,Zeng,
W.,Ning,
D.,Gu,
X.,2009.Computingfenchel-nielsencoordinatesinteichmüllershapespace.In:IEEEInternationalSymposiumonInformationProcessinginSensorNetworks.121-132.
1.共形结构给定一张带有黎曼度量的曲面,计算它的内蕴共形结构的不同表示.一种方法是计算它的Abelian微分群,另一种方法是计算标准的黎曼度量.
2.共形模完全共形不变量称为黎曼曲面的共形模.正如前面所讲的,理论上存在一组有限的数完全决定了黎曼曲面,这些称为黎曼曲面的共形模.一个比较难的问题是显式计算任意给定曲面的共形模.
3.标准黎曼度量黎曼曲面的uniformization定理揭示了每一个黎曼度量都共形等价于一个常Gauss曲率度量.除了球面和环面外,这个度量是唯一的.计算这个度量在计算共形几何中具有基本的重要性.
4.共形映射 计算共形几何 计算两个共形等价的曲面之间的共形映射可以简化为计算它们到标准形状空间(球面、平面、双曲空间中的圆域)之间的共形映射.
5.拟共形映射大部分微分同胚都不是共形的,它们将无穷小圆周映成无穷小椭圆.如果这些椭圆的长短轴比一致有界,那么就称为拟共形映射.拟共形映射的微分是由所谓的Beltrami微分刻画的,Beltrami微分记录了长轴方向和长短轴比.有一个基本定理是说通过Beltrami微分可以恢复拟共形映射.而至于怎样通过Beltrami微分计算拟共形映射,则是一个具有很多应用价值的重要问题.
6.共形镶嵌粘合带边黎曼曲面并研究缝曲线形状和粘合样式之间的关系.这与拟共形映射问题紧密相关. 1.3共形几何在工程应用中的优点 计算共形几何已经被证实在许多工程领域中有重要应用.下面是一些主要理由:
1.标准区域所有带度量的曲面都能共形地映成球面、平面或双曲圆盘中的标准区域.这可以帮助我们将三维几何处理问题转化为二维问题.
2.通过曲率设计度量每一个共形结构都有一个常Gauss曲率的标准度量,这个度量在很多几何应用中非常有价值.例如在双曲度量下,每一个非平凡同伦类都有一个闭测地线代表元.此外,我们可以根据预先给定的曲率设计黎曼度量,这在几何建模中非常有用.
3.一般几何结构共形几何方法能够用来构造其他几何结构,比如仿射结构、射影结构等等.这些结构在几何建模应用中是关键的.
4.微分同胚的构造共形映照和拟共形映照可以被用来构造曲面间的微分同胚.可以应用于曲面注册和比较这些计算机视觉和医学图像中最基本的问题. 计算共形几何
5.等温坐标共形结构可以被当作曲面上的等温坐标图册.在这种坐标下,度量的表达式最简单,因此所有的微分算子,比如Laplace-Beltrami算子,具有很简洁的表达式.这可以用来简化偏微分方程.等温坐标保持局部形状,对于可视化和纹理映射是非常完美的. 2已有工作 图3:基本群的多边形表示 图4:四种类型的图.(a)Acutgraph但不是systemofloops.(b)Asystemofloops.(c)基本群的基但不是systemofloops.(d)同调基,但既不是同伦基也不是cutgraph. 计算共形几何已经有比较长的历史了,起初大部分共形几何方法都是针对平面区域或拓扑圆盘的.直到近些年来才推广到具有复杂拓扑的曲面上,这与当前研究热点计算拓扑的发展是紧密相关的.有相当一部分计算共形算法是依赖于计算拓扑算法的. 计算共形几何 图5:从左到右:输入模型,handle(绿)和tunnel(红)环,handle特征 2.1计算拓扑 计算拓扑的研究对象主要是单纯复形,比如三角网格曲面就是一种二维单纯复形.计算拓扑的一些基本问题就是计算曲面单纯复形的cutgraph,同调群和基本群.知道了cutgraph,就能将曲面剪开成拓扑圆盘,这对于参数化和纹理映照是非常有用的.知道了基本群,就能完全确定封闭曲面的拓扑分类.通常基本群是用多边形表示的,其中有约化多边形表示、标准多边形表示等一些特殊的多边形表示,见图
3. Vegter和Yap[1]给出了计算标准多边形表示的算法,Lazarus等[2]简化了Vegter和Yap的算法,复杂度为O(gn),其中n,g分别为曲面的大小和亏格.标准多边形表示由2g个具有公共点的环组成,令人不满意的是它们可能具有公共边.在大部分应用中,标准多边形表示不是必须的,只需要知道cutgraph就足够了.cutgraph是指三角网格曲面上的一族边集使得曲面去掉这些边后变成拓扑圆盘,如图4所示.Dey和Schipper[3]使用cutgraph得到了检验曲线是否可缩或两曲线是否同伦的快速算法.2002年,Erickson等[4]第一次提出了最优cutgraph的问题:给每一条边赋一个权,求权最小的cutgraph.这篇文章证明了最小cutgraph问题是NP难的,并给出了计算近似最小cutgraph的贪婪算法,该算法复杂度为O(g2nlogn),精度为O(log2g).deVerdière和Lazarus[5]研究了一种称为"systermofloops"的特殊cutgraph,每一个systermofloops都由具有公共基点的2g个环组成,如图4所示.Erickson等[6]给出了一个简单的贪婪算法来计算基本群和第一同调群的生成元,这同时也解决了deVerdière和Lazarus提出了最短systermofloops问题. 计算共形几何 曲面上一些与特征紧密相关的环,比如handles和tunnels,在诸如拓扑修复、曲面参数化和特征识别等应用中非常有用,如图5所示.Dey等[7--9]给出了计算handles和tunnels的算法.Yin等[10]提出了使用universalcoveringspace来计算最短非平凡环的算法.deVerdière[11]使用最优pants分解来找同伦类中的最短环.Xin等[12]研究了高亏格曲面上的测地环.关于曲面上的非平凡环,还有许多文章[13--19],目前仍是一个热点问题. (a)调和1形式 (b)共轭的调和1形式 图6:调和1形式 2.2平面区域 传统的数值复分析方法集中在平面区域的共形映射.[20--25]作了详尽总结.Schwarz-Christoffel映射已经被广泛应用于计算共形映射[26,27].[28--30]研究了多连通区域的Schwarz-Christoffel映射.[31]给出了一种基于交比和Delaunay三角化的鲁棒算法.最近,Marshall等[32]引进了基于迭代简单映射的geodesiczippper算法,Bishop[33]提出了基于双曲几何的线性复杂度的共形映射算法. 2.3亏格为0的曲面 [34]利用余切公式构造了离散调和映射,Lévy等[35]引进了Cauchy-Riemann方程的一阶有限元逼近.2002年,Desbrun等[36]最小化Dirichlet能量得到了离散内蕴参数化.Floater[37]引进平均值坐标来计算广义调和映射.[38,39]对拓扑球面的共形映射进行了研究.在CG领域,[40,41]对拓扑圆盘和球面上的共形映射进行了详尽地总结. 计算共形几何 2.4高亏格曲面 高亏格曲面上共形结构的计算有两个主要方法:全纯微分方法和离散曲率流方法. 图7:全纯1形式 2.4.1全纯微分 离散全纯微分方法是由Gu和Yau[42,43]提出的,用来计算高亏格曲面上的共形结构.这个方法基于Hodge理论,使用热扩散方法来计算每一个上同调类中的调和形式,见图6(a)和6(b).然后利用Hodge星算子构造全纯形式,见图
7.所有计算都是在离散多边形曲面上进行的.Pinkall等[34]定义了一种不同的离散Hodge星算子来计算极小曲面.Mercat[44]通过离散Cauchy-Riemann方程来构造离散全纯映射,不过这个方法要求曲面是四边形网格.2003年,Hirani在他的博士论文[45]中详细介绍了离散外微分方法. Gortler等[46,47]使用离散1形式来对亏格为1的曲面进行参数化.Tong等[48]推广到带有锥奇点的1形式方法,并用来进行remeshing和tiling.2009年,Zeng等[49,50]将全纯微分方法应用于计算带多个边界的亏格为0的曲面上的共形映射,以及拟共形映射. 2.4.2iFlow i流是由Hamilton[51]在Princeton的讨论班上引进的.i流对曲面和三维流形的几何研究产生了革命性的影响,是当前几何研究中极为活跃的方向.特别地, 计算共形几何 它导致了三维Poincaré猜测的证明.Hamilton[52]使用2维i流给出了正亏格曲面uniformization定理的证明.这表明了它在CG领域中有极大的潜在应用价值. 图8:Circlepacking存在很多方法离散光滑曲面,其中与共形映射离散特别相关的是由Thurston[53]引进的circlepacking度量.circlepacking这个概念首先是由Koebe提出的,Thurston猜测平面Jordan区域的circlepacking离散序列收敛于Riemann映射,见图
8.这个猜测被Rodin和Sullivan[54]所证明.ColindeVerdière[55]建立了circlepacking的第一变分原理,然后证明了Thurston的circlepacking度量存在性.这为实现计算circlepacking度量的快速算法铺平了道路,比如Collins和Stephenson[56]就给出了一个算法.Chow和Luo[57]推广了ColindeVerdière的工作,并引进了曲面上的离散i流和离散i能量.它们证明了离散i流的一般存在性和收敛性定理,同时证明了i能量的凸的.基于此,Jin[58]在2008年给出了离散i流的算法实现.另外一个相关的离散方法是circlepattern,它同时考虑网格曲面的组合与几何信息,可以看成是circlepacking的变种.Circlepattern是由Bowers和Hurdal[59]提出的,已经被证明是Bobenko和Springborn[60]提出的凸能量的极小元.2006年,Kharevych等[61]给出了一个有效的circlepattern算法. 2.4.3YamabeFlow Yamabe问题目的是为紧Riemann流形找到具有常标量曲率的共形度量.Yamabe[62]给出了第一个带有漏洞的证明,之后被一些包括Trudinger[63],Aubin[64]和Schoen[65]在内的研究者所更正.关于这个问题的详细总结可以参看Lee和Parker的文章[66]. 2004年,Luo[67]研究了曲面上的离散Yamabe流.他引进了多边形度量的离散共形 计算共形几何 变换概念,这在研究离散Yamabe流和相应的变分原理方面具有关键性的作用.基于离散共形类和几何方面的考虑,Luo定义离散Yamabe能量为微分1形式的积分,然后证明了这个能量是一个局部凸函数.他还从这得出Yamabe流下的曲率发展是一个热方程. 最近,Springborn等[68]的一个非常漂亮的工作表明可以将Yamabe能量和MilnorLobachevsky函数等同起来,将曲率发展的热方程和余切Laplace方程等同起来.近期Gu等[69]使用离散Yamabe能量构造了一个计算离散共形度量的有效算法.Bobenko等[70]讨论了离散双曲Yamabe流,它被Zeng等[71]用来计算双曲结构和标准同伦群生成元. 图9:全局共形的纹理映照 图10:使用特殊的平坦度量设计向量场 2.5应用2.5.1图形学 共形几何方法广泛应用于CG中.等温坐标对于全局共形参数化来说是很自然的[42].因为共形映照不会扭曲局部形状,所以它对于纹理映照来说是非常理想的.图9显示了一个使用全纯微分进行纹理映照的例子.特殊的平坦度量对于设计曲面上的向量场是非常有价值的,图10显示了使用曲率流方法设计的向量场. 计算共形几何 图11:流形样条框架 2.5.2几何建模 几何建模中的一个最基本的问题就是将传统的欧式区域上的样条系统地推广到流形区域上,这与曲面上的一般几何结构关系紧密,见图11和12. 传统的样条方案是建立在仿射不变量上的,如果流形具有仿射结构,那么传统的样条也能直接推广到流形上.然而由于拓扑障碍,一般的流形不具有仿射结构.但是删去一些奇点后,曲面上允许存在仿射结构.详细的讨论请参考Gu等[72]. 仿射结构可以通过共形几何方法显式计算.比如可以通过曲率流和全纯微分方法来计算仿射结构,图13显示的是用曲率流方法构造的仿射结构.与其他的方法比较起来,比如基于平凡联络的方法[73],这些方法的优点是它能给出样条曲面的全局共形参数化,即等温坐标.在这种坐标下,微分算子,比如梯度算子和Laplace-Beltrami算子,具有最简单的形式. 2.5.3医学成像 共形几何在医学成像的很多领域都有应用.比如在脑电图中,不同部分的大脑皮层曲面片的注册是关键性的.大脑表面高度卷曲,而且不同的人的大脑有不同的解剖结构, 计算共形几何 图12:流形样条 图13:仿射结构因此在大脑皮层曲面片之间找到好的匹配是非常有挑战性的任务.图14演示了一个解决方案[39],先通过用标准方式将大脑表面映到球面,然后找到球面的自同构,这样曲面片的注册就很容易建立了. 2.5.4视觉 曲面匹配在计算机视觉中是一个基本问题.图15演示了曲面匹配的基本框架.图16演示了同一个人的不同表情的人脸匹配的例子,细节可参考[74--76].Teichmüller理论可以应用于曲面分类[77,78].通过使用i曲率流,我们可以计算双曲uniformization度量.然后我们使用测地线进行pants分解并计算Fenchel-Nielsen坐标.图17演示了万有覆盖空间在双曲空间中的一个有限部分的计算,图18演示了计算Teichmüller坐标的流程. 计算共形几何 图14:大脑表面的共形映照 图15:曲面匹配框架 2.5.5计算几何 在计算几何中,同伦检测是一个重要的问题.可以使用i流计算双曲uniformization度量[71].根据定理,每一个同伦类中有唯一的闭测地线.给定一个环,我们可以计算这个环的同伦类对应的Möbius变换,这个变换的轴就是双曲度量下的闭测地线.如图19所示,同伦的环的标准代表元是相同的. 计算共形几何 图16:不同表情的人脸匹配 图17:万有覆盖空间在双曲空间中的有限部分 3总结 计算共形几何是一门数学和计算机科学的交叉学科,它对数学理论的掌握要求比较高.很多算法都依赖于拓扑算法,与计算拓扑紧密相关.本文介绍了这个方向的一些基本问题、算法以及应用.目前仍然有很多基本问题没有解决,它们需要更深刻的理解和更强大精确的计算方法.下面列举一些对理论和应用都非常重要的问题.
1.Teichmüller映射给定两个度量曲面和映射同伦类,计算唯一的angledistortion最小的映射,也就是Teichmüller映射. 计算共形几何 图18:Teichmüller空间中的Fenchel-Nielsen坐标 图19:使用双曲度量进行同伦检测
2.Abel微分 计算不同类型的Abel微分群,特别是全纯的二次微分.3.组合结构和共形结构之间的关系 给定一个拓扑曲面,每一个三角化都有一个由circlepacking决定的自然的共形结构,讨论这两个结构之间的关系.4.逼近理论尽管计算共形不变量的算法已经有了,但是逼近的理论结果仍没有建立.对于平面区域的共形映射,不同离散方法的收敛性都已经建立了.但是对于一般曲面而言,收敛性分析仍然是开放的.5.精度和稳定性双曲几何计算对于数值误差是非常敏感的.要提高计算精度是非常具有挑战性的.计算几何中的精确计算方法给出了解决这个问题的方向.在逆距离circlepacking 计算共形几何 方法和组合Yamabe流方法中,可接受曲率空间的非凸性造成了算法的不稳定.因此,曲面需要高精度的三角化.在实际应用中,提高三角化精度对这些算法是非常重要的.交角为锐角的circlepacking算法更加稳定,全纯微分方法最稳定. 计算共形几何 参考文献 [1]Vegter,
G.,Yap,
C.K.,1990.plexitybinatorialsurfaces.In:ProceedingsofthesixthannualsymposiumonComputationalgeometry.NewYork:ACM,102-111. [2]Lazarus,
F.,hiola,
M.,Vegter,
G.,etal,2001.Computingacanonicalpolygonalschemaofanorientabletriangulatedsurface.In:SCG'01:ProceedingsoftheseventeenthannualsymposiumonComputationalgeometry.NewYork:ACM,80-89. [3]Dey,
T.K.,1994.Anewtechniqueputepolygonalschemafor2-manifoldswithapplicationtoydetection.In:ProceedingsofthetenthannualsymposiumonComputationalgeometry.NewYork:ACM,277-284. [4]Erickson,
J.,Har-Peled,
S.,2002.Optimallycuttingasurfaceintoadisk.In:SCG'02:ProceedingsoftheeighteenthannualsymposiumonComputationalgeometry.NewYork:ACM,244-253. [5]deVerdière,
E.C.,Lazarus,
F.,2002.Optimalsystemofloopsonanorientablesurface.In:Proc.43rdAnnualIEEESymp.FoundationsofComputerScience.Springer-Verlag627-636. [6]Erickson,
J.,Whittlesey,
K.,2005.Greedyoptimalyandhomologygenerators.In:SODA'05:ProceedingsofthesixteenthannualACM-SIAMsymposiumonDiscretealgorithms.Philadelphia,PA,USA:SocietyforIndustrialandAppliedMathematics,1038-1046. [7]Dey,
T.K.,Li,
K.,Sun,
J.,2007.putinghandleandtunnelloops.In:CW'07:Proceedingsofthe2007InternationalConferenceonCyberworlds.Washington,DC,USA:IEEEComputerSociety,357-366. [8]Dey,
T.K.,Li,
K.,Sun,
J.,etal,2008.Computinggeometry-awarehandleandtunnelloopsin3dmodels.In:SIGGRAPH'08:ACMSIGGRAPH2008papers.NewYork:ACM,1-
9. [9]Dey,
T.K.,Li,
K.,Sun,
J.,2009.Computinghandleandtunnelloopswithknotlinking.Comput.AidedDes.,41(10):730-738. [10]Yin,
X.,Jin,
M.,Gu,
X.,2007.Computingshortestcyclesusinguniversalcoveringspace.Vis.Comput.,23(12):999-1004. [11]Verdière,
E.C.D.,Lazarus,
F.,2007.Optimalpantspositionsandshortesticcyclesonanorientablesurface.J.ACM,54
(4):18. [12]Xin,
S.Q.,He,
Y.,Fu,
C.W.,etal,2011.Euclideangeodesicloopsonhigh-genussurfacesappliedtothemorphometryofvestibularsystems.In:MICCAI'11:Proceedingsofthe14thinternationalconferenceonMedicalputingputer-assistedintervention.Berlin,Heidelberg:Springer-Verlag,384-392. [13]Chambers,
E.W.,Erickson,
J.,Worah,
P.,2008.Testingcontractibilityinplanarplexes.In:SCG'08:Proceedingsofthetwenty-fourthannualsymposiumonComputationalgeometry.NewYork:ACM,251-259. [14]Chambers,
E.W.,Erickson,
J.,Nayyeri,
A.,2009.Minimumcutsandshortesthomologouscycles.In:SCG'09:Proceedingsofthe25thannualsymposiumonComputationalgeometry.NewYork:ACM,377-385. [15]Chambers,
E.W.,Erickson,
J.,Nayyeri,
A.,2009.Homologyflows,cohomologycuts.In:STOC 计算共形几何 '09:Proceedingsofthe41stannualACMsymposiumonTheoryputing.NewYork:ACM,273-282.[16]Erickson,
J.,2010.Maximumflowsandparametricshortestpathsinplanargraphs.In:SODA'10:ProceedingsoftheTwenty-FirstAnnualACM-SIAMSymposiumonDiscreteAlgorithms.Philadelphia,PA,USA:SocietyforIndustrialandAppliedMathematics,794-804.[17]Erickson,
J.,Worah,
P.,2010.Computingtheshortestessentialcycle.DiscreteComput.Geom.,44
(4):912-930.[18]Dey,
T.K.,Hirani,
A.N.,Krishnamoorthy,
B.,2010.Optimalhomologouscycles,totalunimodularity,andlinearprogramming.In:STOC'10:Proceedingsofthe42ndACMsymposiumonTheoryputing.NewYork:ACM,221-230.[19]Erickson,
J.,2011.Shortestnon-trivialcyclesindirectedsurfacegraphs.In:SoCG'11:Proceedingsofthe27thannualACMsymposiumonComputationalgeometry.NewYork:ACM,236-243.[20]Delillo,
T.K.,1994.Theuracyofnumericalconformalmappingmethods:Asurveyofexamplesandresults.SIAMJournalonNumericalAnalysis,31
(3):pp.788-812.[21]Ivanov,
M.,V.T,1995.Handbookofconformalmappingputer-aidedvisualization.BocaRaton:CRCPress.[22]Binder,
I.,Braverman,
M.,Yampolsky,
M.,2007.Onplexityoftheriemannmapping.ARKIVFORMATEMATIK,45
(2):221-239.[23]Trefethen,
L.,1986.Numericalconformalmapping.Amsterdam:North-HollandPublishingCo.[24]Wegmann,
R.,2005.HandbookofComplexAnalysis:GeometricFunctionTheory.vol2.Amsterdam:Elsevier,351-477.[25]Henrici,,1993.DiscreteFourierAnalysis,CauchyIntegrals,ConstructionofConformalMaps,UnivalentFunctions.vol3.London:Wiley.[26]Driscoll,
T.A.,Trefethen,
L.N.2002.Schwarz-ChristoffelMapping.CambridgePress.[27]Banjai,
L.,Trefethen,
L.N.,2003.Amultipolemethodforschwarz--christoffelmappingofpolygonswiththousandsofsides.SIAMJ.Sci.Comput.,25
(3):1042-1065.[28]DeLillo,
T.K.,Elcrat,
A.R.,Pfaltzgraff,
J.A.,2001.Schwarz-christoffelmappingoftheannulus.SIAMReview,43
(3):pp.469-477.[29]Delillo,
T.,Elcrat,
A.,Pfaltzgraff,
J.,2004.Schwarz-christoffelmappingofmultiplyconnecteddomains.Journald'AnalyseMathématique,94:17-47.[30]Crowdy,
D.,2005.Theschwarz-christoffelmappingtoboundedmultiplyconnectedpolygonaldomains.Proceedings:Mathematical,PhysicalandEngineeringSciences,461(2061):pp.26532678.[31]Driscoll,
T.A.,Vavasis,
S.A.,1998.Numericalconformalmappingusingcross-ratiosanddelaunaytriangulation.SIAMJ.Sci.Comput.,19:1783-1803.[32]Marshall,
D.E.,Rohde,
S.,2007.Convergenceofavariantofthezipperalgorithmforconformalmapping.SIAMJ.Numer.Anal.,45:2577-2609. 计算共形几何 [33]Bishop,
C.J.,2010.Conformalmappinginlineartime.DiscreteComput.Geom.,44:330-428. [34]Pinkall,
U.,Polthier,
K.,1993.Computingdiscreteminimalsurfacesandtheirconjugates.ExperimentalMathematics,2:15-36. [35]Lévy,
B.,Petitjean,
S.,Ray,
N.,etal,2002.Leastsquaresconformalmapsforautomatictextureatlasgeneration.In:Proceedingsofthe29thannualconferenceonComputergraphicsandinteractivetechniques.NewYork:ACM,362-371. [36]Desbrun,
M.,Meyer,
M.,Alliez,
P.,2002.Intrinsicparameterizationsofsurfacemeshes.ComputerGraphicsForum,21
(3):209-218. [37]Floater,
M.S.,2003.Meanvaluecoordinates.Comput.AidedGeom.Des.,20:19-27. [38]Gotsman,
C.,Gu,
X.,Sheffer,
A.,2003.Fundamentalsofsphericalparameterizationfor3dmeshes.In:SIGGRAPH'03:ACMSIGGRAPH2003Papers.NewYork:ACM,358-363. [39]Gu,
X.,Wang,
Y.,Chan,
T.F.,etal,2004.Genuszerosurfaceconformalmappinganditsapplicationtobrainsurfacemapping.IEEETransactionsonMedicalImaging,23:949-958. [40]Floater,
M.S.,Hormann,
K.,2005.Surfaceparameterization:atutorialandsurvey.In:Dodgson,
N.A.,Floater,
M.S.,Sabin,
M.A..Advancesinmultiresolutionforgeometricmodelling.SpringerVerlag,157-186. [41]Sheffer,
A.,Praun,
E.,Rose,
K.,2006.Meshparameterizationmethodsandtheirapplications.Found.Trends.Comput.Graph.Vis.,2:105-171. [42]Gu,
X.,Yau,
S.T.,2003.Globalconformalsurfaceparameterization.In:SGP'03:Proceedingsofthe2003Eurographics/ACMSIGGRAPHsymposiumonGeometryprocessing.Aire-la-Ville,Switzerland,Switzerland:EurographicsAssociation,127-137. [43]Jin,
M.,Wang,
Y.,Yau,
S.T.,etal,2004.Optimalglobalconformalsurfaceparameterization.In:VIS'04:ProceedingsoftheconferenceonVisualization'04.Washington,DC,USA:IEEEComputerSociety,267-274. [44]Mercat,
C.,2001.Discreteriemannsurfacesandtheisingmodel.CommunicationsinMathematicalPhysics,218:177-216. [45]Hirani,
A.N.,2003.Discreteexteriorcalculus.PhDthesis.Pasadena,CA,USA:CaliforniaInstituteofTechnology. [46]Gortler,
S.J.,Gotsman,
C.,Thurston,
D.,2006.Discreteone-formsonmeshesandapplicationsto3dmeshparameterization.Comput.AidedGeom.Des.,23:83-112. [47]Tewari,
G.,Gotsman,
C.,Gortler,
S.J.,2006.Meshinggenus-1pointcloudsusingdiscreteoneforms.ComputersandGraphics,30:917-926. [48]Tong,
Y.,Alliez,
P.,Cohen-Steiner,
D.,etal,2006.Designingquadrangulationswithdiscreteharmonicforms.In:ProceedingsofthefourthEurographicssymposiumonGeometryprocessing.Aire-la-Ville,Switzerland,Switzerland:EurographicsAssociation,201-210. [49]Zeng,
W.,Yin,
X.,Zhang,
M.,etal,2009.Generalizedkoebe'smethodforconformalmappingmultiplyconnecteddomains.In:SPM'09:2009SIAM/ACMJointConferenceonGeometricand 计算共形几何 PhysicalModeling.NewYork:ACM,89-100.[50]Zeng,
W.,Luo,
F.,Yau,
S.T.,etal,2009.Surfacequasi-conformalmappingbysolvingbeltrami equations.In:Proceedingsofthe13thIMAInternationalConferenceonMathematicsofSurfacesXIII.Berlin,Heidelberg:Springer-Verlag,391-408.[51]Hamilton,
R.,1982.Threemanifoldswithpositiveicurvature.J.Differ.Geom.,17:255-306.[52]Hamilton,
R.,1988.MathematicsandGeneralRelativity.vol71.AmericanMathematicalSociety.[53]Thurston,
W.,1980.GeometryandTopologyofThree-Manifolds.PrincetonUniversityPress.[54]Rodin,
B.,Sullivan,
D.,1987.Theconvergenceofcirclepackingstotheriemannmapping.J.Differ.Geom.,26
(2):349-360.[55]ColindeVerdière,
Y.,1991.Unprinciplevariationnelpourlesempilementsdecercles.Invent.Math.,104
(3):655-669.[56]Collins,
C.R.,Stephenson,
K.,2003.Acirclepackingalgorithm.Comput.Geom.TheoryAppl.,25:233-256.[57]Chow,
B.,Luo,
F.,2003.Combinatorialiflowsonsurfaces.J.Differ.Geom.,63
(1):97-129.[58]Jin,
M.,Kim,
J.,Luo,
F.,etal,2008.Discretesurfaceiflow.IEEETransactionsonVisualizationandComputerGraphics,14
(5):1030-1043.[59]Bowers,
P.L.,Hurdal,
M.K.,2003.Planarconformalmappingsofpiecewiseflatsurfaces.In:InVisualizationandMathematicsIII,
H.-C.HegeandK.Polthier,Eds.MathematicsandVisualization.Springer-Verlag3-34.[60]Bobenko,
A.I.,Springborn,
B.A.,2004.Variantionalprinciplesforcirclepatternsandkoebe'stheorem.Trans.Am.Math.Soc.,356:659-689.[61]Kharevych,
L.,Springborn,
B.,Schröder,
P.,2006.Discreteconformalmappingsviacirclepatterns.ACMTrans.Graph.,25:412-438.[62]Yamabe,
H.,1960.Theyamabeproblem.OsakaMath.J.,12
(1):21-37.[63]Trudinger,
N.,1968.Remarksconcerningtheconformaldeformationofriemannianstructurespactmanifolds.Ann.ScuolaNorm.Sup.Pisa,22
(2):265-274.[64]Aubin,
T.,1976.équationsdiffréntiellesnonlinéairesetproblèmedeyamabeconcernantlacourburescalaire.J.Math.PureAppl.,55
(3):269-296.[65]Schoen,
R.,1984.Conformaldeformationofariemannmetrictoconstantscalarcurvature.J.Differ.Geom.,20
(2):479-495.[66]Lee,
J.M.,Parker,
T.H.,1987.Theyamabeproblem.Bull.Am.Math.Soc.,17
(1):39-71.[67]Luo,
F.,Khan,
L.,Bastani,
F.,etal,2004.Adynamicallygrowinganizingtree(dgsot)forhierarchicalclusteringgeneexpressionprofiles.Bioinformatics,20(16):2605-2617.[68]Springborn,
B.,Schröder,
P.,Pinkall,
U.,2008.Conformalequivalenceoftrianglemeshes.In:SIGGRAPHAsia'08:ACMSIGGRAPHASIA2008courses.NewYork:ACM,1-11.[69]Yin,
X.,Jin,
M.,Luo,
F.,etal,2009.Emergingtrendsinputing.In:.Berlin,Heidelberg: 计算共形几何 Springer-Verlag,38-74.[70]Bobenko,
A.,Springborn,
B.,Pinkall,
U.,2010.Discreteconformalmapsandidealhyperbolic polyhedra.arXiv:1005.2698.[71]Zeng,
W.,Jin,
M.,Luo,
F.,etal,2009.Canonicalyclassrepresentativeusinghyperbolic structure.In:Proc.IEEEInt.Conf.ShapeModelingandApplicationsSMI2009.171-178.[72]Gu,
X.,He,
Y.,Qin,
H.,2006.Manifoldsplines.Graph.Models,68
(3):237-254.[73]Crane,
K.,Desbrun,
M.,Schröder,
P.,2010.Trivalconnectionsondiscretesurfaces.Comput. Graph.Forum,29
(5):1525-1533.[74]Wang,
S.,Wang,
Y.,Jin,
M.,etal,2007.Conformalgeometryanditsapplicationson3dshape matching,recognition,andstitching.IEEETrans.PatternAnal.Mach.Intell.,29
(7):1209-1220.[75]Zeng,
W.,Zeng,
Y.,Wang,
Y.,etal,2008.3dnon-rigidsurfacematchingandregistrationbased onholomorphicdifferentials.In:ECCV'08:Proceedingsofthe10thEuropeanConferenceonComputerVision.Berlin,Heidelberg:Springer-Verlag,1-14.[76]Zeng,
W.,Samaras,
D.,Gu,
D.,2010.iflowfor3dshapeanalysis.IEEETrans.PatternAnal.Mach.Intell.,32
(4):662-677.[77]Zeng,
W.,Lui,
L.M.,Gu,
X.,Yau,
S.T.,2008.Shapeanalysisbyconformalmodules.MethodsAppl.Anal.,15
(4):539-556.[78]Jin,
M.,Zeng,
W.,Ning,
D.,Gu,
X.,2009.Computingfenchel-nielsencoordinatesinteichmüllershapespace.In:IEEEInternationalSymposiumonInformationProcessinginSensorNetworks.121-132.
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。