基本图形生成算法.ppt

《基本图形生成算法.ppt》由会员分享，可在线阅读，更多相关《基本图形生成算法.ppt（142页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 直线、圆、椭圆生成算法直线、圆、椭圆生成算法图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。计算机图形学计算机图形学图形显示前需要：扫描转换图形显示前需要：扫描转换+裁剪裁剪裁剪裁剪-扫描转换：最常用，节约计算时间。扫描转换：最常用，节约计算时间。扫描转换扫描转换-裁剪：

2、算法简单；裁剪：算法简单；计算机图形学计算机图形学本章内容本章内容扫描转换直线段 DDA算法 中点画线法 Bresenham画线算法圆弧、椭圆弧扫描转换 中点算法 计算机图形学计算机图形学直线段的扫描转换算法直线段的扫描转换算法l直线的扫描转换:确定最佳逼近于该直线确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这的一组象素，并且按扫描线顺序，对这些象素进行写操作。些象素进行写操作。l三个常用算法：三个常用算法：数值微分法（数值微分法（DDA）中点画线法中点画线法Bresenham算法。算法。计算机图形学计算机图形学数值微分法（）数值微分法（）假定直线的起点、终点分别为：（假定直线的起点、

3、终点分别为：（x0,y0),(x1,y1)，且都为整数。，且都为整数。(X i+1,Yi+k)(X i,Int(Yi+0.5)(X i,Yi)栅格交点表示象素点位置。计算机图形学计算机图形学数值微分数值微分(DDA)法法l基本思想基本思想已知过端点已知过端点P0(x0,y0),P1(x1,y1)的直线段的直线段Ly=kx+b直线斜率为直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。和一次舍入运算。计算机图形学计算机图形学数值微分数值微分(DDA)法法计算计算yi+1i+1=kxi+1i+1+b =kxi i+b+

4、k x =yi i+k x 当当 x=1;yi+1 i+1=yi i+k l即：当即：当x每递增每递增1，y递增递增k(即直线斜率即直线斜率)；l注意上述分析的算法仅适用于注意上述分析的算法仅适用于k 1的情形。的情形。在这种情况下，在这种情况下，x每增加每增加1,y最多增加最多增加1。l当当 k 1时，必须把时，必须把x，y地位互换地位互换计算机图形学计算机图形学数值微分数值微分(DDA)法法l增量算法：在一个迭代算法中，如果每增量算法：在一个迭代算法中，如果每一步的一步的x、y值是用前一步的值加上一个值是用前一步的值加上一个增量来获得，则称为增量算法。增量来获得，则称为增量算法。lDDA算

5、法就是一个增量算法。算法就是一个增量算法。计算机图形学计算机图形学数值微分数值微分(DDA)法法void DDALine(int x0 0,int y0 0,int x1 1,int y1 1,int color)int x；float dx,dy,y,k;dx x,=x1 1-x0 0,dy y=y1 1-y0 0;k=dy/dx,y=y0 0;for(x=x0 0;x x1 1,x+)drawpixel(x,int(y+0.5),color);y=y+k;计算机图形学计算机图形学数值微分数值微分(DDA)法法l例：画直线段例：画直线段P0(0,0)-P1(5,2)x int(y+0.5)y

6、+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5计算机图形学计算机图形学数值微分数值微分(DDA)法法l缺点：缺点：在此算法中，在此算法中，y、k必须是必须是float，且每，且每一步都必须对一步都必须对y进行舍入取整，不利于硬件实进行舍入取整，不利于硬件实现。现。计算机图形学计算机图形学中点画线法中点画线法l原理：原理：假定直线斜率0K P2 2离直线更近更近离直线更近更近-取取P2 2。M在在Q的上方的上方-P1 1离直线更近更近离直线更近更近-取取P1 1M与与Q重合，重合，P1 1、P2 2任取一点。任取一点。问题：如何判

7、断问题：如何判断M与与Q点的关系？点的关系？计算机图形学计算机图形学中点画线法中点画线法假设直线方程为：假设直线方程为：ax+by+c=0其中其中a=y0 0-y1 1,b=x1 1-x0 0,c=x0 0y1 1-x1 1y0 0由常识知：由常识知：欲欲判判断断M点点是是在在Q点点上上方方还还是是在在Q点点下下方方，只需把只需把M代入代入F(x,y),并检查它的符号。并检查它的符号。计算机图形学计算机图形学中点画线法中点画线法构造判别式：构造判别式：d=F(M)=F(xp p+1,yp p+0.5)=a(xp p+1)+b(yp p+0.5)+c当当d0，M在直线在直线(Q点点)上上方，取右

8、方方，取右方P1 1；当当d=0，选，选P1 1或或P2 2均可，均可，约定取约定取P1 1；能否采用增量算法呢？能否采用增量算法呢？计算机图形学计算机图形学中点画线法中点画线法若若d 0-M在直线上方在直线上方-取取P1;此时再下一个象素的判别式为此时再下一个象素的判别式为 d1 1=F(xp p+2,yp p+0.5)=a(xp p+2)+b(yp p+0.5)+c =a(xp p+1)+b(yp p+0.5)+c+a=d+a；增量为增量为a计算机图形学计算机图形学中点画线法中点画线法l若若dM在直线下方在直线下方-取取P2;l此时再下一个象素的判别式为此时再下一个象素的判别式为 d2 2

9、=F(xp p+2,yp p+1.5)=a(xp p+2)+b(yp p+1.5)+c =a(xp p+1)+b(yp p+0.5)+c+a+b=d+a+b；增量为增量为ab计算机图形学计算机图形学中点画线法中点画线法l画线从画线从(x0 0,y0 0)开始，开始，d的初值的初值d0 0=F(x0 0+1,y0 0+0.5)=a(x0 0+1)+b(y0 0+0.5)+c =F(x0 0,y0 0)+a+0.5b=a+0.5b 由于只用由于只用d 的符号作判断，为了只包含整数运算的符号作判断，为了只包含整数运算,可以用可以用2d代替代替d来摆脱小数，提高效率。来摆脱小数，提高效率。计算机图形学

10、计算机图形学中点画线法中点画线法void Midpoint Line(int x0 0,int y0 0,int x1 1,int y1 1,int color)int a,b,d1 1,d2 2,d,x,y;a=y0 0-y1 1,b=x1 1-x0 0,d=2*a+b;d1 1=2*a,d2 2=2*(a+b);x=x0 0,y=y0 0;drawpixel(x,y,color);while(xx1 1)if(d=1d=1就把它减掉，就把它减掉，当当d0.5d0.5的时候就选择的时候就选择(x+1,y+1)(x+1,y+1)否则取下个像素否则取下个像素点为点为(x+1,y)(x+1,y)计

11、算机图形学计算机图形学 程序如下：程序如下：BresenhamLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int x,y,dx,dy;float k,e;int e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;e=-dx;for(i=0;i=0)y+;e=e-1;/;e=e-2*dx;Bresenham画线算法画线算法计算机图形学计算机图形学圆的扫描转换算法圆的扫描转换算法下面仅以圆心在原点、半径下面仅以圆心在原点、半径R为整数的圆为整数的圆为例，讨论圆的生成算法。为例，讨论圆的生成算法。假设圆的方程为：假

12、设圆的方程为：X2 +Y2 =R2计算机图形学计算机图形学圆弧扫描算法圆弧扫描算法lX2 +Y2 =R2Y=Sqrt(R2-X2)在一定范围内，每给定一在一定范围内，每给定一X值，可得一值，可得一Y值。值。当当X取整数时，取整数时，Y须取整。须取整。缺点：浮点运算，开方，缺点：浮点运算，开方，取整，不均匀。取整，不均匀。yx计算机图形学计算机图形学角度角度DDA法法 x=x0+Rcos y=y0+Rsin dx=-Rsin d dy=Rcos d xn+1=x n+dxy n+1=y n+dyxn+1=x n+dx=x n-Rsin d =x n-(y n-y 0)d y n+1=y n+dy

13、=y n+Rcos d =y n+(x n-x 0)d 显然，确定显然，确定x,y的初值及的初值及d 值后，即可以增量方值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。但要采用浮点运算、乘法运算、取整运算。计算机图形学计算机图形学中点画圆法中点画圆法利用圆的对称性，只须讨论利用圆的对称性，只须讨论1/8圆。第二个圆。第二个8分圆分圆P为当前点亮象素，那么，下一个点亮的象素可为当前点亮象素，那么，下一个点亮的象素可能是能是P1（Xp+1，Yp）或）或P2（Xp+1，Yp+1)。MP1P2P（Xp，Yp）计

14、算机图形学计算机图形学中点画圆法中点画圆法构造函数：构造函数：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)MP1P2计算机图形学计算机图形学中点画圆法中点画圆法有如下结论：有如下结论：F（M）M在圆内在圆内-取取P1 F（M）=0-M在圆外在圆外-取取P2为此，可采用如下判别式：为此，可采用如下判别式：MP1P2计算机图形学计算机图形学中点画圆法中点画圆法 d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R

