二维图形生成技术课件.ppt

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 二维图形生成技术,第三章 二维图形生成技术,1,3.1 直线图形,一.生成直线的 DDA 算法,无论是光栅扫描显示器还是绘图机，都可以看成有一个网格(离散单元组成的矩阵)存在，对显示器来说每一个像素就是一个网格点，对绘图机来说笔每走一步的终点也可以看成是一个网格的结点在光栅扫描显示器上表示一条,直线，就是要用最靠近直线的一,些网格点来代表这一直线这个网格就构成屏幕和绘图机,纸张的一个坐标系，相邻两个网,点的距离取为1，每个网格点的坐,标均取整数p,1,p,2,3.1 直线图形p1p2,2,假设 直线的起点坐标为P,1,(x,1,y,1,)，终点坐标为P,2,(x,2,y,2,),x方向的增量为 xx,2,x,1,；y方向上增量为 yy,2,y,1,直线的斜率为,kyx,当,xy,时，让 x 从 x,1,到 x,2,变化，每步递增 1，,那么，x 的变化可以表示为 x,i+1,x,i,1,y 的变化可以表示为 y,i+1,y,i,k,用上式可求得图中直线 P,1,P,2,和 y 方向网格线的交点，但显示时要用象素点(图中的网格结点)来表示，所以要用舍入的办法耒找到最靠近交点处的象素点，并用其来表示直线段。

