GAMES301课程笔记11-共形参数化2(离散共形等价类、曲率流)

这个系列是GAMES301-曲面参数化(GAMES 301: Surface Parameterization)的同步课程笔记。课程内容涉及曲面参数化的基本理论与问题描述、面向离散网格的参数化、基于基函数表示的连续参数化、共形参数化、曲面参数化的应用等。本节课继续介绍共形参数化的理论。

Conformal Mapping on Riemann Metric

Riemann Metric

在上一节中我们介绍过共形映射在曲面的局部可以看做旋转和缩放的复合。这样的过程对于平面的情况可以使用复数来进行表示,而在流形上则可以使用四元数来表示。无论哪种情况在进行旋转时需要指定旋转轴,这就要求我们知道曲面切平面和法向,即知道曲面是如何嵌入在空间中的。

实际上仅通过曲面自身的性质也可以实现共形映射。具体来说我们首先需要引入Riemann度量(Riemann metric)的概念,它是曲面切平面(空间)上的一个双线性函数并且定义了切平面上的内积。对于p点切平面上的任意向量X,它的模长为:

|X|=gp(X,X)

而对于切平面上的两个向量XY,Riemann度量定义了它们之间的夹角:

θ[X,Y]=arccos(gp(X,Y)|X| |Y|)

利用Riemann度量的双线性可以定义一个新的度量gp

gp=gp(dfX,dfY)

在这个新的度量上XY的内积为:

gp(X,Y)=|df(X)| |df(Y)| cosθ[df(X),df(Y)]

当映射f为共形映射时XY在映射前后夹角保持不变,此时可以得到gpgp的关系如下:

gp(X,Y)=s2gp(X,Y)

gp相当于在原始度量gp上进行了一个缩放:

gp=e2λgp

上式中λ(,)称为对数共形因子(log conformal factor)

黎曼度量是曲面的内蕴性质,与曲面在空间中的嵌入无关。当曲面发生等距变换时,曲面上的Riemann度量保持不变。

Curvature

黎曼度量与曲面的曲率也有着深刻的联系。曲面上曲线的曲率在法向上的投影称为法曲率(normal curvature),它衡量了曲面上任意点在给定切向上的弯曲程度。可以证明曲面上任意点的所有方向上存在一对相互垂直的方向使得法曲率分别取最大和最小值,这一对曲率称为曲面的主曲率(principle curvature)。几何处理中最常用的曲率包括高斯曲率(Gaussian curvature)K以及平均曲率(mean curvature)H等,其中高斯曲率与Riemann度量都是曲面上的内蕴量与曲面在空间中的嵌入形式无关。

K=k1k2 H=k1+k22

Uniformation Theorem

曲面单值化定理(uniformation theorem)指出任意曲面都可以通过共形映射变换到具有常高斯曲率的曲面上。以任意亏格为0的曲面为例,一定存在一个共形映射能够将它映射到球面上。

单值化定理是非常强大的理论工具,它表明任意拓扑同胚于圆盘的曲面一定可以通过共形映射变换到圆盘上,即实现了共形参数化。更进一步,我们还可以利用共形映射来实现任意两个同胚于圆盘曲面的变换。

基于单值化定理的参数化算法核心在于计算对数共形因子λ。还是以拓扑同胚于圆盘的曲面为例,只要得到了λ在曲面上的分布就可以无扭曲地将曲面参数化到圆盘上。

Isothermal Coordinate

要计算对数共形因子则需要考察高斯曲率在共形映射前后的关系。这里我们引入局部等温坐标(isothermal coordinate)的概念,对于流形上点p处的一个邻域一定存在坐标变换使得其Riemann度量满足:

g=e2η(s,t)(ds2+dt2)

此时变换后的参数坐标(s,t)即为局部等温坐标。回忆在微分几何中曲面的Riemann度量可以表达为:

g=Edx2+2Fdxdy+Gdy2

我们只需要构造(x,y)(s,t)的变换并消掉 dxdy 项就可以得到局部等温坐标的形式。

在等温坐标下高斯曲率有相对简单的表达形式:

K=e2ηΔη

在共形映射下,新的曲面上Riemann度量只与原曲面相差一个对数共形因子λ,此时新的曲面上高斯曲率满足:

K=e2(η+λ)Δ(η+λ)=e2λ(e2ηΔηe2ηΔλ)=e2λ(KΔgλ)

注意这里的Laplace算子是在局部等温坐标(s,t)上定义的。这样就得到了曲面在共形映射前后高斯曲率的关系,即Yamabe方程

而对于曲面上的边界,其测地曲率(geodesic curvature)也具有类似的结论:

κ=eλ(κnMλ)

Yamabe Equation

把上面两种情况结合起来就得到了曲率在共形映射下需要满足的偏微分方程,即Yamabe方程(Yamabe equation)。在求解参数化时只需要分别指定圆盘内部以及边界上的曲率然后通过曲率流进行迭代即可。

Conformal Equivalence of Triangle Meshes

Discrete Conformal Metric

在上一小节中我们介绍了连续光滑曲面上的共形映射理论,而这一小节则会介绍离散曲面上的共形映射计算方法。回忆在共形映射下曲面变换前后的Riemann度量只相差一个系数,因此在离散曲面上我们可以为每一条边赋予这个系数来表达共形映射。此时这条边上的缩放为两个顶点上对数共形因子的平均值:

