三角网格的全局无缝参数化

本文将介绍三角网格的平面参数化, 以及全局无缝参数化中的相关概念, 并介绍 ⟪Harmonic global parametrization with rational holonomy¹⟫ 这篇文章中的工作. 这篇文章中, 作者给出了一个对任意亏格曲面进行全局无缝参数化的方法, 并且这一方法可以保证局部是单射的.

平面参数化

三角网格的平面参数化的问题指的是, 对于某一三维空间中的网格, 如何将它摊平到二维平面上.

这篇文章讨论主要的问题是, 在网格参数化中, 除非网格的亏格为 0 且有边界, 否则不存在局部单射 (locally injective) 的参数化. 要解决这一问题, 需要在网格上引入锥奇异点和割缝.

锥奇异点

什么是锥奇异点

对于网格中的某一顶点 $v$, 与它相邻的三角形在 $v$ 上的角的角度记为 $\alpha_i$, 我们称这一点处的锥角 (Cone Angle) 为 $\sum_i \alpha_i$. 不难注意到, 如果这一网格是一个平面网格, 且与 $v$ 相邻的三角形之间互不重叠, 那么这一点处的锥角为 $\sum_i \alpha_i = 2\pi$.

在网格参数化中, 当网格因为种种原因无法被摊平到平面上时, 我们会在原始网格上选取一些锥奇异点 (下文中也称锥点), 并用连接锥奇异点和边界的割缝将网格割开, 得到一个可以摊平在平面上的网格. 上图给出了一个锥奇异点被称为 “锥” 的形象的解释, 即我们可以将参数化得到的网格在锥点附近的部分卷起来得到一个锥状的曲面.

由于割缝的存在, 锥奇异点处的锥角不是 $2\pi$. 而这就是锥奇异点的定义. 在下文中我们将通过一些离散微分几何的理论来简单解释这一做法的合理性.

Gauss-Bonnet 公式

回忆微分几何中的概念, 曲面上某一点出的高斯曲率 $K$ 是该点主曲率 $\kappa_1$ 和 $\kappa_2$ 的乘积. 高斯曲率的一个重要性质是它只与曲面上的度量有关, 因此它在等距同构下保持不变. 一个直观的例子是, 我们可以将一张平面弯曲成柱面或锥面, 但它们有相同的高斯曲率 (且都为 0).

对于一整张曲面 $M$, 我们有 Gauss-Bonnet 公式:

$$ \int_M K d A+\int_{\partial M} k_g d s=2 \pi \chi(M), $$

即高斯曲率在整个曲面上的积分 + 测地曲率在曲面边界上的积分 = $2\pi \cdot$ 曲面 $M$ 的欧拉示性数. 如果这张曲面是闭曲面, 我们就有

$$ \int_M K d A=2 \pi \chi(M). $$

对于闭曲面, 我们还有欧拉示性数 $\chi$ 与曲面亏格 $g$ 之间的关系:

$$ \chi = 2 - 2g. $$

离散情形

对于一个三角网格, 我们需要考虑离散情形下的高斯曲率和 Gauss-Bonnet 公式.

我们不加解释地给出离散情形下的高斯曲率 (笔者会在另一篇笔记中详细解释): 对于网格中的某一顶点 $v$, 与它相邻的三角形在 $v$ 上的角的角度记为 $\alpha_i$, 我们称这一顶点上的高斯曲率为

$$ K(v) = 2\pi - \sum_{i} \alpha_i, $$

而对应地, 离散的 Gauss-Bonnet 公式为

$$ \sum_{v} K(v) = 2\pi \chi(M). $$

此外, 对于网格 (事实上, 对于多面体) 我们还有欧拉多面体公式 (Euler’s Polyhedron Formula), 它是 Gauss-Bonnet 公式的一个推论. 记顶点数为 $V$, 边数为 $E$, 面数为 $F$, 则有

$$ \chi = V - E + F. $$

