As-rigid-as possible shape manipulation: 第二步算法的第二小步详解

• 2019 年 10 月 8 日
• 笔记

如前面文章讲述，该论文第二步的第二小步算法以第一小步算法输出为输入。我们先看下第二小步的结果。

绿色框三角形是第一小步的结果，黑色框三角形是第二小步的结果。其中黑色框三角形的变形效果是由绿色框三角形变形而来。

由上篇文章，第一小步的目的是将原始三角形"旋转"和“平移”到某个位置，这个位置满足一个条件——三角形的三个点与第一步算法的三角形之间“点与点”距离和最小。图示如下。

与第一小步针对三角形对应“点与点”之间的优化不同，第二小步针对的是三角形对应“边与边”之间的优化。如下论文配图。

具体算法是，最小化三角形对应边误差和。

我们再看上面的Gif图，这一小步的运行结果保留了上一小步的“旋转”变换。在拖拉控制点时，黑色三角形和绿色三角形同步“旋转”。这也印证了论文原话所说：

That is, we use the rotation of the fitted triangle and ignore its position. The translation is solved for as a side effect only. as-rigid-as possible shape manipulation 原文4.2.2节第三段。

为使最终结果三角形尽量接近 fitted 三角形，

保留了 fitted 三角形的旋转变换。

但是最终三角形中每个点可能存在于不同的三角形中，不同的三角形变形导致

“三角形顶点的位置“

必将是一个

“平衡了所有三角形变形”

的结果。

所以，这一次优化的单位又如同第一步算法——三角形的顶点，与第二步第一小步不同。

我们用系数矩阵来重写这一步的对应边误差和。

其中

对于一个三角形三条边来说，我们有三条边的误差和，

另外，把所有的点按照自由点 u 和控制点 q 重排，重新写误差和函数。

对其求偏导，

即

很显然，矩阵 H' 和 D 都是系数矩阵 H 的子矩阵构成的。向量 f₀ 就是系数向量 f （只不过这里的 f₀ 是针对 u 的。）。在这里，我们只需要对一条边的能量函数 E₂ 推导即可。因为在程序中，我们只需要遍历三角形三条边即可。

直接用Mathematica软件推导系数矩阵 H。

展开得

看上述推导出来的式子，我们要从中取出系数矩阵 H，系数向量 f。注意，这里的常数向量 c 在求偏导的时候变为 0 了。所以我们不需要c。

展开系数矩阵 H 代码：

结果如下。

展开系数向量 f 代码：

得到结果。

至此，我们就可以由系数矩阵 H 求出 H' 和 D 了。

很显然， H' 和 D 都是固定的数值组成的矩阵。系数向量 f 由第二步算法的第一小步的结果生成。

所以，这几个矩阵都在点选完控制点 q 后，对这几个变量进行预计算即可（类似于第一步算法的做法），然后未知量 u 即可通过解方程的形式求出。实时解方程非常快，所以我们可以达到实时的交互。

看一下最终结果，将三步算法的结果都放在一个图中。

蓝色框三角形为第一步算法结果。第一步算法结果作为第二步算法的第一小步算法的输入，绿色框就是这一小步的结果。第一小步算法结果作为第二小步算法的输入，黑色框就是第二小步的结果也就是最终变形结果。

下一篇文章，我们将用C++实现上述过程，并展示我们这一篇论文的最终代码。