图形学教案图形基元的显示市公开课一等奖百校联赛特等奖课件.pptx

第二章第二章 图形基元显示图形基元显示 扫描转换扫描转换 将图形描述转换成将图形描述转换成用象素矩阵表示过程用象素矩阵表示过程图形基元（输出图形元素）图形基元（输出图形元素）图形系统能产生最基本图形图形系统能产生最基本图形 线段、圆、多边形线段、圆、多边形 10/10/第1页第一节第一节 点扫描转换点扫描转换第二节第二节 直线扫描转换算法直线扫描转换算法 第三节第三节 圆扫描转换算法圆扫描转换算法第四节第四节 区域填充区域填充 10/10/第2页第一节第一节 点扫描转换点扫描转换将一个图形区域数学点（x,y）转换为在（x,y）像素点，这里x和y都是实数，实现方法之一是取x整数部分作为x，取y整数部分为y。也就是x=Floor(x),y=Floor(y)。10/10/第3页另一个方法是用像素坐标排列（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/10/第4页第二节第二节 直线扫描转换算法直线扫描转换算法直接使用直线方程转换直接使用直线方程转换DDADDA直线扫描转换算法直线扫描转换算法中点画线法中点画线法 BresenhamBresenham画线算法画线算法 10/10/第5页10/10/第6页 直接使用直线方程转换直接使用直线方程转换:设待画线段两端点坐标值设待画线段两端点坐标值(x1,y1)(x1,y1)和和(x2,y2)(x2,y2)，假定，假定 x1x2 x1fabs(dy)?fabs(dx):fabs(dy);dx/=e;dy/=e;10/10/第11页 x=x1;y=y1;for(int i=1;i0)0 ；直线下方点，直线下方点，F F(x x，y y)0)0。10/10/第15页Q Q在在M M 上方还是下方，只要把上方还是下方，只要把M M 代入代入F F(x x，y y)，并判断它符号。，并判断它符号。d d=F F(M M)=F F(x xi i+1+1，y yi i+0.5)+0.5)=a a(x xi i+1)+1)+b b(y yi i+0.5)+0.5)+c c当当 d d 0 0 0，则取正右方则取正右方P P1 1。当当d d=0=0时，二者一样适当，取时，二者一样适当，取P P1 1。10/10/第16页 对对每每一一个个象象素素计计算算判判别别式式d d，依依据据它符号确定下一象素。它符号确定下一象素。d d0 0 时时，取取正正右右方方象象素素P P1 1，判判断断再下一个再下一个象素应取那个，应计算象素应取那个，应计算d d1 1 =F F(x xi i+2+2，y yi i+0.5+0.5 )=a a(x xi i+2)+2)+b b(y yi i+0.5)+0.5)+c c=d d+a a故故d d增量为增量为a a。而而若若d d00，则则取取右右上上方方向向素素P P2 2。要要判判断下一个象素，则要计算断下一个象素，则要计算10/10/第17页d d2 2=F F(x xi i+2+2，y yi i+1.5)+1.5)=a a(x xi i+2)+2)+b b(y yi i+1.5)+1.5)+c c=d d+a a+b b故在第二种情况，故在第二种情况，d d增量为增量为a a+b b 再看再看d d初始值。显然，第一个象素应初始值。显然，第一个象素应取左端点取左端点(x x0 0，y y0 0)，对应判别式值为，对应判别式值为 10/10/第18页d d0 0=F F(x x0 0+1+1，y y0 0+0.5)+0.5)=a(=a(x x0 0+1)+1)+b b(y y0 0+0.5)+0.5)+c c=a x a x0 0+b yb y0 0+c c+a a+0.5+0.5b b =F F(x x0 0，y y0 0)+)+a a+0.5+0.5b b 但因为但因为(x x0 0，y y0 0)在直线上，故在直线上，故F F(x x0 0，y y0 0)=0)=0。所以，所以，d d初始值为初始值为d d0 0=a a+0.5+0.5b b考虑用考虑用2d2d来代替来代替d d计算计算10/10/第19页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/10/第20页 x=x0;y=y0;SetPixel(x,y);while(xx1 )if(d0)x+;y+;10/10/第21页d+=delta2;else x+;d+=delta1;SetPixel(x,y);/*while*/*MidpointLine*/10/10/第22页 作为一个例子，我们来看中点画线法怎样光栅化一条连接两点(0，0)和(5，2)直线段。因为(x0，y0)=(0，0)且(x1，y1)=(5，2)，直线斜率k=2/5 满足0k1，所以，能够应用上述算法。10/10/第23页 第一个象素应取线段左端点(0，0)。判别式d初始值为d0 =2*a+b=1（a=y0-y1=-2，b=x1-x0=5）。d 往正右方向增量1=2a=-4；d 往右上方增量2=2(a+b)=6。因为d00，所以迭代循环第一步取初始点正右方象素(1，0)，x递增1，并将d更新为：d=d0+1=1-4=-3。10/10/第24页 因为x=1x1，所以进入第二步迭代运算。这时因为d0，故取右上方象素(2，1)，x、y同时递增1，并将d更新为：d=-3+2=3，这么继续分析下去知x、y、d初值和循环迭代过程中每一步值依序以下：10/10/第25页xyd00110-321331-1425521(0，0)、(5，2),a=y0-y1=-2，b=x1-x0=5）d d0 0 =2=2*a a+b b=1=1 10/10/第26页BresenhamBresenham画线算法画线算法:Bresenham提出了一个更加好算法，算法中能够只用整数运算，自然也无须有四舍五入。为了说明简便，假定直 线 斜 率m在 0到 1之 间，而 且 。10/10/第27页设在第设在第i i步已经步已经确定第确定第i i个象素个象素点是点是 ，它，它是直线上点是直线上点 最靠近位置最靠近位置 ，现在看第，现在看第i i+1+1步怎样确定第步怎样确定第i i+1+1个象素点位个象素点位置。置。10/10/第28页,下一个象素点取，下一个象素点取，取两象素点中任意一个 10/10/第29页,应取10/10/第30页,应取 确定P1,令i=1，可计算求出：10/10/第31页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);elsep+=2*dy;演示演示10/10/第33页