参数曲线的快速生成算法毕业论文+外文文献翻译.doc
约48页DOC格式手机打开展开
参数曲线的快速生成算法毕业论文+外文文献翻译,摘 要本毕业设计主要研究参数曲线的直接快速生成，要直接生成参数曲线就需对参数方程{x=f(t),y=g(t),(0 t 1)}的参数t每次增加一个步长，然后计算该点的x和y坐标值并绘制该点。要逐点地生成参数曲线，就要求参数t每次增加的步长要使曲线前进的幅度不得超过一个象素长度，否则有可能跨过一个中间象素而产生断点。为了...
内容介绍
此文档由会员 wanli1988go 发布
摘 要
本毕业设计主要研究参数曲线的直接快速生成，要直接生成参数曲线就需对参数方程{x=f(t),y=g(t),(0 t 1)}的参数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),0LoadStandCursor(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。这就是中点画线法的基本原理。
中点画线算法每步迭代涉及的象素和中点示意图
下面来讨论上述算法的实现。假设直线的起点和终点分别是(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时，则应取正右方的P1。当d=0时，二者一样合适，可以随便取一个。我们约定取正右方的P1。
对每一个象素计算判别式d，根据它的符号确定下一个象素。至此可以写出完整的算法。但是注意到d是xp和yp的线形函数，可采用增量计算，提高运算效率。在d 0的情况下，取正右方象素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，来摆脱小数，写出仅包含整数的算法：
本毕业设计主要研究参数曲线的直接快速生成，要直接生成参数曲线就需对参数方程{x=f(t),y=g(t),(0 t 1)}的参数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),0LoadStandCursor(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。这就是中点画线法的基本原理。
中点画线算法每步迭代涉及的象素和中点示意图
下面来讨论上述算法的实现。假设直线的起点和终点分别是(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时，则应取正右方的P1。当d=0时，二者一样合适，可以随便取一个。我们约定取正右方的P1。
对每一个象素计算判别式d，根据它的符号确定下一个象素。至此可以写出完整的算法。但是注意到d是xp和yp的线形函数，可采用增量计算，提高运算效率。在d 0的情况下，取正右方象素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，来摆脱小数，写出仅包含整数的算法：
