非圆曲线参数化拟合算法的设计与实现*

许东伟，刘建群，林 淦

(广东工业大学 机电工程学院，广州 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。控制点和权值是成对出现的，但对于组代码“41”，只有当每个控制点的权值均不为1时，才出现，默认情况下均为缺省。样条曲线图形信息读取的流程图如图3所示。

图3 样条曲线图形信息读取流程图

3.2 样条曲线拟合算法的设计

根据样条曲线的定义，一条由n+1个控制点所定义的k阶NURBS曲线可以表示成n+k+2段曲线。现研究第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