蔡天賜，趙玉剛，王占軍，劉新玉

(山東理工大學(xué) 機(jī)械工程學(xué)院，山東 淄博 255049)

平面NURBS曲線的等距線有理逼近算法*

蔡天賜，趙玉剛，王占軍，劉新玉

(山東理工大學(xué) 機(jī)械工程學(xué)院，山東 淄博 255049)

基于NURBS曲線導(dǎo)矢的計(jì)算公式，首先給出了平面NURBS曲線精確等距線的生成算法, 這種算法穩(wěn)定可靠、計(jì)算精度高，但它生成的等距線不再是有理多項(xiàng)式形式。根據(jù)等距曲線逼近的關(guān)鍵在于參數(shù)速度模的逼近,因此利用函數(shù)的連分式展開(kāi)式實(shí)現(xiàn)其逼近，在此基礎(chǔ)上導(dǎo)出平面NURBS曲線的等距線有理逼近算法。最后的實(shí)例驗(yàn)證了所提算法的可行性與有效性。

NURBS曲線；等距線；參數(shù)速度；連分式；有理逼近

0 引言

曲線曲面的等距計(jì)算是CAD/CAM系統(tǒng)中的一個(gè)重要幾何運(yùn)算，在NC加工、機(jī)構(gòu)運(yùn)動(dòng)學(xué)、道路設(shè)計(jì)等領(lǐng)域中有著廣泛的應(yīng)用，因此受到眾多學(xué)者的重視，研究文獻(xiàn)豐富。

等距曲線的逼近算法主要有：控制頂點(diǎn)偏移法[1-2]、包絡(luò)方法[3]、基于插值或擬合的方法[4-5]等。這些方法對(duì)等距曲線進(jìn)行了各類有效的逼近, 但仍存在著不少的缺陷：目前大部分等距逼近曲線通常為多項(xiàng)式表示，這往往導(dǎo)致逼近曲線的次數(shù)相當(dāng)高, 或需對(duì)原曲線進(jìn)行多次離散, 因而需要大量的數(shù)據(jù)存儲(chǔ)；目前很多方法所得的等距逼近曲線已不再是基曲線沿法矢方向平移一定距離的點(diǎn)的軌跡，當(dāng)用戶需改變等距距離時(shí), 系統(tǒng)必須從頭開(kāi)始重新生成逼近曲線，這對(duì)于交互操作相當(dāng)不利。

基于NURBS曲線導(dǎo)矢的計(jì)算公式，本文首先給出了平面NURBS曲線精確等距線的生成算法。在研究連分式理論的基礎(chǔ)上，通過(guò)對(duì)NURBS曲線的參數(shù)速度模的有理逼近，完成了平面NURBS曲線的等距曲線的有理逼近。算法所得的等距逼近曲線將保持基曲線法矢的平移方向,當(dāng)用戶改變等距距離時(shí), 也不需要重新運(yùn)行逼近程序, 只需利用原逼近的信息就可快速生成新的等距逼近曲線。另外, 這種等距逼近程序只需運(yùn)行一次即夠, 因而計(jì)算量和存儲(chǔ)量大為減少。最后的應(yīng)用實(shí)例驗(yàn)證了所提算法的合理性和有效性。

1 基于導(dǎo)矢的NURBS曲線精確等距線生成算法

1.1 NURBS曲線定義

一條k次NURBS曲線可以表示為一分段有理多項(xiàng)式函數(shù)：

(1)

其中，di(i=0,1,…,n)是控制點(diǎn)，ωi是權(quán)因子，每一個(gè)控制頂點(diǎn)di都附有一個(gè)權(quán)因子ωi，首末權(quán)因子ω0，ωn>0其余ωi>0。Ni,k(u)是定義在非周期且非均勻節(jié)點(diǎn)矢量U上的k次B樣條基函數(shù)，它可由以下的Cox-deBoor遞推公式求得：

(2)

(3)

其中：li=|di-di-1|(i=1,2,...,n)為控制多邊形各邊長(zhǎng)。

1.2 NURBS曲線精確等距線生成算法

給定正則平面NURBS曲線：P(u)=(x(u),y(u))，其參數(shù)速度P′(u)及其模長(zhǎng)σ(u)分別被定義為：

由此得到基曲線距離為d的等距曲線Pd(u)為：

(4)

其中N(u)是P(u)上對(duì)應(yīng)參數(shù)u處的單位法矢量。

由(4)式可知要計(jì)算N(u)需要計(jì)算參數(shù)速度P′(u)，對(duì)1.1節(jié)中(1)式求導(dǎo)有：

