丁小星

公安海警學(xué)院 基礎(chǔ)部，浙江 寧波315801

1 引言

當(dāng)前在CAD、CAM 等領(lǐng)域，因B 樣條曲線具有局部修改性等良好的性質(zhì)而被廣泛應(yīng)用于表達(dá)各種復(fù)雜的幾何形體。傳統(tǒng)的能量約束法能較直觀、方便地修改與控制曲線曲面形狀，對(duì)此已有不少文獻(xiàn)[1-2]進(jìn)行了研究。文獻(xiàn)[1]將能量?jī)?yōu)化法結(jié)合幾何約束條件，利用求解能量最小曲線的方式來(lái)改變曲線的形狀；文獻(xiàn)[2]提供了一種基于外部能量約束的曲面形狀修改法，將曲面形狀修改所需的約束條件轉(zhuǎn)化為外部能量約束項(xiàng)，通過(guò)求解一個(gè)使曲面能量變化量最小的無(wú)約束優(yōu)化問(wèn)題，得到變形后的曲面，其實(shí)質(zhì)是一種逼近約束條件的過(guò)程。小波技術(shù)能將B 樣條曲線曲面分解成不同分辨率的主體與細(xì)節(jié)，便于對(duì)其形狀實(shí)現(xiàn)靈活的細(xì)節(jié)編輯和整體保形控制，已在幾何造型許多領(lǐng)域得到應(yīng)用[3-5]。文獻(xiàn)[3]針對(duì)小波多分辨率造型中的約束問(wèn)題，結(jié)合能量法實(shí)現(xiàn)小波編輯的約束處理。然而目前對(duì)小波的應(yīng)用主要集中在均勻或準(zhǔn)均勻B樣條小波上，有一定的局限性。文獻(xiàn)[4]介紹了一種雙正交非均勻B 樣條小波，避免了求Gram 矩陣以及大量的積分運(yùn)算，并具有良好的逼近性。本文將文獻(xiàn)[2]的外部能量約束法與文獻(xiàn)[4]的雙正交非均勻B樣條小波相結(jié)合，提出一種B樣條曲線局部修改算法。與文獻(xiàn)[2]的方法相比，該算法局部修改形狀的效果更好，可以滿足一些工程設(shè)計(jì)中局部修改、整體保形的需要。

2 算法介紹

2.1 B 樣條曲線定義

k 次端點(diǎn)插值B 樣條曲線的定義[6]如下：

其中，D=[d0d1… dn]T為控制頂點(diǎn)向量；Nk(u)=[N0,k(u)N1,k(u) … Nn,k(u)]T為基函數(shù)向量；為節(jié)點(diǎn)向量；Nj,k(u)(j=0,1,…,n) 為k 次規(guī)范B 樣條基函數(shù)，它由節(jié)點(diǎn)向量U 按下列遞推公式定義得到：

2.2 雙正交非均勻B 樣條小波簡(jiǎn)介

雙正交非均勻B 樣條小波[4]使多分辨率曲線曲面的造型更加靈活，由基于離散l2范數(shù)構(gòu)造而成，計(jì)算量較小。本節(jié)將簡(jiǎn)介其有關(guān)性質(zhì)，并用此小波對(duì)非均勻B 樣條曲線進(jìn)行分解與重構(gòu)。

設(shè)第l(l ≥0)層節(jié)點(diǎn)向量U(l)插入δl個(gè)節(jié)點(diǎn)得到U(l+1)，故有嵌套節(jié)點(diǎn)向量：U(0)?…?U(l)?U(l+1)?… ，其中。記定義在U(l)上的B樣條基函數(shù)向量為故第l 層B 樣條曲線其中 D(l)=為第l 層控制頂點(diǎn)向量。同層的小波基向量 記 為, 其 中(1 ≤j ≤δl)為雙正交非均勻B 樣條小波，nl+δl=nl+1。第l 層細(xì) 節(jié) 曲 線β(l)(u)=[Ψ(l)(u)]TW(l), 而為第l 層小波基系數(shù)向量。

