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

蔡天赐，赵玉刚，王占军，刘新玉

(山东理工大学 机械工程学院，山东 淄博 255049)

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

蔡天赐，赵玉刚，王占军，刘新玉

(山东理工大学 机械工程学院，山东 淄博 255049)

基于NURBS曲线导矢的计算公式，首先给出了平面NURBS曲线精确等距线的生成算法, 这种算法稳定可靠、计算精度高，但它生成的等距线不再是有理多项式形式。根据等距曲线逼近的关键在于参数速度模的逼近,因此利用函数的连分式展开式实现其逼近，在此基础上导出平面NURBS曲线的等距线有理逼近算法。最后的实例验证了所提算法的可行性与有效性。

NURBS曲线；等距线；参数速度；连分式；有理逼近

0 引言

曲线曲面的等距计算是CAD/CAM系统中的一个重要几何运算，在NC加工、机构运动学、道路设计等领域中有着广泛的应用，因此受到众多学者的重视，研究文献丰富。

等距曲线的逼近算法主要有：控制顶点偏移法[1-2]、包络方法[3]、基于插值或拟合的方法[4-5]等。这些方法对等距曲线进行了各类有效的逼近, 但仍存在着不少的缺陷：目前大部分等距逼近曲线通常为多项式表示，这往往导致逼近曲线的次数相当高, 或需对原曲线进行多次离散, 因而需要大量的数据存储；目前很多方法所得的等距逼近曲线已不再是基曲线沿法矢方向平移一定距离的点的轨迹，当用户需改变等距距离时, 系统必须从头开始重新生成逼近曲线，这对于交互操作相当不利。

基于NURBS曲线导矢的计算公式，本文首先给出了平面NURBS曲线精确等距线的生成算法。在研究连分式理论的基础上，通过对NURBS曲线的参数速度模的有理逼近，完成了平面NURBS曲线的等距曲线的有理逼近。算法所得的等距逼近曲线将保持基曲线法矢的平移方向,当用户改变等距距离时, 也不需要重新运行逼近程序, 只需利用原逼近的信息就可快速生成新的等距逼近曲线。另外, 这种等距逼近程序只需运行一次即够, 因而计算量和存储量大为减少。最后的应用实例验证了所提算法的合理性和有效性。

1 基于导矢的NURBS曲线精确等距线生成算法

1.1 NURBS曲线定义

一条k次NURBS曲线可以表示为一分段有理多项式函数：

(1)

其中，di(i=0,1,…,n)是控制点，ωi是权因子，每一个控制顶点di都附有一个权因子ωi，首末权因子ω0，ωn>0其余ωi>0。Ni,k(u)是定义在非周期且非均匀节点矢量U上的k次B样条基函数，它可由以下的Cox-deBoor递推公式求得：

(2)

(3)

其中：li=|di-di-1|(i=1,2,...,n)为控制多边形各边长。

1.2 NURBS曲线精确等距线生成算法

给定正则平面NURBS曲线：P(u)=(x(u),y(u))，其参数速度P′(u)及其模长σ(u)分别被定义为：

由此得到基曲线距离为d的等距曲线Pd(u)为：

(4)

其中N(u)是P(u)上对应参数u处的单位法矢量。

由(4)式可知要计算N(u)需要计算参数速度P′(u)，对1.1节中(1)式求导有：

(5)

计算P′(u)的关键是对k次B样条基函数求导，由1.1节中(2)式可得基函数导数的递推公式：

(6)

(7)

其中：

由(1)～(3)式和(4)～(6)式可生成任意次NURBS曲线与其精确等距曲线，结合(7)式，则可快速求出常用的三次NURBS曲线的精确等距线。

2 连分式的NURBS等距线有理逼近算法

由第1节中算法，可以计算出平面NURBS曲线的精确等距线，但是由等距曲线的计算表达式可见，在计算单位法矢量N(u)时，参数速度模σ(u)需要进行开方运算，因而σ(u)不再是用多项式表示，这导致NURBS曲线的等距线不再具有有理多项式形式。为了保持CAD/CAM造型系统中数据结构和几何算法的统一性，本节利用函数的连分式展开式对σ(u)进行逼近，进而导出了NURBS曲线的等距曲逼近算法。