(5)

計(jì)算P′(u)的關(guān)鍵是對(duì)k次B樣條基函數(shù)求導(dǎo)，由1.1節(jié)中(2)式可得基函數(shù)導(dǎo)數(shù)的遞推公式：

(6)

(7)

其中：

由(1)～(3)式和(4)～(6)式可生成任意次NURBS曲線與其精確等距曲線，結(jié)合(7)式，則可快速求出常用的三次NURBS曲線的精確等距線。

2 連分式的NURBS等距線有理逼近算法

由第1節(jié)中算法，可以計(jì)算出平面NURBS曲線的精確等距線，但是由等距曲線的計(jì)算表達(dá)式可見(jiàn)，在計(jì)算單位法矢量N(u)時(shí)，參數(shù)速度模σ(u)需要進(jìn)行開(kāi)方運(yùn)算，因而σ(u)不再是用多項(xiàng)式表示，這導(dǎo)致NURBS曲線的等距線不再具有有理多項(xiàng)式形式。為了保持CAD/CAM造型系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)和幾何算法的統(tǒng)一性，本節(jié)利用函數(shù)的連分式展開(kāi)式對(duì)σ(u)進(jìn)行逼近，進(jìn)而導(dǎo)出了NURBS曲線的等距曲逼近算法。

2.1 函數(shù)的連分式展開(kāi)

根據(jù)連分式理論中的逐次迭代算法可將一個(gè)給定的函數(shù)f，轉(zhuǎn)變成如下形式的連分式：

(8)

若用Rn表示上述展開(kāi)式的前n項(xiàng)截?cái)啵頡n=Pn/Qn，由連分式的性質(zhì)可以得到如下的遞推關(guān)系:

(9)

(10)

(11)

2.2 NURBS曲線的等距線有理逼近算法

由上面的論述可知，如何進(jìn)行NURBS曲線的等距線有理逼近，轉(zhuǎn)化為如何用有理形式來(lái)近似表示參數(shù)速度模σ(u)。

首先對(duì)(10)、(11)式取前n項(xiàng)截?cái)嗟茫?/p>

(12)

(13)

最后結(jié)合1.2節(jié)中(4)式即可導(dǎo)出與基曲線P(u)的等距曲線Pd(u)相對(duì)應(yīng)的有理逼近曲線：

(14)

(15)

(16)

(17)

3 NURBS曲線等距線生成算法實(shí)例

基于C++ Builder可視化的開(kāi)發(fā)環(huán)境，通過(guò)自主編程，對(duì)1.2節(jié)和2.2節(jié)中的算法進(jìn)行了仿真驗(yàn)證。

圖1 9個(gè)控制點(diǎn)NURBS曲線效果圖

圖1a所示為9個(gè)控制點(diǎn)按1.2節(jié)算法生成的三次NURBS曲線的精確等距線效果。圖1b、1c所示分別為7個(gè)控制點(diǎn)按2.2節(jié)算法(14)式、10個(gè)控制點(diǎn)按按2.2節(jié)算法(15)式所得的等距逼近效果，截?cái)啻螖?shù)取為5。其中，每個(gè)控制頂點(diǎn)對(duì)應(yīng)的權(quán)因子為1。圖1中1號(hào)曲線代表控制點(diǎn)構(gòu)成的控制多邊形，2號(hào)曲線代表三次NURBS基曲線，圖1a中3號(hào)、4號(hào)曲線代表沿法線正、負(fù)方向得到的NURBS曲線的精確等距線。圖1b、1c中3、4號(hào)曲線則代表沿法線正、負(fù)方向得到的NURBS曲線的等距逼近曲線。

圖2a、2b所示為5個(gè)相同控制點(diǎn)按2.2節(jié)算法中(14)式、(15)式所得的等距逼近效果，截?cái)啻螖?shù)取3，等距距離d=1。1號(hào)曲線代表控制點(diǎn)構(gòu)成的控制多邊形，2號(hào)曲線代表NURBS基曲線，3號(hào)實(shí)線代表NURBS曲線的等距逼近曲線，4號(hào)虛線代表NURBS曲線的精確等距線。通過(guò)改變截?cái)啻螖?shù)，(14)式和(15)式兩種方法所對(duì)應(yīng)的等距逼近誤差ε1(u)和ε2(u)則如表1所列。

圖2 5個(gè)控制點(diǎn)生成的NURBS曲線效果圖 表1 NURBS曲線的等距逼近誤差

