他山之石，可以攻玉。

                                                                                                                ----《诗经·小雅·鹤鸣》

 

       这篇文章的摘要读起来很舒服，依次介绍了采用的全局优化算法，优化函数的两个组成部分及其意义，算法的较低的时间复杂度（优点）和求解的技术手段（稀疏线性方程组）以及三个具体的应用场合，最后是实验结果。

       Laplacian优化算法是最常用的一种网格优化方法，计算简单，几何意义直观[注1]。但是它由三个主要的缺点，一是容易造成 "shrinkage" 的现象，即优化后的网格较优化前缩小了很多[注2]；二是优化的结果和网格节点的顺序相关。文中提出的算法能有效地解决上述两个问题；三是当围绕优化点的其他点所组成的区域为凹多边形时，不加检查的 Laplacian 优化可能产生翻转的网格。

       具体地，先看第一个问题。如果让容易发生 "shrinkage" 的节点不移动或者移动很小，那么很大程度上改善结果。对应到优化问题中来，就是给优化问题加上相应的约束条件。在求解过程中，使用了一个优化问题常用的技巧：将求解有约束的优化问题转化为求解无约束的优化问题（前者称为hard constraints，后者称为soft constraints）。由于涉及到二次规划问题，使用优化的充分条件（求导结果为零）就把问题转化为线性方程组的求解；第二个问题，由于加约束之后的线性方程组有唯一解，它自然和节点的排列顺序无关（考虑线性方程组交换其中两个方程的顺序，并不影响求解的最终结果）；关于第三个问题，由于是一个非凸问题，到目前为止仍然没有什么好的解决办法，文中是通过释放某些点的约束条件来尝试使得网格符合要求。

       细心的童鞋可能会发现，优化问题中要有目标函数。这个真有，文中使用的目标函数是根据 Laplacian 的在每一个点的理想结果推导出来的向量范数来定义的（其中涉及到的矩阵元素由Laplacian算法来确定）。关于优化函数中其中两项的建立，文中说是受ROF 92年那篇经典的文章启发的[2]，这篇文章是数字图像处理领域了解TV算法的必读入门文章，谷歌的搜索结果显示目前已经被引用了8000多次。

       另外，文中也给出了丰富的实验结果，从Fig.1 到 Fig.14，每个 Fig 中平均有三个子图。

      BTW：上个学期有幸听过这篇论文的第一作者的讲座，内容是将压缩感知里面的优化方法应用到 3D 打印技术中（也是他山之石，可以攻玉的典型应用）。刘利刚老师扎实的数学基础，敏锐的前沿科技嗅觉（率先将微软的一款新产品用于科研中），深入浅出的讲解（照顾到不同背景的听众）以及和蔼亲切的作风，都给我留下了深刻的印象，在此赞一个。

参考文献：

      [1] Ligang Liu, Chiew-Lan Tai, Zhongping Ji, Guojin Wa, Non-Iterative Approach for Global Mesh Optimization, Computer-Aided Design, 39(9), 2007.

      下载链接：

      ;

      [2], , 

,, 1 November 1992, Pages 259–268

         下载链接：

         

注1：

      从数学的角度来看，Laplacian算子可能看成是热平衡微分方程的数值迭代的五点格式的一个扩展形式。

注2：

      以前在某篇论文中也见过该结论，但没有细致地去考虑原因。这篇文章给出一个说法，认为原因是由于节点的移动没有限制造成的。其实，我个人觉得，可以通过一个例子来说明原因。考虑一个划分三角网格的圆锥，围绕圆锥顶点的几个点恰好在一个平面内，那么，对圆锥顶点采用 Laplacian 算法进行优化，它将被移动到与它相邻点所在的平面内。就是说，Laplacian 算子可以看成一个磨光算子，不断地将有棱角的地方平滑，物体的体积自然缩小。