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

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

into a convex optimization via distance approximation. In the local stage, a robust and efficient projection method is applied to update
tangent planes. Finally, each segment of the poly-line is projected onto the surface by cutting planes. Experiments exhibit that the
proposed method outperforms existing work on various aspects, including effectiveness, robustness, controllability, and practicability.
Key words: mesh surface; curve design; distance constraint; alternating iteration

在网格曲面上进行曲线设计是进行几何处理与编辑的一项重要内容,且有着广泛的应用背景,如网格处理
中的部件分割 [1,2] 、虚拟手术中的模拟切割 [3,4] 、制造业中的图案设计 [5−7] 以及流形上的计算几何 [8−11] 等.这种曲
线有多种设计方式,其中常见的有插值与光顺两种:用户在网格曲面上输入几个控制点或一条初始曲线,系统便
生成一条附着于曲面的光滑曲线,使之经过这些输入点(插值)或逼近于初始曲线(光顺).换言之,在网格曲面上
设计曲线,需同时满足流形约束(曲线位于曲面上)、光滑约束、插值点约束(若有)等,而其中的流形约束使其较
之于欧式空间的曲线设计问题更为复杂,难度更大.
现有针对网格曲面的曲线设计方法大致可以分为 3 类:投影法 [12−14] 、光顺法 [1,2,4] 以及参数化法 [6,15] .投影法
通常将光滑的空间曲线迭代地投影到网格流形上,方法简单、高效,但其迭代过程缓慢且投影步骤往往不太鲁
棒.光顺法即对给定曲线在保持流形约束下进行光顺,方法通常较为鲁棒,但其效率较低.参数化法即将局部曲
面参数化到欧式平面,在平面上设计曲线并将结果映射回曲面,方法往往鲁棒、高效且灵活,但其受限于局部区
域,难以进行大范围的曲线设计.
针对上述不足,本文提出了一种高效且实用的曲线设计方法.该方法的思想是:将流形约束转化为距离约
束,用切平面逼近局部曲面,将距离约束松弛为点到切平面的距离,并与光滑约束、插值点约束共同作为优化目
标进行求解.求解时采用“整体-局部”交替迭代的思想,并借助 Gauss-Newton 法控制其收敛行为.该方法不仅提
高了鲁棒性与计算效率,而且具有形状可控、适用范围更广等特点,能够应用于多种场合.
1 相关工作

曲线设计是计算机图形学与计算机辅助设计的一个充满活力且具有较长历史的研究话题,现有的大部分
研究工作着眼于欧氏空间的曲线设计,其相关的理论与算法被深入研究并已趋于成熟 [16,17] .随着数字几何的广
泛应用以及工业界与学术界需求的增加,在流形空间,尤其是在曲面上进行曲线设计,越来越多地引起人们的关
注.但是,针对这类方法的理论与算法未及前者成熟.根据曲面表示形式的不同,这些方法可分为两大类:针对参
数曲面的方法与针对网格曲面的方法.前者通常采用参数化法:由于参数曲面具有一个天然的参数域,因此通常
可在参数域上设计曲线并将结果映射至原曲面空间 [18−20] .但是绝大多数方法仅考虑具有单个参数域的参数曲
面,对于形状与拓扑复杂的曲面则不适用.由于在实际应用中网格曲面更为广泛,因此本文仅讨论与研究内容相
关的针对网格曲面的工作.
网格曲面上的曲线由于其所在的曲面具有分段线性特点,通常表示为一条分段线性的折线段.其中,具有广
泛应用背景的离散测地线便是其中一种,且一直是图形学相关领域的研究热点 [9−11] .但测地线旨在计算“局部最
短”的曲线,而本文所研究的是离散曲面上的“光滑”曲线,因此本文仅考虑网格曲面上自由曲线的设计.现有方
法大致分为以下 3 类.
• 投影法
这类方法将流形约束进行松弛,首先生成经过插值点的光滑曲线,然后将其迭代地投影到流形上.Hofer 等
人 [12,13] 提出了一种基于能量极小化的样条曲线插值方法,他们将曲线离散成折线,把问题描述成一个带流形约
束的优化问题,其中,目标函数是样条能量与测地能量的组合;并采用投影梯度法进行求解,即将松弛流形约束
得到的空间曲线迭代地投影到曲面上.该方法与流形的表示形式无关,可用于诸如隐式曲面、参数曲面与网格
曲面等,但其投影步骤并不能保证一定能找到理想的投影点,鲁棒性较差.同时,由于投影采用了移动最小二乘
法(MLS)局部拟合法,效率较低.Pottmann [14] 随后提出了高阶样条能量,并将该方法进行推广在曲面上拟合曲
线.Wallner 和 Pottmann [21] 分别提出两种方法,将欧氏空间中设计细分曲线的线性细分法推广至流形曲面:第 1
种提出用“测地平均法”替代传统的线性平均法,但需计算大量的测地线,较为耗时;第 2 种是在外围空间设计细