金佳培，趙偉華，曾 宇，陳小雕

(杭州電子科技大學計算機學院，浙江 杭州 310018)

G1約束下基于三次內點插值的曲線逼近方法

金佳培，趙偉華，曾 宇，陳小雕

(杭州電子科技大學計算機學院，浙江 杭州 310018)

討論了平面曲線的逼近問題，并提出了基于三次Bézier曲線插值的逼近算法.首先給出了插值三點三切向的三次Bézier曲線的計算公式，其本質上等價于一元三次方程的求解問題，并討論了相關插值曲線的存在性.該插值曲線具有高達6次的逼近階，可期望獲取更好的逼近效果.然后，已滿足誤差的部分保持不變，針對不滿足誤差的部分，事先估算參數(shù)區(qū)間的劃分段數(shù)，并計算每一小區(qū)間對應的逼近曲線.多段插值Bézier曲線自動具有G1連續(xù)性，可進一步合并成C2連續(xù)的三次B樣條曲線.該方法只需修改不滿足誤差的局部曲線段，具有修改的局部性.數(shù)值實例證明了該方法具有更好的逼近效果和計算效率.

等距；逼近；內點插值法；三次Bézier曲線

0 引 言

等距曲線即平行曲線在計算機輔助設計(CAD)/計算機輔助制造(CAM)等領域有著廣泛的應用[1].在實際的CAD/CAM系統(tǒng)中，往往需要使用NURBS曲線來逼近等距曲線，要求滿足給定的精度，其關鍵指標或難點在于盡可能好的逼近效果、盡可能高的效率、自交情況的處理.本文討論前兩種指標，使用合理的計算量，在給定段數(shù)限制下獲取盡可能高的逼近精度，或在給定精度限制下使用段數(shù)盡可能少的曲線，目前主要有3類方法.一是基于控制多邊形的方法[2-4]，在給定曲線的控制多邊形基礎上，為每一個控制點增加一定方向及等距距離的平移，或通過數(shù)值迭代的方法加以進一步改善.二是圓逼近方法[5-7]，應用單位圓弧U(s(u))來逼近對應的單位法向曲線N(u)，最終得到的逼近曲線為C(u)+rU(s(u))給出的2個端點及其的導數(shù)，計算插值的單位圓弧比較容易的，關鍵在于參數(shù)化函數(shù)s(u)的選擇，缺點是結果調整方面不夠靈活[8].三是插值方法[9-11].標準Hermite插值方法的關鍵是估算逼近曲線端點處的導矢量.在空間曲線的情況下，文獻[9]應用插值給定曲線的內點改進了插值效果.文獻[10-11]采用三次Hermite曲線來逼近等距曲線.Josef H.等[10]提出了用最小二乘法來求解逼近問題，但是求解效果不如預期理想.當偏移曲線變得接近平坦時，文獻[11]的方法變得很不穩(wěn)定.端點處具有相同導數(shù)和曲率的兩條曲線，內部形狀也可以有很大的差別.因此，基于端點信息的方法獲取的逼近曲線只有一種結果，很多情況下，獲取的逼近效果很不穩(wěn)定，甚至很差.本文以等距曲線為例，討論基于三次Bézier曲線插值的曲線逼近方法.

1 帶G1約束的內點插值法

1.1 三次Bézier曲線的插值問題

P0=Q0，P3=Q1，P1=Q0+αT0，P2=Q1-βT1

(1)

緊接著是如何確定α和β的值.內點插值法及其逼近效果如圖1所示.圖1(a)中，兩條端點重合但不同形狀的曲線，在端點處具有相同的導數(shù)和曲率；圖1(b)中，當要求逼近曲線和原始曲線相切于原始曲線的某個內點時，在Hausdorff距離的度量下，逼近曲線也可以非常地接近原始曲線.基于這個觀察，給定一個內點，本文推導出一個非線性方程組，并最后轉化為一個單變量三次方程，通過該方程的求解，確定式(1)中α和β的值，從而確定三次Bézier插值曲線的控制點.

圖1 內點插值法及其逼近效果示意圖

1.2 公式推導

(2)

式(2)中的前2個方程是關于α和β的線性方程，求解可得

(3)

將式(3)代入式(2)中的第3個方程中，化簡后得到一個關于未知數(shù)t*的三次方程

H(t*)=h3t*3+h2t*2+h1t*+h0=0.

(4)

若式(4)中H(t*)在[0，1]內有多個根，則選取最接近(u*-a)/(b-a)的根.將t*的值代入式(3)，得到α和β的值.從而由式(1)得到最終的插值曲線.

1.3 插值曲線的存在性討論

若Y″(a)X′(a)-Y′(a)X″(a)≠0，

sm=s0+X″(a)(u*-a)+X?(a)(u*-a)2/2+O(h3)，
s1=s0+X″(a)(b-a)+X?(a)(b-a)2/2+O(h3)，
tm=t0+Y″(a)(u*-a)+Y?(a)(u*-a)2/2+O(h3)，
t1=t0+Y″(a)(b-a)+Y?(a)(b-a)2/2+O(h3)，
pm=p0+X′(a)(u*-a)+X″(a)(u*-a)2/2+O(h3)，
p1=p0+X′(a)(b-a)+X″(a)(b-a)2/2+O(h3)，
qm=q0+Y′(a)(u*-a)+Y″(a)(u*-a)2/2+O(h3)，
q1=q0+Y′(a)(b-a)+Y″(a)(b-a)2/2+O(h3).

