Page 295 - 《软件学报》2020年第10期

金耀 等:距离约束的网格曲面曲线设计方法 3271

其示意图如图 2 所示.

Fig.2 Illustration of the distance from a point to its tangent plane
图 2 点到切平面距离的示意图

从而,公式(7.1)可近似转化为如下优化问题:
min 3 ( )E q = min 3 ∑ M || q − 2q + || + 2 ω N || q −q p || +∑ 2 λ M || (q − ′ ) N⋅ ∑ (q || ) ′ q 2 (10)
∈
q j R q j R j= 1 j− ∈ 1 j j+ 1 j= 1 j k j j= 1 j j j
相对于点到点的距离约束,点到切平面的距离约束由于约束曲线采样点在近切平面上移动,使得一方面
给予其足够的自由度进行光顺,另一方面又能贴近网格曲面,因此能够较快地实现曲线的光顺.
类似基于点到点距离约束的数值方法,本文同样采用“整体-局部”交替迭代的策略求解公式(10).然而,若
直接采用该策略,将可能导致曲线在整体阶段“过度”光顺而偏离曲面,且不能保证算法收敛——虽然能量函数
值在整体阶段得到下降,但在局部投影阶段可能上升.为此,本文借助 Gauss-Newton 法 [37] 的思想,采用局部线搜
索控制其收敛行为.利用公式(10)的 Hessian 矩阵 H(E(q))计算当前曲线顶点的迭代方向,并结合线性回溯搜索
法控制迭代步长.即:当能量函数值大于当前值时,采用对步长折半的方式保证能量函数在迭代过程中单调下
降,从而使算法能够稳定收敛.由于公式(10)确定的能量函数为平方和形式,其对应的 Hessian 矩阵是对称正定
的,因此其每次迭代的“整体”阶段均可转化为凸问题进行求解,无需进行正则化.其迭代求解的每一步通过如
下公式更新曲线顶点位置:
( ), =
s = (( ))E q − 1 ∇ H E q q q − ωs (11)
其中,ω∈(0,1]为迭代步长,通过折半线性回溯法确定大小.
为了提高计算效率,本文分别从整体和局部阶段两方面进行考虑.整体阶段需求解一个线性系统,利用公
式(11)中 Hessian 矩阵的结构在迭代中始终保持不变的性质,通过对矩阵结构进行预分解以加速.局部阶段需
搜索最近点,本文用切平面法向量与局部邻域面片的交点进行近似,一旦找到交点则结束,不必遍历剩余面片.
由于交点不一定存在,此时可采用最近点替代.
由上述算法得到的曲线,其每一段离散的折线将非常接近曲面但往往不严格位于曲面上(对位于不同面
片的相邻两个点形成的线段).为此,本文采用文献[38]中介绍的投影法将其映射到曲面上:对于每一条未处于
网格表面的线段,由一个端点(起始点)向另一个端点(终止点)逐步构造切割平面,与相关的网格边进行求交,并
将交点更新为起始点,逐步往前传播.如此循环,直至起始点与终止点重叠.具体细节可参考文献[38].
综上所述,本文提出的基于距离约束的曲线优化算法可描述如下.
算法 1. 基于距离约束的曲线优化算法.
输入:顺序输入位于曲面 S 的若干插值点{p i },软约束权重λ和ω,最大迭代次数 N,误差阈值ε;
输出:位于曲面 S 且插值于所有{p i }的光滑曲线.
1: 采用第 2.3 节中介绍的方法将曲线离散化为{q j }.
2: 将{} ′ q j 初始化为分段 Dijsktra 路径的采样点.
3: n=0.