有了这些概念, 我们可以这样理解锥奇异点: 参数化得到的网格中, 大部分点处的高斯曲率都为 0, 只有锥奇异点处的高斯曲率不为 0. 这也就是说, 在进行参数化时, 我们放弃将曲面直接摊平到平面上, 而是将其映射到一个可展曲面上. 由于 Gauss-Bonnet 公式的存在, 我们不是直接消除高斯曲率 (i.e. 直接摊平到平面上), 而是将曲面的高斯曲率集中到锥奇异点上, 以使得大部分点处的高斯曲率都为 0.

无缝参数化

在引入了割缝之后, 一个问题就是如何避免会出现如下图的现象:

无缝参数化首先要求, 对应的割缝长度相同. 接着由于纹理贴图是以位图的形式保存的, 因此无缝还要求对应的割缝之间恰好相差一个旋转, 且角度是 $\pi/2$ 的整数倍. 注意到, 这一角度是与锥奇异点处的锥角大小有关的.

算法

我们首先给出这一文章的算法. 对于一个给定的任意亏格的三角网格, 以及它的锥点、割缝和锥点处锥角的大小, HGP 算法是求解如下的优化问题:

其中

• (11) 式是优化调和能量以接近 $\sum_{v_j \in N\left(v_i\right)} w_{i j}\left(z_i-z_j\right)=0$, $w_{ij}$ 是任意的凸权重;
• (12) 式是割缝上的边的旋转条件, 它要求对应的割缝恰好相差一个旋转, 且角度是 $\frac{2\pi}{q}$ 的整数倍 ($r_{ij}$ 是预先给定的), 这一角度实际上来自给定的锥奇异点的锥角大小;
• (13) 式是应用于包含边界点或锥奇异点的三角形的标架条件, 这是为了保证这些三角形的参数化不会出现翻转.

在这片文章的实现中, 作者使用了 [Floater 2003]³ 中的均值权重.

边界上的调和条件

由于割缝的存在, 调和条件实际上需要分为两种情况. 记割缝上的顶点和边形成的图为 $G_S$. 不在割缝上的顶点, 用普通的调和条件即可:

$$ \sum_{v_j \in N\left(v_i\right)} w_{i j}\left(z_i-z_j\right)=0, \quad v_i \in V \backslash G_S. $$

对于在割缝上的顶点, 如下图所示, 我们需要将两条割缝旋转过来, 得到调和条件如下:

$$ \sum_{v_j \in N^*\left(v_i^0\right)} w_{i j}\left(z_i^0-z_j\right)+\sum_{v_j \in N^*\left(v_i^1\right)} w_{i j} e^{\mathrm{i} \frac{2 \pi r_1}{q}}\left(z_i^1-z_j\right)=0 , \quad v_i \in G_S. $$

这一式子看似复杂, 但配合直观的图示很容易理解. 如果一个割缝上的顶点在 $G_S$ 中的度大于 2, 则这一条件会变得更加复杂.

Frame Fixing

求解上述优化问题时存在一个问题, 边界的旋转条件不能保证得到正确的锥角, 所得到的锥角可能会与所给定的相差 $2\pi$ 的整数倍.

论文中解决这一问题的方法 (Frame Fixing) 是以某种方式重新指定出错的锥点的 1-邻域上的标架. 其它的采用基于标架的算法不能进行这一修正, 因为它们在每一个三角形上都有标架, 进行这样的修正会导致出现其它问题. (这一部分笔者没有完全理解)

理论

这一算法依赖于作者给出的这一定理:

Theorem 6.1. Let f denote a q-CCM of S, with specified cone points and holonomy angles determining the rotation constraints. If the cone and boundary triangles are mapped in an orientation-preserving manner, and the induced metric on S achieves the desired cone angles and turning angles, then f is locally injective.¹

这一定理的证明基于 [Gortler, 2006]⁴. 因此在介绍这一定理中的概念及其证明之前, 我们需要先介绍一下 Gortler 等的工作.

Tutte 参数化

我们知道最早的参数化方法是 [Tutte, 1963]⁵ 提出的与圆盘同胚的网格的参数化方法, 是将网格边界映射到一个任意的凸多边形上, 并求解一个使得每个内部顶点都是它的 1-邻域的凸组合的方程组. Tutte 证明了这一方法能保证参数化是在局部和全局 (额外要求三角形之间不出现重叠) 都是单射的:

