GAMES301课程笔记03-无翻转参数化方法(初始存在翻转)

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

上一节课中我们介绍了一些精度的曲面参数化算法，其中Tutte’s embedding可以严格保证参数化后的结果没有翻转，但缺陷在于它往往会产生比较大的几何扭曲；而ABF、LSCM、ARAP等算法虽然有较小的扭曲，但却没有办法来完全避免翻转的问题。因此人们设计了各种不同的算法来处理参数化后翻转的三角形。

Projection

首先我们可以使用投影(projection)的方式来把所有翻转的三角形投影到无投影的空间上。由于在全局上直接进行投影往往比较困难，这类方法一般会采取迭代的方式每次处理一个翻转的三角形。

在介绍具体算法前再回顾一下相关的背景知识。

总结一下，无翻转约束要求三角形的Jacobian矩阵行列式大于0，减少几何扭曲要求conformal distortion有界。

这样参数化的过程可以等价的表示为如下所示的约束问题：

直接求解这样的优化问题仍然非常困难，因此可以使用两步迭代的思路来进行处理。

同时为了解决直接迭代效率过低的问题，还可以使用Anderson加速(Anderson acceleration)的技巧。

而为了寻找到最优的conformal distortion，在迭代时可以从较小的distortion开始逐步增大上界。

另一种进行优化的思路是进行投影时投影到切空间上。

Bounded Distortion Space

bounded distortion space的思想在于重新整理了Jacobian矩阵，使得原始的非凸优化问题可以在一个凸的子空间中进行处理。

在凸空间中进行优化时首先需要重新构造优化目标函数，然后利用二次锥规划进行求解。

Penalty

我们可以利用惩罚项(penalty)来处理翻转的问题，此时翻转的三角形会产生一个很大的代价而没有翻转的三角形不会产生惩罚值。当然大多数情况下惩罚函数都是非凸非线性的，此时求解器的设计和选择就尤为重要。

常见的惩罚函数如下：

而常用的一些求解器如下：

Area Based Methods

考虑三角形的带符号面积$S_t$，当三角形出现翻转时为负值。接下来定义平面上三角网格的面积为每个三角形的带符号面积之和，$A(\mathcal{T})=\sum _t{S}_t$。这样当参数化没有翻转时，累计的有符号面积等于无符号面积$\sum _t{U}_t=\sum _t{S}_t=A(\mathcal{T})$。因此我们可以通过最优化无符号面积$\sum _t{U}_t$来实现无翻转参数化。

由于$\sum _t{U}_t$往往不够光滑，出现三角形退化情况时最小化$\sum _t{U}_t$也不一定保证无翻转，而且$\sum _t{U}_t$存在梯度为0的情况使得优化起来比较困难。

因此在实际处理时可以定义一个新的目标函数TLC(total lifted content)，可以证明TLC有很多优良的性质。

Different Representations

在进行参数化时除了顶点坐标外还可以使用其它的变量，通过转换优化变量往往会更加容易地处理翻转问题。比如说我们可以把优化变量设置为变换的Jacobian矩阵，在优化过程中保证其行列式大于0即可实现无翻转。当然需要注意在相邻边上需要满足一定的约束。

这样整个参数化过程可以理解为分解和组合两步，首先为每个三角形计算低扭曲无翻转的Jacobian矩阵，然后再把它们组合起来。

整个优化问题可以表示为一个无约束优化问题，通过调整$E_{assembly}$的系数$\lambda$来保证得到一个有效的参数化。

除了Jacobian矩阵之外也可以把角度作为优化变量。

Reference

• Lecture 03：无翻转参数化方法 – 初始存在翻转