As-rigid-as possible shape manipulation：优化1
- 2019 年 10 月 8 日
- 筆記
比如论文原作者Igarashi教授在09年发表的论文[1]说到，他们重新整理了论文，提出了新的方法，该方法相比05年论文[2]更清晰、更容易理解。作者在[1]中提出的方法有两个改进，第一个改进是当用户在图形上交互时，不需要点击图形上三角化后的点，只需要点击图形内部任意坐标即可。第二个改进是使用“边”为变形单位，提高了代码的简洁性。最后作者将该方法应用到三维模型纹理展平，相比当时其他流行的纹理展平算法同时兼具质量和性能。
我们直接看论文算法。首先，算法的处理单位从“三角形”变为“边”。
在拖动控制点对图形做变形时，如之前文章，我们期望变形后的图形尽可能“接近”原始图形。按照该论文思想，从数学上讲，我们提出如下的优化方式。
其中 E 表示顶点序号为
的 “边”的集合。
表示变形后的“边”向量，
表示对应的“边”向量。
表示用户交互时点选的控制点坐标， C 表示控制点集合。把刚才提出的优化方式写为数学公式如下。
其中，ω 表示权重变量，论文[1]中使用的 ω = 1000。
（注：论文[1]中的该公式是错误的，按照论文[1]后面的讲述，ω应该在取模括号内。）
这是一个线性的优化问题，论文[1]说可以把上述优化公式简写为
其中 v' 表示所有点的集合，
然后，我们对其做分解，下述表达形式是论文作者给我们推导的。
初看可能没有那么明显。下面我来详细说明。
首先，我们先确定点集 v' 的大小，系数矩阵 A 的大小，常数矩阵 b 的大小。
由点集中任一点都可表示为
那么点集 v' 可表示为
拆分为两个子矩阵，
则可以简单表示 v' 为
就好像 v' 由两个元素构成的向量一样。
同理，b 也可以表示为这样的形式。
最后表示 Av'-b
把 Av'-b 分解为两个子矩阵，那么可以把它看作由两个元素构成的向量。如果对这个向量求模的平方，相当于把两个元素分别取平方再求和。
对 Av'-b 取模的平方
那么
很明显可以看出来，只需要单独看 x 分量或者 y 分量的优化方程即可知晓系数矩阵 A 和常数矩阵 b 的大概样子。
我们再加一个理解过程。
再把原始的优化方程简化一下。
我们换种方式写一下。这两个求和式子完全可以写成 Av'-b 的形式。
以及
那么可以写成
终于回到论文作者推导的式子了。
我觉得写到这，大家绝对能看出来，作者推导的这个式子是怎么出来的。也知道这个式子里 A 中哪些元素是 1、-1、ω，常数向量 b 为什么由边向量和控制点构成，为什么会这样写。我在这里就不再赘述，如果还有问题，可以私信我。
最后，需要对这个最小二乘优化求偏导。
我们只需要通过解方程来求解变形后三角形的所有点的新坐标。
类似于[2]，论文[1]也用两步变换来解决变形问题。
第一步，相似变换。
如果对于下图这样的边
。
一般
都有四个邻接点。如下。
但是当
是图形的边界，则邻接点只有三个。
论文[1]里定义了一个旋转变换
，
(注：T ⇦ Transformation, c ⇦ cos, s ⇦ sin)
这个旋转变换的目的是让这条边
的邻接点在变形时位置尽量不变。那么用优化方程可以表示为
论文作者替我们做出了非常详尽的推导过程。
最终结果表示，这个优化是一个线性的最小二乘优化。我们对
求偏导，并使偏导值为0，得到。
回到这篇文章最初的优化方程
我们只看其中的
现在就可以把优化方程写成如下形式。
类似于如下形式。
可以看出来右边的“边”向量都是 0，也就反映了第一步算法刚开始的对
的优化方程——对"点"的变换。求解这个优化方程有，
第二步，尺度适配。
使用第一步算法的输入为输出，使用一个旋转变换，类似的。
在这一步不同的是，我们要对该变换做归一化。
再看完整的优化方程。
其中，
的计算在第一步算法结束后，用第一步的结果算出来的。所以，
相对于第二步算法来说是常量。所以，这个优化方程是线性的最小二乘优化，可以写成如下形式。
同样的，按照 x 分量和 y 分量分开计算。
和第一步算法类似，只不过右边的"边"向量用第一步的结果生成。
同样的，求偏导得如下等式，我们解方程即可。
最后，我们再完整的看一下实现细节。[1]和[2]相似，同样有很多矩阵是可以预计算的。看一下这两步的优化方程，
由于 A₁ 和 A₂ 类似。我们只看 A₁。
A₁ 的上半部分可以由原始图形的点集来表示。所以这一部分，在读取模型的同时就可以把这部分预计算。
A₁ 的下半部分在用户点击控制点时实时生成，每个元素都是固定的 ω 值构成的。所以这一部分，在每点击一次控制点时预计算。
而 b₁ 和 b₂ 是由控制点的坐标生成，这一部分是用户拖拉控制点时实时变化生成的。
下一篇文章，我们将用C++代码实现。
引用
[1] Igarashi T , Igarashi Y . Implementing As-Rigid-As-Possible Shape Manipulation and Surface Flattening[J]. Journal of Graphics Gpu & Game Tools, 2009, 14(1):17-30.
[2] Igarashi T . As-rigid-as-possible shape manipulation[J]. ACM Trans. Graph. 2005, 24.