Theorem 4.1 (Tutte (1963)). Let $G=\langle\mathcal{V}, \mathcal{E}, \mathcal{F}\rangle$ be a 3-connected planar graph with boundary vertices $\mathcal{B} \subset \mathcal{V}$ defining a unique unbounded exterior face $f_e$. Suppose $\partial f_e$ is embedded in the plane as a (not necessarily strictly) convex planar polygon, and each interior vertex is positioned in the plane as a strictly convex combination of its neighbors, then the straight-line drawing of $G$ with these vertex positions is an embedding. In addition, this embedding has strictly convex interior faces. ⁴

Gortler 等给出了 Tutte 的定理的另一个证明, 并且进行了推广, 证明了网格有多个非凸边界时, 只要边界处的三角形是无翻转的, 那么 Tutte 参数化仍然是局部单射的:

Lemma 4.15. Suppose that: (1) $G$ is an oriented 3-connected mesh of genus 0 having multiple exterior faces. (2) The boundary of the unbounded exterior face is mapped to the plane with positive edge lengths and turning number $2 \pi$. (3) The boundaries of the bounded exterior faces are mapped to the plane with positive edge lengths and turning number $-2 \pi$. (4) $[G, x, y]$ is the straight line drawing of $G$ where each internal vertex is positioned as a convex combination of its neighbors. (5) In $[G, x, y]$ the reflex vertices of all of the exterior face boundaries are also in the convex hull of their neighbors. Then for any $\alpha, \beta$ and $[G, \Delta z]$ constructed as in (4), no vertex or interior face is a saddle in $[G, \Delta z]$. Theorem 4.16. Under the conditions of Lemma 4.15, all interior faces of $[G, x, y]$ are convex and all interior vertices are wheels. Moreover, if all the exterior faces are embedded as disjoint simple polygons (edge crossings are not allowed), then all faces of $[G, x, y]$ are disjoint. ⁴

为了证明 HGP 的定理, 作为准备, 我们将简单介绍 Gortler 等对 Tutte 参数化的定理涉及的概念及其证明.

Index Counting

我们将采用 Index Counting 的方法来进行证明 Tutte 参数化是局部单射的.

我们要证明的是, Tutte 参数化给出的平面网格中, 三角形之间互不重叠. 记参数化得到的网格中, 顶点 $v_i$ 对应的位置为 $f(v_i) = z_i \in \mathbb{C}$. 回忆上文中关于 Tutte 参数化的定义, 平面网格内部的每一个点都是它相邻点的凸组合, 即

$$ z_i = \sum_{v_j \in \mathcal{N}(v_i)} w_{ij} z_j. $$

接下来我们将首先给出一大批定义, 然后通过定理和引理对其中的直观进行说明.

Definition. A discrete 1-form $\rho$ on a mesh surface S is an assignment of a real number $\rho_{ij}$ to each half-edge $h_{ij}$ such that $\rho_{ij} = - \rho_{ji}$.

对于某一 1-形式 $\rho$, 我们称一个点 $v_i$ 是 co-closed, 如果

$$ \sum_{v_j \in \mathcal{N}(v_i)} w_{ij}\rho_{ij} = 0, $$

称一个面 $f_k$ 是 closed, 如果

$$ \sum_{h_{ij} \in f_k} \rho_{ij} = 0. $$

记 $\operatorname{scg}_\rho(v)$ 和 $\operatorname{scg}_\rho(f)$ 为 $\rho_{ij}$ 在环绕一个顶点或面片时发生正负号变化的次数. 对于顶点, 我们考虑的是全部从它出发 (或指向它) 的半边; 对于面片, 我们考虑的是环绕一圈的全部半边. 注意到这两个值都总是正的偶数.

接下来我们给出 index 的定义:

Definition. The index of $\rho$ about a vertex or face $p$ is:

$$ \operatorname{ind}_\rho(p):=\frac{1}{2}\left(2-\operatorname{scg}_\rho(p)\right) $$

注意到, 因为 $\operatorname{scg}$ 总是正的偶数, 所以 index 是 $\leq 1$ 的整数.

