非圓曲線參數化擬合算法的設計與實現*

許東偉，劉建群，林 淦

(廣東工業大學 機電工程學院，廣州 510006)

非圓曲線參數化擬合算法的設計與實現*

許東偉，劉建群，林 淦

(廣東工業大學 機電工程學院，廣州 510006)

通過分析AutoCAD導出的DXF文件中橢圓弧和樣條曲線的圖形信息，利用曲線參數化的思想設計了橢圓弧和樣條曲線的擬合算法。其中，針對橢圓曲線提出了一種基于迭代法的等誤差擬合算法，并給出一個優化的初值使得通過一次迭代即可達到精度要求，進一步減小運算開銷。針對樣條曲線推導了改進的De Boor-Cox算法來減低計算復雜度，利用參數曲線的特性給出樣條曲線的擬合誤差計算公式，并利用伸縮步長法快速計算出擬合節點，成功實現了樣條曲線的擬合。最后通過VC++編程實現了該算法，并驗證了算法的正確性。

DXF；非圓曲線；橢圓??；樣條曲線；擬合算法

0 引言

在現代的工業制造中，非圓曲線的應用越來越廣泛，傳統的只具備直線和圓弧等簡單插補功能的計算機數控系統(CNC)也逐漸升級，如目前一些高檔的數控系統(如SIEMENS、FANUC)用參數曲線插補取代了直線插補和圓弧插補[1]。利用“PC+運動控制卡”開發直接對工件圖形文件進行加工的數控系統，也是國內近年來推進制造業自動化加工的熱點。其中，利用AutoCAD 系統提供的DXF文件中的圖形信息直接進行數控加工過程的實時監控和自動生成數控代碼，是當前此類數控系統常用的加工方法[2]。但目前國內大多數的運動控制卡仍只具備直線和圓弧插補功能。為了現實對任意曲線的讀取與加工，需要設計非圓曲線的擬合算法。

常見的非圓曲線的擬合方法有直線擬合和圓弧擬合。其中由于直線擬合計算簡便，故目前大多數數控系統都采用小直線段來擬合非圓曲線[3]。非圓曲線直線擬合算法的關鍵是確定擬合節點。針對橢圓曲線，文獻[4]通過限定擬合誤差提出了一種簡單高效的等節點擬合算法，但是該算法由于分析誤差時采用簡單的不等式縮放，從而對曲率變化較大的橢圓曲線擬合效果較差。針對樣條曲線， 文獻[5]提出了用蒙特卡羅算法來檢驗擬合誤差，該算法計算簡單，但由于該算法是在擬合區間內隨機取點計算誤差，具有隨機性，需要進行多次檢驗才能判定擬合精度是否達到精度要求；文獻[6]提出了一種計算近似等誤差的節點來擬合樣條曲線，該算法能有效減少擬合段數，但計算節點需要用折線集來逼近，計算量較大。

由于利用曲線的參數化思想可以簡便地表示一條曲線，且不受曲線坐標系選取的影響，對于多值曲線也避免了多義性的問題[7]，因而十分適用于曲線擬合節點的計算。AutoCAD繪制的非圓曲線主要有橢圓弧和樣條曲線，本文主要利用曲線的參數化的思想設計并實現了這兩類曲線的擬合算法，并在前人的基礎上，針對橢圓曲線提出了一種基于迭代法的等誤差擬合算法；針對樣條曲線推導改進的De Boor-Cox算法來減低計算復雜度、利用參數曲線的特性給出樣條曲線的擬合誤差計算方法、并利用伸縮步長法快速給出擬合節點。通過對算法的實現表明，該算法能有效擬合橢圓弧和樣條曲線。

1 曲線的參數化思想

參數化表示在曲線的表示上有很多的優越性，主要表現在：①曲線的表示僅由參數u來控制，不依賴于坐標系的選取；②避免了非參數曲線方程可能會出現的斜率為無窮大的情況，且表示封閉或多值曲線時不會出現多義性；③參數表示的曲線進行平移、縮放、旋轉等幾何變換較為方便。

2 橢圓弧的擬合

平面上任意一條橢圓弧的參數方程可表示為[8]：

(1)

(2)

2.1 橢圓曲線的DXF文件信息

DXF文件格式是AutoCAD圖形文件與外部CAD/CAM系統進行圖形交換的格式，該格式是以帶標記數據的形式表示圖形文件中包含的信息[9]。其中，DXF文件的圖形實體都包含在實體段(ENTITIES)中。橢圓弧在DXF文件的實體段中是以“ELLIPSE”開始標記的，其具體的表段信息與圖形信息的對應關系如表1所示。

