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

2013-02-22 08:12:04丁小星

計算機工程與應用 2013年7期

丁小星

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

1 引言

當前在CAD、CAM 等領域，因B 樣條曲線具有局部修改性等良好的性質而被廣泛應用于表達各種復雜的幾何形體。傳統的能量約束法能較直觀、方便地修改與控制曲線曲面形狀，對此已有不少文獻[1-2]進行了研究。文獻[1]將能量優化法結合幾何約束條件，利用求解能量最小曲線的方式來改變曲線的形狀；文獻[2]提供了一種基于外部能量約束的曲面形狀修改法，將曲面形狀修改所需的約束條件轉化為外部能量約束項，通過求解一個使曲面能量變化量最小的無約束優化問題，得到變形后的曲面，其實質是一種逼近約束條件的過程。小波技術能將B 樣條曲線曲面分解成不同分辨率的主體與細節，便于對其形狀實現靈活的細節編輯和整體保形控制，已在幾何造型許多領域得到應用[3-5]。文獻[3]針對小波多分辨率造型中的約束問題，結合能量法實現小波編輯的約束處理。然而目前對小波的應用主要集中在均勻或準均勻B樣條小波上，有一定的局限性。文獻[4]介紹了一種雙正交非均勻B 樣條小波，避免了求Gram 矩陣以及大量的積分運算，并具有良好的逼近性。本文將文獻[2]的外部能量約束法與文獻[4]的雙正交非均勻B樣條小波相結合，提出一種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為基函數向量；為節點向量；Nj,k(u)(j=0,1,…,n) 為k 次規范B 樣條基函數，它由節點向量U 按下列遞推公式定義得到：

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

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

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

由文獻[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)與細節曲線β(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 樣條曲線形變問題就轉化成求控制頂點改變量ε 的無約束優化問題min ΔE外能量。

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

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

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

算法1

步驟1輸入形變目標點P0，給定曲率容差η，原B 樣條曲線次數k ，節點向量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執行如下迭代算法：

while(l ≥0)

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

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

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

if(b(g)≥η)

{（1）執行節點刪除規則Dpp 得到第l-1 層節點向量U(l-1)；

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

else