问题描述

动画的渐变效果是动画制作与处理过程中的一个重要问题。如果我们将动画中的一些物体的框架用不自交的多边形来描述，动画的渐变过程可以看作是两个不自交多边形互相转化的过程。值得注意的是，在这个问题中，我们可以向其中加入一些约束限制。首先一个必须要保证的约束是在多边形连续变化的过程中不能产生自交现象，另一个要考虑的约束是对多边形点和边的一些限制（如：保持某条线段长度不变，保持某个角大小不变等），实际效果如下图所示。

在传统的解决方案里，比如一些插值类算法，往往很难做到以上两点，尤其是针对复杂的非凸多边形的情况。因此Hayley N. Iben et al. 提出了一种新的算法，与传统方法不同的是，该算法定义了每个多边形的能量函数，对于给定的一个起始多边形和终止多边形，找到一个能量函数最低的多边形作为中间结果，分别迭代计算两个多边形过渡到中间多边形的渐变过程，每次迭代时找到使能量函数和两个多边形的某种距离测度不升的方向，从而逐渐变化到中间结果。最后的形变过程就是由起始多边形到中间多边形的形变过程和终止多边形到中间多边形的反向形变过程组成。该方法的好处是将这种形变过程看作是一个优化问题，从而便于将约束变成一些量化的优化问题的约束条件来处理。

我们组将参考Refolding Planar Polygons这篇论文的内容，复现了本论文中针对复杂多边形渐变这个算法，并进行了简单的效果演示。

算法描述

我们主要实现了论文[1]中描述的基于能量梯度下降的算法。 首先要说明的是平面上简单多边形渐变的存在性，[2]中的理论分析指出，任何平面简单多边形都可以连续展开成一个凸多边形，而且保持过程中的边的长度不变，保持边不相交。因此任何两个兼容的平面简单多边形都可以通过先展开成凸多边形的方式实现连续不自交的渐变过程，这至少说明了问题解的存在性。但是我们实现的算法希望能够以最“直接”、“自然”的方式完成渐变过程。

定义平面上简单多边形的能量函数E，满足如下性质： 1. 一阶连续可微； 2. 对不自交的多边形，能量有限，当趋于自交时，能量趋于无穷； 3. 在多边形展开时能量下降； 4. 能量可分，当图中独立的一部分远离其他部分时，有关这一部分的能量应当消失。

定义两个简单多边形的形状距离J，度量两个简单多边形的相似程度。

算法思想是，从起点图S和终点图T出发，将能量较高的图进行能量下降（形状展开），通过梯度投影，可以在能量下降过程中尽可能保证两者的形状距离减小，尽可能保持约束（如对应边长不变）成立。不断迭代进行这一过程，直到两个图收敛到相同的形状。总结为“能量交替下降直至距离收敛”的思想。 注意到每一步迭代中，虽然两者的形状距离可能回升，但是能量函数均是单调减的，因此收敛是可以保证的，论文[1]中做了严格的证明。

下面对算法细节进行描述。

首先对能量函数E和形状距离J进行数学形式化表达： 对于$N$个结点的简单多边形，令$\boldsymbol{v}_i$表示图中结点，$e_i$表示$\boldsymbol{v}_i$和$\boldsymbol{v}_{i+1}$之间的边，能量函数$E$可采取以下形式： $$ E=\sum_{i=1}^{N}\sum_{j=1,j \neq i, j \neq i-1}^{N} \frac{1}{dist(\boldsymbol{v}_i, e_j)^2} $$ 其中$dist(\boldsymbol{v}_i, e_j)$表示平面上点vi和线段ej的欧几里得距离，

形状距离L采用对应点的欧式距离的平方和，令$\boldsymbol{v}_i$和$\boldsymbol{u}_i$表示两个多边形中对应点 $$ L=\sum_{i=1}^{N}||\boldsymbol{v}_i - \boldsymbol{u}_i||_2^2 $$