2.1 函数的连分式展开

根据连分式理论中的逐次迭代算法可将一个给定的函数f，转变成如下形式的连分式：

(8)

若用Rn表示上述展开式的前n项截断，令Rn=Pn/Qn，由连分式的性质可以得到如下的递推关系:

(9)

(10)

(11)

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

由上面的论述可知，如何进行NURBS曲线的等距线有理逼近，转化为如何用有理形式来近似表示参数速度模σ(u)。

首先对(10)、(11)式取前n项截断得：

(12)

(13)

最后结合1.2节中(4)式即可导出与基曲线P(u)的等距曲线Pd(u)相对应的有理逼近曲线：

(14)

(15)

(16)

(17)

3 NURBS曲线等距线生成算法实例

基于C++ Builder可视化的开发环境，通过自主编程，对1.2节和2.2节中的算法进行了仿真验证。

图1 9个控制点NURBS曲线效果图

图1a所示为9个控制点按1.2节算法生成的三次NURBS曲线的精确等距线效果。图1b、1c所示分别为7个控制点按2.2节算法(14)式、10个控制点按按2.2节算法(15)式所得的等距逼近效果，截断次数取为5。其中，每个控制顶点对应的权因子为1。图1中1号曲线代表控制点构成的控制多边形，2号曲线代表三次NURBS基曲线，图1a中3号、4号曲线代表沿法线正、负方向得到的NURBS曲线的精确等距线。图1b、1c中3、4号曲线则代表沿法线正、负方向得到的NURBS曲线的等距逼近曲线。

图2a、2b所示为5个相同控制点按2.2节算法中(14)式、(15)式所得的等距逼近效果，截断次数取3，等距距离d=1。1号曲线代表控制点构成的控制多边形，2号曲线代表NURBS基曲线，3号实线代表NURBS曲线的等距逼近曲线，4号虚线代表NURBS曲线的精确等距线。通过改变截断次数，(14)式和(15)式两种方法所对应的等距逼近误差ε1(u)和ε2(u)则如表1所列。

图2 5个控制点生成的NURBS曲线效果图 表1 NURBS曲线的等距逼近误差

截断次数n357ε1(u)0.001726795.08066×10-51.50955×10-6ε2(u)0.001726765.07984×10-51.48395×10-6截断次数n810ε1(u)3.15877×10-79.10943×10-8ε2(u)2.93591×10-78.04439×10-8

4 结束语

本文首先给出了基于NURBS曲线导矢的NURBS曲线精确等距线的生成算法，这种算法精确、稳定、高效，基曲线的两条等距曲线能够同时给出，一气呵成。但其缺点是生成的NURBS曲线的等距线不再具有有理多项式形式。

基于NURBS曲线的参数速度模是导致等距线不再是有理多项式这一观察，在研究连分式理论的基础上，通过对参数速度模的有理逼近，完成了平面NURBS曲线的等距线的有理逼近。由最后的仿真实例可以看到，等距曲线逼近效果良好，算法所得的等距逼近曲线仍旧保持基曲线法矢的平移方向，和原等距曲线之间的误差很小，并且随着截断次数的增大，逼近误差不断减小。

[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] 朱心雄. 自由曲线曲面造型技术[M].北京:科学出版社, 1999.

[10] 陈国栋,成敏,王国瑾.基于参数速度逼近的等距曲线有理逼近[J].计算机学报.2002,25(9):1001-1007.

[11] 王仁宏,朱功勤. 有理函数逼近及其应用[M].北京:科学出版社，2004．

[12] 张伟红.平面Bezier曲线的等距曲线有理逼近[D].合肥: 合肥工业大学,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

国家自然科学基金项目(51375285)

蔡天赐(1988—)，男，山东临沂人，山东理工大学硕士研究生，研究方向为数控技术及机电一体化，(E-mail)caiti.anci@163.com；通讯作者：赵玉刚(1964—)，男，山东莱芜人，山东理工大学教授、博士生导师，博士，研究方向为数控技术、机电一体化与特种加工技术，(E-mail)zhanggy9289@126.com。

TH161;TG65

A