尽可能刚性的表面建模（As rigid as possible Surface modeling）

摘要：表面变形和编辑等建模任务可以通过观察表面的局部行为来进行分析。我们认为，通过要求局部变换的刚性定义建模操作在各种设置中都是有用的。这种公式导致非线性但概念上简单的能量公式，该公式将在特定的建模约束下通过变形表面最小化。我们基于此原理设计了一种简单的迭代网格编辑方案，可实现细节保留和直观的变形。我们的算法是有效的并且特别容易实现，使其对实际建模应用具有吸引力。

1.引言

当我们谈到形状时，我们通常指的是不随物体的方向或位置而改变的属性。从这个意义上说，保持形状意味着对象仅旋转或平移，而不是缩放或剪切。然而，在交互式形状建模的上下文中，很明显必须拉伸或剪切形状以满足用户设置的建模约束。用户直观地期望变形能够在局部保持对象的形状，就像对物理对象应用平滑的规模变形时一样。换句话说，形状的小部分应该尽可能严格地改变。

我们的目标是创建一个直接基于上述原理的形状变形框架。当建模操作引起的局部表面变形接近刚性时，往往会保留表面细节。对于表面编辑方案来说，这是一个非常重要的属性，这些方案旨在应用于复杂、详细的表面，例如来自扫描真实3D对象或来自复杂虚拟雕刻工具的表面。最近，保留细节的表面编辑技术在几何建模研究[Sor06, BS07]中受到广泛关注，这要归功于这种详细模型的日益普及，这些模型通常以不规则多边形网格的形式出现。

我们提出了以下源自局部刚性原理的概念模型：物体表面覆盖着小的重叠单元。理想的变形力求使每个单元中的表面的变换尽可能保持刚性。单元的重叠是必要的，以避免单元边界处的表面拉伸或剪切。

​ 图1：使用我们的 as-rigid-as-possible 技术通过平移单个约束点（黄色)获得的大变形

为了使这个建模框架变得实用，我们将定义如何在每个单元中测量刚度。一个自然的选择是根据初始和变形表面上的对应点估计每个单元的刚性变换，然后将此刚性变换应用于原始形状并测量变形形状的偏差。请注意，从相应的表面点估计线性变换，然后测量其非正交性并不是衡量刚性的好方法：任意变形的最佳近似线性变换很可能是正交的。因此，为了定义局部保持变形，应该直接优化刚性变换。

假设我们可以测量每个单元的刚度偏差，建立建模框架需要决定单元大小和位置（或等效地，重叠）。这些参数是相互关联的：首先，所有单元格应覆盖表面的相似区域，或者单元格的面积需要在目标函数中适当加权。其次，应选择重叠部分，使表面的每个部分都被相同数量的单元覆盖。

在下文中，我们将推导出这种用于设置离散曲面（即三角网格）的建模方法。令人惊讶的是，上面概述的主要思想的一个相当简单的表述导致了一个直观的迭代过程，该过程具有保证收敛性，并且易于实现。事实证明，它可以被解释为对现在常见的离散普拉斯建模框架[Sor06]的迭代改进，这极大促进了它在现有建模框架中的采用。我们还将该方法与其他线性和非线性建模框架联系起来，并讨论权衡。

1.1 背景

局部刚度可以看作是各种表面变形模型的主导原则。如果我们看一下衡量两个形状之间差异的经典弹性能量，或所谓的壳能量[TPBF87]：

其中 是 Frobenius 范数，是表面的基本形式，是其变形形式的基本形式，那么我们可以看到当是刚性变换时能量是最小的。这在全局和局部都是正确的：基本形式以独特的方式在局部定义表面，直至刚性转换，这样当和是一个到另一个局部刚性转换时，就会发生局部形状保持。

在任何表面变形情况下，除了微不足道的情况外，表面的完全局部刚性不能保持，因为它会得出表面是全局刚性的。因此，形状距离（1）不会达到零，而是具有某个最小值。当和之间发生的局部变化尽可能刚且平滑时，就达到了这个最小值。平滑表示局部变形局部相似；当它们还接近刚性时，这意味着基本形式几乎被保留，即形状被局部保留。