lij=eλi+λj2lij

Conformal Equivalence

另一种定义共形映射的方法是利用边长的交叉比(cross ratio),可以证明在共形映射下同一条边两个相邻三角形上的交叉比保持不变:

cij=lkilmjlimljk=lkieλk+λi2ljkeλj+λk2lmjeλm+λj2ljkeλj+λk2=lkilmjlimljk=cij

此时对于顶点vi在三角形Δijk上对边ejk所定义的对数共形因子为:

λijk=log(lijlikljk/lijlikljk)

Optimizing Log Conformal Factor

三角形的边长和角度需要满足余弦定理。同时考虑网格内部顶点的内角和为2π,边界顶点上的内角和满足相应的约束。这样优化共形因子就转换为了对三角形角度的优化。

还需要注意的是三角形的边长需要满足三角不等式。当出现不满足三角不等式的情况时,可以通过主动引入退化的方式来保证满足约束。实际进行优化时可以使用一阶方法或是二阶方法。

另一种处理三角不等式的方法是修改三角形的连接关系,通过翻转边的方式来满足三角不等式。

Constraining Length Cross Ratio

除此之外也可以利用交叉比来计算共形映射。由于边长的交叉比在共形映射下保持不变,我们只需要优化网格上顶点的位置并保证边长交叉比不变就实现了共形映射。

Piecewise Möbius Transformation

Möbius Transformation

Möbius变换(Möbius transformation)是复数域到复数域上的映射。对于复数z,它通过Möbius变换可以得到:

f(z)=az+bcz+d

其中参数a,b,c,d为满足adbc0的复数。Möbius变换f(z)的一个性质在于它可以分解为平移(translation)伸缩(dilation)以及反演(inversion)的复合,这保证了Möbius变换可以将复平面上的圆映射为另一个圆。

Piecewise Möbius Transformation

对于三角形,我们可以把Möbius变换作用在它的外接圆上。需要注意的是Möbius变换不能保持直线,原来的直边经过变换后会得到曲线。不过对于分片Möbius变换(piecewise Möbius transformation)我们一般只考虑对顶点的坐标变换,此时只需要把变换后的顶点直接相连即可。因此分片Möbius变换需要保证同一条边在两个相邻三角形定义的变换下有相同的端点。

结合交叉比的概念我们可以利用Möbius变换来实现共形映射。具体来说我们交叉比推广到复数域上,得到复交叉比:

wij=(zkzi)(zmzj)(zizm)(zjzk)

而它的模恰好为实数域中的交叉比:

|wij|=|(zkzi)(zmzj)(zizm)(zjzk)|=lkilmjlimljk

结合Möbius变换在公共边上的约束可以得到公共边上顶点zi需要满足:

|Dijk|=|Dimj|

对于circle packing的问题也有类似的约束条件。

在分片Möbius变换上结合各种约束就可以得到相应的几何变换。

Ricci Flow and Calabi Flow

Ricci Flow

Ricci流(Ricci flow)通过最小化Ricci能量(Ricci energy)来求解Yamabe方程。在共形映射下可以证明Ricci能量关于对数共形因子λ是一个凸函数,且在高斯曲率达到指定值时取全局最小值。

我们在网格上定义对数共形因子λi,然后对高斯曲率进行迭代即可实现离散Ricci流。

在迭代过程中我们还需要更新顶点上的对数共形因子λi。通过一些变形可以把边长以及对数共形因子都表示为角度的函数,这样只需要更新每个三角形上的角度即可。当然在迭代过程中也可能会出现三角形退化的情况,此时可以使用dynamic triangulation的技术来进行处理。

整个离散Ricci流可以使用一阶的梯度下降或是二阶的牛顿法来进行计算。

dynamic triangulation有两种实现方式,一种是在接近退化时进行翻转,而另一种则是在违背Delaunay三角化时进行翻转。试验结果表明第二种实现方式往往具有更高的计算效率。

完成离散Ricci流得到平面上三角形的边长后可以通过指定某个三角形的位置然后利用广度优先遍历的方式将所有的面摆放到平面上,从而得到最终的参数化。对于高亏格的曲面也可以使用类似的方式来进行处理。

Calabi Flow

类似于Ricci流,Calabi流(Calabi flow)通过最优化Calabi能量(Calabi energy)来操作曲面的曲率并实现参数化。Calabi流的优点在于它的能量函数相对简单,而且它关于对数共形因子同样也是一个凸函数。

使用一阶梯度下降法的Calabi流在形式上与Ricci流完全一致,而二阶牛顿法在计算Hessian矩阵时会比较复杂,此时可以使用一些近似方法来进行估计Hessian矩阵。

Calabi流的另一个优势在于它除了平面参数化之外也可以实现球面参数化。

Conjugate Harmonic Functions

上一节介绍过的conjugate harmonic coordinates说明共形映射下两个方向上的变形都是调和函数,而计算调和函数的关键在于选择函数的边界。

Boundary Condition

结合Yamabe方程我们可以估计曲面的边界,但需要注意的是曲面的边界是一个封闭曲线。

Boundary First Flattening

得到优化的边界后再求解Laplace方程即可实现参数化。

Reference