As-rigid-as possible shape manipulation：优化2——基于MKL的矩阵计算优化

之前的文章，我实现了 Igarashi 发表于2005年 Siggraph 的 2D Shape Manipulation 算法。另外，之前发表的一篇公众号文章中，我也实现了 Igarashi 发表于2009年的算法优化论文。

这两个算法的输入都是一个2D形状，形状内部空间被三角化。如下图所示。

这两个算法处理过程大体都分为两步：Pre-Computation 和 Deformation。

Pre-Computation即如下的 Registration 和 Compilation。

Deformation即如下的Manipulation。

两步的处理过程请看我之前发表的系列文章。

这两步算法都涉及最基本的矩阵求解。

其中

是2D形状的点集坐标。根据形状内部空间三角化的稠密程度，矩阵求解的耗时与2D形状的点集数目正相关。

我在代码中使用的是常用的矩阵计算库 Eigen。Eigen 可支持 MKL 优化。

如果你的电脑是Intel的处理器，就可以用这个MKL加速矩阵计算。我们不需要修改代码，只需要引入一个宏EIGEN_USE_MKL_ALL即可，使用极其方便。

我们来看对比结果，使用 MKL 前后差距有多大。

对于Pre-Computaion过程。

MKL Before MKL After

17 ms 6 ms

对于Deformation过程。

MKL Before MKL After

2.3 ms 1.6 ms

看了上述结果，您可能觉得，这也没怎么差多少。也就两三倍的差距，都是可以接受的范围。

但是当我们换作另一个更大，三角化稠密程度更大的形状时，就能看到肉眼可见的差距。

这个形状内的点的数目为694，之前我用的形状只有214个点。我们再看这两个过程的耗时。

对于Pre-Computaion过程。

MKL Before MKL After

840 ms 190 ms

对于Deformation过程。

MKL Before MKL After

90 ms 17 ms

我们可以看到，对于用 MKL 优化之前，Pre-Computation 过程耗时接近 1s。在程序运行过程中，已经是很难以接受的速度了。对于实时的 Deformation 过程，如果没有 MKL 优化，deform 的速率只有 11 帧每秒，这已经是肉眼可见的慢了。

这篇文章应该是As-rigid-as possible Shape Manipulation系列文章的最后一篇文章。

最后，我们加入纹理，看一下形状变形的效果。

该文所有代码都已开源，地址为：

https://coding.net/u/forestsen/p/ARAPShapeManipulation

另外，Github上也开源了，欢迎关注我，star这个项目。

https://github.com/forestsen/ARAPShapeManipulation