二次Ｂéｚｉｅｒ曲線的雙圓弧樣條插值二分算法
2006-12-31 00:00:00盧建彪雍俊海
計算機應用研究 2006年8期
（清華大學 軟件學院 計算機圖形學與輔助設計研究所， 北京 100084）
摘 要：在數控加工領域，通常需要用盡量少段數的圓弧樣條來對曲線進行擬合。采用二分查找算法，用 G1連續的雙圓弧樣條對二次Bézier曲線進行擬合。該算法在給定誤差范圍內所需的圓弧段數較少。最后給出了具體的實例說明。
關鍵詞： 數控加工； 二次Bézier曲線； 雙圓弧樣條； 二分算法
中圖法分類號： TP301.6文獻標識碼： A
文章編號： 1001 3695(2006)08 0166 02
Bisection Algorithms for Approximating QuadraticBézier Curves by G1 Biarc Splines
LU Jian biao， YONG Jun hai
(Institute of Computer Graphics CAD， School of Software，Tsinghua University， Beijing 100084， China)
Abstract: In CNC，it is often required to approximate Bézier curves by G1 arc splines with as few arc segments as possible. A bisection algorithm for approximating a quadratic Bézier curve by a G 1 Biarc spline is presented. The new method reduces the number of the segments in the resultant arc spline under the given error tolerance.Some numerical results are given to illustrate the efficiency of the algorithm.
Key words: CNC; Quadratic Bézier Curves; Biarc Splines; Bisection Algorithms
在數控加工領域，將二次Bézier曲線擬合為圓弧樣條是經常遇到的問題[1～5]，大多數情況下需要將曲線用直線段和圓弧樣條進行逼近，而后進行加工。使用G1圓弧樣條進行擬合有很多優點，如NC工具所走路徑方面，G1圓弧樣條可以顯著減少CNC機器改變停走轉換狀態（Stop and go Motion），改善加工物體表面的品質；另一方面，很多實際的機械部件強制要求G1連續，以保證結果曲面的光滑。
當前研究中，用圓弧樣條對曲線進行逼近，主要分為單圓弧樣條和雙圓弧樣條兩種方法。考慮到連接點處G1連續性的單圓弧樣條算法，與雙圓弧算法比較而言，其優點是可以減少所使用的圓弧段數。缺點是一旦初始頂點處的切線方向確定，整條圓弧樣條就完全唯一地確定下來，從而缺乏靈活性；此外由于除初始確定切線方向的頂點，其他頂點處的切線方向因此也確定下來，因而對多個頂點處有切線方向要求的情況，一般都不適合采用；而且單圓弧樣條穩定性不好，改動初始點或初始切向，整條曲線都要跟著變動；用單圓弧來插值閉曲線要經過特殊處理才能實現。而雙圓弧樣條方法則不存在這些缺點。給定兩個端點以及端點處對應的切線方向，可以用雙圓弧進行擬合。可用于擬合的雙圓弧不唯一，雙圓弧中兩段圓弧公切點的軌跡是一個圓[2，3]。要唯一確定這段雙圓弧，一般還需要附加一個約束條件。在以往研究中，人們給出了很多種約束條件。如選取使得沿雙圓弧曲率平方的積分值最小的樣條以保持曲率連續[6～8]；又如，D.J.Walton等人在文獻[1]中給出了一種用雙圓弧樣條逼近二次Bézier曲線的方法，以當前被擬合的二次Bézier曲線控制多邊形的內心作為單段雙圓弧內兩段圓弧的公切點，從而唯一地確定用于擬合當前曲線的單段雙圓弧。其算法首先計算當前雙圓弧與要擬合的二次Bézier曲線之間的誤差，如果滿足誤差要求，則完成當前擬合；否則在插值誤差最大處將該段二次Bézier曲線劃分后分別進行上述擬合過程，直至完成。此外，人們也提出了一些最優化單段雙圓弧擬合方法[2，5]。
本文中采用雙圓弧樣條進行插值，并使用文獻[1]中確定雙圓弧的方法。這種選取方式的優點主要包括：保持原曲線的凸凹性，這樣確定的單段雙圓弧位于其擬合的二次Bézier曲線的控制多邊形內部，并且算法相對簡單。另一方面，針對文獻[1]擬合過程中對原曲線的劃分方式給出新的算法，即采用二分查找算法，逐段確定用于擬合的雙圓弧樣條。從而使得結果所含圓弧數目更少。
1 單段雙圓弧的確定
本文中以當前被擬合的二次Bézier曲線控制多邊形的內心作為單段雙圓弧內的公切點，從而唯一地確定用于擬合當前曲線的單段雙圓弧。如圖1所示，B0，B1，B2為二次Bézier曲線 Q(t) 的三個控制頂點， I為△B0B1B2的內心，V，W點分別位于線段B0B1B2上，直線VW經過I點且與直線B0B2平行。由三角形內心的性質，可得‖B0V‖=‖VI‖，‖B2W‖=‖IW‖。其中，符號‖#8226;‖用來表示向量的長度。選取B0，V，I，W，B2為雙圓弧的控制頂點，即選取I為雙圓弧的公切點。插值誤差的計算請參見文獻[1] 。
2 二次Bézier曲線的雙圓弧樣條插值二分算法
在運用雙圓弧進行擬合的過程中，一個非常重要的問題就是在保證誤差限制以及其他要求的前提下，盡量減少所使用的圓弧段數。從而減少加工過程中刀具的重新定位，大大節約加工時間，提高生產率[1，2，4]。文獻[4]在文獻[5]的基礎上，采用二分算法，以更少圓弧段數完成對二次Bézier曲線的擬合。其主要思想是對給定曲線進行劃分，分別對每段曲線進行插值，使得每一段的插值誤差盡量接近于給定誤差限，能夠減少插值用的圓弧段數。受這種思想的啟發，本文在文獻[1]的基礎上，采用二分算法來完成對二次Bézier曲線的擬合，逐段確定用于擬合的雙圓弧樣條。對原曲線參數間隔重復進行二分查找以使得每一段的擬合誤差均小于并且很接近于給定誤差限ε，從而使用盡量少的圓弧段數完成插值。算法的具體描述如下：
算法：二次Bézier曲線的雙圓弧樣條插值二分算法。
輸入：二次Bézier曲線 Q(u)，u ∈[0，1]及給定誤差限ε。
輸出：在給定誤差限內插值的G1連續的雙圓弧樣條。
(1)令low=0，high=1。
(2)計算當前被擬合的二次Bézier曲線的起點 BB0， BB0=Q (low)。
(3)計算在誤差范圍ε內，是否可以一段雙圓弧完成擬合 BB0與 Q (1)為起訖點的原曲線。如果可以，則輸出本段雙圓弧，轉至（８）。
（４）令ｍｉｄ＝（ｌｏｗ＋ｈｉｇｈ）／２。
（５）計算當前被擬合的二次Ｂéｚｉｅｒ曲線的控制頂點 ＢＢ＜ｓｕｂ＞０＜／ｓｕｂ＞，ＢＢ＜ｓｕｂ＞＜／ｓｕｂ＞，ＢＢ＜ｓｕｂ＞２＜／ｓｕｂ＞。其中ＢＢ＜ｓｕｂ＞０＜／ｓｕｂ＞為（２）中求出的結果，ＢＢ＜ｓｕｂ＞２＜／ｓｕｂ＞＝Ｑ （ｍｉｄ）， ＢＢ＜ｓｕｂ＞１＜／ｓｕｂ＞可根據二次Ｂéｚｉｅｒ曲線的性質求得。
（６）計算當前插值誤差 ｅ 。
（７）ｉｆ（ ｅ ＞ε），則令ｈｉｇｈ＝ｍｉｄ，并轉至（４）。
ｅｌｓｅ ｉｆ（ ｅ＜ａ ＊ε），則令ｌｏｗ＝ｍｉｄ，并轉至（４）。
ｅｌｓｅ輸出本段雙圓弧，令ｈｉｇｈ＝１，并轉至（２）。
（８）算法結束。
步驟（７）中， ｅ＜ａ ＊ε，其中ａ為小于１且比較接近于１的實數（如０．９９９）。這樣也可避免由于二分法不能夠無限進行下去而導致的程序問題。這樣雖然不能保證擬合每段曲線的誤差都等于ε，但卻可根據實際需要控制插值誤差的范圍。
3 實驗結果
采用文獻[1]中的例子（圖2(a)～圖2(c)) 和文獻[2]中的例子（圖2(d))作為結果示例。
例1中二次Bézier曲線的控制頂點分別為（1，1），（1，2）和（3，2）（圖2(a))；例2中二次Bézier曲線的控制頂點分別為（1，1），（2，1）和（4.5，2.75）（圖2(b))；例3中二次Bézier曲線的控制頂點分別為（1，1），（5，1）和（1，2.75）（圖2(c))。結果對比如表1所示。結果顯示，針對這幾組業界常見的實例，本文方法比文獻[1]中算法所用圓弧段數更少（約為文獻[1]中結果的67.8%）。
文獻[2]中給出了一種最優化雙圓弧擬合方法，采用例4（圖2(d)）作為結果示例。其中二次Bézier曲線的控制頂點分別為（ 2，8），（0，0）和（2，8），誤差限ε=0.01，擬合結果[2]中包含12段圓弧。使用本文中所介紹的算法，擬合結果由八段圓弧（四段雙圓弧）構成。本文方法所得到的八段圓弧，相應數據如表2（其中，( x，y)為圓心坐標，r 為圓的半徑）所示。
4 結論
本文提出了一種用雙圓弧樣條擬合二次Bézier曲線的二分算法。實例顯示，與以往雙圓弧樣條擬合的結果進行比較，使用了更少的圓弧段數；此外還具有保持原曲線凸凹性，雙圓弧位于其擬合的二次Bézier曲線的控制多邊形內部等優點；其算法簡單、實用。
參考文獻：
[1]D J Walton， D S Meek. Approximation of Quadratic Bézier Curves by Arc Splines[J].Journal of Computational and Applied Mathematics，1994，54(1):107-120.
[2] 丁瑋，陳虎，邱輝，等.平面曲線的雙圓弧最佳逼近[J].組合機床與自動化加工技術，2002，346(12):32-34.
[3] Jun Hai Yong， et al. A Note on Approximation of Discrete Data by G1 Arc Splines[J].Computer Aided Design，1999，31(14):911-915.
[4] Jun Hai Yong， et al .Bisection Algorithms for Approximating Quadratic Bézier Curves by G1Arc Splines[J]. Computer Aided Design，2000，32(4):253-260.
[5] Hyungjun Park. Error bounded Biarc Approximation of Planar Curves[J].Computer Aided Design， 2004， 36(12):1241-1251.
[6] D N Moreton， et al . Application of a Biarc Technique in CNC Machining[J]. Computer Aided Engineering Journal， 1991，8(2):54-60.
[7] D S Meek， D J Walton. Approximation of Discrete Data by G1 Arc Splines[J]. Computer Aided Design， 1992，24(6):301-306.
[8] Y J Tseng， et al . Numerically Controlled Machining of Freeform Curves Using Biarc Approximation[J]. International Journal of Advanced Manufacturing Technology， 2001，17(11):783-790.
作者簡介：盧建彪(1980-)，男，河北任丘人， 碩士研究生，研究方向為計算機輔助幾何設計和計算機軟件；雍俊海(1973-)， 男， 福建莆田人，副教授，博士，研究方向為計算機輔助幾何設計、計算機圖形學及產品數據的標準化。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