根据欧拉多面体公式, 我们给出如下定理, 它将 index 与曲面的拓扑结构联系起来. 并且我们将发现这一定理事实上是 Index Counting 的核心, 它是欧拉多面体公式的一个推论:

Theorem (Index Formula). A non-vanishing 1-form $\rho$ on a closed mesh surface $S$ of genus $g$ satisfies the following formula:

$$ \sum_{v \in V} \operatorname{ind}(v)+\sum_{f \in F} \operatorname{ind}(f)=\chi(S)=2-2 g $$

Proof.

$$\begin{aligned} \sum_{v \in V} \operatorname{ind}(v)+\sum_{f \in F} \operatorname{ind}(f) & =\frac{1}{2} \sum_{v \in V}(2-\operatorname{scg}(v))+\frac{1}{2} \sum_{f \in F}(2-\operatorname{scg}(f)) \\ & =V+F-\frac{1}{2}\left(\sum_{v \in V} \operatorname{scg}(v)+\sum_{f \in F} \operatorname{scg}(f)\right) \\ & =V+F-\frac{1}{2}(2 E) \\ & =V+F-E \\ & =2-2 g . \end{aligned} $$

其中 $\sum_{v \in V} \operatorname{scg}(v)+\sum_{f \in F} \operatorname{scg}(f) = 2E$ 是因为如下图所示, 对于任意一条半边 $h$, 由于 $\rho_{h_f} = -\rho_{h_v}$, 不论 $\rho_h$ 的正负如何, 它总会恰好贡献一次符号变化, 即所有符号变化的次数之和为半边的总数, 两倍边的总数.

接下来考虑具体的 1-形式. 事实上, 在下文中我们所考虑的 1-形式只有 $\rho_{i j}^x:=\operatorname{Re}\left(z_j-z_i\right)$ 和 $\rho_{i j}^y:=\operatorname{Im}\left(z_j-z_i\right)$, 以及它们的任意线性组合 $\rho^{\alpha, \beta}:=\alpha \rho^x+\beta \rho^y$.

注意到对于 $\rho^{\alpha, \beta}$, 网格中所有的内部点都是 co-closed, 所有的面片都是 closed. 因而在这些点或面上, $\operatorname{ind}_{\rho^{\alpha, \beta}} \leq 0$.

对于我们的 $\rho^{\alpha, \beta}$, 因为它的定义来自二维网格中顶点之间的位置关系, 所以它的 index 能给出二维网格的性质, 我们将用它来研究网格中三角形是否发生重叠. 如下图, 我们可以将二维网格中的顶点根据它们的 1-邻域的性质分为两类, 那么 $f$ 在 wheel vertex 处就是局部单射的, 而在 non-wheel vertex 处就不是.

以下的引理给出了 $\rho^{\alpha, \beta}$ 与顶点的 1-邻域的性质之间的关系:

Lemma. If a vertex $v$ of is non-wheel, then for some $\alpha$ and $\beta$, the 1-form $\rho^{\alpha, \beta}$ is non-vanishing and $\operatorname{ind}_{\rho^{\alpha, \beta}}(v) < 0$. Proof. 如上图所示, 对于 non-wheel 的顶点, $\rho^y$ 的符号变化了至少四次, 因此有 $\operatorname{ind}_{\rho^{y}}(v) \leq -1 < 0$. 其它的情形同理.

有了以上的准备工作, 我们可以来证明 Tutte 参数化了. 假设有一个任意的 1-形式 $\rho = \rho^{\alpha, \beta}$, 不妨设 $(\alpha, \beta) = (0, -1)$. 如下图, 我们画出使得它为正的半边.

首先, 我们知道 Tutte 参数化考虑的是与圆盘同胚的三角网格, 这里我们给它补上一个外部的面, 使其成为一个与球同胚的曲面.

我们考虑这一二维网格上的 index. 存在这样的情况: 二维网格中的三角面, 我们给它补上的面, 原本边界上的点, 网格内部的点. 我们进行如下的分类讨论:

