计算机图形学02.ppt

计算机图形学计算机图形学Computer GraphicsComputer Graphics使用班级：地信2009级 王增武 WangZTel:13518208752QQ:64434430第一章第一章 绪论绪论第二章第二章 光栅图形学光栅图形学第三章第三章 曲线和曲面曲线和曲面第四章第四章 图形变换图形变换第五章第五章 造型技术造型技术第六章第六章 真实感图形显示真实感图形显示上机实验上机实验第二章第二章 基本图形生成算法基本图形生成算法2.1 2.1 直线的生成算法直线的生成算法2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法2.3 2.3 区域填充算法区域填充算法2.4 2.4 线宽与线型处理线宽与线型处理2.5 2.5 字符的生成字符的生成2.6 2.6 图形裁剪图形裁剪2.7 2.7 反走样技术反走样技术第二章第二章 基本图形生成算法基本图形生成算法2.1 2.1 直线的生成算法直线的生成算法2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法2.3 2.3 区域填充算法区域填充算法2.4 2.4 线宽与线型处理线宽与线型处理2.5 2.5 字符的生成字符的生成2.6 2.6 图形裁剪图形裁剪2.7 2.7 反走样技术反走样技术2.1 2.1 直线的生成算法直线的生成算法画一条从画一条从(x x1 1,y y1 1)到到(x x2 2,y y2 2)的直线，实质上是一个发的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。这现最佳逼近直线的像素序列，并填入色彩数据的过程。这过程也称为过程也称为直线光栅化直线光栅化。连续性连续性粗细、亮度要粗细、亮度要均匀均匀像素逼近待画像素逼近待画直线直线速度速度2.1 2.1 直线的生成算法直线的生成算法1直线直线DDA算法算法(Digital Differential Analyser)假设假设 直线的起点坐标为直线的起点坐标为P P1 1(x(x1 1,y,y1 1)，终点坐标为，终点坐标为P P2 2(x(x2 2,y,y2 2)x x方向的增量为方向的增量为 x xx x2 2x x1 1 ；y y方向上增量为方向上增量为 y yy y2 2y y1 1 直线的斜率为直线的斜率为 m my yx x 当当 x xy y 时，让时，让 x x 从从 x x1 1 到到 x x2 2 变化，每步递增变化，每步递增 1 1，那么，那么，x x 的变化可以表示为的变化可以表示为 x xi+1i+1x xi i1 1 y y 的变化可以表示为的变化可以表示为 y yi+1i+1y yi im m 用上式可求得图中直线用上式可求得图中直线 P P1 1P P2 2 和和 y y 向网格线的交点，但显示时要用舍入向网格线的交点，但显示时要用舍入 找到最靠近交点处的象素点耒表示。找到最靠近交点处的象素点耒表示。当当 xy xdy?DxDy1a true 1 m1b false 1/m 12a true -1 m2b false -1/m 13a true -1 -m3b false -1/m -14a true 1 -m4b false 1/m -1表1 8个象限中的坐标增量值2.1 2.1 直线的生成算法直线的生成算法研究表中的数据，可以发现研究表中的数据，可以发现两个规律两个规律。当当 d dx x d dy y时时 D Dx x =1=1，D Dy y=m m否则否则 D Dx x =1/=1/m m，D Dy y=1=1 D Dx x、D Dy y的符号与的符号与d dx x、d dy y的符号相同。的符号相同。2.1 2.1 直线的生成算法直线的生成算法算法描述如下：dda_line(xa,ya,xb,yb,c)int xa,ya,xb,yb,c;float delta_x,delta_y,x,y;int dx,dy,steps,k;dx=xbxa;dy=ybya;if(abs(dx)abs(dy)steps=abs(dx);else steps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;x=xa;y=ya;set_pixel(x,y,c);for(k=1;k00，则，则y yi i+1+1=y yi i+1+1，否则，否则y yi i+1+1=y yi i。将式将式(2.1)(2.1)、(2.2)(2.2)、(2.3)(2.3)代入代入d d1 1 d d2 2，再用，再用d dx x乘等式两边，并以乘等式两边，并以P Pi i=(=(d d1 1 d d2 2)d dx x代入上述等式，得代入上述等式，得 P Pi i=2=2x xi id dy y 2 2y yi id dx x+2d+2dy y+(2+(2b b 1)1)d dx x (2.4)(2.4)d d1 1 d d2 2是用以判断符号的误差。由于在是用以判断符号的误差。由于在1 1a a象限，象限，d dx x总大于总大于0 0，所，所以以P Pi i仍旧可以用作判断符号的误差。仍旧可以用作判断符号的误差。P Pi i+1+1为为 P Pi i+1+1=P Pi i+2d+2dy y 2(2(y yi i+1+1 y yi i)d dx x (2.5)2.5)2.1 2.1 直线的生成算法直线的生成算法求误差的初值求误差的初值P P1 1，可将，可将x x1 1、y y1 1和和m m、b b代入式代入式(2.4)(2.4)中的中的x xi i、y yi i而得到而得到 P Pi i=2=2x xi id dy y 2 2y yi id dx x+2d+2dy y+(2+(2b b 1)1)d dx x (2.4)(2.4)P P1 1=2d=2dy y d dx x2.1 2.1 直线的生成算法直线的生成算法 综述上面的推导，第综述上面的推导，第1 1a a象限内的直线象限内的直线BresenhamBresenham算法思想如下：算法思想如下：画点画点(x x1 1,y y1 1)，d dx x=x x2 2 x x1 1，d dy y=y y2 2 y y1 1，计算误差初值，计算误差初值P P1 1=2d=2dy y d dx x，i i=1=1；求直线的下一点位置求直线的下一点位置 x xi i+1+1=x xi i+1+1 如果如果P Pi i00，则，则y yi i+1+1=y yi i+1+1，否则，否则y yi i+1+1=y yi i；画点画点(x xi i+1+1,y yi i+1+1)；求下一个误差求下一个误差P Pi i+1+1，如果，如果P Pi i00，则，则P Pi i+1+1=P Pi i+2d+2dy y 2d2dx x，否则，否则 P Pi i+1+1=P Pi i+2d+2dy y；i i=i i+1+1；如果；如果i id|dydy|为分支，并分别将为分支，并分别将2 2a a、3 3a a象限的直线和象限的直线和3 3b b、4 4b b象限的直线变换到象限的直线变换到1 1a a、4 4a a和和2 2b b、1 1b b象限方向去，以实现程序处理的简洁。象限方向去，以实现程序处理的简洁。2.1 2.1 直线的生成算法直线的生成算法3 中点画线法中点画线法假定直线斜率假定直线斜率0K P2离直线更近更近离直线更近更近-取取P2。uM在在Q的上方的上方-P1离直线更近更近离直线更近更近-取取P1uM与与Q重合，重合，P1、P2任取一点。任取一点。问题：如何判断问题：如何判断M与与Q点的关系？点的关系？(M为为P1P2的中点的中点)M2.1 2.1 直线的生成算法直线的生成算法假设直线方程为：ax+by+c=0 (x0,y0)(x1,y1)其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。2.1 2.1 直线的生成算法直线的生成算法构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+cu当d0，M在直线(Q点)上方，取右方P1；u当d=0，选P1或P2均可，约定取P1；2.1 2.1 直线的生成算法直线的生成算法d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c能否采用增量算法呢？能否采用增量算法呢？2.1 2.1 直线的生成算法直线的生成算法若若d 0-M在直线上方在直线上方-取取P1;此时再下一个象素的判别式为此时再下一个象素的判别式为 d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c =a(xp+1)+b(yp+0.5)+c+a=d+a；增量为增量为a2.1 2.1 直线的生成算法直线的生成算法若若dM在直线下方在直线下方-取取P2;此时再下一个象素的判别式为此时再下一个象素的判别式为 d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c =a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量为增量为ab2.1 2.1 直线的生成算法直线的生成算法画线从画线从(x0,y0)开始，开始，d的初值的初值d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c =F(x0,y0)+a+0.5b=a+0.5b 由于只用由于只用d 的符号作判断，为了只包含整数运算的符号作判断，为了只包含整数运算,可以用可以用2d代替代替d来摆脱小数，提高效率。来摆脱小数，提高效率。2.1 2.1 直线的生成算法直线的生成算法void Midpoint Line(int x0,int y0,int x1,int y1,int color)int a,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(xx1)if(d0)x+;y+;d+=d2;else x+;d+=d1;drawpixel(x,y,color);/*while*/*mid PointLine*/2.1 2.1 直线的生成算法直线的生成算法例：用中点画线法例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2 b=x1-x0=5d0=2a+b=1 d1=2a=-4d2=2(a+b)=6ixiyid1 0012 10-33 2134 31-15 425第二章第二章 基本图形生成算法基本图形生成算法2.1 2.1 直线的生成算法直线的生成算法2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法2.3 2.3 区域填充算法区域填充算法2.4 2.4 线宽与线型处理线宽与线型处理2.5 2.5 字符的生成字符的生成2.6 2.6 图形裁剪图形裁剪2.7 2.7 反走样技术反走样技术2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法基础知识基础知识给出圆心坐标给出圆心坐标(x xc c,y yc c)和半径和半径r r，假设圆的方程为：假设圆的方程为：X2+Y2=r2逐点画出一个圆周的公式有下列两种：逐点画出一个圆周的公式有下列两种：直角坐标法直角坐标法(x x x xc c)2 2+(+(y y y yc c)2 2=r r2 2由上式导出：由上式导出：当xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的，xxc越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法 极坐标法极坐标法x x=x xc c+r r coscos，y y=y yc c+r r sinsin 当当从从0 0到到作递增时，由此式便可作递增时，由此式便可求出圆周上均匀分布的求出圆周上均匀分布的360360个点的个点的(x x,y y)坐标。坐标。圆的特征圆的特征:八对称性。八对称性。只要扫描转换八分之一圆弧，只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集就可以求出整个圆弧的象素集.将圆周分为将圆周分为8 8个象限个象限(右右图图)，只要将第，只要将第1 1a a象象限中的圆周光栅点求出，其余限中的圆周光栅点求出，其余7 7部分圆周就可以通过对称法则部分圆周就可以通过对称法则计算出来。计算出来。2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法3 3 主要算法主要算法角度角度DDA法法中点画圆法中点画圆法Bresenham画圆算法画圆算法生成圆弧的正负法生成圆弧的正负法生成圆弧的多边形逼近法生成圆弧的多边形逼近法（圆的内接正多边形迫近法、圆的等面积正多边形迫近法）（圆的内接正多边形迫近法、圆的等面积正多边形迫近法）2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法1中点画圆法中点画圆法构造函数：构造函数：F（X，Y）=X2 +Y2-R2；则；则 F（X，Y）=0 （X，Y）在圆上；）在圆上；F（X，Y）0 （X，Y）在圆外。）在圆外。设设M为为P1、P2间的中点，间的中点，M=(Xp+1,Yp-0.5)MP1P22.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法有如下结论：有如下结论：F（M）M在圆内在圆内-取取P1 F（M）=0-M在圆外在圆外-取取P2为此，可采用如下判别式：为此，可采用如下判别式：MP1P22.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法考虑中心在原点，半径为R的第二个8分圆，构造判别式（圆方程）2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法若 d=0,则应取P2为下一象素，而且下一象素的判别式为 第 一个象素是（0,R），判别式d的初始值为2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法为了进一步提高算法的效率，可以将上面的算法中为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。用整数实现中点画圆法。使用使用e=d-0.25代替代替d e0=1-R2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法MidPointCircle(int r int color)int x,y;float d;x=0;y=r;d=1.25-r;circlepoints(x,y,color);/显示圆弧上的八个对称点显示圆弧上的八个对称点 while(x=y)if(d0)d+=2*x+3;else d+=2*(x-y)+5;y-;x+;circlepoints(x,y,color);2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法2圆的圆的Bresenham算法算法设圆的半径为设圆的半径为r r。先考虑圆心在。先考虑圆心在(0,0)(0,0)，并从，并从x x=0=0、y y=r r开始的顺时针方向的开始的顺时针方向的1/81/8圆周的生成过程。在这种情况下，圆周的生成过程。在这种情况下，x x每步增加每步增加1 1，从，从x x=0=0开始，到开始，到x x=y y结束。即有结束。即有x xi i+1+1=x xi i+1+1相应的相应的y yi i+1+1则在两种可能中选择：则在两种可能中选择：y yi i+1+1=y yi i或者或者y yi i+1+1=y yi i 1 1选择的原则是考察精确值选择的原则是考察精确值y y是靠近是靠近y yi i还是还是靠近靠近y yi i 1(1(右右图图)，计算式为计算式为y y2 2=r r2 2(x xi i+1)+1)2 2d d1 1=y yi i2 2 y y2 2=y yi i2 2 r r2 2+(+(x xi i+1)+1)2 2d d2 2=y y2 2(y yi i 1)1)2 2=r r2 2(x xi i+1)+1)2 2(y yi i 1)1)2 2 y的位置2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法令令p pi i=d d1 1 d d2 2，并代入，并代入d d1 1、d d2 2，则有，则有 p pi i=2(=2(x xi i+1)+1)2 2+y yi i2 2+(+(y yi i 1)1)2 2 2 2r r2 2 (2.6)(2.6)p pi i称为误差。如果称为误差。如果p pi i00则则y yi i+1+1=y yi i，否则，否则y yi i+1+1=y yi i 1 1。p pi i的递归式为的递归式为 p pi i+1+1=p pi i+4+4x xi i +6+2(+6+2(y yi+1i+12 2 y yi i2 2)2(2(y yi+1i+1 y yi i)(2.7)(2.7)p pi i的初值由式的初值由式(2.6)(2.6)代入代入x xi i=0=0，y yi i=r r而得而得 p p1 1=3=3 2 2r r (2.8)(2.8)2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法圆周生成算法思想如下：圆周生成算法思想如下：求误差初值，求误差初值，p p1 1=3=3 2 2r r，i i=1=1，画点，画点(0,(0,r r)；求下一个光栅位置，其中求下一个光栅位置，其中x xi i+1+1=x xi i+1+1，如果，如果p pi i00则则y yi i+1+1=y yi i，否则否则y yi i+1+1=y yi i 1 1；画点画点(x xi i+1+1,y yi i+1+1)；计算下一个误差，如果计算下一个误差，如果p pi i00则则p pi i+1+1=p pi i+4+4x xi i+6+6，否则，否则p pi i+1+1=p pi i+4(+4(x xi i y yi i)+10)+10；i i=i i+1+1，如果，如果x x=y y则结束，否则返回步骤则结束，否则返回步骤2 2。2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法圆的圆的BresenhamBresenham算法的程序实现如下：算法的程序实现如下：circle(xccircle(xc,ycyc,radius,c),radius,c)intint xcxc,ycyc,radius,c;,radius,c;intint x,y,p;x,y,p;x=0;x=0;y=radius;y=radius;p=3p=3 2*radius2*radius；while(xwhile(xy)y)plot_circle_points(xc,yc,x,y,cplot_circle_points(xc,yc,x,y,c););if(pif(p0)p=p+4*x+6;F(xi,yi)向右-向圆外Pi在圆外时-F(xi,yi)0-向下-向圆内2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法即求得Pi点后选择下一个象素点Pi+1的规则为：u当F(xi,yi)0 取xi+1=xi+1，yi+1=yi;u当F(xi,yi)0 取xi+1=xi，yi+1=yi-1;这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi)时正时负，故称正负法。快速计算的关键是F(xi,yi)的计算，能否采用增量算法？2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法若F(xi,yi)已知，计算F(xi+1,yi+1)可分两种情况：1、F(xi,yi)0-xi+1=xi+1，yi+1=yi;-F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2 -=(xi+1)2+yi2-R2=F(xi,yi)+2xi+12、F(xi,yi)0-xi+1=xi，yi+1=yi-1;-F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2 -=xi2+(yi 1)2-R2=F(xi,yi)-2yi+1初始值：略2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法4 生成圆弧的多边形逼近法I.圆的内接正多边形迫近法II.圆的等面积正多边形迫近法2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法圆的内接正多边形逼近法思想：当一个正多边形的边数足够多时，该多边形可思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。以和圆无限接近。即即因此，在允许的误差范围内，可以用正多边形代替圆。因此，在允许的误差范围内，可以用正多边形代替圆。设内接正设内接正n边形的顶点为边形的顶点为Pi(xi,yi),Pi的幅角为的幅角为 i,每一每一条边对应的圆心角为条边对应的圆心角为a，则有，则有xi=Rcos i yi=Rsin i2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法 内接正内接正n边形代替圆边形代替圆计算多边形各顶点的递推公式计算多边形各顶点的递推公式 Xi+1 Rcos(a+i)=Yi+1 Rsin(a+i)Xi+1 cos a-sin a Xi =Yi+1 sin a cosa Yi因为因为:a是常数，是常数，sin a，cosa只在开始时计算一次所以，一个只在开始时计算一次所以，一个顶点只需顶点只需4次乘法，共次乘法，共4n次乘法，外加直线段的中点算法的计算量。次乘法，外加直线段的中点算法的计算量。2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法圆的等面积正多边形逼近法当用内接正多边形逼近圆时，其面积要小于当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。边形和圆弧相交，称之为圆的等面积正多边形。2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法圆的等面积正多边形逼近法步骤：l求多边形径长，从而求所有顶点坐标值l由逼近误差值，确定边所对应的圆心角2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法5 椭圆的扫描转换F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为上下两部分，以切线斜率为-1的点作为分界点。的点作为分界点。椭圆上一点处的法向：椭圆上一点处的法向：N(x,y)=(F)x i +(F)y j =2b2 x i +2a2 y j2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M22.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2在当前中点处，法向量（在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5)的的y分量比分量比x分量大分量大,即：即：b2(Xp+1)a2(Yp-0.5),而在下一中点，不等式而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分改变方向，则说明椭圆弧从上部分转入下部分2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法椭圆的中点画法与圆弧中点算法类似：确定一个象素后，接着在两与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点。号确定更近的点。先讨论椭圆弧的上部分先讨论椭圆弧的上部分设设(X Xp p，Y Yp p)已确定，则下一待选像素的中点是已确定，则下一待选像素的中点是(X(Xp p+1,Y+1,Yp p-0.5)-0.5)d d1 1=F(X=F(Xp p+1,Y+1,Yp p-0.5)=b-0.5)=b2 2(X(Xp p+1)+1)2 2+a+a2 2(Y(Yp p-0.5)-0.5)2 2-a-a2 2b b2 22.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法 根据根据d1 1的符号来决定下一像素是取正右方的那个，还是右的符号来决定下一像素是取正右方的那个，还是右下方的那个。下方的那个。若若d1 10，中点在椭圆内，取正右方象素，判别式更新为：，中点在椭圆内，取正右方象素，判别式更新为：d1 1=F(Xp p+2,Yp p-0.5)=d1 1+b2(2Xp p+3)d1 1的增量为的增量为b2(2Xp p+3)当当d1 10，中点在椭圆外，取右下方象素，更新判别式：，中点在椭圆外，取右下方象素，更新判别式：d1 1=F(Xp p+2,Yp p-1.5)=d1 1+b2(2Xp p+3)+a2(-2Yp p+2)d1 1的增量为的增量为b2(2Xp p+3)+a2(-2Yp p+2)2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法 d1 1的初始条件：椭圆弧起点为(0，b)；第一个中点为(1,b-0.5)初始判别式：d1010=F(1,b-0.5)=b*b+a*a(-b+0.25)转入下一部分，下一象素可能是正下方或右下方，此时判别式要初始化。d2 2=F(Xp p+0.5,Yp p-1)=b2(Xp p+0.5)2+a2(Yp p-1)2-a2b2 若d2 2=0,取正下方像素，则d2 2=F(Xp p+0.5,Yp p-2)=d2 2+a2(-2Yp p+3)下半部分弧的终止条件为 y=02.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法程序：程序：MidpointEllipe(a,b,color)inta,b,color;intx,y;floatd1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(x,y,color);while(b*b*(x+1)a*a*(y-0.5)if(d10)if(d20)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-；elsed2+=a*a*(-2*y+3);y-;putpixel(x,y,color);第二章第二章 基本图形生成算法基本图形生成算法2.1 2.1 直线的生成算法直线的生成算法2.2 2.2 圆（椭圆）的生成算法圆（椭圆）的生成算法2.3 2.3 区域填充算法区域填充算法2.4 2.4 线宽与线型处理线宽与线型处理2.5 2.5 字符的生成字符的生成2.6 2.6 图形裁剪图形裁剪2.7 2.7 反走样技术反走样技术2.3 2.3 区域填充算法区域填充算法1基础知识基础知识区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。赋予指定的颜色代码。区域填充中最常用的是多边形填色。多边形的表示方法多边形的表示方法u顶点表示顶点表示u点阵表示点阵表示(内点表示内点表示)2.3 2.3 区域填充算法区域填充算法多边形分为凸多边形、凹多边形、含内环的多边形。2.3 2.3 区域填充算法区域填充算法扫描线与多边形相交光栅化后直线变成离散点 多边形填色一个首要的问题，是判断一个像素是在多边形多边形填色一个首要的问题，是判断一个像素是在多边形内还是多边形外。数学上提供的方法是内还是多边形外。数学上提供的方法是“扫描交点的奇偶数判扫描交点的奇偶数判断法断法”。1基础知识基础知识(续）续）1 基础知识基础知识(续）续）-逐点判断算法逐点判断算法算法原理：逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部。voidFillPolygonPbyP(Polygon*P,intpolygonColor)intx,y;for(y=ymin;y=ymax;y+)for(x=xmin;x=xmax;x+)if(IsInside(P,x,y)PutPixel(x,y,polygonColor);elsePutPixel(x,y,backgroundColor);/*endofFillPolygonPbyP()*/问题：如何判别点(x,y)关于多边形区域P的内外关系？（1）射线法（2）累计角度法（3）编码算法（略）（1）射线法 步骤：*从待判别点v发出射线*求交点个数k*k 的奇偶性决定了点与多边形的内外关系（2 2）累计角度法）累计角度法步骤：步骤：*从从v点向多边形点向多边形P顶点顶点发出射线，形成有向角发出射线，形成有向角*计算有相交的和，得计算有相交的和，得出结论出结论奇异情况处理优点：简单缺点：计算量大，速度慢。2.3 2.3 区域填充算法区域填充算法1基础知识基础知识(续）续）填色算法分为两大类：填色算法分为两大类：扫描线填色扫描线填色(Scan-Line Filling)(Scan-Line Filling)算法。这类算法建立在多边形边算法。这类算法建立在多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互填色。界的矢量形式数据之上，可用于程序填色，也可用于交互填色。种子填色种子填色(Seed Filling)(Seed Filling)算法。这类算法建立在多边形边界的图像算法。这类算法建立在多边形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。所以，它一般只形式数据之上，并还需提供多边形边界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。能用于人机交互填色，而难以用于程序填色。2.3 2.3 区域填充算法区域填充算法2扫描线填色算法扫描线填色算法基本思想：基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。显示这些区间的象素，即完成填充工作。对于一条扫描线填充过程可以分为四个步骤：对于一条扫描线填充过程可以分为四个步骤：（1）求交）求交（2）排序）排序（3）配对）配对（4）填色）填色2.3 2.3 区域填充算法区域填充算法2扫描线填色算法扫描线填色算法算法的基本思想。算法的基本思想。多边形以多边形以n n、x_arrayx_array、y_arrayy_array的形式给出，其中，的形式给出，其中，x_arrayx_array、y_arrayy_array中存放着多边形的中存放着多边形的n n个顶点的个顶点的x x，y y坐标。坐标。用水平扫描线从上到下扫描由点线段用水平扫描线从上到下扫描由点线段构成的多段定义成的多边形。每根扫构成的多段定义成的多边形。每根扫描线与多边形各边产生一系列交点。描线与多边形各边产生一系列交点。这些交点按照这些交点按照x x坐标进行分类，将分坐标进行分类，将分类后的交点成对取出，作为两个端点，类后的交点成对取出，作为两个端点，以所需要填的色彩画水平直线。多边以所需要填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。形被扫描完毕后，填色也就完成。2.3 2.3 区域填充算法区域填充算法2扫描线填色算法扫描线填色算法(续）续）上述基本思想中，有几个问题需要解决或改进：左、右顶点处理。当以1、2、3的次序画多边形外框时，多边形的左顶点和右顶点如右图中所示的顶点2。它们具有以下性质。左顶点2：y1y2y2y3其中y1、y2、y3是3个相邻的顶点的y坐标。多边形的顶点当扫描线与多边形的每个顶点相交时，会同时产生2个交点。这时，填色就会因扫描交点的奇偶计数出错而出现错误。因此，对所有左、右顶点作如下处理：2.3 2.3 区域填充算法区域填充算法2扫描线填色算法扫描线填色算法(续）续）左、右顶点的入边(以该顶点为终点的那条边，即12边)之终点删去。对于左顶点，入边端点(x1,y1)、(x2,y2)修改为(x1,y1)、(,y21)；对于右顶点，入边端点(x1,y1)、(x2,y2)修改为(x1,y1)、(,y2+1)；其中，即入边的斜率。对于多边形的上顶点(y2y1、y2y3)或下顶点(y2y1、y2 i 结点的结点的x值递增值递增 x；若允许多边形的边自相交，则用冒泡排序法对若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；表重新排序；/*polyfill*/2扫描线填色算法扫描线填色算法(续）续）2.3 2.3 区域填充算法区域填充算法边界标志算法边界标志算法基本思想：基本思想：u帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。边形边界所经过的象素打上标志。u然后再采用和扫描线算法类似的方法将位于多边形内的各个然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。区段着上所需颜色。u使用一个布尔量使用一个布尔量inside来指示当前点是否在多边形内的状态。来指示当前点是否在多边形内的状态。2.3 2.3 区域填充算法区域填充算法算法过程算法过程void edgemark_fill(polydef,color)多边形定义多边形定义 polydef；int color;对多边形对多边形polydef 每条边进行直线扫描转换；每条边进行直线扫描转换；inside=FALSE;for(每条与多边形每条与多边形polydef相交的扫描线相交的扫描线y)for(扫描线上每个象素扫描线上每个象素x)if(象素象素 x 被打上边标志被打上边标志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);else drawpixel(x,y,background);算法算法2 2：（以边为中心的边缘填充算法）（以边为中心的边缘填充算法）1 1、将绘图窗口的背景色置为；、将绘图窗口的背景色置为；2 2、对多边形的每一条非水平边做：、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余从该边上的每个象素开始向右求余栅栏填充算法栅栏填充算法对于每条扫描线与多边形的交点，将交点与栅栏之间的对于每条扫描线与多边形的交点，将交点与栅栏之间的扫描线上的像素取补，也就是说，若交点位于栅栏左边，则扫描线上的像素取补，也就是说，若交点位于栅栏左边，则将交点之右、栅栏之左的所有像素取补；若交点位于栅栏右将交点之右、栅栏之左的所有像素取补；若交点位于栅栏右边，则将栅栏之右、交点之左的所有像素取补。边，则将栅栏之右、交点之左的所有像素取补。多边形外的像素处理大大减少，被重复取补的像素数目多边形外的像素处理大大减少，被重复取补的像素数目也有减少，但仍有一些像素被重复取补。也有减少，但仍有一些像素被重复取补。2.3 2.3 区域填充算法区域填充算法用软件实现时，扫描线算法与边界标志算法的执行速用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。行速度比有序边表算法快一至两个数量级。2.3 2.3 区域填充算法区域填充算法种子填色又称边界填色种子填色又称边界填色(Boundary Filling)(Boundary Filling)。它的功能是，。它的功能是，给出多边形光栅化后的边界位置及边界色代码给出多边形光栅化后的边界位置及边界色代码boundary_colorboundary_color，以及多边形内的一点，以及多边形内的一点(x,y)(x,y)位置，要求将颜色位置，要求将颜色fill_colorfill_color填填满多边形。满多边形。3 3 种子填色算法种子填色算法 2.3 2.3 区域填充算法区域填充算法算法要求区域是连通的算法要求区域是连通的连通性：连通性：4连通、8连通1.4连通：连通：从区域内任意一点出发，从区域内任意一点出发，可通过上、下、左、右可通过上、下、左、右四个方向到达区域内的任意象素；四个方向到达区域内的任意象素；3 3 种