《计算机图形学 第2版 教学课件 ppt 作者 徐长青 第2章 图形基元的显示》由会员分享，可在线阅读，更多相关《计算机图形学 第2版 教学课件 ppt 作者 徐长青 第2章 图形基元的显示（69页珍藏版）》请在金锄头文库上搜索。
1、第二章 图形基元的显示,扫描转换 将图形描述转换成用象素矩阵表示的过程 图形基元（输出图形元素）图形系统能产生的最基本图形 线段、圆、多边形,第一节 直线扫描转换算法 第二节 圆的扫描转换算法 第三节 区域填充,第一节 直线扫描转换算法,DDA直线扫描转换算法 中点画线法 Bresenham画线算法,设待画线段两端点的坐标值(x1,y1)和(x2,y2)，假定 x1x2 y=mx+b m=(y2-y1)/(x2-x1) b=(x2y1-x1y2)/(x2-x1) ,对x每增1取允许的各整数值,void DDALine(int x1,int y1,int x2,int y2) double dx
2、,dy,e,x,y; dx=x2-x1; dy=y2-y1; e=(fabs(dx)fabs(dy)?fabs(dx):fabs(dy); dx/=e; dy/=e;,x=x1; y=y1; for(int i=1;i=e;i+) SetPixel(int)(x+0.5), (int)(y+0.5); x+=dx; y+=dy; ,假定直线斜率在0、1之间 x= xi时已选（xi，yi）象素 x= xi +1与直线最近的象素 P1 ( xi + 1，yi )、 P2 ( xi+1，yi+1) M表示P1与P2的中点 M = ( xi+1，yi +0.5)。 Q是直线与垂直线x=xi +1的交点
3、 若M在Q的下方，则P2离直线近，应取为下一个象素,中点画线法的实现 起点和终点分别为 ( x0 , y0 ) 和( x1 , y1 )。 F(x , y) = ax + by + c 其中，a=y0y1，b=x1x0， c=x0y1x1y0 。 直线上的点，F (x，y) = 0 ； 直线上方的点，F(x，y)0 ； 直线下方的点，F(x，y)0。,将M代入F(x，y) d = F(M) = F( xi+1，yi+0.5 ) =a ( xi+1 ) + b ( yi+0.5 ) + c 当 d 0，则取正右方的P1。 当d=0时，二者一样合适，取P1。,对每一个象素计算判别式d，根据它的符号
4、确定下一象素。 d0 时，取正右方象素P1 ，判断再下一个象素应取哪个，应计算 d1 = F ( xi+2 ，yi+0.5 ) = a ( xi+2 ) + b ( yi+0.5 ) +c = d + a 故d的增量为a。 而若d0，则取右上方象素P2。要判断再下一个象素，则要计算,d2 = F ( xi+2，yi+1.5 ) = a ( xi+2 ) +b ( yi+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、.5 )+c = ax0+by0 +c+a+0.5b =F (x0,y0) + a + 0.5b 由于(x0，y0)在直线上， 故F(x0，y0)=0。 因此,d的初始值为d0 = a+0.5b 考虑用2d来代替d的计算,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);,x = x0 ; y = y0 ; SetPixel(x,y
6、); while( xx1 ) if( d0 ) x +; y +;,d+= delta2; else x +; d+= delta1; SetPixel(x,y); /* while */ /* MidpointLine */,(0，0)、(5，2) a = y0 -y1 = -2，b = x1 - x0 = 5 d0 = 2 * a + b = 1,斜率m在0到1之间，并且 设在第i步已经确定第i个象素点是 ，它是直线上点 的最接近位置( ) 现在看第i+1步如何确定第i+1个象素点的位置。,d1,d2,下一个象素点取,，下一个象素点取,，取两象素点中的任意一个,应取,应取,确定P1 ,令
7、i=1，可计算求出：,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=x2;x+) ,SetPixel(x,y); if(p=0) y+; p+=2*(dy-dx); else p+=2*dy; ,第二节 圆的扫描转换算法,x2+y2=R2,中点画圆法,讨论如何从点(0，R)至 ( ， )的18圆周,x坐标为xi的象素(xi,yi)下一个象素只能是(xi+1,yi) 的P1点或 (xi+1,yi-1) 的P2点,M
8、,构造函数：F(x,y)=x2+y2-R2 圆上的点，F(x,y)=0 圆外的点，F(x,y)0 圆内的点，F(x,y)0时，M在圆外，取P2 F(M)=0时，P1或P2随取一个即可，取P2,构造判别式,若d0，取P1作为下一个象素，而且再下一个象素的判别式为,而若d0，应取P2作为下一个象素，而且再下一个象素的判别式,第一个象素是(0,R)，判别式d的初始值为 d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R。,void MidpointCircle(int R) int x,y; double d; x=0;y=R;d=1.25-R; SetPixel(x,y); wh
9、ile(xy) if(d0) d+=2*x+3; x+;, else d+=2*(x-y)+5; x+; y-; SetPixel(x,y); ,在上述算法中，使用了浮点数来表示判别式d。 简化算法，在算法中全部使用整数，使用e=d-0.25代替d。 显然，初始化运算d=1.25-R对应于e=1-R。 判别式d0对应于e-0.25。 算法中可把d直接换成e。又由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以e-0.25等价于e0。,上述算法还可以进一步改进。以提高效率。注意到d的增量是x、y的线性函数，每当x递增1，d递增x=2。每当y递减1，d递增y =2。由于初始象素
10、为(0,R)，所以x的初值为3，y的初值为-2R+5。,void MidpointCircle2(int R) int x,y,deltax,deltay,d; x=0;y=R;d=1-R; deltax=3; deltay=5-R-R; SetPixel(x,y); while(xy) if(d0) d+=deltax; deltax+=2;deltay+=2; x+;, else d+=deltay; deltax+=2; deltay+=4; x+; y-; SetPixel(x,y); ,Bresenham画圆算法,在0xy的1/8圆周上，象素坐标x值单调增加，y值单调减少。,设第i步
11、已确定（xi,yi）是要画圆上的象素点，看第i+1步象素点（xi+1,yi+1）应如何确定。下一个象素点只能是(xi+1,yi)或(xi+1,yi-1)中的一个,H,D,精确圆弧是，则dH 0和dD0若pi0，必有pi0，dD0，必有pi0。 得出结论： pi做判别量， pi0选H点为下一个象素点，当pi0 0时，选D点为下一个象素点。,从 计算,当pi0时，应选D点，即选,当pi0时，应选H，即选,画圆的起始点是(0，R)， 即x1=0，y1=R，代入前式，令i=1， 就得到：,void BresenhamCircle(int R) int x,y,p; x=0; y=R; p=3-2*R;
12、 for(;x=0) p+=4*(x-y)+10; y-; ,else p+=4*x+6; 只需修改语句SetPixel(x,y)，画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心在任意位置的圆周。,区域填充, 种子填充算法 区域是指光栅网格上的一组象素。 区域填充是把某确定的象素值送入 到区域内部的所有象素中。,区域填充方法分为两大类。 区域由多边形围成，区域由多边形的顶点序列来定义;另一类方法是通过象素的值来定义区域的内部，相应的技术称为是以象素为基础的.,内定义区域，定义方法是指出区域内部所具有的象素值,此时区域内部所有象素有某个原值oldvalue; 边界定义区域，定义
13、方法是指出区域边界所具有的象素值。此时区域边界上所有象素具有某个边界boundaryvalue。区域的边界应该是封闭的，并且应该指明区域的内部。 以象素为基础的区域填充主要是依据区域的连通性进行。,四连通:从区域中的一个象素出发，经连续地向上下左右四个相邻象素的移动，就可以到达区域内的任意另一个象素. 八连通:如果除了要经上下左右的移动，还要经左上、右上、左下和右下的移动，才能由一个象素走到区域中另外任意一个象素.,利用区域的连通性进行区域填充，除了需要区域应该明确定义外，还需要事先给定一个区域内部象素，这个象素称为种子。 做区域填充时，要进行对光栅网格的遍历，找出由种子出发能达到而又不穿过边
14、界的所有象素。 这种利用连通性的填充，其主要优点是不受区域不规则性的影响，主要缺点是需要事先知道一个内部象素。,void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue) /*(x，y)为种子 oldvalue是原值 newvalue是新值，应不等于原值。*/ if (GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue);/赋新值 Floodfill(x,y-1,oldvalue,newvalue); /四向扩散 Floodfill(x,y+1,oldvalue,newvalue);
15、 Floodfill(x-1,y,oldvalue,newvalue); Floodfill(x+1,y,oldvalue,newvalue); ,演示,void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue) /*(x,y) 为种子位置 boundaryvalue是边界象素值 newvalue是区域内象素新值，未填充前区域内不应有值为newvalue的象素。*/ if( GetPixel(x,y)!=boundaryvalue & GetPixel(x,y)!=newvalue) / 未达边界且未访问过, SetPixel(x,y,newvalue);/赋以新值 Boundaryfill(x,y-1,boundaryvalue,newvalue); /向四个方向扩散。 Boundaryfill(x,y+1,boundaryvalue,newvalue); Boundaryfill(x-1,y,boundaryvalue,newvalue); Boundaryfill(x+1,y,boundaryvalue,newvalue); ,扫描线种子填充算法 将区域内由边界点限定的同一行内相连接的不具有新值newvalue的一组象素称为一个象素段，象素段用它最右边的象素来标识。 算法的步骤
