一種參數三次樣條曲線光順優化算法

章虎冬

?

一種參數三次樣條曲線光順優化算法

章虎冬

（西安郵電學院應用數理系，陜西西安710121）

論文給出了一種基于修改因子和修改角度的平面參數三次樣條曲線的優化光順算法，該算法通過求解一個帶有修改因子和修改角度的目標函數得到光順后的型值點，插值光順后的型值點得到光順曲線。目的是使曲線的曲率變化均勻的同時，使光順后的曲線與原曲線的偏差盡量小，此算法簡單易行，計算量較小。

計算機應用；自動光順算法；修改因子；修改角度；參數三次樣條曲線

計算機輔助幾何設計中的一項重要任務就是如何根據給定的數據點產生一條光順的曲線或曲面。但是，由于數字化過程中的誤差影響，一般得到的插值或擬合曲線（或曲面）不能令人滿意，這樣，對曲線或曲面進行光順，就顯得至關重要。就曲線而言，光順法可以分為優化法和選點修改法；其中Kjellander采用了Hermit插值來調整型值點；基本思路是：運用近似的作為參數三次樣條曲線的能量，然后插值“壞點”兩邊的點和切矢生成三次Hermit曲線，用“更好”的點來代替“壞點”，然后生成光順曲線；但是，這種光順法也有偶然失敗的時候，例如美國波音公司的李(Lee,1989)就給出了反例。Sapidis N，康寶生等采用了節點刪除和插入法；滿家巨等給出了基于擾動控制頂點的B樣條曲線光順法；它們都屬于選點修改法。曲線選點修改法的主要步驟：①找出“壞點”；② 對“壞點”進行修改和插值曲線；③ 反復循環以上兩步，直至插值出較滿意的曲線；其缺點是算法每次只能調整一個控制頂點，局部算法可適用于對一些簡單曲線進行光順，對數據量較大的復雜曲線運用局部算法光順往往需要多次重復對曲線進行調整，不但運算量大，且難以保證曲線的整體效果。本文給出了一種基于修改因子和角度的平面參數三次樣條曲線的光順算法，運用光順準則來找出需要光順的“壞點”，然后通過求解一個帶約束的優化問題求得調整后的點的位置，通過插值光順后的點得到光順曲線。此算法的目的是使曲線的曲率變化均勻的同時，使光順后的曲線與原曲線的偏差盡量小，此算法簡單易行，計算量較小。

1 參數三次樣條曲線及其求解

（2）

（3）

（5）

聯立式（3），式（4）與式（5），得到下面的方程組

由于最左邊的矩陣主對角占優，所以方程組有唯一解，求解式（6），把得到的代入式（2），可求出。

2 ‘壞點’的判別

對曲線進行光順，首先必須給出具體的光順準則，目前在光順中經常使用的光順準則有：

光順準則1（Farin等給出）：一條曲線是光順的，如果相應的曲率曲線是連續的，有適當的符號（如果曲線的凹凸性已知），且盡可能地接近一個有著盡可能少的單調段的分段單調函數。

光順準則2（蘇步青、劉鼎元等給出）：

（1）二階參數連續（連續）；

（2）沒有多余拐點；

（3）曲率變化比較均勻。

光順準則3（施法中等給出）：

（1）二階幾何連續（指位置、切線方向與曲率矢連續，記為）；

（2）不存在奇點與多余拐點；

（3）曲率變化比較均勻；

（4）應變能較小。

光順準則4（Hans Hagen等給出）：

以應變能量為最小和擾動為最小的線性組合作為光順準則，即

光順準則5（Sapidis N等給出）：

在相應于z值最大的內節點處曲線應該被光順，其中，是曲率弧長的導數。

光順準則6（kjellander給出）：

三階導數跳躍最大的地方曲線應該被光順。

光順準則7（poliakoff等給出）：

光順準則8（Janet F Poliakoff等給出）：在最大的內節點處曲線應該被光順，其中

關于這些關順準則都有自己適合的用途，有的適用于整體光順，有的適用于局部光順，作者這里采用計算量小且用于局部光順的光順準則6來找出壞點。

3 算法原理

（1）Kjellander方法

（2）本文方法

Step 1 由光順準則計算出需要光順的型值點。

Step 3 下面解一個帶約束的優化問題

Step 5 反復上面的過程，直到插值出較滿意的曲線。

4 算 例

圖1是運用Kjellander法對曲線進行光順的實際算例，圖2是運用本文的光順法對曲線進行光順的實際算例，這里取，表示光順前型值點的橫坐標序列，表示光順前型值點的縱坐標序列，表示光順后型值點的橫坐標序列，表示光順后型值點的縱坐標序列，和是求解方程式（8）得到的值；由下面的曲率圖可以看出，不管是Kjellander法還是本文的方法，曲線的光順性都得到了改善。從對應的曲線圖可以看出，本文的光順法得到的曲線與原曲線的偏差比Kjellander法得到的曲線與原曲線的偏差小；從下面的曲率圖可以看出，本文的光順法得到的曲線的曲率圖比Kjellander法得到的曲線的曲率圖更加平滑，總之，與Kjellander法相比，本文的光順法具有更好的光順效果。

圖2 本文光順法光順前后的曲線和曲率圖 （藍的點畫線是光順前的曲線和曲率）

5 結 論

本文給出了參數三次樣條曲線的優化光順算法，它是通過解決一個優化問題得到修改因子和修改角度，從而得到光順后的曲線，數值實例表明，在光順后的曲線與原曲線的偏差盡量小的情況下，使得曲線得到較好的光順。

[1] Kjellander J A P. Smoothing of cubic parametric splines [J]. CAD, 1983, 15(3): 175-179.

[2] Lee E T Y. Energy, fairness, and a counterexample [J]. CAD, 1989, 21(1): 37-40.

[3] Sapidis N, Farin G. Automatic fairing algorithm for B-spline curves [J]. CAD, 1989, 21(2): 121-129.

[4] 康寶生, 趙錄剛. 平面三次NURBS曲線的自動光順算法[J]. 計算機輔助設計與圖形學學報, 2002, 14(3): 225-227.

[5] 滿家巨, 胡事民，雍俊海, 等. B-樣條曲線的節點去除與光順[J]. 軟件學報, 2001, 12(1): 143-147.

An Optimal Fairing Algorithm for Parametric Cubic Spline Curves

ZHANG Hu-dong

( Depatment of Applied Mathematics and Physics, Xi’an Posts and Telecomunications Institute, Xi’an Shaanxi 710121, China )

An optimal fairing algorithm for planar parametric cubic spline curves is proposed based on revising gene and revising angle. Faired point can be obtained by resolving a objective function of containing modifying geneand revising angleand faired curves is obtained by interpolating the faired point. The purpose of this algorithm is to make the change of curvature of faired curves more gradual and its deviation from the initial curves smaller. It is shown that the algorithm is simply facile and needs a smaller calculation.

computer application; optimal fairing algorithm; revising gene; revising angle; parametric cubic spline curves

TP 391

A

1003-0158(2011)03-0041-04

2009-11-10

陜西省教育廳基金資助項目（08JK435；09JK728）

章虎冬（1979-），男，內蒙古呼和浩特人，講師，碩士研究生，主要研究方向為計算機輔助幾何設計。