算法是基于梯度下降的迭代算法，在每一步迭代中，令H为当前S,T中能量函数E相对较高的一个。根据算法“能量交替下降直至距离收敛”的思想，每一步迭代中，仅对能量较高的多边形H进行梯度下降。 利用上面两个式子，对$2N$个坐标点求导，容易得到能量函数梯度$G=\nabla E$ 距离梯度$D=\nabla L$ 。 显而易见的是，沿着距离梯度$D$移动坐标点，两个多边形会逐渐靠近，但是有可能边会相交；沿着能量梯度$G$移动坐标点，多边形会渐渐膨胀但是并不会逐渐靠近。如何在保证边不发生相交的前提下，让两个多边形尽可能靠近呢？

答案是保持$D$的大方向不变，在能量梯度$G$的指导下予以纠正（energy-guided），以期在保证不会产生自交的情况下，最大限度的减少两多边形的距离。用数学的语言，就是将$D$投影到$G$的零空间中去，或者说，从$D$中减去$G$方向上的分量，如下面公式所示

$$ D=(I-GG^T)D = D-(D^T G)G $$

在上述基础上，我们可以增加额外的限制来进一步控制该渐变过程，这里可以考虑的一种限制是限定某两点间的距离为常数。如果对所有相邻点间的边都施加此种限制，则相当于把每条边都变成了不可伸缩的刚体，这和很多实际场景是相符的，其变换过程也看起来更加自然和具有美感。

这里假设每个限制都是可微的，且可以表达成$\Omega(H)=0$的标准形式。对于上述提出的相邻点间距离相等的限制，可以表达如下: $$ ||\boldsymbol{v}_i-\boldsymbol{v}_{i+1}||^2-l_i^2=0 $$

若有$M$个限制，参数坐标有$2N$个，我们将每个限制的梯度向量$\nabla \Omega\in R^{2N}$组成一个$M\times2N$的矩阵$J$，然后将$D$投影到$J$的零空间中。投影后的$D$与$\nabla \Omega $ 正交，因此不会违反这些限制。按照如下公式投影$D$ $$ D:=D-J^Tl $$ 其中$l$是$D$在$J$的行空间中的线性组合系数，可通过以下线性方程组解出 $$ JJ^Tl=JD $$ 可参考论文[3]理解该式的推导过程。

为了防止错误累积，在实际实现中，增加了一个正则项 $$ JJ^Tl=JD+\alpha e $$ 其中$e_k=\Omega_k(H)$, $\alpha$是一个正常数，其越小说明这些限制越严格

之前提到每一次迭代，要保证能量不升，我们也可以把它看作一个特殊的限制。将$G$添加到限制矩阵的最后一行，记为$f$；将一个正常数$\gamma$加到$e$的最后，记为$K$；通过下式求解$l$： $$ KK^Tl = KD + \alpha f。 $$ 值得注意的是，由于梯度会连续变化，沿着投影后的$D$前进微小的步长仍旧可能导致能量上升，在这种情况下可以调整$\gamma$的取值，或直接沿着$G$能量方向梯度下降，忍受暂时可能的距离上升。

实现细节

该算法使用javascript语言实现，在网站Demo中运行于服务器端。

网站后端使用 nodejs 实现，前端使用 html + javascript 实现，实现过程中使用了两个开源工具包： - d3.js：用于画图和动画演示 - jquery.js：用于简化javascript的函数

前后端的通信使用了 websocket 和 AJAX 两种技术。

下面重点讲解一些算法实现的关键细节： - 在判断多边形的边是否相交时，我们使用了四次 toLeftTest。但是会出现三点共线的情况，此时我们通过判断共线的点是否存在包含关系，来判断是否有相交的情况。判断是否存在某个点被在另一条线段包含的情况，我们使用了逐一点积的方法进行检验。

代码可见 https://github.com/lgh303/refolding-planar-polygons

结果演示

demo 1：

demo 2：

Reference

[1] Iben H N, O’Brien J F, Demaine E D. Refolding planar polygons[J]. Discrete & Computational Geometry, 2009, 41(3): 444-460. [2] Connelly R, Demaine E D, Rote G. Straightening polygonal arcs and convexifying polygonal cycles[C]//Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on. IEEE, 2000: 432-442. [3] Hueck U, Schreyer H L. The use of orthogonal projections to handle constraints with applications to incompressible four‐node quadrilateral elements[J]. International journal for numerical methods in engineering, 1992, 35(8): 1633-1661.