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

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

c = argmin x 0 ∫ 1 || ′′ x ( ) || dt 2 t ⎫ ⎪
s.t. ( )tx = ,i = p 1,2,..., N ⎬ ⎪ (1)
i k i ⎪
x ()t ∈ S ⎪ ⎭

其中,x(t)∈S 表示位于曲面 S 的曲线, x″(t)为曲线关于位置参数 t 的二阶导,其几何意义与曲线的曲率正相关.
当S为网格曲面时,其上的曲线可表示为分段线性的离散曲线c=〈V,E〉,其中,V={q 1 ,q 2 ,…,q n }⊂S为曲线上的顶点
集,E 为形成曲线的边集.
• 当曲线为开曲线时, E = {qq 1 | i = 1,2,...,n − 1} ⊂ S ;
ii+
• 当其为闭曲线时, E = {qq (1)%(i+ n+ 1) | i = 1,2,..., }n ⊂ S (%为取模运算).
i
由于曲线是离散的,公式(1)中曲线的二阶导数 x″(t)并不存在,因此需首先对该公式进行离散化,并采用数值
方法进行求解.
2.2 流形约束转化

对于离散网格曲面 S,由于其没有解析表达式,导致公式(1)中的流形约束难以显式表示,从而给求解该带约束
3
的优化问题带来较大的困难.为此,本文引入一个距离函数 D:R ×S→R,用于度量空间中任意点到流形 S 的距离,从而
将流形约束转化为距离约束,即等价地表示为曲线上任意点 q∈x(t)到曲面 S 的距离为 0:
D(q,S)=0,∀q∈x(t) (2)
而距离函数 D 则可定义为点到局部曲面的最短距离:
D(q,S)=||q−q′||,q′=argmin s∈S∩B(q,r) d(q,s) (3)
其中,d 为点到点的欧式距离函数,B(q,r)为 q 的半径为 r 的球形邻域.
2.3 离散化

公式(1)中带约束的优化问题可用数值方法求解,但首先需进行离散化.为方便对二阶微分表示的 3 次样条能量
进行离散化,类似文献[12],本文采用弦长参数化方法计算采样密度,即对相邻两个插值点所形成的线段 p i p i+1 ,确定
其采样点个数 N i 为
N i =⎣||p i −p i+1 ||/D+0.5⎦−1 (4)
其中,D 为离散步长,亦即每条线段的长度(默认情况下设置为网格平均边长的五分之一),用于控制曲线的采样密度.
由此,该曲线可离散成折线段,其有序采样点为{q j },其中, q = p (k i 为插值点在采样点中的序号).由于该离散方式
i k i
使得曲线上的采样点能近似均匀分布,因此公式(1)的目标函数可近似地离散化表示为均权拉普拉斯能量 [33] :
E = s ∑ M j= 1 || q j− 1 − 2q j + q j+ 1 || 2 (5)
其中,对于开曲线,M 表示折线段中除却首尾端点的离散点个数;而对于闭曲线,M 表示所有离散点个数.于是,公式
(1)可改写为如下离散表达式:
min 3 ∑ M || −q 2q + q || 2 ⎫
q j R j= 1 j− ∈ 1 j j+ 1 ⎪
⎪
s.t. q i k = i ,i = p 1,2,...,N ⎬ (6)
D (, ) S = q j 0, j = 1,2,...,M ⎪
⎪
⎭
为求解该问题,本文运用罚函数法,结合距离公式(3),并将公式(5)中硬约束表示的插值点约束与流形约束分别
作成软约束,则公式(5)进一步转化为如下优化问题:
( ) =
min Eq min M || q − 2q + q || + ∑ 2 ω N || q − p || + 2 λ ∑ ∑ M || q − || ′ q 2 (7.1)
3
3
q j R q q j R q , j S j= ′ 1 j− ′ ∈ 1 j j+ 1 j= 1 j k j j= 1 j j
∈
∈
∈
, j S
s.t. ′ =q j argmin s ∈∩ B ( j q , )r d ( , )q s (7.2)
j
S
其中,
8
• 参数ω默认取作大的数值(10 ),使之近似满足插值约束;