壳层能量（1）是表面位置的非线性函数，这使得在实践中难以操作。几何建模[kcvs98, bk04]中的几项工作建议制定这种能量的线性化离散版本。线性化允许有效的优化，但是当涉及到大变形（特别是旋转）时，它会导致伪影，例如局部细节失真和一般形状失真作为对局部细节失真的部分步长，可以采用多分辨率表面表示[ZSS97, GSS99]，首先使表面的平滑（低频）分量变形，然后通过局部位移添加回高频细节。不幸的是，当变形引入弯曲[BSPG06]时，这种解决方案很快会导致局部自相交。

如上所述，最小化形状变形的另一种方法是尝试设计局部刚性的变换。尽可能刚性的变形原理成功地应用于形状插值[ACOL00, XZWB05]。在这种情况下，源和目标的形状是已知的，问题是如何确定中间的“形状路径”，使得从源到目标的变形尽可能地呈现刚性；这个通过对离散表面元素的变换执行极分解并分别插值缩放和旋转分量来完成。在形状编辑中，变形任务更难，因为目标表面是未知的，只给出了几个建模约束（通常是表面元素子集的一些规定位置）。

一种可能的方法是同时优化局部刚性变换和保持微分坐标[Ale01]；这是由 Sorkine等人提出的。[SLCO*04]和五十岚等人。[IMH05]。然而，这种优化是非线性的，因为旋转不能在2D或3D中进行线性参数化。在2D中，可以线性表达相似变换；这可以用来设计二维形状的两步编辑过程：第一步，优化局部相似变换，第二阶段消除各向同性缩放。Schaefer等人实施了相同的想法。[SMW06]在2D自由形式变换（空间扭曲）的背景下：他们为2D空间扭曲设计了一个移动最小二乘框架，其中空间网格的每个元素尽可能刚性地变换，并且翘曲由几个网格点上的位置约束控制。在3D中，即使是相似变换也不能线性参数化；保持有效的线性变形框架 Sorkine等人。[SLOC04]使用相似变化的一阶近似，当变形只涉及适度的旋转时效果很好。

请注意，形状距离（1）有两个参数和，**它们确定切向畸变（即第一个基本形式）相对于法线方向（第二个基本形式）相对权重。**利普曼等人[LCOGL07]假设等距变形，从而保留第一个基本形式，并设计了一种优雅的方法，使用Cartan的离散表面移动框架公式来最小化第二个基本形式的偏差。Wardetzky等人[WBH*07]表明当变形时等距时，弯曲能量项可以表示为表面位置的二次能量。在不同的情况下，可以对这两个术语应用于不同的“权重”；等距并不总是最重要的部分（例如，当所需的表面变形时拉伸而不是弯曲时）。还值得注意的是，如果允许更复杂的建模约束，即，如果用户明确指定要应用于表面上某些控制点的所需旋转（或一般仿射变换)，则编辑可以相对通过将这些变换传播到表面的无约束部分[YZX04,LSLCO05,ZRKS05,LCOGL07]，很容易实现。当规定的仿射变换和平移兼容时，这会产生令人愉悦和直观的结果[LSLCO05]；然而，一般来说，这种编辑方法对翻译不敏感，并且可能导致不直观的形状扭曲。

在这项工作中，我们直接将3D离散曲面的尽可能刚性编辑制定为变分问题。能量公式是非线性的，我们展示了一种简单的迭代方法来最小化它。最近提出了几种相关的非线性变分变形方法：双重拉普拉斯[ATLF06]以朴素的拉普拉斯编辑作为初始猜测，并迭代调整局部拉普拉斯坐标以与表面法线重合，并将表面几何重新调整为那些拉普拉斯算子。这种交替迭代的方法在精神上与我们的相似，但他们没有制定出他们的迭代旨在最小化的特定能量，因此不清楚如何表征迭代过程的固定点。对于高分辨率模型的交互式操作，非线性方法通常过于昂贵，因此通常采用多分辨率。例如，在以下方法中就是这种情况。金字塔坐标[KS06]被表述为局部拟合平面上的非线性位移；黄等人[HSL06]采用非线性拉普拉斯约束（与其他约束相结合，例如体积保存）并最小化小子空间网格上的目标函数。粗略子空间的变形确定空间扭曲，使用3D平均值坐标[JSW05]实现，以使详细表面变形。PRIMO系统[BPGK06]将表面与包围它的棱镜集合联系起来；棱镜被认为是刚性物体，它们相邻面之间的集成距离通过改进的牛顿方案最小化，再次结合巧妙的多分率技术。