表1 橢圓表段圖形信息對應關系表

2.2 橢圓弧擬合算法的設計

圖1 橢圓曲線的直線擬合示意圖

ku-v-akcosα0+bsinα0=0

(3)

(4)

易知橢圓曲線上一點P(acosθi,bsinθi)的切線的斜率為

(5)

(6)

記b=a×i、α1-α0=Δθ，設擬合精度為δ，并令d=δ，代入式(6)，可解得

(7)

由式(7)可構造出迭代方程

(8)

結合式(2)橢圓的參數化表示，在第n段擬合直線段，通過對參數u設置Δun的步長，即可在誤差范圍內簡便地計算出直線擬合的各個節點，其中

(9)

2.3 橢圓弧擬合算法的實現

通過逐次增Δun的步長，使參數u由0累加至1，并逐次代入橢圓的參數方程(式(2))，即可得到擬合橢圓曲線的一系列節點坐標。用直線段兩兩連接這些節點，就可以得到擬合后的橢圓曲線。

3 樣條曲線的擬合

利用AutoCAD繪制的樣條曲線通常為非均勻有理B樣條曲線(NURBS)，且默認情況下，權值均為1，次數為3。由n+1個控制點所定義的一條k階(k-1次)NURBS曲線的參數化方程可定義為[11]

(10)

其中，wi為權值，與控制點Pi相對應；Ni,k(u)為樣條曲線的基函數，按De Boor - Cox遞推公式[12]可定義為

(11)

(12)

圖2 樣條曲線與控制點之間關系圖

3.1 樣條曲線的DXF文件信息

樣條曲線在DXF文件的實體段中是以“SPLINE”開始標記的，其部分表段信息與圖形信息的對應關系如表2所示。

表2 樣條曲線表段圖形信息對應關系表

其中，樣條曲線的維數加上1就可以得到樣條曲線的階數k?？刂泣c和權值是成對出現的，但對于組代碼“41”，只有當每個控制點的權值均不為1時，才出現，默認情況下均為缺省。樣條曲線圖形信息讀取的流程圖如圖3所示。

圖3 樣條曲線圖形信息讀取流程圖

3.2 樣條曲線擬合算法的設計

根據樣條曲線的定義，一條由n+1個控制點所定義的k階NURBS曲線可以表示成n+k+2段曲線?，F研究第l段(即tl≤u≤tl+1)曲線，由式(10)，有

(13)

將式(11)代進式(13)，整理得到

(14)

若記

(15)

(16)

則反復將式(11)代進式(14)進行迭代運算，整理得到

(17)

voidCSpline::DeBoorCox(doubleu,intl,CMyPoint&m_knotPoint)

