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

3270 Journal of Software 软件学报 Vol.31, No.10, October 2020

• λ由用户控制,用于平衡光滑性与流形约束的满足程度.
2.4 数值求解
由公式(7.1)、公式(7.2)所定义的优化问题可知:每一对 q j 与 ′ q 都是彼此相关的,其非线性程度较高,因此直
j
接求解难度较大.为此,本文计算相邻插值点之间的 Dijsktra 路径作为初始曲线,根据公式(4)所得的采样点数量
在曲线上均匀采样离散点{q j },并设置 {} { }=q ′ j q ;然后借鉴局部/整体交替迭代的优化策略 [34] 进行求解,即将该
j
两组优化变量进行分离,并把每次迭代分解为整体阶段和局部阶段,直至前后两次计算得到的曲线差异很小为
止,其计算过程如下.
整体阶段.固定 {},q ′ 求解{q j }.此时即计算能量函数(7.1)的极小值.由于该式是关于{q j }的二次函数,因此可
j
转化为矩阵方程组 AQ=B,其中,A 为常系数矩阵.
局部阶段.固定{q j },求解{}.q ′ j 此时对每一个 q j ,求解问题(7.2),即在 q j 的球形邻域与网格曲面的交集中搜索
最近点.由于计算球体与网格的交集以及在该交集处的最近点较为耗时,因此可采用拓扑邻域替代球体几何邻
域,即将前一次迭代得到的投影点 ′ q j n− 1 (n 为迭代次数)所在三角形面片 f 0 的 r-环拓扑邻域的面片集合 F 作为交
集.在该交集中,搜索 q j 到该局部区域的最近点距离:
q ′ = argmin i f ∈ F d (, ) f =q j i argmin i f ∈ F min s ∈ i f d q j (8)
(, ) s
j
其中,点到三角形的距离 d(q j ,f i )可采用文献[35]中介绍的方法.具体地,以 f 0 作为种子点,以广度优先的方式遍历
F,对每个面片计算该点在面片上的法向投影:若投影点在其内部,则将其作为投影点并结束搜索;否则,计算点
到面片的距离并更新最近点,直至遍历完所有面片.当局部区域非凸时,有可能存在多个最近点,此时可选取使
局部拉普拉斯能量,即 || ′ j− n− 1 1 2 ′ j n + q q ′ −q j+ n− 1 1 || 最小的最近点作为候选点.
2
易证,上述交替迭代的优化策略可使能量函数(7.1)单调下降,从而收敛.具体地,在每一次迭代中,其整体阶
段求解能量函数极小值能获得比当前能量更低的值;而在局部阶段,由于固定{q j },能量函数(7.1)的前 2 项为常
数,第 3 项由于 D ( , )S ≤q j || q j − ′ q j ||, 因此也能得到更低的值.从而对于每一次迭代,该策略均将使能量值下降.
但由于 ′ q 由前一阶段曲线采样点计算得到,而非当前 q j 的投影点,直接用欧式距离 || q j − j || ′ q 度量点到曲面
j
的距离并不精确.因此,上述算法虽能收敛,但收敛速度较为缓慢.本文采用该方法在骆驼头模型上设计一条经
过 3 个插值点的闭合曲线,如图 1 所示.随着迭代的进行,曲线变得越来越光滑,但其变化过程缓慢,迭代次数过
多.虽然该算法在理论上是收敛的,且其整体阶段仅需高效地回代计算更新曲线坐标,但由于其局部阶段的投影
计算耗时相对较多,若迭代次数过多将严重影响计算效率.在本实验中,达到最大迭代次数(1 000)依然未能收敛.

(a) 骆驼头模型上的迭代曲线 (b) 能量函数变化图
Fig.1 Iteration results and its energy graph with point-to-point distance constraints (λ=0.1)
图 1 基于点到点距离约束的迭代结果与能量图(λ=0.1)

为此,本文借鉴用于曲面配准的迭代最近点(ICP) [36] 的算法思想,用对应点处的切平面逼近局部曲面,并采
用点到切平面的距离近似度量点到曲面的距离.设 ′ q 处的切平面为 T j ,其对应的法向为 N ′ 则 q j 到曲面 S 的
(),q
j
j
距离可近似表示如下:
(, ) | (q
D q S = − ′ ⋅ q ) N ′ q (9)
( ) |
j j j j