计算机图形学计算机图形学Computer GraphicsComputer Graphics使用班级：地信2009级 王增武 WangZengwucuit.edu.cnTel: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 种子填色算法种子填色算法( (续）续） 2.3 2.3 区域填充算法区域填充算法算法要求区域是连通的算法要求区域是连通的连通性：连通性： 4连通、8连通2.8连通连通从区域内任意一点出发，从区域内任意一点出发，可通过上、下、左、右、左上、可通过上、下、左、右、左上、左下、右上、右下八个方向左下、右上、右下八个方向到达区域内的任意象素；到达区域内的任意象素； 3 3 种子填色算法种子填色算法( (续）续） 2.3 2.3 区域填充算法区域填充算法4连通与连通与8连通区域的区别连通区域的区别连通性：连通性： 4连通可看作连通可看作8连通区域，但对边界有要求连通区域，但对边界有要求对边界的要求对边界的要求2.3 2.3 区域填充算法区域填充算法种子填色算法种子填色算法实现实现采用栈结构：栈顶出栈出栈象素置成多边形色按左、上、右、下入栈边界表示的边界表示的4连通区域连通区域void BoundaryFill4(int x,int y,int oldColor,int newColor)int color;color = GetPixel(x,y);if(color != boundaryColor) & (color != newColor)PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/2.3 2.3 区域填充算法区域填充算法扫描线填色、种子填色算法扫描线填色、种子填色算法比较比较不同点：不同点：1.基本思想不同；前者是顶点表示转换成点阵表示，基本思想不同；前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。后者只改变区域内填充颜色，没有改变表示方法。2.对边界的要求不同对边界的要求不同前者只要求扫描线与多边形边界交点个数为偶数。后前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。者：区域封闭，防止递归填充跨界。3.基本的条件不同基本的条件不同前者：从边界顶点信息出发。前者：从边界顶点信息出发。后者：区域内种子点。后者：区域内种子点。圆域的填充 对每条扫描线，计算它与圆域的相交区间。接着，为每一条扫描线建立一个新圆表，存放在该行第一次出现的圆的有关信息。然后，为当前扫描线设置一个活化圆表。由于一条线与一个圆只能相交一个区间，所以在活性圆表中，每个圆只需一个结点即可。结点内存放当前扫描线的区间端点，以及用于计算下一条扫描线与圆相交的区间端点所需的增量。该增量用于在当前扫描线处理完毕之后，对端点坐标进行更新计算，以便得到下一条扫描线的区间端点。区域填充属性1填充样式2填充颜色3填充图案四种填充方法：(1)均匀着色方法：将图元内部像素置成同一颜色(2)位图不透明：若像素对应的位图单元为1，则以前景色显示该像素；若为0，则以背景色显示该像素；(3)位图透明：若像素对应的位图单元为1，则以前景色显示该像素；若为0，则不做任何处理。(4)像素图填充：以像素对应的像素图单元的颜色值显示该像素。基本问题基本问题关键是建立区域与图像间的对应关系关键是建立区域与图像间的对应关系方法方法1：建立整个绘图空间与图像空间的：建立整个绘图空间与图像空间的1-1映射映射方法方法2：建立区域局部坐标空间与图像空间的：建立区域局部坐标空间与图像空间的1-1映射映射适用：动画中漫游图像例，透过车窗看外景建立区域局部坐标空间与图像空间的建立区域局部坐标空间与图像空间的1-1映射映射第二章第二章 基本图形生成算法基本图形生成算法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.4 2.4 线宽与线型处理线宽与线型处理1.直线的线宽处理2.圆弧线宽处理3.线型处理第二章第二章 基本图形生成算法基本图形生成算法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.5 2.5 字符的生成字符的生成1点阵式字符点阵式字符点阵式字符将字符形状表示为一个矩形点阵，由点阵中点的不点阵式字符将字符形状表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。同值表达字符的形状。使用点阵式字符时，需将字库中的矩形点阵复制到缓冲器中指使用点阵式字符时，需将字库中的矩形点阵复制到缓冲器中指定的单元中去。在复制过程中，可以施加变换，以获得简单的变化。定的单元中去。在复制过程中，可以施加变换，以获得简单的变化。点阵式字符及其变化2.5 2.5 字符的生成字符的生成2矢量式字符矢量式字符矢量式字符将字符表达为点坐标的序列，相邻两点表示一条矢量，矢量式字符将字符表达为点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻画。下图字符的形状便由矢量序列刻画。下图表表示出用矢量式表示的字符示出用矢量式表示的字符“B B”。“B B”是由顶点序列是由顶点序列 a a, , b b, , c c, , d d, , e e, , f f, , e e, , g g, , h h, , i i, , j j, , k k, ,j j, , a a, , l l 的坐标表达。的坐标表达。矢量式表示字符矢量式表示字符“B B”2.5 2.5 字符的生成字符的生成3方向编码式字符方向编码式字符方向编码式字符用有限的若干种方向编码来表达一个方向编码式字符用有限的若干种方向编码来表达一个字符。字符。 “B B”：8 8方向编码方向编码00001234440001234444066660000123444000123444406666。2.5 2.5 字符的生成字符的生成4 4 轮廓字形技术轮廓字形技术 直接使用点阵式字符方法将耗费巨大的存储空间。直接使用点阵式字符方法将耗费巨大的存储空间。压缩方法有多种，最简单的有黑白段压缩法。另一种方法是部件压缩方法有多种，最简单的有黑白段压缩法。另一种方法是部件压缩法。三是轮廓字形法，这种方法压缩比大，且能保证字符质，压缩法。三是轮廓字形法，这种方法压缩比大，且能保证字符质，是当今国际上最流行的一种方法。是当今国际上最流行的一种方法。轮廓字形法采用直线、或者二次轮廓字形法采用直线、或者二次BezierBezier曲线、三次曲线、三次BezierBezier曲线的曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义和一些指示横宽、竖宽、基点、基线等的控制信息，区域。轮廓线定义和一些指示横宽、竖宽、基点、基线等的控制信息，就构成了字符的压缩数据。就构成了字符的压缩数据。第二章第二章 基本图形生成算法基本图形生成算法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.6 2.6 图形裁剪图形裁剪裁剪裁剪(clipping)(clipping)是裁去窗口之外物体或物体部分的一是裁去窗口之外物体或物体部分的一种操作。种操作。2.6.1直线的剪裁直线的剪裁 Cohen-Sutherland算法、中点分割裁剪算法、算法、中点分割裁剪算法、 Barsky算法算法2.6.2多边形的剪裁多边形的剪裁 Sutlerland_Hodgman算法算法2.6.3字符串的剪裁字符串的剪裁 2.6 2.6 图形裁剪图形裁剪1直线的剪裁直线的剪裁直线和窗口的关系可以分为如下直线和窗口的关系可以分为如下3 3类：类： 整条直线在窗口内。此时，不需剪裁，显示整条直线。整条直线在窗口内。此时，不需剪裁，显示整条直线。 整条直线在窗口外，此时，不需剪裁，不显示整条直线。整条直线在窗口外，此时，不需剪裁，不显示整条直线。部分直线在窗口内，部分直线在窗口外。此时，需要求出直线与窗部分直线在窗口内，部分直线在窗口外。此时，需要求出直线与窗框的交点，并将窗口外的直线部分剪裁掉，显示窗口内的直线部分。框的交点，并将窗口外的直线部分剪裁掉，显示窗口内的直线部分。2.6 2.6 图形裁剪图形裁剪1直线的剪裁直线的剪裁 直线剪裁算法有两个主要步骤。首先将不需剪裁的直线直线剪裁算法有两个主要步骤。首先将不需剪裁的直线挑出，即删去挑出，即删去 在窗外的直线。然后，对其余直线，逐条与在窗外的直线。然后，对其余直线，逐条与窗框求交点，并将窗口外的部分删去。窗框求交点，并将窗口外的部分删去。2.6 2.6 图形裁剪图形裁剪1直线的剪裁（续）直线的剪裁（续）Cohen-SutherlandCohen-Sutherland直线剪裁算法直线剪裁算法以区域编码为基础，将窗口及其周围的以区域编码为基础，将窗口及其周围的8 8个方向以个方向以4 bit4 bit的二进制数进行编码。的二进制数进行编码。如图所示的编码方法将窗口及其邻域如图所示的编码方法将窗口及其邻域分为分为5 5个区域：个区域： 内域：区域内域：区域(0000)(0000)。 上域：区域上域：区域(1001, 1000, 1010)(1001, 1000, 1010)。 下域：区域下域：区域(0101, 0100, 0110)(0101, 0100, 0110)。 左域：区域左域：区域(1001, 0001, 0101)(1001, 0001, 0101)。右域：右域：区域区域(1010, 0010, 0110)(1010, 0010, 0110)。 2.6 2.6 图形裁剪图形裁剪1直线的剪裁（续）直线的剪裁（续）当线段的两个端点的编码的当线段的两个端点的编码的逻辑逻辑“与与”非零非零时时 ，线段为显然不可见的，线段为显然不可见的 对对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右；下、左、右；2.6 2.6 图形裁剪图形裁剪1直线的剪裁（续）直线的剪裁（续）算法的主要思想是，对每条直线算法的主要思想是，对每条直线P P1 1P P2 2： 对直线两端点对直线两端点P P1 1、P P2 2编码分别记为编码分别记为C C1 1( (P P1 1)=)=a a1 1, , b b1 1, , c c1 1, , d d1 1 ，C C2 2( (P P2 2)=)=a a2 2, , b b2 2, , c c2 2, , d d2 2 其中，其中，a ai i、b bi i、c ci i、d di i取值范取值范围为围为1, 01, 0，i i1, 21, 2。 如果如果a ai i= =b bi i= =c ci i= =d di i=0=0，则显示整条直，则显示整条直线，取出下一条直线，返步骤线，取出下一条直线，返步骤(1)(1)。否则。否则，进入步骤，进入步骤(3)(3)。如果如果| |a a1 1 a a2 2|=1|=1，则求直线与窗上边，则求直线与窗上边( (y y= =y yw w-max-max) )的交点，并删去交的交点，并删去交点以上部分。如果点以上部分。如果| |b b1 1 b b2 2|=1|=1，| |c c1 1 c c2 2= |= |1 1，| |d d1 1 d d2|2|=1=1，作类似处，作类似处理。理。 返步骤返步骤(1)(1)。中点分割裁剪算法中点分割裁剪算法基本思想：基本思想：从从P P0 0点出发找出离点出发找出离P P0 0最近的可见点，和从最近的可见点，和从P P1 1点出发找出点出发找出离离P P1 1最近的可见点。这两个可见点的连线就是原线段的可见部分。最近的可见点。这两个可见点的连线就是原线段的可见部分。与与Cohen-SutherlandCohen-Sutherland算法一样首先对线段端点进行编码，并把线段算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。第三种情况，用中点分割的方法求出线段与窗口的交点。A A、B B分别为分别为距距P P0 0 、 P P1 1最近的可见点，最近的可见点，P Pm m为为P P0 0P P1 1中点。中点。 中点分割算法中点分割算法- -求求线线段与窗口的交点段与窗口的交点从从P P0 0出发找距离出发找距离P P0 0最近可见点采用中点分割方法最近可见点采用中点分割方法先求出先求出P P0 0P P1 1的中点的中点P Pm m, ,若若P P0 0P Pm m不是显然不可见的，并且不是显然不可见的，并且P P0 0P P1 1在窗口中有可见部分，则在窗口中有可见部分，则距距P P0 0最近的可见点一定落在最近的可见点一定落在P P0 0P Pm m上，所以用上，所以用P P0 0P Pm m代替代替P P0 0P P1 1；否则取否则取P Pm mP P1 1代替代替P P0 0P P1 1。再对新的再对新的P P0 0P P1 1求中点求中点P Pm m。重复上述过程，直到。重复上述过程，直到P Pm mP P1 1长度小于给长度小于给定的控制常数为止，此时定的控制常数为止，此时P Pm m收敛于交点。收敛于交点。从从P1P1出发找距离出发找距离P P1 1最近可见点采用上面最近可见点采用上面类似方法。类似方法。中点分割裁剪算法对分辩率为对分辩率为2N*2N的显示器，上述二分过程至多进行的显示器，上述二分过程至多进行N次。次。主要过程只用到加法和除法运算，适合硬件实现，主要过程只用到加法和除法运算，适合硬件实现，它可以它可以用左右移位来代替乘除法，这样就大大加快了速度用左右移位来代替乘除法，这样就大大加快了速度。中点分割裁剪算法中点分割裁剪算法 设要裁剪的线段是设要裁剪的线段是P P0 0P P1 1。 P P0 0P P1 1和窗口边界交于和窗口边界交于A,B,C,DA,B,C,D四点。算法四点。算法的基本思想是从的基本思想是从A,BA,B和和P P0 0三点中找出三点中找出最靠近的最靠近的P P1 1点，图中要找的点是点，图中要找的点是P P0 0。从从C,DC,D和和P P1 1中找出最靠近中找出最靠近P P0 0的点。图的点。图中要找的点是中要找的点是C C点。那么点。那么P P0 0C C就是就是P P0 0P P1 1线段上的可见部分。线段上的可见部分。梁友栋梁友栋- -BarskyBarsky算法算法梁友栋梁友栋- -BarskyBarsky算法算法 线段的线段的参数表示参数表示x=x0+t xy=y0+t y 0=t tl,则可见线段区间则可见线段区间 tl , tut0t1t2t301梁友栋梁友栋- -BarskyBarsky算法：算法：交点计算交点计算梁友栋梁友栋- -BarskyBarsky算法算法始边和终边的确定及交点计算：始边和终边的确定及交点计算：令令 Q QL L= - x D= - x DL L= x= x0 0-x-xL L Q QR R= x D= x DR R= x= xR R-x-x0 0 Q QB B= - y D= - y DB B= y= y0 0-y-yB B Q QT T= y D= y DT T= y= yT T-y-y0 0交点为交点为 t ti i= = D Di i / / Q Qi i i=L,R,B,Ti=L,R,B,TQ Qi i 0 0 0 t ti i为与终边交点参数为与终边交点参数Q Qi i =0 =0 D Di i 0 0 0 时时, , 分析另一分析另一D, D, 梁友栋梁友栋- -BarskyBarsky算法算法当当Q Qi i =0=0时时 若若D Di i 0 0 时时, ,线段不可见线段不可见（如图中（如图中ABAB，有，有Q QR R=0=0，D DR R00 0 时时, , 分析另一分析另一D, D, （如图中的（如图中的EFEF就是这种情况，它使就是这种情况，它使Q QL L=0=0，D DL L00和和Q QR R=0=0，D DR R00。这时由于。这时由于EFEF和和x=x=x xL L及及x=x=x xR R平行，故不必去平行，故不必去求出求出EFEF和和x=x=x xL L及及x=x=x xR R的交点，而让的交点，而让EFEF和和y=y=y yT T及及y=y=y yB B的交的交点决定直线段上的可见部分。）点决定直线段上的可见部分。） EFAB2多边形的剪裁多边形的剪裁 多边形剪裁算法的关键在于，通过剪裁，要保持窗口内多边形的边界部多边形剪裁算法的关键在于，通过剪裁，要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态，以便填色算法得以正确实现而使剪裁后的多边形的边仍然保持封闭状态，以便填色算法得以正确实现( (如下如下图图(c)(c)。2多边形的剪裁多边形的剪裁（续）（续）思路：将多边形的各边先相对于窗口的某一条边界进行裁思路：将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。次，便可得到最终结果。Sutherland-Sutherland-HodgmanHodgman算法算法Sutherland-Hodgman算法分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入。逐边裁剪算法逐边裁剪算法2多边形的剪裁多边形的剪裁（续）（续）实现方法：实现方法：设置二个表设置二个表 输入顶点表输入顶点表( (向量向量) )用于存放被裁剪多边形的顶点用于存放被裁剪多边形的顶点p p1 1-p-pm m。 输出顶点表输出顶点表( (线性链表线性链表) )用于存放裁剪过程中及结果的顶用于存放裁剪过程中及结果的顶点点 q q1 1-q-qn n。输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。针或逆时针方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。裁剪。Sutherland-Sutherland-HodgmanHodgman算法算法2多边形的剪裁多边形的剪裁（续）（续）具体操作：具体操作： P Pi i 若位于边界线的可见一侧，则若位于边界线的可见一侧，则 P Pi i 送输出顶点表送输出顶点表 P Pi i 若位于边界线的不可见一侧，则将其舍弃。若位于边界线的不可见一侧，则将其舍弃。 除第一个顶点外，还要检查每一个除第一个顶点外，还要检查每一个 P Pi i 和前一顶点和前一顶点 P Pi-1i-1是否位于窗口是否位于窗口边界的同一侧，若不在同一侧，则需计算出交点送输出顶点表。边界的同一侧，若不在同一侧，则需计算出交点送输出顶点表。 最后一个顶点最后一个顶点 P Pn n则还要与则还要与 P P1 1 一起进行同样的检查。一起进行同样的检查。p1p2p3p4p5q1q2q3q42多边形的剪裁多边形的剪裁（续）（续）q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：裁剪前：裁剪后：裁剪后：输入顶点表：输入顶点表：p1p2p3p4p5输入顶点表输入顶点表:不变不变输出顶点表：输出顶点表：空空输出顶点表输出顶点表:q1q2p3q7q8q5q6q4q3Sutherland-Hodgman算法考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分两个部分: :可见一侧；不可见一侧。可见一侧；不可见一侧。多边形的各条边的两端点多边形的各条边的两端点S S、P P。它们与裁剪线的位置关系只。它们与裁剪线的位置关系只有四种有四种Sutherland-Hodgman算法情况（情况（1 1）仅输出顶点）仅输出顶点P P；情况（情况（2 2）输出）输出0 0个顶点；个顶点；情况（情况（3 3）输出线段）输出线段SPSP与裁剪线的交点与裁剪线的交点I I；情况（情况（4 4）输出线段）输出线段SPSP与裁剪线的交点与裁剪线的交点I I和终点和终点P PSutherland-Hodgman算法框图 处理线段SP过程子框图Sutherland-Hodgman算法u上述算法仅用一条裁剪边对多边形进行裁剪，得到一上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。个顶点序列，作为下一条裁剪边处理过程的输入。u对于每一条裁剪边，算法框图同上，只是判断点在窗对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段口哪一侧以及求线段SPSP与裁剪边的交点算法应随之改变。与裁剪边的交点算法应随之改变。多边形裁剪错觉：直线段裁剪的组合？错觉：直线段裁剪的组合？新的问题新的问题：1）边界不再封闭，需要用窗口边界的恰当部）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？分来封闭它，如何确定其边界？多边形裁剪2）一个凹多边形可能被裁剪成几个小的多边形，如何）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？确定这些小多边形的边界？Sutherland-Hodgman算法思考：l如何推广到任意凸多边形l裁剪窗口？Sutherland-Hodgeman算法对凸多边形应用本算法可以得到正确对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着点表，所以表中最后一个顶点总是连着第一个顶点。第一个顶点。Sutherland-Hodgeman算法解决这个问题有多种方法，一是把凹解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是正确的连接顶点对。再有就是WeilerWeiler- -AthertonAtherton算法。算法。Weiler-Athenton算法裁剪窗口为任意多边形（裁剪窗口为任意多边形（凸、凹、带内环）的情况：的情况：主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B Weiler-Athenton算法多边形顶点的排列顺序（使多边形区域位于有向边的左侧多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外）外环：逆时针环：逆时针 ；内环：顺时针；内环：顺时针主多边形和裁剪多边形把二维平面分成两部分。主多边形和裁剪多边形把二维平面分成两部分。内裁剪：内裁剪：AB外裁剪：外裁剪：A-B裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界Weiler-Athenton算法如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：为如下两类：进点：主多边形边界由此进入裁剪多边形内进点：主多边形边界由此进入裁剪多边形内 如，如，I1,I3, I5, I7, I9, I11出点：主多边形边界由出点：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域. 如，如， I0,I2, I4, I6, I8, I10 Weiler-Athenton算法1）建顶点表；2）求交点；3）裁剪1 1、建立主多边形和裁剪多边的顶点表、建立主多边形和裁剪多边的顶点表2 2、求主多边形和裁剪多边形的交点，并将这些交点按顺序、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针间建立双向指针 。3 3、裁剪、裁剪: : 如果存在没有被跟踪过的交点，执行以下步骤：如果存在没有被跟踪过的交点，执行以下步骤： Weiler-Athenton算法Weiler-Athenton算法 (1)建立空的裁剪结果多边形的顶点表建立空的裁剪结果多边形的顶点表 (2)选取任一没有被跟踪过的交点为始点，将选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中其输出到结果多边形顶点表中 (3)如果该交点为进点，跟踪主多边形边边界；如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界否则跟踪裁剪多边形边界 (4) 跟踪多边形边界，每遇到多边形顶点，跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇将其输出到结果多边形顶点表中，直至遇到新的交点到新的交点 (5)将该交点输出到结果多边形顶点表中，并将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多跟踪裁剪多边形边界，现在改为跟踪主多边形边界）边形边界） (6)重复重复(4)、(5)直至回到起点直至回到起点取取I7为起点，所得裁剪结果多边形为起点，所得裁剪结果多边形I7I0q0I3I4I5I6I7。取。取I8为起点，所得裁剪结果为起点，所得裁剪结果多边形为多边形为I8I9I10I11I2q2I1I8。Weiler-AthentonWeiler-Athenton算法算法交点的奇异情况处理交点的奇异情况处理 1、与裁剪多边形的边重合的主多边形的边不参与求交点；、与裁剪多边形的边重合的主多边形的边不参与求交点；2、对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁、对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点该顶点不看作交点 3 3 字符串的剪裁字符串的剪裁 字符串剪裁有字符串剪裁有3 3种可选择的方法。种可选择的方法。 字符串的有或无剪裁字符串的有或无剪裁 (all-or-none-text) 字符的有或无剪裁字符的有或无剪裁 (all-or-none-character)(all-or-none-character)字符的精密剪裁字符的精密剪裁第二章第二章 基本图形生成算法基本图形生成算法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.7 2.7 反走样技术反走样技术温故而知新本章重点本章重点直线的生成算法、圆（椭圆）的生成算法直线的生成算法、圆（椭圆）的生成算法区域填充算法区域填充算法图形裁剪图形裁剪作业