(5)

當參數(shù)區(qū)間的長度h=b-a足夠小時，使得上述的泰勒展開式(5)成立，則有如下定理.

定理當參數(shù)區(qū)間長度h足夠小使得式(5)成立時，式(4)中的H(t*)在區(qū)間(0，1)內至少有一實根.

證明首先將式(5)分別代入H(0)和H(1)得H(0)=-0.0625(Y″(a)X′(a)-Y′(a)X″(a))2h3+O(h4),H(1)=0.0625(Y″(a)X′(a)-Y′(a)X″(a))2h3+O(h4).當Y″(a)X′(a)-Y′(a)X″(a)≠0時，有H(0)<0且H(1)>0.由中間值定理知，存在t*∈(0，1)使得H(t*)=0.證畢.

1.4 內點參數(shù)u*的啟發(fā)式設置方法

圖2 選擇不同的u*及其相應的逼近曲線

另外，本文提出了一個啟發(fā)式的方法來確定u*的值，不同的u*及其相應的逼近曲線如圖2所示，給定的曲線是沒有拐點的.圖2分別繪制了給定曲線，以及對應u*等于0.3，0.5和0.7時的逼近曲線；相應的等距曲線與逼近曲線之間的Hausdorff距離分別為0.120 6，0.031 1和0.021 2，其中u*=0.7對應的曲線具有最佳的逼近效果，而矩形框內的逼近效果不佳.這個例子中，給定曲線的曲率在參數(shù)um=0.68時達到最大，非常接近0.70.在本節(jié)的啟發(fā)式方法中，如果給定曲線的曲率是單調的，那么參數(shù)u*可以簡單設置為(a+b)/2；否則，u*的值可以設置為um，即全局或局部最大曲率發(fā)生處對應的參數(shù).然后，根據(jù)式(3)可得到α和β的值，以及相應的插值曲線.

1.5 誤差的逼近階分析

φ(a)=a，φ(u*)=u*，φ(b)=b，φ′(a)=λ1，φ′(u*)=λ2，φ′(b)=λ3.

1.6 生成C2-連續(xù)逼近B樣條曲線

首先是產生G1連續(xù)逼近三次Bézier曲線線段.若一條三次Bézier插值曲線已經(jīng)滿足給定的逼近誤差，則該曲線已經(jīng)是C2-連續(xù)，直接輸出該曲線.否則，依據(jù)1.5節(jié)的方法估算劃分參數(shù)子區(qū)間，將等距曲線細分為若干個小區(qū)間段，對應小區(qū)間內已經(jīng)滿足誤差的曲線段不必重新計算，未滿足誤差的小區(qū)間局部加細直到滿足誤差即可.然后采用文獻[6]中的方法，將兩條G1連續(xù)的三次Bézier曲線合并成一條C2-連續(xù)的三次B樣條曲線.最后，可得到C2-連續(xù)的逼近B樣條曲線.

2 實例比較與討論

本節(jié)演示一些例子說明內點插值方法，并與已有的方法進行比較.一般來說，文獻[2]和文獻[3]中基于控制多邊形的方法在已有的方法中效率是最快的.插值方法是計算時間與對應逼近效果之間的一個折衷.文獻[7]、文獻[11]中的插值方法速度快，但相應的逼近效果可能一般，甚至存在算法不穩(wěn)定的問題.文獻[7]中的標準的三次Hermite插值方法通過端點處曲率的插值在不同的參數(shù)化方法下，可以產生相同的逼近曲線，但它對曲率比較敏感.通過選擇合適的u*值，內點插值方法可以產生一個更好的效果，平均計算時間在幾毫秒到幾十毫秒之間.

例1圖3顯示了有4個控制點的凸三次Bézier曲線的實例.圖3(a)對應的偏移半徑為r=0.5，其中實心曲線來自于新方法，選定內點的參數(shù)對應為給定曲線最大曲率發(fā)生處的參數(shù)，對應由新方法產生的逼近曲線是一個三次Bézier曲線，與等距曲線幾乎是一致的.其它不同線型虛線表示的曲線分別是由文獻[2]方法、文獻[3]方法、文獻[4]方法、文獻[10]方法和文獻[11]方法所得到的.圖3(b)表示等距半徑為0.2，0.4，0.6，0.8，1.0，1.2時對應的逼近曲線.

圖3 一個凸三次Bézier曲線實例

方法dhtc/ms文獻[2]0.1094.499文獻[3]0.2283.270文獻[4]1.00780.430文獻[10]0.150803.000文獻[11]0.2921.344本文0.02039.890

