一種B 樣條曲線局部修改算法

丁小星

公安海警學院 基礎部，浙江 寧波315801

1 引言

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

2 算法介紹

2.1 B 樣條曲線定義

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

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

2.2 雙正交非均勻B 樣條小波簡介

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

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

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

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

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

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

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

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

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

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

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

算法1

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

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

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

while(l ≥0)

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

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

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

if(b(g)≥η)

{（1）執(zhí)行節(jié)點刪除規(guī)則Dpp 得到第l-1 層節(jié)點向量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é)點刪除規(guī)則Dpp：

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

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

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

3 實驗實例

本文以VC6.0 和MATLAB7.0 為實驗平臺[8]，應用算法1 給出實驗實例，并與文獻[2]的能量法進行效果對比。

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

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

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

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

圖1 原B 樣條曲線與目標點

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

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

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

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

4 結(jié)論

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

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

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

[3] 殷金祥，沈利冰，陳關龍，等.小波多分辨率造型中基于能量法約束條件的處理[J].機械工程學報，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].計算機工程與應用，2012，48（6）：171-176.

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

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

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