15、2 若若d=0,则则P2 为下一个象素，那么再下一个象素为下一个象素，那么再下一个象素的判别式为：的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2 =d+（2xp+3）+（-2 yp+2）即即d 的增量为的增量为 2(xp-yp)+5.d的初值的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2 =1.25-RMP1P2计算机图形学计算机图形学中点画圆法中点画圆法 MidpointCircle(int r,int color)int x,y;float d;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(

16、xy)if(d F(xi,yi)向右-向圆外Pi在圆外时-F(xi,yi)0-向下-向圆内计算机图形学计算机图形学生成圆弧的正负法生成圆弧的正负法即求得即求得P Pi i点后选择下一个象素点点后选择下一个象素点P Pi+1i+1的规则为：的规则为：当当F(xF(xi i,y,yi i)0 )0 取取x xi+1i+1=x=xi i+1+1，y yi+1i+1=y=yi i;当当F(xF(xi i,y,yi i)0 0 取取x xi+1i+1=x=xi i，y yi+1i+1=y=yi i-1;-1;这样用于表示圆弧的点均在圆弧附近，且使这样用于表示圆弧的点均在圆弧附近，且使F(xF(xi i,

17、y,yi i)时正时负，故称正负法。时正时负，故称正负法。快速计算的关键是快速计算的关键是F(xF(xi i,y,yi i)的计算，能否采用增的计算，能否采用增量算法？量算法？计算机图形学计算机图形学生成圆弧的正负法生成圆弧的正负法l若若F(xF(xi i,y,yi i)已知，计算已知，计算F(xF(xi+1i+1,y,yi+1i+1)可分两种可分两种情况：情况：l1 1、F(xF(xi i,y,yi i)0-x)0-xi+1i+1=x=xi i+1+1，y yi+1i+1=y=yi i;l -F(x -F(xi+1i+1,y,yi+1i+1)=(x)=(xi+1 i+1)2+(y+(yi+1

18、i+1)2-R-R2l -=(x-=(xi i+1)+1)2+y+yi i2 -R-R2=F(x=F(xi i,y,yi i)+2x)+2xi i+1+1l2 2、F(x F(xi i,y,yi i)0-x0-xi+1i+1=x=xi i，y yi+1i+1=y=yi i-1;-1;l -F(x -F(xi+1i+1,y,yi+1i+1)=(x)=(xi+1 i+1)2+(y+(yi+1i+1)2-R-R2l -=x-=xi i2+(y+(yi i 1)1)2-R-R2=F(x=F(xi i,y,yi i)-2y)-2yi i+1+1l3 3、初始值：略、初始值：略计算机图形学计算机图形学生成

19、圆弧的多边形逼近法生成圆弧的多边形逼近法圆的内接正多边形迫近法圆的等面积正多边形迫近法计算机图形学计算机图形学圆的内接正多边形逼近法圆的内接正多边形逼近法l思想：当一个正多边形的边数足够多时，思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即该多边形可以和圆无限接近。即l因此，在允许的误差范围内，可以用正因此，在允许的误差范围内，可以用正多边形代替圆。多边形代替圆。l设内接正设内接正n边形的顶点为边形的顶点为P Pi i(x(xi i,y,yi i),P),Pi i的幅的幅角为角为 i,每一条边对应的圆心角为每一条边对应的圆心角为a，则有，则有lx xi i=Rcos i ly

20、yi i=Rsin i计算机图形学计算机图形学圆的内接正多边形逼近法圆的内接正多边形逼近法 内接正n边形代替圆l计算多边形各顶点的递推公式 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次乘法，外次乘法，外加直线段的中点算法的计算量。加直线段的中点算法的计算量。计算机图形学计算机图形学圆的等面积正多边形逼近法圆的等面积正多边形逼近法l当用内接正多边形逼近圆时，其

21、面积要当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。弧相交，称之为圆的等面积正多边形。计算机图形学计算机图形学圆的等面积正多边形逼近法圆的等面积正多边形逼近法步骤：l求多边形径长，从而求所有顶点坐标值l由逼近误差值，确定边所对应的圆心角计算机图形学计算机图形学椭圆的扫描转换椭圆的扫描转换lF(x,y)

22、=b2x2+a2y2-a2b2=0l椭椭圆圆的的对对称称性性，只只考考虑虑第第一一象象限限椭椭圆圆弧弧生生成成，分分上上下下两两部部分分，以以切切线线斜斜率率为为-1的点作为分界点。的点作为分界点。l椭圆上一点处的法向：椭圆上一点处的法向：N(x,y)=(F)x i +(F)y j =2b2 x i +2a2 y j计算机图形学计算机图形学在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5)的y分量比x分量大,即：b2(Xp+1)a2(Yp-0.5),而在下一中点，不等式改变方向，则说明

23、椭圆弧从上部分转入下部分计算机图形学计算机图形学椭圆的中点画法椭圆的中点画法l与与圆圆弧弧中中点点算算法法类类似似：确确定定一一个个象象素素后后，接接着着在在两两个个候候选选象象素素的的中中点点计计算算一一个个判判别别式式的的值值，由判别式的符号确定更近的点由判别式的符号确定更近的点先讨论椭圆弧的上部分先讨论椭圆弧的上部分设设(Xp，Yp)已已确确定定，则则下下一一待待选选像像素素的的中中点点是是(Xp+1,Yp-0.5)d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2计算机图形学计算机图形学 根根据据d1的的符符号号来来决决定定下下一一像像素素是是取取

24、正正右右方方的的那那个个，还是右上方的那个。还是右上方的那个。l若若d10，中中点点在在椭椭圆圆内内，取取正正右右方方象象素素，判判别别式更新为：式更新为：d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量为的增量为b2(2Xp+3)l当当d10，中中点点在在椭椭圆圆外外，取取右右下下方方象象素素，更更新新判判别式：别式：d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)d1的增量为的增量为b2(2Xp+3)+a2(-2Yp+2)计算机图形学计算机图形学l d1的初始条件：椭圆弧起点为的初始条件：椭圆弧起点为(0，b)；l第一个中点为第一个中

25、点为(1,b-0.5)初始判别式：初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)l转转入入下下一一部部分分，下下一一象象素素可可能能是是正正下下方方或或右右下下方，此时判别式要初始化。方，此时判别式要初始化。d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若若d2=0,取正下方像素，则取正下方像素，则d2=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)下半部分弧的终止条件为下半部分弧的终止条件为 y=0计算机图形学计算机图形学区域填充算法区域填充算法l区域指已经表示成点阵形式的填充图形，指已经表示成点阵形式的填充图

26、形，它是象素的集合。它是象素的集合。l区域填充指先将区域的一点赋予指定的指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的过程。区域填充算法要求区域是连通的计算机图形学计算机图形学区域填充区域填充l表示方法：内点表示、边界表示内点表示、边界表示l内点表示枚举处区域内部的所有像素枚举处区域内部的所有像素内部的所有像素着同一个颜色内部的所有像素着同一个颜色边界像素着与内部像素不同的边界像素着与内部像素不同的颜色颜色l边界表示枚举出边界上所有的像素枚举出边界上所有的像素边界上的所有像素着同一颜色边界上的所有像素着同一颜色内

27、部像素着与边界像素不同的颜色内部像素着与边界像素不同的颜色计算机图形学计算机图形学边界填充算法边界填充算法计算机图形学计算机图形学2.3 多边形的扫描转换与区域填充多边形有两种重要的表示方法：多边形有两种重要的表示方法：顶点表示和表示和点阵表示。表示。多边形的扫描转换:把多边形的顶点表示转换把多边形的顶点表示转换为点阵表示。为点阵表示。区域可采用内点表示和边界表示两种表示形区域可采用内点表示和边界表示两种表示形式。式。区域填充:指先将区域的一点赋予指定的颜色，指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。然后将该颜色扩展到整个区域的过程。计算机图形学计算机图形学多边形类型多

28、边形类型多边形分为凸多边形、凹多边形、含内环的多边形。多边形分为凸多边形、凹多边形、含内环的多边形。计算机图形学计算机图形学2.3.1多边形的扫描转换扫描线算法基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。对于一条扫描线填充过程可以分为四个步骤：（1）求交（2）排序（3）配对（4）填色计算机图形学计算机图形学一个多边形与若干扫描线一个多边形与若干扫描线 计算机图形学计算机图形学数据结构数据结构活性边表活性边表(AET)(AET)：把与当前扫描线相交的边称为活性：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点边，并把它们按与扫描

29、线交点x x坐标递增的顺序存坐标递增的顺序存放在一个链表中放在一个链表中结点内容结点内容 x x：当前扫描线与边的交点坐标：当前扫描线与边的交点坐标xx：从当前扫描线到下一条扫描线间：从当前扫描线到下一条扫描线间x x的增量的增量ymaxymax：该边所交的最高扫描线号：该边所交的最高扫描线号y ymaxmax计算机图形学计算机图形学新边表（新边表（NETNET）存放在该扫描线第一次出现的边。若某边存放在该扫描线第一次出现的边。若某边的较低端点为的较低端点为y yminmin，则该边就放在扫描线，则该边就放在扫描线y yminmin的新的新边表中边表中上图所示各条扫描线的新边表上图所示各条扫描

30、线的新边表NETNET计算机图形学计算机图形学假定当前扫描线与多边形某一条边的交点的假定当前扫描线与多边形某一条边的交点的x x坐标坐标为为x x，则下一条扫描线与该边的交点不要重计算，则下一条扫描线与该边的交点不要重计算，只要加一个增量只要加一个增量xx。设该边的直线方程为：设该边的直线方程为：ax+by+c=0ax+by+c=0；若若y yy yi i，x=xx=x i i；则当；则当y=yy=y i+1 i+1时，时，其中其中 为常数为常数计算机图形学计算机图形学交点问题交点问题扫描线与多边形的顶点或边界相交时，必须正确的交点扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检

31、查顶点的两条边的另外两个端点的的取舍。只需检查顶点的两条边的另外两个端点的y y值。值。按这两个按这两个y y值中大于交点值中大于交点y y值的个数是值的个数是0,1,20,1,2来决定。来决定。计算机图形学计算机图形学算法过程算法过程void polyfill(polygon,color)void polyfill(polygon,color)int color;int color;多边形多边形 polygon;polygon;for(for(各条扫描线各条扫描线i)i)初始化新边表头指针初始化新边表头指针NET iNET i；把把y y min min=i =i 的边放进边表的边放进边表N

32、ET i;NET i;y=y=最低扫描线号；最低扫描线号；初始化活性边表初始化活性边表AETAET为空；为空；for(for(各条扫描线各条扫描线i)i)计算机图形学计算机图形学把新边表把新边表NET i NET i 中的边结点用插入排序法插入中的边结点用插入排序法插入AETAET表，使之按表，使之按x x坐标递增顺序排列；坐标递增顺序排列；遍历遍历AETAET表，把配对交点区间表，把配对交点区间(左闭右开左闭右开)上的象素上的象素(x,y)(x,y)，用，用drawpixel(x,y,color)drawpixel(x,y,color)改写象素改写象素颜色值；颜色值；遍历遍历AETAET表，

33、把表，把y y max max=i=i 的结点从的结点从AETAET表中删除，并表中删除，并把把y y max max i i 结点的结点的x x值递增值递增 x x；若允许多边形的边自相交，则用冒泡排序法对若允许多边形的边自相交，则用冒泡排序法对AETAET表表重新排序；重新排序；/*polyfill*/*polyfill*/计算机图形学计算机图形学边界标志算法边界标志算法l用软件实现时，扫描线算法与边界标志用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，算法的执行速度几乎相同，l但由于边界标志算法不必建立维护边表但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法

34、以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。有序边表算法快一至两个数量级。计算机图形学计算机图形学区域填充区域填充区域填充要求区域是连通的l连通性 4 4连通、连通、8 8连通连通l4连通：l8连通计算机图形学计算机图形学区域填充区域填充l4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求计算机图形学计算机图形学计算机图形学计算机图形学A：适合于内点表示区域的填充算法设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进

35、行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。种子填充算法种子填充算法计算机图形学计算机图形学种子填充算法种子填充算法l例例：多多 边边 形形 由由 P0P1P2P3P4构构 成成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)l设设种种子子点点为为（3，3），搜搜索索的的方方向向是是上上、下下、左左、右右

36、。依依此此类类推推，最最后后像像素素被被选选中并填充的次序如图中箭头所示中并填充的次序如图中箭头所示 计算机图形学计算机图形学种子填充算法种子填充算法递归算法可实现如下void FloodFill4(int x,int y,int oldColor,int newColor)if(GetPixel(x,y)=oldColor)PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);Flood

37、Fill4(x+1,y,oldColor,newColor);/*end of FloodFill4()*/计算机图形学计算机图形学种子填充算法种子填充算法边界表示的4连通区域void BoundaryFill4(int x,int y,int boundaryColor,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,

38、y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/计算机图形学计算机图形学l该算法也可以填充有孔区域。l缺点：(1)(1)有些象素会入栈多次，降低算法效率；栈结有些象素会入栈多次，降低算法效率；栈结构占空间。构占空间。(2)(2)递归执行，算法简单，但效率不高，区域内递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进每一象素都引起一次递归，进/出栈，费时费出栈，费时费内存。内存。

39、l改进算法，减少递归次数，提高效率。改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法解决方法是用扫描线填充算法种子填充算法种子填充算法计算机图形学计算机图形学二维裁剪二维裁剪直线段裁剪直接求交算法直接求交算法Cohen-Sutherland算法算法中点分割算法中点分割算法参数化裁剪算法参数化裁剪算法Liang-Barskey算法算法多边形裁剪 Sutlerland_Hodgman算法算法 Weiler-Athenton算法算法 计算机图形学计算机图形学裁剪裁剪l裁剪：裁剪：确定图形中哪些部分落在显示区之内，确定图形中哪些部分落在显示区之内，哪些落在显示区之外哪些落在显示区之外,以便

40、只显示落在显示区以便只显示落在显示区内的那部分图形。这个选择过程称为内的那部分图形。这个选择过程称为裁剪。图形裁剪算法，直接影响图形系统的效率。图形裁剪算法，直接影响图形系统的效率。计算机图形学计算机图形学点的裁剪点的裁剪l图形裁剪中最基本的问题。图形裁剪中最基本的问题。l假设窗口的左下角坐标为假设窗口的左下角坐标为(x(xL L,y,yB B),),右上角坐标为右上角坐标为(x(xR R,y,yT T)，对于给定点，对于给定点P(x,y),P(x,y),则则P P点在窗口内的条点在窗口内的条件是要满足下列不等式：件是要满足下列不等式：x xL L=x=x=x=xR Rl并且并且y yB B=

41、y=y=y=yT T否则，否则，P P点就在窗口外。点就在窗口外。l问题：对于任何多边形窗口，如何判别？(xL,yB)(xR,yT)计算机图形学计算机图形学直线段裁剪直线段裁剪l直线段裁剪算法是复杂图形裁剪的基础。复杂直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。也可以化为直线段的裁剪问题。直接求交算法直接求交算法Cohen-Sutherland算法算法中点算法中点算法梁友栋梁友栋barskey算法算法参数化裁剪算法参数化裁剪算法计算机图形学计算机图形学直线段裁剪直线段裁剪l裁剪线段与窗口的关

42、系：裁剪线段与窗口的关系：(1)线段完全可见；线段完全可见；(2)显然不可见；显然不可见；(3)其它其它l提高裁剪效率：提高裁剪效率：快速判断情形快速判断情形(1)(2)，对于情形对于情形(3)，设法减，设法减少求交次数和每次求少求交次数和每次求交时所需的计算量。交时所需的计算量。计算机图形学计算机图形学直接求交算法直接求交算法直线与窗口边都直线与窗口边都写成参数形式，写成参数形式，求参数值。求参数值。计算机图形学计算机图形学基本思想：对于每条线段基本思想：对于每条线段P P1 1P P2 2分为三种情况处理分为三种情况处理分为三种情况处理分为三种情况处理:（1 1）若）若P P1 1P P2

43、 2完全在窗口内，则显示该线段完全在窗口内，则显示该线段P P1 1P P2 2简简称称“取取”之。之。（2 2）若）若P P1 1P P2 2明显在窗口外，则丢弃该线段，简称明显在窗口外，则丢弃该线段，简称“弃弃”之。之。（3 3）若线段不满足）若线段不满足“取取”或或“弃弃”的条件，则的条件，则在交点处把线段分为两段。其中一段完全在窗在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理口外，可弃之。然后对另一段重复上述处理100100010101Cohen-SutherlandCohen-Sutherland裁剪裁剪计算机图形学计算机图形学Cohen-Suther

44、landCohen-SutherlandCohen-SutherlandCohen-Sutherland算法算法算法算法l将区域码的各位从右到左编号，则坐标区将区域码的各位从右到左编号，则坐标区域与各位的关系为：域与各位的关系为：上上 下下 右右 左左 X X X XX X X X任何位赋值为任何位赋值为1 1，代表端点落在相应的位，代表端点落在相应的位置上，否则该位为置上，否则该位为0 0。若端点在剪取矩形。若端点在剪取矩形内，区域码为内，区域码为00000000。如果端点落在矩形的。如果端点落在矩形的左下角，则区域码为左下角，则区域码为01010101。计算机图形学计算机图形学Cohen-

45、SutherlandCohen-SutherlandCohen-SutherlandCohen-Sutherland算法算法算法算法一旦一旦给定所有的线段端点的区域给定所有的线段端点的区域码，就可以快速判断哪条直线完码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：在窗口外。所以得到一个规律：计算机图形学计算机图形学Cohen-SutherlandCohen-Sutherland裁剪裁剪若若P P1 1P P2 2完全在窗口内完全在窗口内code1=0,code1=0,且且code2=0,code2=0,则则“取取”若若P P1 1

46、P P2 2明显在窗口外明显在窗口外code1&code20code1&code20，则，则“弃弃”在交点处把线段分为两段。其中一段完全在窗口外，在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。可弃之。然后对另一段重复上述处理。编码编码 线段裁剪线段裁剪计算机图形学计算机图形学Cohen-SutherlandCohen-Sutherland裁剪裁剪如何判定应该与窗口的哪条边求交呢？编码中对应位为编码中对应位为1的边。的边。l计算线段计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点与窗口边界的交点if(LEFT&code!=0)if(LEFT&code

47、!=0)x=XL;x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);y=y1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code!=0)else if(RIGHT&code!=0)x=XR;x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BOTTOM&code!=0)else if(BOTTOM&code!=0)y=YB;y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);x=x1+(x2-x1)*(YB-y1)/(y2-y1);el

48、se if(TOP&code!=0)else if(TOP&code!=0)y=YT;y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);x=x1+(x2-x1)*(YT-y1)/(y2-y1);具体算法见具体算法见p201p201计算机图形学计算机图形学Cohen-SutherlandCohen-Sutherland直线裁剪算法小结直线裁剪算法小结l本算法的优点在于简单，易于实现。他可以简本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，左，右，下，上的顺序依次进行，

49、处理之后，剩余部分就是可见的了。在这个算法中求交点剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。算法对于其他形状的窗口未必同样有效。l特点：用编码方法可快速判断线段的完全可见特点：用编码方法可快速判断线段的完全可见和显然不可见。和显然不可见。计算机图形学计算机图形学中点分割裁剪算法中点分割裁剪算法l基本思想：基本思想：从从P P0 0点出发找出离点出发找出离P P0 0最近的可见点，和从最近的可见点，和从P P1 1点出发找出离点出发找出离P P1 1最近的可见点。这两个可见点的连线最

50、近的可见点。这两个可见点的连线就是原线段的可见部分。就是原线段的可见部分。l与与Cohen-SutherlandCohen-Sutherland算法一样首先对线段端点进行编算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。割的方法求出线段与窗口的交点。A A、B B分别为距分别为距P P0 0 、P P1 1最近的可见点，最近的可见点，P Pm m为为P P0 0P P1 1中点。中点。计算机图形学计算机