136.参数曲线的快速生成算法毕业设计.doc

江 南 大 学毕 业 设 计 论 文论文题目：参数曲线的快速生成算法姓 名： 学 院：信息工程学院专 业：计算机科学与技术指导老师： 日 期：2003年6月摘 要本毕业设计主要研究参数曲线的直接快速生成，要直接生成参数曲线就需对参数方程x=f(t),y=g(t),(0t1)的参数t每次增加一个步长，然后计算该点的x和y坐标值并绘制该点。要逐点地生成参数曲线，就要求参数t每次增加的步长要使曲线前进的幅度不得超过一个象素长度，否则有可能跨过一个中间象素而产生断点。为了提高曲线生成算法的速度，本毕业设计针对如何选择最佳的步长进行比较讨论，以使曲线前进的幅度在不超过一个象素的前提下，选择尽量大的步长。为了进一步提高算法的速度，在前面讨论的最佳步长的基础上又采用了双步逐点曲线生成算法，即将上述得到的步长增加一倍，以使算法的循环次数减少一半。由于步长增加一倍，这样当曲线前进一步时，其幅度有时会大于一个象素的长度，这时我们通过插值的方法来确定跨过的那个中间象素。通过上述讨论的算法能够比较快速的逐点生成曲线，为了实现上述算法，本毕业设计使用Visual C+6.0为工具并以三次Bezier曲线、普通参数曲线x=f(t)=X3t3+X2t2+X1t+X0, y=g(t)=Y3t3+Y2t2+Y1t+Y0，以及导师所给的一个特殊的曲线方程为例编程实现上述算法。关键词：参数曲线，逐点，双步，Visual C+6. 0 作者： 二零零三年 六月Abstract This graduation project main reseach the direct born of the parameter curve x=f(t),y=g(t),0<= t <=1,quickly.To direct born of the parameter curve it need to increase the parameter t a step length each time,then caculate this points coordinates value of x and y and draw this point.For drawing the parameter curve by point to point it orde to the parameter ts step length of increased make the progress range of the curve can not large than the length of one pels, otherwise the curve may step over one middle pels and skip one point that it should be on the curve. For speeding up the arithmetic of the drawing of the curve, this graduation project have discussed the choice of the best step length, so as to choose the biggst step length on the premise that the progress range is not large than one ples. To speeding up the arithmetic more, before the base of discussion about the best step length just now,we take the arithmetic of double step form of the curve by point to point ,and it double the step length that it be caculated just now to lessen the time of the circulation in the arithmetic to the half.Because it have doubled the step length,the progrss rang may large than the length of one pels when the curve go ahead one step.Then we must take the method of difference to make sure the middle pels that be steped over.It can draw the curve quickly that used the arithmetic we have discussed.To achive the arithmetic,I have used the Visual C+6.0 and take example for the three time Bezier parameter curve ,a common parameter curvex=f(t)=X3t3+X2t2+X1t+X0, y=g(t)=Y3t3+Y2t2+Y1t+Y0, 0t1 and a curve that my teacher gived to me to complete the program. Keywords：curve，point to point，double step，Visual C+6. 0 Author: July 2003目 录摘 要.1第一章 与本毕业设计相关的Visual C+内容介绍1.1 Visual C+6.0简介41.2 与本毕业设计有关的Visual C+内容介绍.5第二章 计算机图形学中常用的算法2.1 常用直线的绘制算法62.2 常用的参数曲线的绘制算法.7第三章 参数曲线的快速生成算法及实现3.1 普通参数曲线生成算法的介绍.113.2 最佳的步长值.133.3 双步逐点曲线生成算法.143.4 以三次Bezier曲线为例编程实现该算法.163.5 普通参数曲线方程的编程实现.283.6 使用双步逐点曲线生成算法需要注意的一个问题.31第四章 导师所给的参数方程的研究4.1 通过在屏幕上鼠标点击若干点然后绘制曲线.324.2 通过在对话框中输入控制点的坐标绘制曲线.36第五章 结论38第六章 个人小结.39第七章 附录英文资料翻译.40参考文献.48第一章 与本毕业设计相关的Visual C+的内容介绍1.1 Visual C+简介 Visual C+6.0是美国Mcrosoft公司在多年使用过程中不断改进的基础上推出的，用于支持Win32、Windows95/98和Windows NT平台的应用程序、服务和控件开发的工具。随着计算机多媒体技术和图形图象技术的蓬勃发展，特别是Windows操作系统在微机中的大量使用，可视化技术得到了人们的广泛的重视，越来越多的计算机专业人员和非专业人员都开始研究并应用可视化技术。一般来说，可视化技术包含两个方面的含义。一是可视化编程，也就是软件开发阶段的可视化，可视化编程使得工作轻松愉快、饶有趣味，给软件开发人员以一种全新的感受。可视化技术的另一含义就是利用计算机图形学的方法和技术，对收集到的大量数据进行处理，并用图形图象的方式直观而具体的显示出来。要支持可视化编程，就需要有相应的可视化开发环境，而Visual C+6.0就是目前使用极为广泛的支持可视化编程的集成环境。像其他的可视化集成开发环境（如Visual Basic、Delphi、C+ Build）一样，VC6集程序的代码编辑、编译、连接、调试等于一体，给编程人员提供了一个完整而又方便的开发界面和许多有效的辅助开发工具。VC+6.0的AppWizard可以为很大一部分类型的程序提供框架代码，用户不需要书写代码，只需要按几个按钮就可以生成一个完整的可以运行的程序。和其他可视化集成开发环境比较，用VC6做一些普通常见的界面可能体现不出什么优势，甚至有时候还很麻烦，需要书写更多的代码，但用VC6做界面更加灵活，尤其当用户需要定制一些特别的界面时用VC6更加方便。因为VC6基于C+语言，又来自Windows操作系统，所以在众多的可视化集成开发环境中，VC6是Windows底层编程的最佳选择。Visual C+6. 0在它前一版本的基础上做了很大改进，提供了许多新的特点，如下所述：· 编译器较前一版得到了很大的改进，不但可以支持ANSI C+新标准，现在也可以支持布尔类型，并且对于摸板的支持也得到了相当的改善。· Visual C+6. 0开发环境Developer Studio是由Windows95/98或Windows NT环境下运行的一套集成工具所组成，The Developer Studio编辑器有了很大的改善，它具有允许编辑器为你自动完成通用语句编辑的特点。使用Developer Studio，不仅可以创建由Visual C+6. 0使用的源文件和其它文档，而且可以创建、查看和编辑与任何与ActiveX部件有关的项目和项目配置，可以使用工作区窗口来查看和访问项目中的各种元素。· 这个开发系统包括一些增加的MFC库的新功能。增加了用于Internet Explore和Windows98中编程的新的通用控件。· Visual C+6. 0提供了快速的集成数据苦访问，允许用户建立强有力的数据库应用程序，可以使用ODBC类和高性能的32位ODBC驱动程序来访问各种数据库管理系统，也可以使用DAO（数据访问对象）类通过编程语言来访问和操纵数据库中的沪剧并管理数据库、数据库对象与结构。· Visual C+6. 0对Internet提供了强有力的支持，Win32 Internet API使Internet成为应用程序的一部分并简化了对Internet服务（FTP、HTTP和Gopher）的访问。ActiveX控件可以用在Internet和桌面应用程序中，其文档可以显示在整个Web浏览器中，同时，可以使用ChttpServer，ChttpFilter，ChttpServerContext，ChttpFilterContext和ChttpStream类来创建动态连接库以便添加功能到Internet服务器和Web页中。· 一个增强型的在线帮助系统使得Visual C+6. 0变的容易学习，只须单击鼠标即可实现。若你在机器上安装了MSDN，再线帮助系统将自动使用最新的MSDN版本。1.2 与本毕业设计有关的Visual C+的内容介绍在本次毕业设计中，为了能够方便的显示生成的参数曲线，主要通过使用Visual C+6.0生成基于Doc/View结构的单文档应用程序来实现参数曲线的生成算法，并在程序运行后的视图窗口上显示该曲线。在基于Doc/View结构的应用程序中，Cview类的主要作用是用来管理视图包括处理用户（键盘或鼠标）输入和在视图窗口上显示文档的数据等；CDocument类负责管理程序的数据并提供程序数据的文件I/0功能以及存储Cview类所要观察和处理的信息。在生成参数曲线的实现程序中使用到了有关CView类的视图窗口响应鼠标输入和在视图窗口中画点的相关知识，以及CDocument类的有关视图窗口内容重绘的相关知识，并在程序中添加了对话框资源以能够实现在对话框中手动输入方程的系数来完成绘制不同的参数曲线。为了能够在屏幕上画点和改变鼠标形状，首先需要在程序中为视图类增加有关的数据成员。首先在View类的头文件中加入HCURSOR类型的变量m_hCross，数据变量m_hCros是鼠标句柄，然后在View类实现文件中的构造函数中通过语句m_hCross=AfxGetApp()->LoadStandCursor(IDC_CROSS)初始化该变量，该语句的作用是取得Windows标准鼠标形状句柄并赋给m_hCross，然后就可以通过ClassWizard添加鼠标动作的消息处理函数。例如，要为程序添加鼠标左键单击消息处理函数，首先在打开的ClassWizard对话框中的Class name组合框中选择View类，然后在Object Ids列表框选中第一行，并在Message列表框中选中WM_LBUTTONDOWN一行，最后单击Add Function按钮即可。类似的还可以为程序添加WM_RBUTTONDOWN（鼠标右键单击）消息处理函数。因为需要逐点地生成曲线，因此在程序中需要使用到MFC（Microsoft Fundation Class）中的CDC（设备上下文）类的成员函数SetPixel（）来实现在屏幕上画点，CDC类主要用于在指定设备上下文上（如窗口客户区、打印机）进行绘图、显示文本等操作。第二章 计算机图形学中常用的算法2.1 常用直线的算法 画直线的算法有很多，例如数值微分法，中点画线法，Bresenham化线算法等。在这里只介绍一个比较方便常用的中点画线法。为了讨论方便，本小节假定直线斜率在0、1之间。其他情况可参照下述讨论进行处理。如图所示，若直线在x方向增加一个单位，则在y方向上的增量只能在0、1之间。假设x坐标为xp的各象素点中，与直线最近者已确定，为(xp,yp)，用实心小圆表示。那么，下一个与直线最近的象素只能是正右方的P1(xp+1,yp)或右上方的P2(xp+1,yp+1)两者之一，用空心小圆表示。再以M 表示P1、P2的中点，即M=(xp+1,yp+0.5）。又设想Q是理想直线与垂直直线x=xp+1的交点。显然，若M在Q的下方，则P2离直线近，应取为下一个象素；否则应取P1。这就是中点画线法的基本原理。 P2QMP1P=（XP，YP）中点画线算法每步迭代涉及的象素和中点示意图下面来讨论上述算法的实现。假设直线的起点和终点分别是(x0,y0)，(x1,y1)。则直线的方程为 F(x,y) = ax + by + c=0其中，a = y0-y1，b = x1-x0，c = x0yi-x1y0。对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)>0；而对于直线下方的点F(x,y)<0。因此，欲判断前述Q在M的上方还是下方，只要把M代入F(x,y)，并判断它的符号。构成判别式 d=F(M)=F(xp+1,yp+0.5)=a(xp+1) + b(yp+0.5) + c当d<0时，M在直线下方（即在Q的下方），故应取右上方的P2作为下一个象素。而当d>0时，则应取正右方的P1。当d=0时，二者一样合适，可以随便取一个。我们约定取正右方的P1。对每一个象素计算判别式d，根据它的符号确定下一个象素。至此可以写出完整的算法。但是注意到d是xp和yp的线形函数，可采用增量计算，提高运算效率。在d0的情况下，取正右方象素P1，欲判断再下一个象素应取哪个，应计算 d1=F(xp+2，yp+0.5) =a(xp+2) + b(yp+0.5)+ c= d + a故d 的增量为a。而若d<0，则右上方的象素P2，欲判断再下一个象素，则要计算d2=F(xp+2，yp+1.5)=a(xp+2)+b(yp+1.5)+ c = d + a + b故在第二种情况，d 的增量为a+b。再看d的初值。显然，第一个象素应取左端点(x0,y0)，相应的判别式为 d0=F(x0+1,y0+0.5)=a(x0+1)+ b(y0+0.5) + c = ax0+by0+a+c+0.5b = F(x0，y0)+ a+0.5b但由于(x0,y0)在直线上，故F(x0,y0)=0。因此，d的初值为d0= a+0.5b。 由于使用的只是d 的符号，而且d的增量都是整数，只是其初值包含小数。因此我们可以使用2d代替d，来摆脱小数，写出仅包含整数的算法：MidPointLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color; int a,b,delta1,delta2,d,x,y; a= x0- y1; b=x1- x0; delta1=2*a; delta2=2*(a+b); x= x0; y=y0 ; drawpixel(x,y,color); while(x< x1) if(d<0) x+;y+;d+= delta2;elsex+;d+= delta1;drawpixel(x,y,color); 2.2 常用的参数曲线的绘制算法常用的参数曲线有许多，如Bezier，B样条，非均匀有理B样条、圆锥曲线等。本小节将以Bezier曲线为代表，讲解其绘制算法。Bezier曲线的公式 ：给定空间n+1个点的位置矢量Pi，Bezier曲线上各点坐标的插值公式是：C(t) =, 0t1Pi构成该曲线的特征多边形，是Bernstein基函数，也是曲线上各点位置矢量的调和函数。=ti(1-t)n-i=Cti(1-t)n-i i=0,1,2,n首先，讨论三次Bezie曲线的绘制由上述公式可以推出三次Bezier曲线形式：当n=3时,C(t)= = P0(1t)3 + 3P1t (1t)2 + 3P2 t2 (1t) + P3t3 0t1可以将其改写为如下的形式：C3(t) = ( CS P0+ Ct P1)S+Ct2 P2 )S+ Ct3P3其中，S=1-t，则可以通过如下程序绘制曲线：float hornbez(degree,coeff,t)/* Input:degree:曲线的次数coeff:保存曲线的系数t: 参数的值 Output: 该参数的坐标值*/int degree;float coeff;float t; int i,n_choose_i; float fact,t1,aux; t1=1.0-t; fac=1.0; n_choose_i=1; aux=coeff0*t1; /*开始循环计算坐标值*/ for(i=1i<degree;i+) fact = fact*t;n_choose_i= n_choose_i*(degree-i+1)/i;aux=(aux+fact* n_choose_i*coeffi*t1; aux=aux+fact*t*coeffdegree; return aux;下面来讨论n次Bezier曲线的绘制。在前面我们介绍了一个程序用于计算相应曲线上的诸点，但其只适用于三次Bezie曲线，既不通用而且计算量较大。用如下Cas-teljau算法产生曲线上的点列相对要简单许多。Cas-teljau算法：给定空间n+1个点Pi(i=0,1,2,n)及参数t，则有：(t)=(1-t)(t)+ t(t)r=1,2.n, i=0,1.n-r, 0t1其中(t)即为Pi, (t)是曲线上具有参数t的点。 当n=3时，用Cas-teljau算法递推出的(t)呈直角三角形，对应如下所示： 该三角形垂直边上的点P0，P1，P2， P3是曲线P(t)在0t1内的控制点，斜边上的点是P(t)在0t1/2内的控制点，水平直角边上的点是P(t)在1/2t1内的控制点。这种用分割Bezier曲线控制多边形的方法为离散化的曲线提供了方便。用Cas-teljau算法绘制Bezier曲线的程序如下：void bez_to_points(degree,npoints,coeff,points)/*Input :degree:曲线的次数npoint:控制点的数目coeff:控制点的坐标Output: 曲线上点的坐标*/int degree,npointes; float coeff,points; float t,delt; int i; float decas(); delt=1.0/(float)npoints; /*步长*/ t=0.0; for(i=0;i<=npoints;i+) pointsi=decas(degree,coeff,t);t=t+delt; float decas(degree,coeff,t)float coeff;float t;int degree; int r,i; float t1; float coeffa10; t1=1.0-t; for(i=1;i<=degree;i+) coeffai=coeffi; /*计算(t)地值 for(r=1;r<=degree;r+) for(i=1;r<=degree-r;i+) coeffai=t1*coeffai+t*coeffat+1; return(coeffa0); 第三章 参数曲线的快速生成算法及实现3.1 普通参数曲线生成算法的介绍本毕业设计所研究的参数曲线生成算法要具备直接、逐点、快速的特点。要直接生成参数曲线就需要对曲线的参数每次增加一个步长，然后计算该点的坐标值x和y并绘制该点。要逐点地生成参数曲线，就要求参数每次增加的步长要使曲线前进的幅度不得超过一个象素的长度，否则有可能跨过一个中间象素而产生断点。要快速生成曲线则要求在不产生断点的情况下尽量减少画点次数以及不重复画一个象素点来达到加快曲线的生成速度。根据参考文献可以得到一个满足上述要求的逐点生成参数曲线的整数算法。设曲线的参数方程为：首先讨论第一个方程x=f( t ),首先把曲线分成n 段（限定t取i/n，其中0in。）根据拉格朗日中值定理：f(x+x)f( x )=f()(x)，当n 满足n时，可以得到如下公式：=1 （3.1）根据公式3.1，可以使得算法中每次循环，即每步前进不超过1个象素，从而保证了曲线的连续性。为了只使用整数运算，可将方程x=f(t)乘一正整数N，使其转换成整数方程： Nxi =( i ) + zi ， 其中( i )=N·f(),它和xi (x坐标的整数位置)及其余数zi ()均为整数。各个量的含义如下图所示。xi表示与计算出的值f()最近的象素点的x坐标。余数zi 表示xif(i/n)xixi f(i/n)(a) (b) 图1-1 xi与 f()两者的关系 与f()的差距（当然为了整数化，也乘了一个N值）。若是图（a）的情况，则zi为负值，即取曲线左边的象素点；若是图（b）的情况，则 zi为正值，即取曲线右边的象素点。算法逐点计算曲线上的象素。设当前象素点的x坐标是xi，则下一点的x坐标xi+1应该满足 N xi+1 = (i+1) + zi+1，其中 (i+1)=( i )+( i )=Nxizi +( i )根据3.1式有：=NN，而，所以N。因此，xi+1的可能取值为xi1，xi 或xi +1。这样就得到了xi+1和zi+1的计算公式：xi+1 zi+1这样，就得到了x坐标和余数z的递推计算公式。y坐标的计算公式可以根据以上的讨论同理得到。步长大小（即1/n）的确定是非常重要的。确定步长的标准是：在使曲线前进的幅度不超过一个象素长度的前提下，选择尽量大的步长（即小的n值），以便算法提高速度。如果步长选得太小，则在绘制曲线时造成取点过密，因而重复绘制了很多象素点，浪费了大量的计算也降低了算法的速度。在参考文献提出的算法中，取n的值为： n = max (nx，ny)其中nx和ny分别对于x坐标和y坐标选择的n的值，为nx=· m · ny=· m ·其中m为曲线的次数。而该参考文献又对nx和ny值进行了进一步的优化，减小了n 的值，取： nx= m · ny= m ·其中X和Y是曲线第i个控制点的坐标。可以证明这样选择的n值满足上述的条件n。3.2 最佳的步长值根据参考文献中对上述算法进行编程和分析运行结果，发现该算法在绘制曲线时每次循环使曲线前进的幅度的最大值往往不能接近于1（多数在0.6至0.8之间）。这说明在上一小节介绍的算法中的n的取值并没有达到最佳值。从理论上分析，我们的目标是要找到满足条件n的最小的n值，即寻找的最小上界。上述的m ·虽然是的一个上界，但并不是其最小上界。下面将讨论如何求出的最小上界以及最佳的n值。的最小上界显然应该出现在f(t)的极值点处或曲线的端点处，即当参数t = 0或 t =1处，因此应该以在曲线的两端点处和其在两端点之间的极值点处的函数值中的最大者作为其最小上界。由于我们采用了求函数的最大极值作为其上界，因此它是最小上界，因为该上界就在曲线上，如果它再小一点则必有曲线上的一点大于它。下面我们将以三次Bezier曲线为例描述最佳n的计算过程。对于三次Bezier曲线：f( t ) = X0(1t)3 + 3X1t (1t)2 + 3X2 t2 (1t) + X3t3对其求导,得 f ( t )=3(X1X0)(1t)2 + 2(X2 X1)(1t)t + (X3X2) t2=3X3X22(X2X1)+X1X0 t2+2(X22X1+X0) t + X1X0，要求f(t)的极值点就要将其对t 再次求导并另其导函数为0，得：6X33(X2X1)X0 t + X22X1 + X0= 0 设V= X22X1 + X0，W= X33(X2X1)X0；由上式得，当t=时，f( t )取到极值3X1X0。显然，在端点处( t = 0 和t = 1)的值分别为3和3。所以，nx的取值为当0，1时 nx = 3）当0，1时，nx = 3）同理，根据ny来求得ny 的值。最后取 n = max(nx,ny)，从而得到了最佳的n值。 由上面的讨论可知，n值决定了算法的循环次数，n值愈小，算法的速度愈快。在上面计算得到的n值已经比较理想了，那么，是否还可以再进一步减小n值呢？下面提出一个双步逐点曲线生成算法来进一步减小n值。3.3 双步逐点曲线生成算法从上一小节的描述可知，新算法通过求极值已经找到了满足条件n的最小n值。如果再进一步减小n的值，则在曲线上可能出现断点，即曲线前进的幅度大于了一个象素的长度，从而漏过了一个中间的象素。在前面求得的最小n值的基础上，本小节提出双步逐点曲线生成算法，其基本思想是，将n 值减小二分之一（即将步长增加一倍）。这样当曲线前进一步时，其幅度有时会大于一个象素的长度。为了不使曲线出现漏点，我们通过插值的方法来确定跨过的那个中间象素。用此方法可使上一小节提出的算法的循环次数减少一半，并大大提高了参数曲线的生成速度。下面将具体描述双步逐点曲线生成算法的思想。设n 仍是上节计算出的单步算法的n 值。为了保证算法的双步特性，将3.1式（拉格朗日中值定理）=1乘2，得= 2该式保证了双步算法在将步长增加一倍（即n值减小二分之一）时，曲线每次前进的幅度不会大于两个象素的长度。我们还是先讨论x坐标的情况，y坐标与x坐标同理。设当前点坐标xi已经确定，则下一点的x 坐标xi+1应该满足Nxi+1 = (i+1) + zi+1 ,其中 (i+1)=( i ) +( i )= Nxizi +( i )由第一小节中的等式=NN可知：= N=（）2N，而，所以 N可以看出，xi+1的可能取值为xi2，xi1，xi，xi +1和xi +2。由上面的讨论就得到了xi+1的计算公式： 当 (k)N (i)zi < (k+)N时， xi+1 = xi + k。其中k=2,1,0 ,1,2 。而由zi+1 =N xi+1(i+1) 可以得到zi+1的计算公式：当xi+1 = xi + k时，zi+1= zi( i ) + kN。其中 k=2,1,0 ,1,2。这样，就得到了xi+1和zi+1的递推公式，通过它我们就可以计算出下一象素点的x坐标和下一步的余数z 。下面我们来讨论当曲线前进一步时，其幅度大于一个象素的长度的情况。当x坐标增加或减少的幅度大于一个象素长度（即xi+1 = xi + 2 或xi+1 = xi2）时，就要通过插值的方法来确定被跨过的那个中间象素。这要分几种情况来考虑，以坐标增加的情况为例：·如果y坐标没有增加（即yi+1 = yi），则显然应该选择中间象素（xi +1, yi）如下图（a）的情况；·如果y坐增加2（即yi+1 = yi + 2），则显然应该选择中间象素（xi +1, yi + 1）如下图（b）的情况；·如果y坐增加1（即yi+1 = yi + 1），则应该选择中间象素（xi +1, yi）和（xi +1, yi + 1）中距离曲线较近的一个。选择的方法是将y的坐标的增加的幅度减少一半，然后判断是否大于N/2（参见上述算法原理）。若大于N/2，则选择（xi +1, yi + 1），否则选择（xi +1, yi）。如下图（c）、（d）的情况（xi，yi）（xi+1，yi） （xi+2，yi）（xi，yi）（xi+1，yi+1）（xi+2，yi+2）图（a） 图（b）（xi，yi） （xi+2，yi+1）（xi+1，yi+1）（xi，yi）（xi+1，yi） （xi+2，yi+1）图（c） 图（d）为了提高计算速度，计算过程应尽量避免使用乘法运算，因此这里在每次循环计算下一点的函数插值时，引入了差分运算，通过降阶的方法，就可以用加法来代替乘法运算。 差分的定义：设函数f( x )在等距节点处的函数值f(xk) = yk (k=0,1,2) ，则称两个节点xk和xk+1 处函数值之差yk+1yk为函数f( x )在xk处以h为步长的一阶差分，记作yk，即 yk =yk+1yk称节点xk和xk+1 处一阶差分之差yk+1yk为f(x)在xk处二阶差分，记作2yk，即 2yk =(yk)=yk+1yk一般地，称m1阶差分的差分 myk =(m1yk) =m1yk+1m1yk为f(x)在xk处的m阶差分。回到上述算法的讨论当中，由上述差分公式可得： k+1( i ) =k(i+1)k( i )得 k(i+1)=k( i )k+1( i ) ，k=0,1,m.根据差分的性质可知，m次多项式的m阶差分恒为常数，则当i处的各阶差分已知时，用m次加法即可求得i + 1处的各阶差分。在计算xi+1和zi+1时，并未用到函数值(i+1)，而只用到了函数的一阶差分(i+1)，这只需m1次整数加法即可求得。对于y坐标同理可以得到类似的结果。我们将在下一小节编程实现该双步曲线生成算法。3.4 以三次Bezier曲线为例编程实现该算法下面是以三次Bezier为例的算法实现程序，其中(x，y)表示当前象素；a1，a2，a3和b1，b2，b3分别表示f和g的一、二、三阶差分k( i )和k( i ) (k=1，2，3)；z1和z2分别表示f和g的余项zi；变量fx和fy用于消除角点象素，fx为1表示前一个象素是通过x坐标加1（y坐标不变）来到当前象素的，fy为1表示前一个象素是通过y坐标加1（x坐标不变）来到当前象素的。所谓角点象素就是如下图所示的象素。当fx为1时，如果求出的下一个象素是向