这个方法称之为数字微分分析法，简称DDA假设 直线的起点坐标为P1(x1,y1)，终点坐标为P,3,算法描述如下,：,int x,1,，y,1,，x,2,，y,2,；,int x；,float dx，dy，k，y；,dxx,2,x,1,；,dyy,2,y,1,；,kdydx,；,xx,1,；,yy,1,；,for(xx,1,；xx,2,；x),putpixel(x，(int)y，pixelcolor),；,yyk,；,该算法仅适用于k1 的情况，而当k1时，则需将 x 和 y 的位置交换算法描述如下：,4,二维图形生成技术课件,5,void dda_line(int xa,int ya,int xb,int yb,int c),float delta_x,delta_y,x,y;,int dx,dy,steps,k;,dx=xb-xa;,dy=yb-ya;,if(abs(dx)abs(dy)steps=abs(dx);,else steps=abs(dy);,delta_x=float(dx)/float(steps);,delta_y=float(dy)/float(steps);,x=xa;y=ya;putpixel(x,y,c);,for(k=1;k=steps;k+),x=x+delta_x;,y=y+delta_y;,putpixel(x,y,c);,void dda_line(int xa,int ya,in,6,二.生成直线的 Bresenham 算法,基本原理,二.生成直线的 Bresenham 算法基本原理,7,二.,生成直线的 Bresenham 算法,设 kyx，先讨论 0k1的情况：,若以屏幕上x方向的象素点作为横坐标，则有 x,i+1,x,i,1,而 y,i+1,y,i,k(x,i+1,x,i,)y,i,k (1),设 b 点是直线上的点，其坐标是(x,i+1,，y,i+1,)，显然，该点只能用屏幕上的象素点c 或 d 来表示。

设 a 为c、d 的中点，若 b 在,a 的上面则应取 d，否则应取 c关键问题,：,(1)如何判断 b是在 a 的上面还是,下面，设置一个标志变量 e；,(2)如何建立标志变量 e 的递推公式x,i,X,i+1,Y,i,Y,i+1,Y,i+1,b,a,c,d,二.生成直线的 Bresenham 算法xiXi+1Yi,8,设,e(x,i+1,)y,i+1,y,i,0.5,(2),若b在a的下面，则有 e(x,i+1,)0,由图中可知：当,e(x,i+1,),0时,y,i+1,y,i,1,e(x,i+1,)0时,y,i+1,y,i,递推：,由(2)、(3)式可得：,e(x,i+2,)y,i+2,y,i+1,0.5y,i+1,ky,i+1,0.5,y,i+1,y,i,0.5k1 e(x,i+1,),0,y,i+1,y,i,0.5k e(x,i+1,)0,e(x,i+1,)k1 e(x,i+1,),0,e(x,i+1,)k e(x,i+1,)=k)，则称参数曲线,n,P(t)P,i,N,i,k,(t)(0t1),i=0,为k阶(或k1次)的B样条曲线其中N,i,k,(t)为,B样条基函数,给定的n1个点为B样条曲线的控制顶点，由其构成的多边折线称,B特征多边形,。

六.B样条曲线,36,1.二次B样条曲线,二次B样条曲线的端点特性与Bezier曲线不同，它是以二次B特征多边形的二边上的中点为其起点和终点，并在端点处与二边相切二次B样条曲线的矩阵表示形式如下：,1 2 1 P,0,Q(t)t,2,t 1 2 2 0 P,1,1 1 0 P,2,分解后的,参数式为：x(t)a,x,t,2,b,x,t c,x,y(t)a,y,t,2,b,y,t c,y,式中系数分别为：,a,x,(x,0,2x,1,x,2,)2 b,x,x,1,x,0,c,x,(x,0,x,1,)2,a,y,(y,0,2y,1,y,2,)2 b,y,y,1,y,0,c,y,(y,0,y,1,)2,12,1.二次B样条曲线12,37,由三个控制顶点(P,0,、P,1,、P,2,)确定,的一条,二次B样条曲线是,一条,抛物线，,如果再增加一个,控制顶点P,3,，就可由,P,1,、P,2,、P,3,三个控制顶点生成第二条,二次B样条曲线由于,第一条,二次B样,条曲线的终点就是,第二条,二次B样条,曲线的起点，而且它们有,一条公共的,切线P,1,P,2,，所以二条,二次B样条曲线在,切点衔接处达到C,1,连续。

p,0,p,1,p,2,p,0,p,1,p,2,p,3,由三个控制顶点(P0、P1、P2)确定p0,38,2.三次B样条曲线,三次B样条曲线的端点特性：,p,0,p,1,p,2,p,3,P,(0),P,(1),P,(0),P,(1),2.三次B样条曲线p0p1p2p3P (0)P,39,三次B样条曲线的矩阵表示形式如下：,1 3,3 1 P0,1 3,6 3 0 P1,6,3 0 3 0 P2,1 4 1 0 P3,分解后的,参数式为：,x(t)a,x,t,3,b,x,t,2,c,x,t d,x,y(t)a,y,t,3,b,y,t,2,c,y,t d,y,式中系数分别为：,a,x,(x,0,3x,1,3x,2,x,3,)6 a,y,(y,0,3y,1,3y,2,y,3,)6,b,x,(x,0,2x,1,x,2,)2 b,y,(y,0,2y,1,y,2,)2,c,x,(x,0,x,2,)2 c,y,(y,0,y,2,)2,d,x,(x,0,4x,1,x,2,)6 d,y,(y,0,4y,1,y,2,)6,Q(t)t,3,t,2,t 1,(,0t1,),(0t1),三次B样条曲线的矩阵表示形式如下：Q,40,三次B样条曲线的连续性：,在已有的三次B样条曲线的基础上，增加一个控制点，就,可相应地增加一段B样条曲线，并自然地达到 C,2,连续。

p,0,p,1,p,2,p,3,p,4,P1,(0),P1,(1),P2,(0),P2,(1),P1,(0),P1,(1),P2,(0),P2,(1),三次B样条曲线的连续性：p0p1p2p3p4,41,作业：,1简述三次Bezier曲线的调和函数表达式与其,矩阵表示形式之间的关系给定空间n个点的位置向量P,i,(i=1,2,-n)，,写出根据这n个控制点用三次B样条曲线来,绘制自由曲线的算法作业：,42,。