由文獻(xiàn)[4]知存在重構(gòu)矩陣G(l)和H(l)使[[N(l)k (u)]T|[ψ(l)(u)]T]=成立，重構(gòu)矩陣的計(jì)算公式參見(jiàn)文獻(xiàn)[4]的 式（19）～（23）。P(l+1)(u)=P(l)(u)+β(l)(u)=(G(l)D(l)+H(l)W(l))可得到控制頂點(diǎn)重構(gòu)公式為：

若要將高分辨率曲線P(l+1)(u)分解為低分辨率曲線P(l)(u)與細(xì)節(jié)曲線β(l)(u)，則只需求的最小二乘解即可得到D(l)和W(l)。

2.3 基于外部能量約束的B 樣條曲線修改算法

文獻(xiàn)[2]提出一種基于外部能量約束的曲線形狀修改算法，基本思路如下：

給定點(diǎn)P0，確定B 樣條曲線上距其最近的點(diǎn)P(u′0)，外部能量約束項(xiàng)為E外能量=||P(u′0)-P0||2。記形變后的B樣條曲線為，矩陣A(u)=Nk(u)[Nk(u)]T；B(u)=DTA(u)-P0[Nk(u)]T，控制頂點(diǎn)改變量為ε=[ε0ε1… εn]T。則B 樣條曲線形變前后的外部能量變化量為：

故B 樣條曲線形變問(wèn)題就轉(zhuǎn)化成求控制頂點(diǎn)改變量ε 的無(wú)約束優(yōu)化問(wèn)題min ΔE外能量。

說(shuō)明通過(guò)實(shí)驗(yàn)（圖5）發(fā)現(xiàn)，直接使用能量法，B 樣條曲線除逼近給定點(diǎn)的部分形變外其余部分形變也較大，且在曲率較大的節(jié)點(diǎn)處較明顯，未實(shí)現(xiàn)局部修改的目的。為解決此問(wèn)題，本文引入2.2 節(jié)的雙正交非均勻B 樣條小波改進(jìn)此算法。

2.4 基于雙正交非均勻B樣條小波的曲線修改算法

算法基本思想：（1）先用雙正交小波對(duì)原曲線P(g)(u)分解得到低分辨率曲線P(g-1)(u) 和細(xì)節(jié)曲線β(g-1)(u) ；（2）再用外部能量約束法使P(g-1)(u) 局部逼近給定點(diǎn)；（3）重構(gòu)得到局部修改后的曲線P(g)(u)；（4）若P(g)(u)滿足給定的曲率容差則終止算法，反之則將P(g-1)(u)作為原曲線重復(fù)上述過(guò)程直至得到所需結(jié)果。算法具體步驟如下：

算法1

步驟1輸入形變目標(biāo)點(diǎn)P0，給定曲率容差η，原B 樣條曲線次數(shù)k ，節(jié)點(diǎn)向量U=U(g)，控制頂點(diǎn)向量D=D(g)，初始層次l=g 。

步驟2應(yīng)用基于增量法的誤差算法[5，7]得到原曲線P(u)=P(g)(u)上距P0最近的點(diǎn)P(u′0)，u′0∈[uk,un+1]。

步驟3執(zhí)行如下迭代算法：

while(l ≥0)

{（1）執(zhí)行2.3 節(jié)外部能量約束算法，得到控制頂點(diǎn)改變量ε(l)故

（2）執(zhí)行2.2 節(jié)重構(gòu)公式（2）得到形變后的控制頂點(diǎn)向量（注：若l=g 則跳過(guò)此步驟）；

（注：離u′0最近的兩個(gè)節(jié)點(diǎn)曲率改變量無(wú)需算）；

if(b(g)≥η)

{（1）執(zhí)行節(jié)點(diǎn)刪除規(guī)則Dpp 得到第l-1 層節(jié)點(diǎn)向量U(l-1)；

得到D(l-1)與W(l-1)，l=l-1，回到while循環(huán)；}

else

{輸出P(g)(u)=[Nk(u)]TD(g)，退出while循環(huán)；}

}

