网格变形算法

需求分析

根据几何模型上的几个特征点，对几何模型进行变形。比如

技术分析

把几何模型使用三角面片表示，然后通过网格映射变形进行实现。关于网格这块有本经典的书可以参考，《ploygon mesh processing》。上面那个模型看着比较复杂，现在使用比较简单的模型来讲解一种映射方法。

如上图，为2D模型，左图为原始模型，${\mathbf{P}}_1$ ， ${\mathbf{P}}_2$ ，${\mathbf{P}}_3$ ，${\mathbf{P}}_o$ 坐标已知，右图为变形后模型，其中${\mathbf{P}}_{11}$ ， ${\mathbf{P}}_{12}$ ，${\mathbf{P}}_{13}$ 坐标已知，求${\mathbf{P}}_{1o}$ 的坐标。将${\mathbf{P}}_{1o}$的坐标表示成${\mathbf{P}}_{11}$ ， ${\mathbf{P}}_{12}$ ，${\mathbf{P}}_{13}$ 的线性组合，比如$${\mathbf{P}}_o=k_1{\mathbf{P}}_1+k_2{\mathbf{P}}_2+k_3{\mathbf{P}}_3$$ ,因为是映射嘛，这里使用同样的系数 $\mathbf{k}$ ，即$${\mathbf{P}}_{1o}=k_1{\mathbf{P}}_{11}+k_2{\mathbf{P}}_{12}+k_3{\mathbf{P}}_{13}$$ 写成坐标的矩阵形式
$$\left[\begin{array}{ccc}{P}_{1x}& P_{2x}& P_{3x}\\ P_{1y}& P_{2y}& P_{3y}\end{array}\right]\left[\begin{array}{c}{k}_1\\ k_2\\ k_3\end{array}\right]=\left[\begin{array}{c}{P}_{ox}\\ P_{oy}\end{array}\right]（1）$$
和
$$\left[\begin{array}{ccc}{P}_{11x}& P_{12x}& P_{13x}\\ P_{11y}& P_{12y}& P_{13y}\end{array}\right]\left[\begin{array}{c}{k}_1\\ k_2\\ k_3\end{array}\right]=\left[\begin{array}{c}{P}_{1ox}\\ P_{1oy}\end{array}\right]（2）$$
如果能从（1）式中求出$k_1$, $k_2$ ,$k_3$然后带入（2）式，就可以算出待求点坐标了。至于如何从（1）式中求出$k_1$, $k_2$ ,$k_3$，其实是一个线性方程组求解问题，$$A_{mn}{X}_n=b$$
在三维空间里，m=3（也就是xyz三个分量），有几个特征点，n就等于几。因为不是方阵无法直接求逆，可以使用伪逆矩阵进行计算，只要解出一组解的k值，就是找到了一个点映射。其他的网格点依次执行就可以了。这样算出来的网格可能会畸变比较大，或者形状不理想现象。至于畸变大可以描述为不够平滑，仍然有很多数学工具可以使用，比如拉普拉斯平滑等。