上述所有非线性方法都产生了非常有说服力的结果，就像我们在这里介绍的方法一样；我们技术的优点是它的能量公式导致了一个迭代最小化方案，该方案非常容易实现，同时仍然保证收敛。此外，最小化的步骤与拉普拉斯表面变形技术有关，这可能对依赖此思想的建模框架有用。

2.离散曲面设置

下面我们用表示一个三角形网格，其拓扑由n个顶点和m个三角形确定。我们用表示连接到顶点的一组顶点，也称为单环邻居。的分段性几何嵌入由顶点位置 定义。假设被变形为具有相同连通性和不同几何嵌入的。

在网格的拓扑元素上定义单元是很自然的。由于需要重叠，每个单元格应由多个三角形组成。我们相信选择基于顶点的定义是很自然的，其中每个单元格覆盖入射在顶点的三角形。我们首先分析每个单元的近似刚性变化，并形式化一个能量函数来测量与这种刚性变化的偏差，然后我们展示如何最小化这种能量并在建模操作的上下文中使用它。

2.1 分析两个单元格之间的刚性变换

给定与顶点对应的单元，及其变形版本 。我们通过观察在和 上的顶点 发出的边来定义两个单元之间的近似刚性变换。如果变形 是刚性的，则存在一个旋转矩阵 使得：

当变形不是刚性的时，我们仍然可以找到在加权最小二乘意义上的拟合上述方程的最佳近似旋转 ，即最小化：

这是形状匹配问题[Hor87]的加权实例。我们将在下一节讨论权重的正确选择。

我们简要描述了固定， 的最佳旋转矩阵 的推导。为方便起见，让我们表示边缘并且对于变形单元 的也是如此。我们将 上的求和表示为的简写。那么我们可以将（3)式改写为：

不包含 的项在最小化中是恒定的，因此可以删除，因此我们留下

​ 图2：演示能量公式（3）中适当边缘加权的重要性。使用均匀加权（统一加权，wij=1）的变形会导致不对称的结果，而余切加权（科坦权重）能够消除啮合偏差的影响。

让我们用 表示协方差矩阵：

其中 是包含权重的 的对角矩阵， 是包含作为其列，对于 也是如此。众所周知，当是对称半正定的（如果 是一个 psd 矩阵，那么对于任何正交 ，)，得到了最大化的旋转矩阵 。可以从 的奇异值分解推导出 ：

直到改变与最小奇异值对应的列的符号，使得。

2.2 局部刚性能量

我们测量整个网格变形刚度的简单想法是总结每个单元的刚度偏差，如图（3）所示。因此，我们得到以下能量函数：

其中 ， 是一些固定的单元格和边缘权重。请注意，仅取决于的几何形状，即取决于顶点位置。特别是，由于参考网格（我们的输入形状)是固定的，因此中的唯一变量是变形的顶点位置。这是因为最佳旋转矩阵是的明确定义的函数，如上一节所示。

如图（2）所示，每边权重 和每单元权重 的选择对于使我们的变形能量尽可能与网格无关非常重要。权重应补偿非均匀的单元格并防止离散化偏差。因此，我们使用 [PP93,MDSB03]：

其中是与网格边缘（i，j) 相对的角度（对于边界边缘，只有一个这样的角度存在)。我们进一步注意到，由（3)定义的刚度偏差是一个积分量，因此单元能量与单元面积成正比，我们可以设置 =1 。对此的另一种解释将使用区域校正的边缘权重 ，其中是单元[MDSB03] 的 Voronoi 区域，然后还将单元权重设置为 Voronoi 区域：。面积项简单地抵消了，我们剩下的是对称余切权重 wij。

3.建模框架

在建模框架中，我们需要在一些用户定义的建模约束下求解的位置以最小化。这意味着我们不知道先验的刚性变换，因此也需要解决它们。因此，我们首先将解释为和的函数，并且在任何建模情况下，我们都在寻找两组变化下的最小能量。

为了求解下一个局部最小能量状态（从给定的位置和旋转初始向量开始），我们建议使用简单的交替最小化策略。这意味着，对于给定的一组固定的刚性变换，我们找到最小化的位置。然后我们找到对于给定位置集最小化的刚性变换。我们继续这些交错的迭代，直到达到局部能量最小值。

让我们首先看看如何为给定的一组修改位置找到最佳刚性变换。总和（7)中的每一项仅涉及每个单元的刚醒变换，即我们可以计算每个单元的最优变换，而不考虑其他单元及其刚性变换。因此，我们在（3)中寻求一个最小化每个单元能量的。然而，对此的解决方案在第 2.1 节中详述，即等式（6)。

