计算机图形学 第2版 作者 徐长青 第2章 图形基元的显示.pptVIP

第二章 图形基元的显示 扫描转换 将图形描述转换成用象素矩阵表示的过程 图形基元（输出图形元素）图形系统能产生的最基本图形 线段、圆、多边形 第一节 直线扫描转换算法 第二节 圆的扫描转换算法 第三节 区域填充 第一节 直线扫描转换算法 DDA直线扫描转换算法 中点画线法 Bresenham画线算法 设待画线段两端点的坐标值(x1,y1)和(x2,y2)，假定 x1x2 y=mx+b m=(y2-y1)/(x2-x1) b=(x2y1-x1y2)/(x2-x1) ,对x每增1取允许的各整数值 假定直线斜率在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的交点 若M在Q的下方，则P2离直线近，应取为下一个象素 void MidpointCircle(int R) { int x,y; double d; x=0;y=R;d=1.25-R; SetPixel(x,y); while(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。由于初始象素为(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画圆算法 在0≤x≤y的1/8圆周上，象素坐标x值单调增加，y值单调减少。 设第i步已确定（xi,yi）是要画圆上的象素点，看第i+1步象素点（xi+1,yi+1）应如何确定。下一个象素点只能是(xi+1,yi)或(xi+1,yi-1)中的一个 H D 精确圆弧是③，则dH 0和dD0．若pi0，即dH dD应选H点。若pi≥0，即dH ≥dD应选D点。 若精确圆弧是①或②，显然H是应选择点，而此时dH ≤0，dD0，必有pi0。 若精确圆弧是④或⑤，显然D是应选择点，而此时dH 0，dD≤0，必有pi0。 得出结论： pi做判别量， pi0选H点为下一个象素点，当pi0 ≥0时，选D点为下一个象素点。 从 计算 当pi≥0时，应选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; for(;x=y;x++) { SetPixel(x,y); if(p=0) { p+=4*(x-y)+10; y--; } else { p+=4*x+6; } } } 只需修改语句SetPixel(x,y)，画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心在任意位置的圆周。 区域填充 ● 种子填充算法