截?cái)啻螖?shù)n357ε1(u)0.001726795.08066×10-51.50955×10-6ε2(u)0.001726765.07984×10-51.48395×10-6截?cái)啻螖?shù)n810ε1(u)3.15877×10-79.10943×10-8ε2(u)2.93591×10-78.04439×10-8

4 結(jié)束語(yǔ)

本文首先給出了基于NURBS曲線導(dǎo)矢的NURBS曲線精確等距線的生成算法，這種算法精確、穩(wěn)定、高效，基曲線的兩條等距曲線能夠同時(shí)給出，一氣呵成。但其缺點(diǎn)是生成的NURBS曲線的等距線不再具有有理多項(xiàng)式形式。

基于NURBS曲線的參數(shù)速度模是導(dǎo)致等距線不再是有理多項(xiàng)式這一觀察，在研究連分式理論的基礎(chǔ)上，通過(guò)對(duì)參數(shù)速度模的有理逼近，完成了平面NURBS曲線的等距線的有理逼近。由最后的仿真實(shí)例可以看到，等距曲線逼近效果良好，算法所得的等距逼近曲線仍舊保持基曲線法矢的平移方向，和原等距曲線之間的誤差很小，并且隨著截?cái)啻螖?shù)的增大，逼近誤差不斷減小。

[1] Cobb, E.S. Design of sculptured surfaces using the B-spline representation．Ph.D. Dissertation, University of utah. USA. Jun.1984．

[2] Tiller,W., Hanson, E.G., Offsets of two-dimensional profiles.IEEE Computer Graphics and Application, 1984,4(9):36-46.

[3] Lee,I.K., M.S., Elber,G... Planar curve offset based on circle approximation. Computer Aided Design , 1996, 28(8):617-630．

[4] Klass, R.An offset spline approximation for plane cubic splines. Computer Aided Design,1983,15(5) : 97-299.

[5] Piegl, L.A., Tiller,W. Computing offsets of NURBS curves and surfaces. Computer Aided Design, 1999,3l(2):147-156．

[6] Hoschek J. Spline approximation of offset curves. Computer Aided Geometric Design,1988, 5(1):34-40．

[7] De Boor C. On calculating with B-splines. Journal of Approximation Theory, 1972, 2: 50-62.

[8] Les Piegl, Wayne Tiller. The NURBS BOOK [M]. Second Edition. Beijing: Tsinghua University Press, 2010.

[9] 朱心雄. 自由曲線曲面造型技術(shù)[M].北京:科學(xué)出版社, 1999.

[10] 陳國(guó)棟,成敏,王國(guó)瑾.基于參數(shù)速度逼近的等距曲線有理逼近[J].計(jì)算機(jī)學(xué)報(bào).2002,25(9):1001-1007.

[11] 王仁宏,朱功勤. 有理函數(shù)逼近及其應(yīng)用[M].北京:科學(xué)出版社，2004．

[12] 張偉紅.平面Bezier曲線的等距曲線有理逼近[D].合肥: 合肥工業(yè)大學(xué),2006.

(編輯 趙蓉)

The Rational Approximation Algorithm of Planar NURBS Curve and Its Offset

CAI Tian-ci, ZHAO Yu-gang, WANG Zhan-jun, LIU Xin-yu

(School of Mechanical Engineering, Shandong University of Technology, Zibo Shandong 255049,China)

Based on the derivatives of NURBS curve, the generation algorithm of offset curve is proposed. This algorithm is stable, reliable and accurate, but the offset curve it generates is no longer a rational polynomial form. According to the crux of offset curve approximation lies in the approximation of parametric speed, the rational approximation method of the norm of parametric speed based on the function of continued fraction expansion is provided. On that basis, the rational approximation algorithm of offset curve is derived. The final examples verify the feasibility and effectiveness of the proposed algorithms.

NURBS；offset curve；parametric speed; continued fraction; rational approximation

1001-2265(2014)06-0035-03

10.13462/j.cnki.mmtamt.2014.06.010

2013-09-17；

2013-10-12

國(guó)家自然科學(xué)基金項(xiàng)目(51375285)

蔡天賜(1988—)，男，山東臨沂人，山東理工大學(xué)碩士研究生，研究方向?yàn)閿?shù)控技術(shù)及機(jī)電一體化，(E-mail)caiti.anci@163.com；通訊作者：趙玉剛(1964—)，男，山東萊蕪人，山東理工大學(xué)教授、博士生導(dǎo)師，博士，研究方向?yàn)閿?shù)控技術(shù)、機(jī)電一體化與特種加工技術(shù)，(E-mail)zhanggy9289@126.com。

TH161;TG65

A