• 对于二维网格中的面片, 如图所示, 我们发现 $\rho$ 一定会出现符号的变化, 因此 $\operatorname{index}_{\rho}\leq 0$;
• 对于我们给它补上的面, 根据 Tutte 参数化的定义, 它是凸的, 因而 $\operatorname{index}_{\rho} = 0$;
• 对于网格内部的点, 以及边界上除了最上和最下两个点以外的点, 同样地, $\rho$ 一定会出现符号的变化, 因此 $\operatorname{index}_{\rho}\leq 0$;
• 对于边界上最上和最下的两个点, 我们发现 $\rho$ 不会出现符号的变化, 因此 $\operatorname{index}_{\rho} = 1$.

综合以上讨论, 我们有

$$\sum_{v \in V} \operatorname{ind}(v)+\sum_{f \in F} \operatorname{ind}(f) \leq 2.$$

但根据 Index 公式, 我们有

$$\sum_{v \in V} \operatorname{ind}(v)+\sum_{f \in F} \operatorname{ind}(f) = \chi(S) = 2.$$

因此上文中所述的 $\operatorname{ind}_{\rho} \leq 0$ 的面片和顶点上, 都有 $\operatorname{ind}_{\rho} = 0$. 因此所有内部顶点都是 wheel, 因而 Tutte 参数化是局部单射的. 又因为 Tutte 参数化将边界固定到凸的多边形上, 所以它是全局单射的.

HGP

在这些准备之后, 我们终于可以开始证明 HGP 是局部单射了.

如上图 A 和 B 所示, 我们将对 $S$ 进行参数化得到的二维网格 $S_C^0$, 复制为 $q$ 份: $S_C^0, \dots, S_C^{q-1}$, 并且 $S_C^{n}$ 是 $S_C^0$ 旋转 $\frac{2n\pi}{q}$. 对于每一条割缝, 总是恰好存在另一个 $S_C^n$ 上的对应的割缝, 使其恰好互相平行. 图 A 和 B 中用相同的颜色标出了这样对应的割缝. 我们将这 $q$ 个二维网格在这些对应的割缝处相连, 得到 $\tilde{S_q}$, 这被称为是 $S$ 的 $q$-fold branched cover.

对于图 A, 所得到是类似下图的图形; 对于图 B, 所得到的是两个与圆盘同胚的网格. 我们将在 $\tilde{S_q}$ 上进行 Index Counting.

尽管这样拼出的二维网格中, 可能存在很多三角形的重叠, 但这些都是全局意义下的重叠, 我们所要考虑的是局部的性质. 不难注意到, 我们要说明 HGP 参数化是局部单射的, 只需说明 $\tilde{S_q}$ 中所有的内部顶点都是 wheel, 因而这一次我们要在 $\tilde{S_q}$ 上进行 Index Counting.

有了 $\tilde{S_q}$ 后, 我们就有一个覆盖映射 (Covering map) $P_q: \tilde{S_q} \rightarrow S$.

首先, 我们考虑 $\tilde{S_q}$ 的拓扑结构. 我们有 Riemann-Hurwitz formula:

Theorem. If $\tilde{M}$ is an $N$-fold branched cover of a base surface $M$, and $\mathcal{R}$ denotes the ramification points of $\tilde{M}$ and $e_P$ denotes the ramification index at $P$, then the following formula holds:

$$ \chi(\tilde{M})=N \chi(M)-\sum_{P \in \mathcal{R}}\left(e_P-1\right) $$

即

$$ \chi(\tilde{S_q})=q \chi(S)-\sum_{P \in \mathcal{R}}\left(e_P-1\right) $$

其中, $\mathcal{R}$ 是 ramification point 的集合, ramification point 指的是 branch point $\in S$ (在这里就是 cone vertex) 在 $\tilde{S_q}$ 中的原像. 例如在图 A 的例子中, 只有一个 ramification point, 而在图 B 的例子中有两个. $e_P$ 是指在 $P$ 的邻域中, 这一覆盖映射几乎是 $z \rightarrow z^{e_P}$, 我们称 $e_P$ 为 ramification index.

对于锥点 $v_i$, 设其锥角为 $\frac{2 k_i \pi}{q}$, 则由一些简单的群论的知识, 我们知道这一点恰有 $\operatorname{gcd}(k_i, q)$ 个 ramification point (即 $\left|P_q^{-1}(v_i)\right| = \operatorname{gcd}(k_i, q)$), 且若 $P$ 是一个 ramification point, 则 $e_P = \frac{q}{\operatorname{gcd}(k_i, q)}$.

