GAMES301课程笔记10-共形参数化1(Circle填充、柯西黎曼方程)
这个系列是GAMES301-曲面参数化(GAMES 301: Surface Parameterization)的同步课程笔记。课程内容涉及曲面参数化的基本理论与问题描述、面向离散网格的参数化、基于基函数表示的连续参数化、共形参数化、曲面参数化的应用等。本节课主要介绍共形参数化的基本理论。
Intro to Conformal Mapping
Angle-Based Flattening
共形映射(conformal mapping)的一个重要性质在于保角性，因此在介绍共形映射的相关概念前我们先回顾一下满足保角性的参数化方法。其中ABF的主要思想在于最小化三角形的角度扭曲，在参数化时ABF会对内部顶点周围的内角按照比例缩放到\(2 \pi\)，同时边界上顶点的角度与原曲面保持一致。
在此基础上ABF还引入了三角形内角和约束以及正弦定理导出的重建约束，通过求解一个最小二乘优化问题来实现参数化。
Least-Square Conformal Mapping
另一种常见的保角参数化算法是LSCM，它通过对三角形进行相似变换来控制角度扭曲。
利用相似变换的Jacobian矩阵可以推导出参数化需要满足的PDE，实际上它就是Cauchy-Riemann方程(Cauchy-Riemann equation)。
实际计算时LSCM同样是定义了一个最小二乘优化问题来进行求解。还需要注意的是LSCM可能会出现退化的情况，为了避免这种问题还需要固定参数平面上的两点。
Conformal Mapping
因此共形映射的核心思想在于保证参数化后角度保持不变。对于连续曲面的情况这会使得参数化后的曲面往往仍然是曲面；而对于离散曲面我们基本无法保证参数平面上完全没有角度扭曲，一般只能通过优化的方法来尽可能减少扭曲。
共形映射的保角性使得它在很多领域都有大量的应用。
Differential of Conformal Mapping
Plane-to-Plane
离散共形映射仍然是三角网格上的线性映射。由于要求保持三角形上角度不变，映射后的形状会保持一定的刚性。
而连续共形映射则要求曲面上任意上任意两个(切平面上)方向向量在映射前后保持夹角不变。
更严格来说，记映射\(f\)将平面上点\(p\)映射到\(f(p)\)。\(p\)点上\(v\)方向的方向导数为：
\[df (v) = \lim_{t \to 0} \frac{f(p+tv) - f(p)}{t}\]实际上微分运算\(df\)是一个线性算子，我们可以利用\(f\)的Jacobian矩阵来进行计算：
\[df (v) = J_f v\]
\(p\)点上任意两个方向\(v\)和\(w\)经过映射\(f\)作用会得到两个新的方向\(df(v)\)和\(df(w)\)。如果我们要求映射前后向量的夹角保持不变则有：
\[\theta [v, w] = \theta [df(v), df(w)]\]为了计算\(v\)和\(w\)的有向角度，我们使用复数来表示方向向量。此时映射前后的有向夹角可以表示为：
\[v^{-1} \ w = df^{-1}(v) \ df(w)\]进而可以得到复线性(complex linear)：
\[df (zv) = z \ df(v)\]
由于复线性对于任意复数\(z\)成立，我们只需要考虑实数轴和虚数轴上的单位向量即可。整理之后就得到了Cauchy-Riemann方程：
\[df (i) = i \ df(1)\]它的另一种常见形式为：
\[\begin{cases} \frac{\partial f_x}{\partial x} = \frac{\partial f_y}{\partial y} \\ \frac{\partial f_x}{\partial y} =-\frac{\partial f_y}{\partial x} \\ \end{cases} \Leftrightarrow J = \begin{bmatrix} a & -b \\ b & a \end{bmatrix}\]Jacobian矩阵的形式说明共形映射是一个相似变换。
Manifold-to-Manifold
接下来我们把平面上的共形映射推广到流形上。此时无法直接在流形上定义方向导数，我们需要借助曲线来定义微分。记流形\(\mathcal{M}\)上存在曲线\(\Gamma\)，它在\(t=0\)时恰为\(p\)点且其切向量为方向向量\(v\)：
\[\Gamma (0) = p\] \[\Gamma' (0) = v\]这样我们就可以利用曲线\(\Gamma\)来定义\(f\)的微分：
\[df (v) = \lim_{t \to 0} \frac{f(\Gamma(t)) - f(\Gamma(0))}{t}\]此外还可以证明这个定义与\(\Gamma\)的选取无关。
流形上的Cauchy-Riemann方程与平面情况几乎一致，我们只需要把虚数单位\(i\)改成两个流形上的共形结构\(\mathcal{J}\)即可：
\[df (\mathcal{J}_{\mathcal{M}} v) = \mathcal{J}_{\mathcal{N}} \ df (v)\]
Spin Transformations
Quaternions
由于共形映射可以理解为旋转和缩放，对于三维空间我们可以使用四元数(quaternion)来对复数进行推广。
四元数包含3个虚部\(i,j,k\)，它的一些常用计算性质如下：
Spin Transformation
利用四元数就可以定义曲面切平面上的spin transform。此时我们对切平面上的向量\(df(X)\)利用四元数\(\lambda\)进行旋转和缩放，可以得到变换后的向量\(d\tilde{f} (X)\)：
\[d \tilde{f} (X) = \bar{\lambda} \ df(X) \ \lambda\]当然\(\lambda\)需要满足一定的条件，具体来说它需要满足Dirac方程(Dirac equation)：
\[D \lambda = - \frac{df \wedge d \lambda}{\vert df \vert^2} = \rho \lambda\]在求解Dirac方程时可以把它转换为特征方程，即给定初始\(\rho\)来构造特征方程并通过不断迭代来进行修正：
\[(D - \rho) \ \lambda = \gamma \ \lambda\] \[\rho \leftarrow \rho + \gamma\]当\(\gamma\)趋于0时表明迭代收敛，此时得到的\(\lambda\)即为所需四元数。
实际上\(\rho\)有明确的几何意义，它描述了变换前后曲面上mean curvature half-density的变化：
\[\tilde{H} \vert d \tilde{f} \vert = H \vert df \vert + \rho \vert df \vert\]同时需要注意的是spin transform一定是共形映射，但共形映射不一定都是spin transform。
Circle Packing and Circle Patterns
Circle Packing
由于共形映射在每一点上都是一个相似变换，我们可以在曲面上每一点放置一个小圆，那么在映射后每个圆形都可以保持形状。而随着圆半径不断缩小，离散曲面上的映射会不断接近于连续情况下的映射。
circle packing算法就是在这样的观察下进行定义的。我们把网格上的顶点作为圆心，同时要求圆与网格的边相切。
假设circle packing是存在的，利用余弦定理可以推导出三角形上三个顶点圆的半径与内角的关系：
\[\cos \theta_t = \frac{(r_0 + r_1)^2 + (r_0 + r_2)^2 - (r_1 + r_2)^2}{2 (r_0 + r_1) (r_0 + r_2)}\]此时circle packing存在的充要条件即为三个内角和为\(2 \pi\)。
整个circle packing算法的核心在于计算网格上内部顶点对应圆的半径，整个算法的流程如下：
circle packing算法的缺陷在于它没有考虑网格自身的几何，只考虑了网格上的连接关系。这在网格上存在狭长或是扁平三角形的情况下会导致比较大的几何扭曲。
Circle Patterns
针对circle packing的缺陷，circle patterns算法提出在三角形的每一个面上保持外接圆的相对夹角来实现共形映射。
首先考虑平面上的Delaunay三角化。利用平面几何的相关知识可以得到两个外接圆切线相对夹角与两个相邻三角形内角的关系。
更进一步，三角网格的内点上需要满足切线的相对夹角之和为\(2 \pi\)，而在边界上则可以利用曲率来计算。
还需要注意的是Delaunay三角化的凸包性，它只能表示凸的边界。对于非凸边界的情况则需要在局部计算Delaunay三角化。
Conjugate Harmonic Functions
在复平面上我们可以把Cauchy-Riemann方程写成梯度的形式：
\[\begin{cases} \frac{\partial u}{\partial x} = \frac{\partial v}{\partial y} \\ \frac{\partial u}{\partial y} =-\frac{\partial v}{\partial x} \\ \end{cases} \Leftrightarrow \nabla v = i \ \nabla u\]上式说明\(u\)和\(v\)两个映射的梯度相当于在逆时针方向旋转了90度，或者说它们互为共轭(conjugate)。如果进一步对梯度求散度则可以得到：
\[\begin{cases} \Delta u = \nabla \cdot (\nabla u) = \nabla \cdot (-i \nabla v) = 0 \\ \Delta v = \nabla \cdot (\nabla v) = \nabla \cdot ( i \nabla u) = 0 \\ \end{cases}\]即\(u\)和\(v\)两个映射都是调和映射。基于共轭调和映射的参数化方法包括conjugate harmonic 1-forms以及conjugate harmonic coordinates两类。
Conjugate Harmonic 1-Forms
Conjugate Harmonic Coordinates