​ 图3：尽可能刚性的编辑方法的连续迭代。最初猜测是朴素的拉普拉斯编辑结果（如 [LSCO*04] 但没有任何局部旋转估计）。原始直杆模型如图6所示。

为了根据给定的旋转计算最佳顶点位置，我们计算相对于位置的梯度。让我们计算的偏导数 。请注意，在中，导数不为零的唯一项是那些涉及顶点和的项：

利用的事实，我们得出：

将偏导数设置为零 w.r.t 每一个我们得到一下稀疏线性方程组：

左侧的线性组合就是应用于的离散 Laplace-Beltrami 算子；方程组可以紧凑地写为：

其中是个 n 向量，其第 i 行包含来自（8)式的右侧表达式。我们还需要将建模约束合并到这个系统中。用最简单的形式，可以用一些固定的位置来表示

其中是约束顶点的索引集。这些由用户交互操作的静态和句柄顶点组成。将这些约束纳入（9)仅意味着替换相应的变量，有效地从中删除相应的行和列，并用值更新右侧。

请注意，刚性变换仅影响系统的右侧，而系统矩阵仅取决于初始网格。因此，我们可以使用直接求解器，并且系统矩阵只需分解一次即可最小化。此外，由于由三列组成（对于三个坐标函数)，我们只需使用相同的 n×n 因式分解对每个坐标执行三次反向替换即可求解。由于是对称正定的，因此具有减少填充重排序的稀疏 Cholesky 分解是一种有效的求解器选择 [Tol03]。

总而言之，的总体最小化过程如下。首先预先计算系数并预先分解（9) 的系统矩阵。给定初始猜测，估计局部旋转，如第 2.1 节所述。新位置通过求解（9) 获得，将插入右侧。然后通过重新计算局部旋转并使用它们为线性系统定义新的右侧来执行进一步的最小化等等。这导致手头的非线性问题的有效解决方案，因为只需要反向替换。

4.结果与讨论

ARAP 技术通过优化局部旋转来很好地处理平移，代价是全局非线性优化。值得注意的是，所需的数值机制和线性系统的设置几乎与线性变分方法相同。

一个重要的实现问题是启动优化的初始猜测；由于我们最小化的能量是非线性的，因此可能存在多个局部最小值，并且解决方案取决于这种情况下的初始猜测。重要的是使用质量合理的初始猜测（即，离初始形状和直观预期的结果不太远）以允许快速收敛，但需要快速计算。

ARAP 技术有一个有趣的特性是在建模约束允许的范围内保持边缘长度。如果建模约束不对表面施加拉伸，则优化总是努力收敛到边长误差很小的状态。

5.结论

ARAP 方法的重要特征是：

​ （1）稳健性，由保证不会在每个步骤中增加能量的最小化过程产生

​ （2）简单，因为最小化的每一步在概念上都类似于拉普拉斯建模

​ （3）效率，因为拉普拉斯系统矩阵在整个迭代过程中是恒定的，并且只需要被分解一次。

迭代中的每一步都可以通过在整个最小化过程中求解具有常数矩阵的线性系统来执行，这实际上是对能量泛函进行仔细设计的结果。 合理接近最小值所需的迭代次数取决于（锚定的）拉普拉斯矩阵的条件数，该矩阵通常与网格大小成正比。 具体来说，如果我们保持边界条件相同并细化网格，即使网格元素的形状是完美的，条件数也会成比例增长（关于均匀锚定拉普拉斯矩阵条件数的详细分析和边界，请参见 [CCOST05]；对于等边三角形的镶嵌，均匀拉普拉斯算子与余切拉普拉斯算子重合，在其他情况下，余切拉普拉斯算子的边界可能更悲观）。 这意味着随着网格的细化，稳定性会下降，并且通常需要更多的迭代直到收敛（除了每次迭代变得更加昂贵的事实之外）。 这个实际的效率问题可以很容易地通过多分辨率技术得到缓解。

ARAP 技术的另一个有趣的品质是它可以简单地扩展到体积单元，例如四面体。由于刚度是根据每个单元的边缘测量的，因此无需更改能量设置——只需插入体积网格的连通性即可。因此，如果关注的是体积的保存而不是表面的保存，那么这很容易实现。方然，与其他最近的方法一样，优化可以应用与粗略的体积网格，它控制嵌入其中的形状，而不是直接控制离散的表面或体积。