{

intk=m_degree+1; //k是樣條曲線的階數

CMyPoint*Point=newCMyPoint[k]; //數組Point[k]用于迭代運算

doubled;

for(intj=0;j

{

Point[j].x=m_controlPoint[l+j].x*m_weight[l+j]; //控制點記錄在m_controlPoint[]中

Point[j].y=m_controlPoint[l+j].y*m_weight[l+j]; //權值記錄在m_weight[]中

}

for(intr=1;r

{

for(inti=k-1;i>=r;i--)

{

d=(u-m_t[i+l])/(m_t[i+k-r+l]-m_t[i+l]);

Point[i].x=d*Point[i].x+(1-d)*Point[i-1].x;

Point[i].y=d*Point[i].y+(1-d)*Point[i-1].y;

}

}

}

3.3 誤差分析與擬合算法的實現

(18)

(19)

采用伸縮步長法來求取擬合的節點，設擬合精度為δ、初始步長為Δ，則若每次計算出來的擬合誤差d>δ，就使步長Δ=Δ/2重新進行計算，直到滿足精度要求。具體的擬合流程如圖4所示。

圖4 樣條曲線擬合流程圖

4 非圓曲線擬合算法的實現

通過用VC++編程從DXF文件中將實體段的信息讀取出來，并根據以上非圓曲線的擬合方法，最終在VC++開發出來的數控軟件界面上實現。圖5是在AutoCAD中繪制橢圓弧和樣條曲線圖，圖6是根據AutoCAD導出的DXF文件圖形信息在數控軟件上擬合生成的曲線圖。

圖5 AutoCAD繪制的橢圓弧和樣條曲線

圖6 VC++繪制的擬合曲線圖

圖6中的擬合曲線的尺寸為660mm×590mm，其中橢圓曲線長軸為639.6mm、短軸為196.8mm，樣條曲線為6階(5次)、21個控制點、權值均為1的NURBS曲線。設置擬合精度為0.02mm，則擬合后的直線段數及最大擬合誤差如表3所示。

表3 曲線擬合直線段數及誤差表

5 結束語

本文針對DXF文件提供的非圓曲線信息，基于曲線參數化的思想，設計了橢圓弧和樣條曲線的擬合算法，并最終通過在VC++上編程實現，驗證了擬合算法

的有效性與正確性。同時，通過對橢圓弧和樣條曲線的擬合誤差的分析，確定了采用直線擬合時參數u的步長，保證了擬合曲線的精度要求。對與現有的數控系統，本算法成功實現了將非圓曲線轉化為小直線段，即可實現對非圓曲線的加工，具有很大的實用價值。

[1] 王允森，蓋榮麗，孫一蘭，等．基于牛頓迭代法的NURBS曲線插補算法 [J]．組合機床與自動化加工技術，2013(4)：13-17．

[2] 郭景峰，潘曉，吳雷．基于DXF文件的曲線擬合方法的設計與實現[J]．機床與液壓，2006(11)：210-213．

[3] 廖效果．數控技術[M]．武漢：湖北科學技術出版社，2010．

[4] 楊澤林，馬凱，呂靜．DXF文件的橢圓(弧)曲線擬合算法的設計與實現[J]．自動化儀表，2011，32(11)：13-16．

[5] 粟爛芝，王品．NURBS曲線自適應插值擬合算法[J]．組合機床與自動化加工技術，2011(1)：26-29．

[6] 譚正華，楊恢先，湯安平．分段三次NURBS曲線及其折線集逼近插值算法[J]．計算機應用與軟件，2008，25(8)：248-250.

[7] 李培培．曲線造型中關于擬合、參數化及形狀優化問題的研究[D]．濟南：山東大學，2012．

[8] Kunwoo Lee．Principles of CAD/CAM/CAE Systems [M]．Korea：Prentice Hall，1999．

[9] 施為，劉建群，呂振飛．石材橋式切割機數控系統軟件開發[J]．機床與液壓，2012，40(23)：104-107．

[10] 楊澤林，馬凱，呂靜．DXF文件的橢圓(弧)曲線擬合算法的設計與實現[J]．自動化儀表，2011，32(11)：13-16．

[11] Hongyao Shen，Xinhua Yao，Jianzhong Fu．Smooth non-uniform rational B-spline (NURBS) machining with kinematic limit for short linear segments[J]．Computer Integrated Manufacturing，2011，24(12)：1103-1116．

[12] Akemi Galvez，Andres Iglesias．Efficient particle swarm optimization approach for data fitting with free knot B-splines．Computer-Aided Design，2011(43)：1683-1692．

(編輯 趙蓉)

Design and Implementation of Non-circular Curve Parameterized Fitting Algorithm

XU Dong-wei， LIU Jian-qun， LIN Gan

(School of Electromechanical Engineering,Guangdong University of Technology,Guangzhou 510006, China)

Through analyzing the graphic information of elliptical arcs and spline curves in the DXF file, fitting algorithms of elliptical arcs and spline curves are designed with the idea of parametric design. Among them, an equal-error fitting algorithm based on iteration method is proposed for elliptical arcs. The proposed algorithm also gives an optimized initial value to decrease iteration times. By deriving the improved De Boor-Cox algorithm to reduce the computational complexity, and giving the fitting error calculation formula with characteristics of parametric curve, and calculating the fitting nodes based on the retractable step method, another fitting algorithm for spline curves is successfully implemented. The correctness of the algorithm is verified in VC++ programming.

DXF; non-circular curve; elliptical arc; spline curve; fitting algorithm

1001-2265(2014)04-0030-05

10.13462/j.cnki.mmtamt.2014.04.008

2013-08-25；

2013-09-18

廣東省數控一代項目(2012B011300046, 2012B011300070)；廣東省教育部產學研結合項目(2012B091100023);廣東省教育廳研究生示范基地項目(2013JDXM29)

許東偉(1989—)，男，廣東揭陽人，廣東工業大學碩士研究生，研究方向為數控技術與自動化研究，(E-mail)xodongwei@163.com。

TH122；TG65

A