相應的等距曲線與逼近曲線間的Hausdorff距離以及平均計算時間如表1所示.本例中，新方法的逼近效果是最好的，文獻[2]方法次之.文獻[10]的最小二乘法所需的計算時間是所有列出的方法中最多的，文獻[3]方法和本文方法的計算時間次之，文獻[2]、文獻[4]和文獻[11]方法的計算時間相對更少.

圖4 非多項式曲線實例

例3圖5顯示了更多的例子，將文獻[7]、文獻[11]中的標準三次Hermite插值方法和本文方法作比較.從圖中可以明顯看出本文方法得到的曲線具有最小的逼近誤差.本例表明，與標準的三次Hermite插值方法相比，本文方法可以提高相應的逼近效果.

圖5 文獻[7]、文獻[11]中Hermite插值方法和本文方法的比較

3 結束語

本文提出的內點插值方法本身計算相對簡單，且具有計算的局部修改性，即當曲線局部編輯后，僅僅需要局部修改區(qū)域的計算.與全局計算方法相比，具有很高的計算效率，可以方便曲線的編輯.本文方法不需要控制多邊形的信息，可應用于包括非多項式或任意形式表示的光滑曲線.本文方法理論上可達6次逼近階，實例也表明了它有更好的逼近效果.未來工作仍有很大的發(fā)展空間.首先，當給定曲線形狀比較復雜時，如何預先進行分段，使得每一小段曲線，本文的內點插值法得到的曲線可以滿足給定的誤差.其次，內點參數(shù)u*的最優(yōu)化問題仍然未解決.再次，等距曲線本身的自交處理，即裁剪掉自相交的部分，也是未來可能的研究方向.最后，能否略過Bézier曲線局部逼近的步驟，直接使用B樣條曲線來表示最終的逼近曲線，也是個值得討論的問題.

[1] HU Q. Constrained polynomial approximation of quadric surfaces[J]. Applied Mathematics & Computation, 2014,248(248):354-362.

[2] TILLER W, HANSON E. Offsets of Two-Dimensional Profiles[J]. Computer Graphics & Applications IEEE, 1984,4(9):36-46.

[3] COBB E S. Design of sculptured surfaces using the B-spline representation[M]. Salt Lake City: University of Utah, 1984:33-52.

[4] COQUILLART S. Computing offsets of B-spline curves[J]. Computer-Aided Design, 1987,19(6):305-309.

[5] KHAN M, CHEN Z. Approximation of planar offset curves with globally bounded error for B- spline NC tool paths[J]. International Journal of Production Research, 2012,50(23):1-15.

[6] KIM Y J, LEE J, KIM M S, et al. Efficient offset trimming for planar rational curves using biarc trees[J]. Computer Aided Geometric Design, 2012,29(7):555-564.

[7] FAROUKI R T, NEFF C A. Analytic properties of plane offset curves[J]. Computer Aided Geometric Design, 1990,7(7):83-99.

[8] BASTL B, JüTTLER B, KOSINKA J, et al. Volumes with piecewise quadratic medial surface transforms: Computation of boundaries and trimmed offsets[J]. Computer-Aided Design, 2010,42(6):571-579.

[9] H?LLIG K, KOCH J. Geometric Hermite interpolation[J]. Computer Aided Geometric Design, 1995,12(6):567-580.

[10] HOSCHEK J, WISSEL N. Optimal approximate conversion of spline curves and spline approximation of offset curves[J]. Computer-Aided Design, 1988,20(8):475-483.

[11] KLASS R. An offset spline approximation for plane cubic splines[J]. Computer-Aided Design, 1983,15(5):297-299.

[12] ZHAO H Y, WANG G J, MATHEMATICS D O, et al. Offset approximation based on reparameterizing the path of a moving point along the base circle[J].高校應用數(shù)學學報B輯(英文版),2009,24(4):431-442.

CubicInnerPointInterpolationBasedMethodforApproximatingOffsetCurvesunderG1Constraint

JIN Jiapei, ZHAO Weihua, ZENG Yu, CHEN Xiaodiao

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Offset curves have wide applications in computer-aided design(CAD) and robot path planning(RPP). Interpolation method needs no information of the control polygon and seems to be more flexible. This paper discusses approximating offset curves and proposes a method based on cubic Bézier inner point interpolation. It derives the formulae of cubic Bézier curves which interpolate three points and three of their directional tangent vectors, which is turned into a univariate cubic polynomial equation; it also discusses the existence of the interpolation curve. It can achieve approximation order of 6, which means to possibly obtain better approximation effect. The cubic interpolation Bézier curves areG1continuous, which can be merged into aC2continuous B-spline curve. The proposed method is a local one, which means that only the segments not satisfying the given tolerance need to be subdivided into several sub-segments, and the number of the sub-segments can be pre-estimated. Numerical examples show that the proposed method can achieve much better approximation effect than previous methods.

offset; approximation; inner point interpolation method; cubic Bézier curve

TP391.41

A

1001-9146(2017)05-0038-06

10.13954/j.cnki.hdu.2017.05.008

2016-11-16

國家自然科學基金資助項目(61672009)

金佳培(1991-)，女，浙江海寧人，碩士研究生，計算機圖形圖像.通信作者：陳小雕教授，E-mail:xiaodiao@hdu.edu.cn.