由于我们要在闭曲面上进行 Index Counting, 我们需要考虑 $\tilde{S_q}$ 的边界的个数和性质. 对于边界 $B_j$, 假设其 turning angle 为 $\frac{2 l_j \pi}{q}$, 则类似地, $P_q^{-1}(B_j)$ 有 $\operatorname{gcd}(l_j, q)$ 个联通的部分, 这些就是 $\tilde{S_q}$ 的边界, 且它们的 turning angle 为 $\frac{2 l_j \pi}{\operatorname{gcd}(l_j, q)}$. 此外我们有如下引理:

Lemma. If a boundary component $B_j$ has turning angle $2 \pi \phi$ for some integer $\phi$, then the total index contribution (for a non-vanishing $\tilde{\rho}^{\alpha, \beta}$ ) of its exterior face and vertices is $\phi+1$.

与 Tutte 参数化的证明中类似地, 我们在这些联通的边界部分上补上外部的面.

接下来我们将在 $\tilde{S_q}$ 上进行 Index Counting. 首先我们由离散的 Gauss-Bonnet 公式可以得到如下引理:

Lemma (Gauss-Bonnet).

$$ q|C|-\sum_{v_i \in C} k_i+\sum_{j=1}^m l_j=q(2-2 g-m) $$

其中 $C$ 为所有锥点的集合, $m$ 为 $S$ 的边界的数量.

回忆 Index 公式:

$$ \sum_{v \in V} \operatorname{ind}(v)+\sum_{f \in F} \operatorname{ind}(f)=\chi(S) $$

对 $\tilde{S_q}$ 引用 Index 公式, 并代入上文中讨论的结果, 得到

$$ \begin{aligned} \text { RHS } & =q(2-2 g-m)-\sum_{P \in \mathcal{R}}\left(e_P-1\right)+\sum_{j=1}^m \operatorname{gcd}\left(l_j, q\right) \\ & =q(2-2 g-m)-q|C|+\sum_{v_i \in C} \operatorname{gcd}\left(k_i, q\right)+\sum_{j=1}^m \operatorname{gcd}\left(l_j, q\right) \\ & =\sum_{v_i \in C} \operatorname{gcd}\left(k_i, q\right)+\sum_{j=1}^m \operatorname{gcd}\left(l_j, q\right)-\sum_{v_i \in C} k_i+\sum_{j=1}^m l_j \end{aligned} $$

接下来考虑等式左侧的部分. 记 $s$ 为所有内部顶点 (即边界点和锥点以外的顶点) 和所有内部面上 index 的总和. 剩下来要考虑的就是 ramification points 和我们所补上的外部的面.

对于 ramification point, 我们注意到在 $\tilde{S_q}$ 中, 它们就相当于锥角为 $2 N \pi$ 的锥点 (参考 Tutte 参数化证明中, 顶点分类的第二种 non-wheel vertex), 其 index 为 $1-N$. 因此所有 ramification point 的 index 之和为

$$ \sum_{v_i \in C} \operatorname{gcd}\left(k_i, q\right)\left(1-\frac{k_i}{\operatorname{gcd}\left(k_i, q\right)}\right)=\sum_{v_i \in C} \left(\operatorname{gcd}\left(k_i, q\right)-k_i\right). $$

类似地, 所有外部的面的 index 之和为

$$ \sum_{j=1}^m \operatorname{gcd}(l_j, q) (1 + \frac{l_j}{\operatorname{gcd}(l_j, q)}) = \sum_{j=1}^m \left(\operatorname{gcd}(l_j, q) + l_j\right). $$

则

$$ \text { LHS } = s + \sum_{v_i \in C} \left(\operatorname{gcd}\left(k_i, q\right)-k_i\right) + \sum_{j=1}^m \left(\operatorname{gcd}(l_j, q) + l_j\right) $$

根据 Index 公式, $\text{LHS} = \text{RHS}$, 我们有 $s = 0$. 因此所有的内部顶点都是 wheel vertex. QED.