136.参数曲线的快速生成算法毕业设计.doc
《136.参数曲线的快速生成算法毕业设计.doc》由会员分享,可在线阅读,更多相关《136.参数曲线的快速生成算法毕业设计.doc(49页珍藏版)》请在三一办公上搜索。
1、 江 南 大 学毕 业 设 计 论 文论文题目:参数曲线的快速生成算法姓 名: 学 院:信息工程学院专 业:计算机科学与技术指导老师: 日 期:2003年6月摘 要本毕业设计主要研究参数曲线的直接快速生成,要直接生成参数曲线就需对参数方程x=f(t),y=g(t),(0t1)的参数t每次增加一个步长,然后计算该点的x和y坐标值并绘制该点。要逐点地生成参数曲线,就要求参数t每次增加的步长要使曲线前进的幅度不得超过一个象素长度,否则有可能跨过一个中间象素而产生断点。为了提高曲线生成算法的速度,本毕业设计针对如何选择最佳的步长进行比较讨论,以使曲线前进的幅度在不超过一个象素的前提下,选择尽量大的步长
2、。为了进一步提高算法的速度,在前面讨论的最佳步长的基础上又采用了双步逐点曲线生成算法,即将上述得到的步长增加一倍,以使算法的循环次数减少一半。由于步长增加一倍,这样当曲线前进一步时,其幅度有时会大于一个象素的长度,这时我们通过插值的方法来确定跨过的那个中间象素。通过上述讨论的算法能够比较快速的逐点生成曲线,为了实现上述算法,本毕业设计使用Visual C+6.0为工具并以三次Bezier曲线、普通参数曲线x=f(t)=X3t3+X2t2+X1t+X0, y=g(t)=Y3t3+Y2t2+Y1t+Y0,以及导师所给的一个特殊的曲线方程为例编程实现上述算法。关键词:参数曲线,逐点,双步,Visua
3、l C+6. 0 作者: 二零零三年 六月Abstract This graduation project main reseach the direct born of the parameter curve x=f(t),y=g(t),0= t LoadStandCursor(IDC_CROSS)初始化该变量,该语句的作用是取得Windows标准鼠标形状句柄并赋给m_hCross,然后就可以通过ClassWizard添加鼠标动作的消息处理函数。例如,要为程序添加鼠标左键单击消息处理函数,首先在打开的ClassWizard对话框中的Class name组合框中选择View类,然后在Objec
4、t Ids列表框选中第一行,并在Message列表框中选中WM_LBUTTONDOWN一行,最后单击Add Function按钮即可。类似的还可以为程序添加WM_RBUTTONDOWN(鼠标右键单击)消息处理函数。因为需要逐点地生成曲线,因此在程序中需要使用到MFC(Microsoft Fundation Class)中的CDC(设备上下文)类的成员函数SetPixel()来实现在屏幕上画点,CDC类主要用于在指定设备上下文上(如窗口客户区、打印机)进行绘图、显示文本等操作。第二章 计算机图形学中常用的算法2.1 常用直线的算法 画直线的算法有很多,例如数值微分法,中点画线法,Bresenha
5、m化线算法等。在这里只介绍一个比较方便常用的中点画线法。为了讨论方便,本小节假定直线斜率在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。
6、这就是中点画线法的基本原理。 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) +
7、 c当d0时,则应取正右方的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。而若d0,则右上方的象素P2,欲判断再下一个象素,则要计算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+ c = d + a + b故在第二种情况
8、,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,d
9、elta1,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(d0) x+;y+;d+= delta2;elsex+;d+= delta1;drawpixel(x,y,color); 2.2 常用的参数曲线的绘制算法常用的参数曲线有许多,如Bezier,B样条,非均匀有理B样条、圆锥曲线等。本小节将以Bezier曲线为代表,讲解其绘制算法。Bezier曲线的公式 :给定空间n+1个点的位置矢量Pi,Bezier曲线上各
10、点坐标的插值公式是: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
11、,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=1idegree;i+) fact = fact*t;n_choose_i= n_choose_i*(degree-i+1)/i;aux=(aux+fact* n_choose_i*coeffi*t1;
12、 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)呈直角三角形,对应如下所示: 该三角形垂
13、直边上的点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
14、 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;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 136 46 参数 曲线 快速 生成 算法 毕业设计
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-3929941.html