第四章-二维图形生成技术.ppt

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 二维图形生成技术,4.1 直线图形,y,x,1,2,3,4,n,1,2,3,4,m,p,1,p,2,一.生成直线的 DDA 算法,假设 直线的起点坐标为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。,二.,生成直线的 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 的中点，判断。,关键问题,：,(1)如何判断 b是在 a 的上面还是,下面，设置一个标志变量 e；,(2)如何建立标志变量 e 的递推公式。,x,i,X,i+1,Y,i,Y,i+1,Y,i+1,b,a,c,d,设,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,Q,(t),P,i,N,i,k,(t)(0t1),i=0,为k阶(或k1次)的B样条曲线。其中N,i,k,(t)为,B样条基函数,。给定的n1个点为B样条曲线的控制顶点，由其构成的多边折线称,B特征多边形,。,1.二次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,二次B样条曲线的端点特性与Bezier曲线不同，它是以二,次B特征多边形的二边上的中点为其起点和终点，并在端点,处与二边相切。,p,0,p,1,p,2,由三个控制顶点(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,3,2.三次B样条曲线,三次B样条曲线的端点特性：,p,0,p,1,p,2,p,3,P,(0),P,(1),P,(0),P,(1),三次B样条曲线的矩阵表示形式如下：,1 3,3 1,P,0,1 3,6 3 0,P,1,6,3 0 3 0,P,2,1 4 1 0,P,3,分解后的,参数式为：,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样条曲线的连续性：,在已有的三次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),