本文介绍一种网格分割线的优化算法，该方法能够找到网格上更精确、更光滑的分割位置，并且分割线能够*地合并和分裂，下面介绍算法的具体原理和过程。
曲面上的曲线可以由水平集（level set）形式表示，通常表示为φ(r) = 0，其代表曲面上具有相同函数值的等值曲线，由于函数值为零，一般称为零水平集。当曲线在曲面上移动时，可以用如下水平集方程表示：
上式为函数φ(r)对时间t的偏导，即函数φ(r)随时间t的变化情况，等式右边v表示曲线移动速度，▽φ表示曲面上函数φ(r)的梯度。
驱动曲线在曲面上移动有多种方式，而测地曲率流（geodesic curvature flow）是其中最常见的形式，如果以测地曲率来驱动曲线移动，那么曲线的水平集方程可以表示为：
此时函数φ(r)就是曲面上各点到曲线的测地距离（曲线的一侧为正，另一侧为负），而移动速度就是曲线的测地曲率
。
上述方程表示在测地曲率的作用下曲线长度不断减小，并且本身保持光滑，同时曲面上测地曲率越大的区域曲线移动速度越快。如果在方程中加入曲面的几何特性g(r)权重之后，那么曲线可以移向期望的目标区域，此时对应的水平集方程表达式为：
其中g(r)的范围为[0,1]，在目标区域g(r) → 0。
上述水平集方程有不同的求解方式，文章[Kaplansky et al. 2009]采用显式积分的方式来进行求解：
其中φ(tn)代表tn时刻曲面上函数φ(r)值。
文章[Zhang et al. 2010]采用半隐式积分的方式来求解水平集方程：
其中φ(tn)代表tn时刻网格曲面上函数φ(r)值；S是一个对角矩阵，其表达式为S = diag(s1, s2, …, sn)，式中si是顶点vi周围1环邻域三角片面积的1/3；G也是一个对角矩阵，其表达式为G = diag(|▽φ|1, |▽φ|2, …, |▽φ|n)，式中|▽φ|i是顶点vi上函数φ(r)的梯度模长；H的表达式如下：
式中τ1、τ2以及αij、βij的含义如下图所示：
对比上面两种求解方式，半隐式积分的求解方式更加稳定，迭代步长能够取相对较大值，但是在每次迭代过程中都需要求解线性方程组，因此计算过程相对更加耗时。
% Pseudocode
. Initialize the level-set function U
for i = :iter
2.1. Calculate the gradient ▽U
2.2. Normalize the gradient ▽U/|▽U|
2.3. Calculate the divergence div(g*▽U/|▽U|)
2.4. Update the level-set equation ΔU = step * |▽U| * div(g*▽U/|▽U|)
2.5. Determine the new curves as its zero level-set
end
本文为原创，转载请注明出处：http://www.cnblogs.com/shushen。
参考文献：
[1] Kaplansky, L. and Tal, A. (2009), Mesh Segmentation Refinement. Computer Graphics Forum, 28: 1995–2003.
[2] Zhang, J., Wu, C., Cai, J., Zheng, J. and Tai, X.-c. (2010), Mesh Snapping: Robust Interactive Mesh Cutting Using Fast Geodesic Curvature Flow. Computer Graphics Forum, 29: 517–526.