DDG课程笔记4-曲面参数化

这个系列是对CMU离散微分几何课程(CMU CS 15-458/858: Discrete Differential Geometry)的总结和回顾。本节我们介绍基于共形映射的曲面参数化方法。

Overview

曲面参数化可以理解为将空间曲面展开成平面的过程。在日常生活中曲面参数化最常见的例子是世界地图，这里我们将球面展开成平面矩形或是其他平面图形。

对曲面进行参数化时可能会导致各种各样的扭曲。还是以世界地图为例，地图上的面积并不能表示实际的面积大小：在地图上格陵兰岛看着比澳大利亚要大，但实际的面积却要小得多(Greenland: 2.166m km², Australia: 7.692m km²)。

显然，我们希望参数化后的曲面能够保持原始曲面上的几何量，比如说角度、长度、面积等。其中能够保证角度在变换前后保持不变的映射称为共形映射(conformal map)，稍后我们会介绍共形映射的各种性质。使用共形映射的好处之一我们有非常扎实的理论保证，比如说我们可以保证对于开放曲面共形映射是一定存在的；同时基于共形映射的参数化方法在计算上也大多比较高效，很多算法甚至可以做到实时；此外共形映射往往会得到比较平滑的结果，而其它的参数化方法则不一定能够保证这点。

Conformal Map

Complex Numbers

在这一节我们开始介绍共形映射的相关理论。由于共形映射与复分析有着深刻的联系，因此在正式介绍前首先来补充一些复数的基本知识。我们知道复平面上的点可以表示为实部和虚部的形式：

z = a + b i

i^{2} = - 1

从几何的角度上看，虚数单位 $i$ 可以理解为将向量逆时针转90 $^{\circ}$ 。

同时复数的代数运算法则也可以理解为平面向量的运算法则：

利用欧拉公式(Euler’s formula)我们还可以把复数表示成极坐标的形式：

e^{i θ} = \cos θ + i \sin θ

此时复数的乘法相当于对向量的长度进行缩放同时对角度进行加减：

z_{1} z_{2} = (r_{1} e^{i θ_{1}}) \cdot (r_{2} e^{i θ_{2}}) = (r_{1} r_{2}) e^{i (θ_{1} + θ_{2})}

Conformal Structure

对于曲面切平面上的向量 $X$ ，我们可以利用向量叉乘来表示旋转：

N \times d f (X)

显然旋转后的向量一定也位于切平面上，因此存在一个映射 $J$ 使得：

d f (J X) = N \times d f (X)

我们称 $J$ 为映射 $f$ 诱导的共形结构(conformal structure)，具有共形结构的曲面则称为黎曼曲面(Riemann surface)。

不难发现共形结构 $J$ 和虚数单位 $i$ 起着类似地作用， $J$ 也满足 $i$ 的定义：

J \circ J = - id

其中 $id$ 表示恒等映射。上式说明对向量 $X$ 使用两次 $J$ 相当于将 $X$ 反向。

Cauchy-Riemann Equation

对于共形映射我们要求切平面上任意两个向量的夹角在变换前后保持不变，实际上我们并不需要考虑所有的夹角只需考虑共形结构 $J$ 即可。将参数化后的平面用复平面来表示，此时共形映射 $z : M \to C$ 满足Cauchy-Riemann方程(Cauchy-Riemann equation):

d z (J X) = i d z (X)

Cauchy-Riemann方程表明在切平面上进行旋转和在参数化平面上进行旋转是一致的，因此曲面上的角度在参数化后保持不变。

Riemann Metrics

此外我们还可以通过黎曼度量来认识共形映射。对于同一个曲面的两个度量 ${\tilde{g}}_{p}$ 和 $g_{p}$ ，如果它们在曲面任意点 $p$ 上只相差一个系数，则称两个度量是共形等价(conformally equivalent)：

{\tilde{g}}_{p} = e^{2 u (p)} g_{p}

其中 $e^{2 u (p)}$ 说明该系数为正且与点 $p$ 相关。回忆黎曼度量给出了曲面切平面上内积的定义，我们可以定义曲面上的长度和角度：

| X | = \sqrt{g (X, X)}

∠ (X, Y) = \arccos (\frac{g (X, Y)}{| X | | Y |})

不难验证对于共形等价的两个度量，它们关于角度的定义是相同的。

Spectral Conformal Parameterization

本节最后来介绍基于共形映射的曲面参数化算法，限于篇幅和自身水平有限这里仅介绍使用Cauchy-Riemann方程的SCP算法。

Complex Differential Forms

设 $α$ 为曲面上的1-form，利用共形结构的性质可以得到1-form对应的Hodge star算子：

⋆ α (X) = α (J X)

同时定义2-form的Hodge star算子为：

⋆ ω = ω (X, J X)

上式意为度量面积微元只需要考虑切平面上相互垂直的两个向量 $X$ 和 $J X$ 。

接着定义1-form之间的内积为：

⟨ ⟨ α, β ⟩ ⟩ = \int_{M} ⋆ α \land β

因此函数的模为：

‖ α ‖ = ⟨ ⟨ α, α ⟩ ⟩

同时可以证明Hodge star算子不会改变模长(旋转不改变面积)：

‖ ⋆ α ‖ = ‖ α ‖

然后我们需要将微分形式拓展到复数域上，定义微分形式的共轭为：

(\bar{α}) (X) = \overset{―}{(α (X))}

\overset{―}{(α \land β)} (X, Y) = \overset{―}{(α \land β (X, Y))}

在此基础上可以定义complex 1-form的内积为：

⟨ ⟨ α, β ⟩ ⟩ = Re \int_{M} ⋆ \bar{α} \land β

可以证明上式定义的内积是(半)正定的，而且是Hermitian内积(Hermitian inner product)：

