图形学教案第二章图形基元的显示

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第二章 图形基元的显示,扫描转换 将图形描述转换成用象素矩阵表示的过程,图形基元（输出图形元素）图形系统能产生的最基本图形,线段、圆、多边形,10/1/2024,第一节 点扫描转换,第二节 直线扫描转换算法,第三节 圆的扫描转换算法,第四节 区域填充,10/1/2024,第一节 点扫描转换,将,一个图形区域的数学点（,x,y,）,转换为在（,x,y,）,的像素点，这里,x,和,y,都是实数，实现的方法之一是取,x,的,整数部分作为,x,，取,y,的,整数部分为,y,。,也就是,x=Floor(x),y=Floor(y),。,10/1/2024,另一种方法是用像素坐标排列（,x,y,）,所在坐标系统的整数值；转换时，使用,x=Floor(x+0.5),和,y=Floor(y+0.5),这种情况把（,x,y,）,所在坐标系统的原点放在像素（,0,，,0,）的中心。,满足：,x-0.5,x x+0.5;,y-0.5,y y+0.5,。,10/1/2024,第二节 直线扫描转换算法,直接使用直线方程转换,DDA,直线扫描转换算法,中点画线法,Bresenham,画线算法,10/1/2024,10/1/2024,直接使用直线方程转换,:,设待画线段两端点的坐标值,(x1,y1),和,(x2,y2),，,假定,x1,fabs,(,dy,)?,fabs,(,dx,):,fabs,(,dy,);,dx,/=e;,dy,/=e;,10/1/2024,x=x1;,y=y1;,for(,int,i=1;i0,；,直线下方的点，,F,(,x,，,y,)0。,10/1/2024,Q,在,M,的上方还是下方，只要把,M,代入,F,(,x,，,y,)，,并判断它的符号。,d,=,F,(,M,),=,F,(,x,i,+1,，,y,i,+0.5)=,a,(,x,i,+1)+,b,(,y,i,+0.5)+,c,当,d,0,，,则取正右方的,P,1,。,当,d,=0,时，二者一样合适，取,P,1。,10/1/2024,对每一个象素计算判别式,d,，,根据它的符号确定下一象素。,d,0,时，取正右方象素,P,1,，,判断,再下一个,象素应取那个，应计算,d,1,=,F,(,x,i,+2,，,y,i,+0.5,),=,a,(,x,i,+2),+,b,(,y,i,+0.5)+,c,=,d,+,a,故,d,的增量为,a,。,而若,d,0，,则取右上方向素,P,2,。,要判断下一个象素，则要计算,10/1/2024,d,2,=,F,(,x,i,+2,，,y,i,+1.5),=,a,(,x,i,+2)+,b,(,y,i,+1.5)+,c,=,d,+,a,+,b,故在第二种情况，,d,的增量为,a,+,b,再看,d,的初始值。显然，第一个象素应取左端点(,x,0,，,y,0,)，,相应的判别式值为,10/1/2024,d,0,=,F,(,x,0,+1,，,y,0,+0.5),=a(,x,0,+1)+,b,(,y,0,+0.5)+,c,=,a x,0,+,b y,0,+,c,+,a,+0.5,b,=,F,(,x,0,，,y,0,)+,a,+0.5,b,但由于(,x,0,，,y,0,),在直线上，故,F,(,x,0,，,y,0,)=0。,因此，,d,的初始值为,d,0,=,a,+0.5,b,考虑用2,d,来代替,d,的,计算,10/1/2024,void,MidpointLine,(,int,x0,int,y0,int,x1,int,y1),int,a,b,delta1,delta2,d,x,y;,a=y0-y1;,b=x1-x0;,d=2*a+b;,delta1=2*a;,delta2=2*(a+b);,10/1/2024,x=x0;,y=y0;,SetPixel,(x,y);,while(xx1 ),if(d0),x+;,y+;,10/1/2024,d+=delta2;,else,x+;,d+=delta1;,SetPixel,(x,y);,/*while*/,/*,MidpointLine,*/,10/1/2024,作为一个例子，我们来看中点画线法如何光栅化一条连接两点,(0,，,0),和,(5,，,2),的直线段。由于,(,x,0,，,y,0,),=,(0,，,0),且,(,x,1,，,y,1,),=,(5,，,2),，,直线斜率,k,=2/5,满足,0,k,1,，,所以，可以应用上述算法,。,10/1/2024,第一个象素应取线段左端点,(0,，,0),。判别式,d,的初始值为,d,0,=2*,a,+,b,=1,（,a,=,y,0,-,y,1,=-2,，,b,=,x,1,-,x,0,=5,）。,d,往正右方向的增量,1,=2,a,=-4,；,d,往右上方的增量,2,=2(,a,+,b,)=6,。,由于,d,0,0,，,所以迭代循环的第一步取初始点的正右方象素,(1,，,0),，,x,递增,1,，并将,d,更新为：,d,=,d,0,+,1,=1-4=-3,。,10/1/2024,因为,x,=1,x,1,，,所以进入第二步迭代运算。这时由于,d,0,，,故取右上方象素,(2,，,1),，,x,、,y,同时递增,1,，并将,d,更新为：,d,=-3+,2,=3,，,这样继续分析下去知,x,、,y,、,d,的初值和循环迭代过程中每一步的值依序如下：,10/1/2024,x,y,d,0,0,1,1,0,-3,2,1,3,3,1,-1,4,2,5,5,2,1,(0,，,0),、,(5,，,2),a,=,y,0,-,y,1,=,-,2,，,b,=,x,1,-,x,0,=5,）,d,0,=2,*,a,+,b,=1,10/1/2024,Bresenham,画线算法,:,Bresenham,提出了一个更好的算法，算法中可以只用整数运算，自然也不必有四舍五入。为了说明简便，假定直线斜率,m,在,0,到,1,之间，并且 。,10/1/2024,设在第,i,步已经确定第,i,个象素点是 ，它是直线上点 的最接近位置 ，现在看第,i,+1,步如何确定第,i,+1,个象素点的位置。,10/1/2024,下一个象素点取,，下一个象素点取,，取两象素点中的任意一个,10/1/2024,应取,10/1/2024,应取,确定,P,1,令,i,=1，,可计算求出：,10/1/2024,void,BresenhamLine,(,int,x1,int,y1,int,x2,int,y2),int,x,y,dx,dy,p;,x=x1;,y=y1;,dx,=x2-x1;,dy,=y2-y1;,p=2*,dy,-,dx,;,for(;x=0),y+;,p+=2*(,dy-dx,);,else,p+=2*dy;,演示,10/1/2024,