節(jié)點(diǎn)刪除規(guī)則Dpp：

（1）計(jì)算第l層形變前節(jié)點(diǎn)曲率的平均值 K(l)=

（2）刪除曲率大于Kˉ(l)的節(jié)點(diǎn)，得到U(l-1)。

步驟4輸出經(jīng)局部修改的B 樣條曲線

3 實(shí)驗(yàn)實(shí)例

本文以VC6.0 和MATLAB7.0 為實(shí)驗(yàn)平臺(tái)[8]，應(yīng)用算法1 給出實(shí)驗(yàn)實(shí)例，并與文獻(xiàn)[2]的能量法進(jìn)行效果對(duì)比。

實(shí)例輸入：目標(biāo)點(diǎn)P0，給定曲率容差η=0.08，B 樣條曲線次數(shù)k=3，節(jié)點(diǎn)向量U(4)，控制頂點(diǎn)向量D(4)，初始層次l=4。

（1）調(diào)用算法1 得到局部形變前后的B 樣條曲線，如圖1～圖4 所示。

（2）直接使用2.3 節(jié)的外部能量約束算法[2]得到形變前后的B 樣條曲線，如圖5 所示。

實(shí)驗(yàn)結(jié)果：圖3 和圖4 表明，算法1 使得B 樣條曲線形變前后，除逼近部分外形狀變化較??；圖5 表明直接采用能量法使B 樣條曲線整體形變較大，尤其在節(jié)點(diǎn)曲率較大處表現(xiàn)更明顯。實(shí)驗(yàn)結(jié)果說(shuō)明本文算法局部修改形狀的效果較好。

圖1 原B 樣條曲線與目標(biāo)點(diǎn)

圖2 低頻形變前后的B 樣條曲線

圖3 局部形變后的B 樣條曲線

圖4 局部形變前后的B 樣條曲線

圖5 能量法得到形變前后的曲線

4 結(jié)論

將雙正交非均勻B 樣條小波結(jié)合能量約束法，給出了一種B 樣條曲線局部修改算法。實(shí)驗(yàn)結(jié)果表明，本文算法僅使曲線局部發(fā)生形變，與文獻(xiàn)[2]的能量約束法相比，具有一定的保形效果。該方法仍有待改進(jìn)之處，如因需多次分解重構(gòu)曲線以達(dá)到效果，計(jì)算量較大，故提高效率是下一步需要研究的問(wèn)題。

[1] Wesselink W，Veltkamp R.Interactive design of constrained variational curves[J].Computer Aided Geometric Design，1995，12（5）：533-546.

[2] 朱翔，胡事民，孫家廣.基于外部能量約束的曲面形狀修改[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2000，12（9）：651-655.

[3] 殷金祥，沈利冰，陳關(guān)龍，等.小波多分辨率造型中基于能量法約束條件的處理[J].機(jī)械工程學(xué)報(bào)，2007，43（5）：14-18.

[4] Pan Rijing，Yao Zhiqiang.Biorthogonal nonuniform B-spline wavelets based on a discrete norm[J].Computer Aided Geometric Design，2009，26（4）：480-492.

[5] 丁小星，潘日晶，郭志恒.基于雙正交非均勻B 樣條小波的曲線逼近方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（6）：171-176.

[6] 施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B 樣條[M].北京：北京航空航天大學(xué)出版社，2001：212-219.

[7] 丁小星，潘日晶.應(yīng)用增量法生成非均勻B 樣條曲線曲面[J].福建師范大學(xué)學(xué)報(bào)，2010，26（2）：38-46.

[8] 蘇金明，王永利.MATLAB 實(shí)用教程[M].北京：電子工業(yè)出版社，2008：262-268.