⟨ ⟨ α, α ⟩ ⟩ \geq 0

⟨ ⟨ α, β ⟩ ⟩ = \overset{―}{⟨ ⟨ β, α ⟩ ⟩}

Conformal Parameterization

利用Hodge star算子我们可以将Cauchy-Riemann方程改写为：

⋆ d z = i d z

在此基础上定义共形能量(conformal energy)为：

E_{C} (z) = \frac{1}{4} ‖ ⋆ d z - i d z ‖^{2}

共形能量 $E_{C} (z)$ 可以描述映射 $z$ 是否满足Cauchy-Riemann方程，显然对于共形映射其共形能量为0。此时寻找共形映射 $z$ 等价于最小化共形能量即：

z = \arg min E_{C} (z)

将共形能量 $E_{C} (z)$ 进行展开得到：

\begin{aligned} E_{C} (z) & = \frac{1}{4} | | ⋆ d z - i d z | |^{2} = \frac{1}{4} ⟨ ⟨ ⋆ d z - i d z, ⋆ d z - i d z ⟩ ⟩ \\ = \frac{1}{4} (⟨ ⟨ ⋆ d z, ⋆ d z ⟩ ⟩ - ⟨ ⟨ ⋆ d z, i d z ⟩ ⟩ - ⟨ ⟨ i d z, ⋆ d z ⟩ ⟩ + ⟨ ⟨ i d z, i d z ⟩ ⟩) \\ = \frac{1}{2} ⟨ ⟨ d z, d z ⟩ ⟩ - \frac{i}{2} ⟨ ⟨ ⋆ d z, d z ⟩ ⟩ \\ = E_{D} (z) - A (z) \end{aligned}

其中 $E_{D} (z) = \frac{1}{2} ⟨ ⟨ d z, d z ⟩ ⟩$ 为映射 $z$ 对应的Dirichlet能量； $A (z) = \frac{i}{2} ⟨ ⟨ ⋆ d z, d z ⟩ ⟩ = - \frac{i}{2} \int_{M} d \bar{z} \land d z$ 为曲面参数化后映射到复平面的面积；上式说明共形能量等于Dirichlet能量和参数化后面积的差。为防止出现面积退化为0的情况，我们可以引入约束条件：

\begin{aligned} z & = \arg min E_{C} (z) \\ s.t. & ‖ z ‖^{2} = 1 \\ ⟨ ⟨ z, 1 ⟩ ⟩ = 0 \end{aligned}

其中 $1$ 为恒为1的常值函数。第一个约束表示参数化后曲面不会出现退化的情况，而第二个约束表示参数化后曲面的中心为原点。

Optimization

最后我们来介绍如何求解最小化共形能量。对于Dirichlet能量项，利用Laplace算子可以转换为：

E_{D} (z) = \frac{1}{2} ⟨ ⟨ d z, d z ⟩ ⟩ = \frac{1}{2} ⟨ ⟨ Δ z, z ⟩ ⟩ = \frac{1}{2} z^{H} Δ z

需要说明的是此时的Laplace算子与我们之前定义的符号相反，即 $Δ = - ⋆ d ⋆ d$ 。同样地，将面积项展开可以得到：

A (z) = - \frac{i}{2} \int_{M} d \bar{z} \land d z = \frac{i}{4} \sum_{e_{i j} \in \partial M} {\bar{z}}_{i} z_{j} - {\bar{z}}_{j} z_{i} = z^{H} A z

其中 $\partial M$ 表示曲面的边界。将两项代回原式得到离散后的共形能量：

E_{C} (z) = z^{H} (\frac{1}{2} Δ - A) z = z^{H} C z

进而得到离散后的约束优化问题：

\begin{aligned} z & = \arg min z^{H} C z \\ s.t. & z^{H} z = 1 \\ z^{H} 1 = 0 \end{aligned}

不难发现此时优化问题相当于求解复数矩阵 $C$ 的最小特征只对应的特征向量，可以使用反幂法(inverse iteration)来迭代求解。迭代格式如下：

初始化向量 $z_{0}$ ；
求解线性方程： $C z_{i} = z_{i - 1}$ ；
平移到原点： $z_{i} = z_{i} - {\bar{z}}_{i}$ ；
进行缩放： $z_{i} = \frac{z_{i}}{‖ z_{i} ‖}$ ；
返回步骤2直至残差 $r = ‖ C z_{i} - (z_{i}^{H} C z_{i}) z_{i} ‖^{2}$ 收敛。

由于函数内积与向量内积是不完全等价的，优化问题的第一个约束条件应该修改为：

‖ z ‖^{2} = \int_{M} ⋆ \bar{z} \land z = z^{H} M z = 1

其中 $M$ 为节点dual cell面积构成的对角矩阵。此时求解特征值问题转化为求解广义特征值：

C z = λ M z

对反幂法进行修改得到最终的迭代格式如下：

初始化向量 $z_{0}$ ；
令 $w = M z_{i - 1}$ ;
求解线性方程： $C z_{i} = w$ ；
平移到原点： $z_{i} = z_{i} - {\bar{z}}_{i}$ ；
进行缩放： $z_{i} = \frac{z_{i}}{\sqrt{z_{i}^{H} M z_{i}}}$ ；
返回步骤2直至残差 $r = ‖ C z_{i} - (z_{i}^{H} C z_{i}) M z_{i} ‖^{2}$ 收敛。

总结一下，SCP是一种基于共形映射的曲面参数化方法，通过最小化共形能量来寻找共形映射。在网格上我们利用广义特征值迭代来求解最小化共形能量，得到网格顶点到复数域的映射(向量) $z$ ，其中 $z$ 的实部表示顶点在参数化平面的 $x$ 轴坐标，虚部表示顶点的 $y$ 轴坐标。