章虎冬

?

一種參數(shù)三次樣條曲線光順優(yōu)化算法

章虎冬

（西安郵電學(xué)院應(yīng)用數(shù)理系，陜西西安710121）

論文給出了一種基于修改因子和修改角度的平面參數(shù)三次樣條曲線的優(yōu)化光順?biāo)惴?，該算法通過求解一個(gè)帶有修改因子和修改角度的目標(biāo)函數(shù)得到光順后的型值點(diǎn)，插值光順后的型值點(diǎn)得到光順曲線。目的是使曲線的曲率變化均勻的同時(shí)，使光順后的曲線與原曲線的偏差盡量小，此算法簡單易行，計(jì)算量較小。

計(jì)算機(jī)應(yīng)用；自動(dòng)光順?biāo)惴ǎ恍薷囊蜃?；修改角度；參?shù)三次樣條曲線

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

1 參數(shù)三次樣條曲線及其求解

（2）

（3）

（5）

聯(lián)立式（3），式（4）與式（5），得到下面的方程組

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

2 ‘壞點(diǎn)’的判別

對(duì)曲線進(jìn)行光順，首先必須給出具體的光順準(zhǔn)則，目前在光順中經(jīng)常使用的光順準(zhǔn)則有：

光順準(zhǔn)則1（Farin等給出）：一條曲線是光順的，如果相應(yīng)的曲率曲線是連續(xù)的，有適當(dāng)?shù)姆?hào)（如果曲線的凹凸性已知），且盡可能地接近一個(gè)有著盡可能少的單調(diào)段的分段單調(diào)函數(shù)。

光順準(zhǔn)則2（蘇步青、劉鼎元等給出）：

（1）二階參數(shù)連續(xù)（連續(xù)）；

（2）沒有多余拐點(diǎn)；

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

光順準(zhǔn)則3（施法中等給出）：

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

（2）不存在奇點(diǎn)與多余拐點(diǎn)；

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

（4）應(yīng)變能較小。

光順準(zhǔn)則4（Hans Hagen等給出）：

以應(yīng)變能量為最小和擾動(dòng)為最小的線性組合作為光順準(zhǔn)則，即

光順準(zhǔn)則5（Sapidis N等給出）：

在相應(yīng)于z值最大的內(nèi)節(jié)點(diǎn)處曲線應(yīng)該被光順，其中，是曲率弧長的導(dǎo)數(shù)。

光順準(zhǔn)則6（kjellander給出）：

三階導(dǎo)數(shù)跳躍最大的地方曲線應(yīng)該被光順。

光順準(zhǔn)則7（poliakoff等給出）：

光順準(zhǔn)則8（Janet F Poliakoff等給出）：在最大的內(nèi)節(jié)點(diǎn)處曲線應(yīng)該被光順，其中

關(guān)于這些關(guān)順準(zhǔn)則都有自己適合的用途，有的適用于整體光順，有的適用于局部光順，作者這里采用計(jì)算量小且用于局部光順的光順準(zhǔn)則6來找出壞點(diǎn)。

3 算法原理

（1）Kjellander方法

（2）本文方法

Step 1 由光順準(zhǔn)則計(jì)算出需要光順的型值點(diǎn)。

Step 3 下面解一個(gè)帶約束的優(yōu)化問題

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

4 算 例

圖1是運(yùn)用Kjellander法對(duì)曲線進(jìn)行光順的實(shí)際算例，圖2是運(yùn)用本文的光順法對(duì)曲線進(jìn)行光順的實(shí)際算例，這里取，表示光順前型值點(diǎn)的橫坐標(biāo)序列，表示光順前型值點(diǎn)的縱坐標(biāo)序列，表示光順后型值點(diǎn)的橫坐標(biāo)序列，表示光順后型值點(diǎn)的縱坐標(biāo)序列，和是求解方程式（8）得到的值；由下面的曲率圖可以看出，不管是Kjellander法還是本文的方法，曲線的光順性都得到了改善。從對(duì)應(yīng)的曲線圖可以看出，本文的光順法得到的曲線與原曲線的偏差比Kjellander法得到的曲線與原曲線的偏差?。粡南旅娴那蕡D可以看出，本文的光順法得到的曲線的曲率圖比Kjellander法得到的曲線的曲率圖更加平滑，總之，與Kjellander法相比，本文的光順法具有更好的光順效果。

圖2 本文光順法光順前后的曲線和曲率圖 （藍(lán)的點(diǎn)畫線是光順前的曲線和曲率）

5 結(jié) 論

本文給出了參數(shù)三次樣條曲線的優(yōu)化光順?biāo)惴?，它是通過解決一個(gè)優(yōu)化問題得到修改因子和修改角度，從而得到光順后的曲線，數(shù)值實(shí)例表明，在光順后的曲線與原曲線的偏差盡量小的情況下，使得曲線得到較好的光順。

[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曲線的自動(dòng)光順?biāo)惴╗J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002, 14(3): 225-227.

[5] 滿家巨, 胡事民，雍俊海, 等. B-樣條曲線的節(jié)點(diǎn)去除與光順[J]. 軟件學(xué)報(bào), 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

陜西省教育廳基金資助項(xiàng)目（08JK435；09JK728）

章虎冬（1979-），男，內(nèi)蒙古呼和浩特人，講師，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)。