二维图形基础课件.ppt

1、2022-7-26计算机图形学演示稿 纪玉波制作(C)13.13.1直线生成算法直线生成算法 最基本的图形显示方式是直线方式。实际上，无论什么复杂图形，它们无非是由直线段和曲线段组成。而对于曲线及各种复杂的图形，可以将其离散成许多小直线段，连接各直线来逼近欲生成的曲线或其它复杂图形，所以一般图形都可以看成是由直线段组成。因此，直线段生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速度。在光栅显示器上显示图形是将线段上所有象素点亮的过程。如果已知直线段两个端点，可以有很多种不同的数学方法来决定应改变在两端点之间的那些象素的亮度值才能显示出两点间的直线。在绘图仪上绘直线段，主要决定X、Y方向

2、上的位移量，这些算法之间主要区别是判别和生成x、y增量的过程和方法的不同。2022-7-26计算机图形学演示稿 纪玉波制作(C)21.1.点的生成点的生成 点是图形中最基本的图素，直线、曲线以及其它的图元都是点的集合。在几何学中，一个点既没有大小，也没有维数，点只是表示坐标系统中一个位置。在计算机图形学中，点是用数值坐标来表示的。在直角坐标系中点由（x,y)两个数值组成的坐标表示，在三维坐标系中点是由（x,y,z)三个数值组成的坐标表示。在输出设备上输出一个点，就要把应用程序中的坐标信息转换成所用输出设备的相应位置。对于一个CRT监视器来说，输出一个点就是要在指定的屏幕位置上打开电子束，使该位

3、置上的荧光点亮。在PC机中，点亮屏幕上一个点是由BIOS控制完成的，各种程序语言中都有描点语句。例如C语言为putpixel(x,y,color)。2022-7-26计算机图形学演示稿 纪玉波制作(C)32 2.DDA DDA直线直线生成生成算法（算法（digital differential analyzer)digital differential analyzer)直线是点的集合，在几何学中直线被定义为两个点之间的最短距离。也就是说一条直线是指所有在它上面的点的集合。直线是一维的，即它们具有长度但没有面积。直线可以向一个方向及其相反的方向无限伸长，这不是计算机图形学中所需要的，在图形学中

4、研究的对象是直线段。已知线段的起点坐标（x1,y1），终点坐标（x2,y2)，这两点就确定了一条线段。一般来讲，任何图形输出设备都能准确地画出水平线X和垂直线Y,或对角线，但要画出一条准确斜线不是件容易的事。在光栅系统中，线段通过象素绘制，水平和垂直方向的台阶大小受象素的间隔限制。这就是说，必须在离散位置上对线段取样，并且在每个取样位置上决定距线段最近的象素，画一条直线实际上就计算出来一系列与该线靠近的象素。2022-7-26计算机图形学演示稿 纪玉波制作(C)4直线的点斜式方程为：ymxb其中，m表示直线的斜率，b是y轴截距。给定线段的两个端点（x1,y1）和（x2,y2)，可以计算斜率m和

5、截距b:m(y2y1)/(x2x1)by1mx1 对任何沿直线给定的x的增量x，对应的y增量y：ymx同样，对应于y的增量y，x的增量x为：x(1/m)y2022-7-26计算机图形学演示稿 纪玉波制作(C)5 DDA直线生成算法是一种基于上述直线方程的线段扫描转换算法。在一个坐标轴上以单位间隔增量，决定另一个坐标轴上最靠近线段路径的对应整数值。为了使产生的直线光滑，应使X、Y两方向上每一步的增量都不大于一个单位，因此当|m|1时，应该使用x做自变量，而当|m|1时应该使用y做自变量。也就是说应该选定x2x1和y2y1中绝对值较大者作为步进的控制量。假定x2x1的绝对值大于y2y1的绝对值，取

6、x为一个象素单位长，即x 每次递增一个象素，然后利用下式计算相应的y值：yk+1ykyykmx 对于|m|1的线段，可通过计算由Y方向的增量y引起的改变来生成直线：xk+1xkxxkmy 2022-7-26计算机图形学演示稿 纪玉波制作(C)6DDA直线生成算法的伪语言描述如下：begin if abs(x2x1)abs(y2y1)then lenghtabs(x2x1)else lenghtabs(y2y1)endif x(x2x1)/lenght y(y2y1)/lenght xx1 yy1 k1 while(klenght)putpixel(x,y)xxx yyy kk1 endwhil

7、e endDDA方法计算象素位置要比直接使用代数方程快。它利用光栅特性消除了代数方程中的乘法，而在X和Y方向使用合适的增量来逐步沿线段的路径计算各象素位置。但浮点增量的连续迭加中取整误差的积累会使长线段所计算的象素位置偏离实际线段，而且算法中的取整操作和浮点运算仍然十分耗时。2022-7-26计算机图形学演示稿 纪玉波制作(C)7DDA直线绘制的直线绘制的C+实现实现void DDA直线绘制(HDC hdc)int k;double x1=50,y1=50,x2=300,y2=350;double x,y,deltx,delty,length;if(fabs(x2-x1)=fabs(y2-y1

8、)length=fabs(x2-x1);else length=fabs(y2-y1);deltx=(x2-x1)/length;delty=(y2-y1)/length;x=x1;y=y1;k=1;while(k=length)SetPixel(hdc,x,y,RGB(0,0,0);x=x+deltx;y=y+delty;k=k+1;Sleep(50);DDA直线绘制演示直线绘制演示2022-7-26计算机图形学演示稿 纪玉波制作(C)8 3 3 BresenhamBresenham直线直线生成生成算法算法 Bresenham直线生成算法是由Bresenham提出的一种精确而有效的光栅线段生

9、成算法，算法的目标是选择表示直线的最佳光栅位置。为此，算法根据直线的斜率确定选择变量在X方向上或在Y方向上每次递增一个单位，另一变量的增量为0或1，它取决于实际直线与最近网格点位置的距离，这一距离称为误差。算法的构思巧妙，使得每次只需检查误差项的符号即可确定所选象素。2022-7-26计算机图形学演示稿 纪玉波制作(C)9 以第一象限的直线为例。假设斜率m在01之间。如下图所示。若通过（0,0）的直线的斜率ml2，它与x1直线的交点离yl直线较y0直线近，光栅点（1,1）比（1,0）更逼近于该直线，因此应该取象素点（1,1）。如果斜率ml2，则应取象素点（1,0）。当斜率ml2时，差值相同，可

10、以任选（1,1）或（1,0）象素点。2022-7-26计算机图形学演示稿 纪玉波制作(C)10 通常，所选象素点与实际的直线位置之间存在差值。当斜率m在01之间时，x每增加一单位，y 应该增加m，记e为y方向上的误差。当选取实际直线位置上方的象素点时，误差为em1；当选取实际直线位置下方的象素点时，误差为em。为了简化判断，可首先令误差项的初值为e0-1/2，这样只要判断e的符号即可。第一步，当 e1me00，选取上面的象素点（1,1）；当e1me00,选取下面的象素点（1,0）。e1作为累计误差项供下一步判断继续使用。设第k步的误差为ek，选取上面象素点后的积累误差为：ek+1ek（m1）选

11、取下面的象素点后的积累误差为：ek+1ekm2022-7-26计算机图形学演示稿 纪玉波制作(C)11 根据上述思想的Bresenham直线生成算法描述如下：begin xx1 yy1 xx2-x1 yy2-y1 my/x e-1/2 for k1 to x putpixel(x,y)eem if(e0)yy1 ee1 endif xx1 next k endfor end此Bresenham算法在计算直线斜率和误差项时要用到浮点算术运算和除法，如果采用整数算术运算和避免除法，可以加快算法的速度。实际上，误差项e的数值大小与算法的执行没有什么关系，相关的只是e的符号，因此作简单变换，即可得到整

12、数算法。2022-7-26计算机图形学演示稿 纪玉波制作(C)12 将e乘以2x记为E2xe，则E同e有相同的符号，取代e判断E的符号确定象素点的过程仍然正确。此时上述算法中各误差项的表示式做如下变动：初始误差项：E02xe0 -x；积累误差 ek+1ekm修改为：Ek+12xek+1 2x(eky/x）2xek2y Ek2y；如果选取上面的象素点，积累误差还要减去1，修改为：Ek+12x（ek+11）E k+12x 2022-7-26计算机图形学演示稿 纪玉波制作(C)13 由于x、y是整数，因此算法全部运算都只使用整数，修改后的Bresenham直线生成算法描述如下：begin xx1 y

13、y1 xx2x1 yy2y1 E-x for k1 To x putpixel(x,y)EE2y If(E0)yy1 EE2x endif xx1 next k endfor end对于斜率值大于1的线段，只要交换x和y之间的规则，即沿Y方向以单位步长增加并计算最接近线段路径的x连续值。考虑到XY平面各种八分和四分区域间的对称性，Bresenham算法对任意斜率的线段具有通用性。2022-7-26计算机图形学演示稿 纪玉波制作(C)14Bresenham算法直线绘制例子：考虑绘制从点（0，0）到（8，4）的线段。初值计算：x=0 y=0 x=8 y=4(循环计算过程部分：e-x for k1

14、To x putpixel(x,y)ee2y If(e0)yy1 ee2x endif xx1)i绘制点坐标exy1（0，0）-8112（1，1）0213（2，1）-8324（3，2）0425（4，2）-8536（5，3）0637（6，3）-8748（7，4）0842022-7-26计算机图形学演示稿 纪玉波制作(C)15Bresenham直线绘制的直线绘制的C+实现实现void Bresenham直线绘制(HDC hdc)int k;double x1=50,y1=50,x2=300,y2=300;double x,y,deltx,delty,E;x=x1;y=y1;deltx=x2-x1;

15、delty=y2-y1;E=-deltx;for(k=1;k=0)y=y+1;E=E-2*deltx;x=x+1;Sleep(50);Bresenham直线绘制演示直线绘制演示2022-7-26计算机图形学演示稿 纪玉波制作(C)163.2 3.2 二次曲线绘制算法二次曲线绘制算法 二次曲线是指那些能用二次函数 Ax2BxyCy2DxEyF0来表示的曲线，包括圆、椭圆、抛物线、双曲线等。由于图形输出设备的基本动作是显示象素点或者是画以步长为单位的直线段，所以，从图形显示器和绘图机上输出的图形，一般除了水平线和垂直线以外，其他的各种线段，包括直线和曲线，都是由很多的点和短直线构成的锯齿形线条组成

16、的。也就是说，需要把曲线离散化，把它们分割成很多短直线段，用这些短直线段组成的折线来逼近曲线。2022-7-26计算机图形学演示稿 纪玉波制作(C)173.2.1 3.2.1 圆的参数方程生成算法圆的参数方程生成算法 圆是图形中经常使用的元素，圆被定义为所有离一中心位置（xc,yc）距离为给定值R的点集，其函数方程为：(xxc)2(yyc)2R2利用这个方程，我们可以沿X轴从xcR 到xcR以单位步长计算对应的y值来得到圆周上每点的位置,但这并非是生成圆的好方法。2022-7-26计算机图形学演示稿 纪玉波制作(C)18圆的方程绘制方法圆的方程绘制方法C+实现实现void 圆的方程绘制(HDC

17、 hdc)double xc=300,yc=200,R=150;double x,y;y=yc;for(x=xc-R;x=450;x+)y=sqrt(R*R-(x-xc)*(x-xc)+yc;SetPixel(hdc,x,y,RGB(0,0,0);y=-sqrt(R*R-(x-xc)*(x-xc)+yc;SetPixel(hdc,x,y,RGB(0,0,0);Sleep(50);圆的方程绘制方法演示圆的方程绘制方法演示2022-7-26计算机图形学演示稿 纪玉波制作(C)19 这一方法包括乘法和平方根运算，计算量较大，所画象素位置间的间距也是不一致的。下面介绍两种生成速度较快的算法。先介绍圆的

18、参数生成方法。2022-7-26计算机图形学演示稿 纪玉波制作(C)20假定园心在(xc,yc)点，将圆用参数方程表示：sincosRyyRxxcc 02将 离散化)2sin()2cos(nkRyynkRxxckck0kn使用上述离散化方程，可以得到如下算法：begin for k0 to n xxcRcos(2.k/n)yycRsin(2.k/n)putpixel(x,y)next k endfor end 2022-7-26计算机图形学演示稿 纪玉波制作(C)21 使用上述方法可沿圆周等距点绘制出圆来。算法中，n取的值越大，计算的点越多，但执行时间越长。此算法的缺点是含有三角函数，计算量大

19、。为了避免三角函数运算，考虑下图,如果已经计算出圆上一点（xk,yk）,则增加一个角度 后，下一点（xk+1,yk+1）的坐标值可以用上一个点表示出。xk+1Rcos()R(coscos sinsin)R.coscosRsinsin xkcosyksin yk+1Rsin()R(sincoscossin)RcoscosRsinsin ykcosxksin2022-7-26计算机图形学演示稿 纪玉波制作(C)22当 足够小时有：cos1 sin如是方程式可以改写为：xk+1=xkyk yk+1=ykxk习惯上用 表示一个较小的量，用它替代,式子改写为：xk+1=xkyk yk+1=ykxk202

20、2-7-26计算机图形学演示稿 纪玉波制作(C)23利用前式，圆的参数方程生成算法可以描述如下：begin xxcR yyc 0 for 2 putpixel(x,y)xxy yyx endforend上述算法中，选取的值越小，计算的点越多，但执行时间越长。为了在光栅系统上得到连续的边界，可选取1R，这样绘制的象素位置大约为一个单位间隔。此算法也被称为DDA圆的生成算法。此圆的生成算法中仍包含浮点数和乘法运算，影响速度。2022-7-26计算机图形学演示稿 纪玉波制作(C)24圆的参数绘制方法圆的参数绘制方法C+实现实现void ApplicationProceesing(HDC hdc)do

21、uble xc=300,yc=200,R=150;double x,y,theta,delta;x=xc+R;y=yc;delta=1.0/R;for(theta=0;thetamD，显然这时只能取D点或V点，为此比较mD和 mV的大小VDDVmm 222222)1()()1()1(RyxRyxkkkk2022-7-26计算机图形学演示稿 纪玉波制作(C)30如果DV0，那么点V的距离大于点D的距离，这时应取D点。反之，如果DV0，应取V点。当两距离相等时，规定取D点。这样当 DV0 时取D（xk1,yk1）点 DV0 时取V（xk,yk1）点此时有：(xk1)2(yk-1)2R20（D点在圆

22、外）(xk)2(yk-1)2R20 （V点在圆内）因此DV的表达式可简化为 DV(xk1)2(yk-1)2R2(xk)2(yk-1)2R2 2(（xk1)2(yk-1)2R2）2xk1 2（kxk）1当 k0 时，表明D（xk1,yk1）点恰好在圆上，自然应取D点。2022-7-26计算机图形学演示稿 纪玉波制作(C)31 上述结果可以归纳为当k0 时 HD0 时取H（xk1,yk）点 HD 0 时取D（xk1,yk1）点当 k0 时 DV0 时取D（xk1,yk1）点 DV0 时取V（xk,yk1）点当 k0 时取D（xk1,yk1）点。由此容易导出简单的增量算法递推关系。首先考虑水平移动到

23、H（xk1,yk）象素点，称此为第k+1个象素，新象素xk+1、yk+1值及误差计算公式k+1为:xk+1xk1 yk+1yk k+1(xk+11)2(yk+1-1)2 R2 (xk+1)2 2xk+11(yk-1)2R2 (xk1)2 2xk+11(yk-1)2 R2 k2 xk+112022-7-26计算机图形学演示稿 纪玉波制作(C)32类似地可以推出，当取 D（xk+1,yk1）象素点时 xk+1xk+1 yk+1yk1 k+1k2xk+12yk+12当取 V（xk,yk1）象素点时 xk+1xk yk+1yk1 k+1k2yk+12 由于上面各个公式中，只涉及到整数的加减运算，所以基

24、于这种方法设计的算法运算速度快。2022-7-26计算机图形学演示稿 纪玉波制作(C)33 下面给出Bresenbam画圆算法描述（第一象限四分之一圆）：begin xk0 ykR k2(1R)(k=(xk1)(yk1)R=1(R1)=2(1R)Limit0 1 putpixel(xk,yk)if ykLimit then 4 if k0 then 2 if k0 then 3 if k0 then 20 2 2k2yk1 if 0 then 10 if 0 then 20 3 2k2xk1 if 0 then 20 if 0 then 30 10 xkxk1 kk2xk1 goto 1 20

25、 xkxk1 ykyk1 kk2xk-2yk2 goto 1 30 ykyk1 kk2yk1 goto 1 4 finish end 2022-7-26计算机图形学演示稿 纪玉波制作(C)34 如果圆心不在原点，设圆心坐标为（xc,yc),只需要改变初始化值：xk=xc yk=yc+R k=(xc+1)2+(yc+R-1)2-R2 =xc2+2xc+1+yc2+2yc(R-1)-2R+1由圆的对称性，很容易将上述方法转换到其它三个象限中。2022-7-26计算机图形学演示稿 纪玉波制作(C)35绘制以坐标原点为圆心，半径8的圆在第一象限的部分。x0=0y0=8R=8k=(xk+1)2+(yk-

26、1)2-R2当k0时取D（xk+1,yk-1）点 k=k+2xk+1-2yk+1+2当k0时 DV=2(k-xk)-1 DV0时取D（xk+1,yk-1）点 k=k+2xk+1-2yk+1+2 DV0时取V（xk,yk-1）点 k=k-2yk+1+2当k=0时取D（xk+1,yk-1）点 k=k+2xk+1-2yk+1+2绘 制 坐 标 点HDDVkxy-1408(0,8)-13-1118(1,8)-7-628(2,8)3-1237(3,7)-11-347(4,7)7-356(5,6)5165(6,5)-11974(7,4)3473(7,3)-71882(8,2)191781(8,1)1718

27、80（8,0）结 束Bresenham圆的绘制算法例子：2022-7-26计算机图形学演示稿 纪玉波制作(C)363.2.2 3.2.2 其它二次曲线的绘制其它二次曲线的绘制 由于各种其它二次曲线都有类似于圆的参数方程，因此其生成算法可以仿照圆的参数方程DDA生成算法设计。例如椭圆的参数方程为sin.cos.ycxcRyyRxx 02只有Rx和Ry两个半轴常数不同于圆的单一半径R，但它们并不影响算法设计。几乎可以不加改变地使用圆的DDA算法过程。2022-7-26计算机图形学演示稿 纪玉波制作(C)373.33.3线的属性线的属性基本的线属性是线型、线颜色和线宽度。对线型的指定包括实线、虚线和

28、点划线等。线颜色由控制RGB监视器中三支电子枪的亮度的RGB分量来给出。常把图形设备能产生的最小直线宽度认为是1个点宽度，例如1个象素的宽度。以此作为基本线宽，再定义二倍或四倍线宽。线宽的默认值常选取基本线宽。2022-7-26计算机图形学演示稿 纪玉波制作(C)38 3.4 3.4区域填充区域填充 一个区域是指一组相邻而又相连的象素，且具有同样的属性。根据边或轮廓线的描述，生成实区域的过程称为区域填充。区域填充算法可分为两大类：一是种子填充算法；二是扫描转换填充算法。种子填充算法首先假定封闭轮廓线内某点是已知的，然后算法开始搜索与种子点相邻且位于轮廓线内的点。种子填充算法只适用于光栅扫描设备

29、。扫描转换填充算法则是按扫描线的顺序确定某一点是否位于多边形或轮廓线范围之内。这些算法一般从轮廓线的顶部开始进行到它的底部。区域填充的边界可以是直线也可以是曲线。2022-7-26计算机图形学演示稿 纪玉波制作(C)39 区域的建立和定义通常可采用两种方式：一是内定义区域（Interior-Defined），用这种方式定义的区域内部所有象素具有同一种颜色或亮度值，而区域外的所有象素具有另种颜色或亮度值。另一种是边界定义区域（Boundary-Defined）这种方式定义的区域，其边界上所有象素均具有特定的颜色或亮度值，而在区域内的象素则具有不同于边界值的某种颜色或亮度值。较常使用的还是边界定义

30、的方式。2022-7-26计算机图形学演示稿 纪玉波制作(C)403.4.1 扫描转换填充算法扫描转换填充算法 一般的封闭轮廓线都是简单的多边形。而由曲线构成的轮廓线可用适当的多边形逼近之。有了对多边形轮廓的描述，要对此多边形内的区域进行填充，最本质的问题是要找出位于该多边形边界内的全部象素，即进行多边形对平面上点的包含性检查。然后，再将那些位于多边形内的全部象素的象素值置换成相应的数值。除边界线外，多边形中相邻象素几乎都具有相同的特性，这种性质称为空间连贯性。同样，光栅扫描图形显示的扫描线上相邻象素也具有连贯特性，扫描转换填充算法就是利用了这一特性。在给定的扫描线上，象素的这种特性只有在多边

31、形的边和该扫描线交点处才会发生变化。这些交点把扫描线划分成一些段。2022-7-26计算机图形学演示稿 纪玉波制作(C)41 扫描转换填充算法适用于规则边界的封闭区域，通常是将由顶点定义的多边形的边及其内部用预期的象素值予以填充，因此常称为多边形扫描变换。右图所示是一简单多边形，各条扫描线与多边形有不同的交点个数，交点将扫描线分成了不同的区域。求出扫描线与多边形的交点后，将各条扫描线上的交点按X方向从小到大排序后两两配对。每对交点所确定的区间均取填充的光强或色彩，其它区间则取背景光强或色彩，即可完成填充。2022-7-26计算机图形学演示稿 纪玉波制作(C)42 当扫描线与多边形顶点交于多边形

32、的局部最高点或局部最低点时，交点应计2次，否则只计1次。确定多边形某顶点是否是局部最高点或最低点只需检查交于该顶点的两条边的另两个端点，如果它们的y值都大于顶点的y值，则该顶点是局部最低点，如果它们的y值都小于顶点的y值，则该顶点是局部最高点。如果一条边大于顶点的y值，而另一条边小于顶点的y值，则该顶点既不是局部最高点也不是局部最低点。前图中A和C是局部最高点，B和F是局部最低点，D 和E 既不是局部最高点也不是局部最低点。故扫描线在A、B、C和F处的交点应计两次，而在D 和E处只计一次。2022-7-26计算机图形学演示稿 纪玉波制作(C)43 应用上述方法可得到几种有效的多边形扫描转换算法

33、，这些算法是建立在按扫描顺序对多边形边与扫描线交点进行排序的基础上,故称为有序边表算法。下面给出一个简单的有序边表算法。有序边表算法：1.求出每一条扫描线与多边形各边的交点，把各个交点的坐标（xk,yk）存贮在表中；2.按扫描线以及扫描线上交点x值的递增顺序对该表进行排序。例如交点（x1,y1）和(x2,y2)，当y1y2或y1y2而x1x2时，（x1,y1）将位于（x2,y2）的前面；3按（x1,y1）和(x2,y2)形式成对提取巳排序表的交点；4将每一对交点之间的象素置成填充的光强或颜色。2022-7-26计算机图形学演示稿 纪玉波制作(C)443.4.2 3.4.2 边填充法边填充法 另

34、一种扫描转换方法即所谓的边填充算法。其基本思想是对每条扫描线和每条多边形的交点（xk,yk），将该扫描线上交点右方的所有象素取补。对多边形的每条边作此处理，就可以完成多边形区域填充。边填充算法描述如下：1.取多边形的一条边；2.求出每一条扫描线与该边的交点坐标（xk,yk）；3.将（xk,yk）右边的全部象素取补；4还有没处理的多边形边时转1，否则结束。2022-7-26计算机图形学演示稿 纪玉波制作(C)45下图示出了边填充算法的实现过程。2022-7-26计算机图形学演示稿 纪玉波制作(C)46 上述算法的缺点是对于复杂的图形，一些象素可能被访问多次，一种改进的办法是引入栅栏。通过多边形设

35、一栅栏，每次只对交点与栅栏之间的象素点取补，可使访问象素的次数减少。下图示出了这一算法的原理。2022-7-26计算机图形学演示稿 纪玉波制作(C)473.4.4 3.4.4 种子填充算法种子填充算法 以上讨论的填充多边形的算法都是按扫描线顺序进行的。种子填充算法则来用完全不同的方法。种子填充算法假设在多边形或区域内部至少有一个象素是已知的。然后设法找到区域内所有其它象素，并对它们进行填充。区域可以由其内部点或边界来定义。如果区域是采用内部定义，那么该区域内部所有象素具有同一种颜色或值，而区域外的所有象素具有另一种颜色或值。如果区域是采用边界定义的，那么区域边界上所有象素均具有特定的值或颜色，

36、区域内部所有的象素均不取这一特定值。然而边界外的象素则可具有与边界相同的值。填充内部定义的区域的算法称为泛填充算法（flood fill algorithm），填充边界定义的区域的算法称为边界填充算法。2022-7-26计算机图形学演示稿 纪玉波制作(C)48 内部定义的或边界定义的区域可分为4连接或8连接两种。如果区域是4连接的，那么区域内每一象素可通过四个方向，即上、下、左、右移动到达相邻象素。对于8连接区域,区域内的每一象素可通过两个水平方向，两个垂直方向和四个对角线方向的移动到达相邻象素。下图是4连接和8连接内部定义区域的简单例子。2022-7-26计算机图形学演示稿 纪玉波制作(C)

37、49 对4连接算法，应用边界定义区域，可使用堆栈以建立简单的种子填充算法。使用的堆栈的种子填充算法如下：1 种子象素压入堆栈；2 当堆栈非空时做 （1）栈顶象素出栈；（2）将出栈象素置成填充颜色；（3）检查每个与当前象素邻接的4连接象素，若其中有象素不为边界且没有设置成填充颜色，将该象素压入堆栈；（4）转22022-7-26计算机图形学演示稿 纪玉波制作(C)50算法可用伪语言描述如下：算法：seed(x,y)作为种子 BV(BoundaryValue)边界值 NV(NewValue)填充值 begin pixel(x,y)=seed(x,y)push pixel(x,y)while(stac

38、k not empty)pop pixel(x,y)if pixel(x,y)NV then putpixel(x,y,NV)pixel(x,y)=NV endif if pixel(x+1,y)NV and pixel(x+1,y)BV then push pixel(x+1,y)endif if pixel(x,y+1)NV and pixel(x,y+1)BV then push pixel(x,y+1)endif if pixel(x-1,y)NV and pixel(x-1,y)BV then push pixel(x-1,y)endif if pixel(x,y-1)NV and

39、pixel(x,y-1)BV then push pixel(x,y-1)endif endwhile end2022-7-26计算机图形学演示稿 纪玉波制作(C)51种子填充算法例子如右图所示，种子的坐标为（2，3），以四连通顺时针左起点为例，其进出栈顺序为：种子（2，3）进栈，初始栈：（2，3）（1）种子（2，3）出栈，四个相邻点进栈；栈：（2，2），（3，3），（2，4），（1，3）（2）点（1，3）出栈，相邻点（1，2），（1，4）进栈；栈：（2，2），（3，3），（2，4），（1，2），（1，4）（3）点（1，4）出栈，相邻点（2，4）进栈；栈：（2，2），（3，3），（2，4），（

40、1，2），（2，4）（4）点（2，4）出栈，相邻点进栈（无）；栈：（2，2），（3，3），（2，4），（1，2）2022-7-26计算机图形学演示稿 纪玉波制作(C)52（5）点（1，2）出栈，相邻点（2，2）进栈；栈：（2，2），（3，3），（2，4），（2，2）（6）点（2，2）出栈，相邻点（2，1），（3，2）进栈；栈：（2，2），（3，3），（2，4），（2，1），（3，2）（7）点（3，2）出栈，相邻点（3，3）进栈；栈：（2，2），（3，3），（2，4），（2，1），（3，3）（8）点（3，3）出栈，相邻点进栈（无）；栈：（2，2），（3，3），（2，4），（2，1）（9）点（2，

41、1）出栈，相邻点进栈（无）；栈：（2，2），（3，3），（2，4）（10）点（2，4）出栈，相邻点进栈（无）；栈：（2，2），（3，3）（11）点（3，3）出栈，相邻点进栈（无）；栈：（2，2）（12）点（2，2）出栈，相邻点进栈（无）；（13）栈空结束。2022-7-26计算机图形学演示稿 纪玉波制作(C)53种子填充算法主要实现子程序实例种子填充算法主要实现子程序实例void Seed_Fill_draw(HDC hdc)int i;COLORREF BoundColor;POINT triangle=300,275,280,325,320,325,300,275;POINT fourli

42、ne=250,340,300,375,350,340,300,350,250,340;BoundColor=RGB(255,0,0);SetColor(BoundColor,hdc);Ellipse(hdc,180,200,420,400);Ellipse(hdc,230,230,270,310);Ellipse(hdc,330,230,370,310);Ellipse(hdc,245,264,255,296);Ellipse(hdc,345,264,355,296);for(i=0;i3;i+)line(hdc,trianglei,trianglei+1);for(i=0;i=0)x=ak;

43、y=bk;k-;rgbColor=GetPixel(hdc,x,y);if(rgbColor!=FillColor)&(rgbColor!=BoundColor)SetPixel(hdc,x,y,FillColor);Sleep(20);mx=x;my=y;for(i=1;i5;i+)x=mx;y=my;2022-7-26计算机图形学演示稿 纪玉波制作(C)55 for(i=1;i5;i+)x=mx;y=my;if(i=1)x+;else if(i=2)y+;else if(i=3)x-;else y-;rgbColor=GetPixel(hdc,x,y);if(rgbColor!=FillC

44、olor)&(rgbColor!=BoundColor)k+;ak=x;bk=y;2022-7-26计算机图形学演示稿 纪玉波制作(C)56void line(HDC hdc,POINT point1,POINT point2)MoveToEx(hdc,point1.x,point1.y,NULL);LineTo(hdc,point2.x,point2.y);return;/设置颜色void SetColor(COLORREF color,HDC hdc)LOGPEN PenColor=PS_SOLID,1,1,color;HPEN rgbPen;rgbPen=CreatePenIndirec

45、t(&PenColor);SelectObject(hdc,rgbPen);种子填充算法演示种子填充算法演示2022-7-26计算机图形学演示稿 纪玉波制作(C)57 上面的算法是一种深度优先搜索算法，采用堆栈实现。也可以改为广度优先搜索，采用队列实现。3.4.5 扫描线种子填充算法扫描线种子填充算法 种子填充算法的缺点是可能把太多的象素压入堆栈，有些象素甚至会入栈多次，降低算法的效率，存储空间需求大。解决的一种方法是对每一条扫描线实行种子算法。在任意不间断的扫描线象素段中，只取一个种子象素。象素段是指区域内相邻象素在水平方向的组合，它的两端以具有边界值的象素为界，其中间不包括具有新值的象素。

46、2022-7-26计算机图形学演示稿 纪玉波制作(C)58对于区域内的每一象素段，我们可以只保留其最右（或左）端的象素作为种子象素。因此，区域中每一个末被填充的部分，至少有一个象素段是保持在栈里的。扫描线种子填充算法适用于边界定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。算法叙述如下：1 种子象素入栈；2 当堆栈非空时做 （1）栈顶象素出栈；2022-7-26计算机图形学演示稿 纪玉波制作(C)59（2）沿扫描线对出栈象素的左右象素进行填充，直到遇到边界象素为止，即每出栈一个象素，便对包含该象素的整个区间进行

47、填充；（3）上述区间内最左最右的象素分别记为xLeft、xRight；（4）在区间xLeft,xRight中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或为已填充的象素，若存在非边界未填充的象素，则把每一区间的最右象素取作种子象素入栈；（5）转2 此算法可以有效地解决简单种子填充算法存在的堆栈可能过深的问题。2022-7-26计算机图形学演示稿 纪玉波制作(C)60扫描线种子填充算法主要实现子程序实例扫描线种子填充算法主要实现子程序实例void push(int x,int y)pointstop0=x;pointstop1=y;top+;void pop()x=points

48、top-10;y=pointstop-11;top-;void Scanline_seed_fill_draw(HDC hdc)int i;COLORREF BoundColor;POINT triangle=300,275,280,325,320,325,300,275;POINT fourline=250,340,300,375,350,340,300,350,250,340;BoundColor=RGB(255,0,0);SetColor(BoundColor,hdc);2022-7-26计算机图形学演示稿 纪玉波制作(C)61Ellipse(hdc,180,200,420,400);E

49、llipse(hdc,230,230,270,310);Ellipse(hdc,330,230,370,310);Ellipse(hdc,245,264,255,296);Ellipse(hdc,345,264,355,296);for(i=0;i3;i+)line(hdc,trianglei,trianglei+1);for(i=0;i4;i+)line(hdc,fourlinei,fourlinei+1);Scanline_seed_fill(hdc,300,300,RGB(0,0,255),BoundColor);Scanline_seed_fill(hdc,250,280,RGB(0,

50、255,0),BoundColor);Scanline_seed_fill(hdc,350,280,RGB(0,255,0),BoundColor);Scanline_seed_fill(hdc,300,360,RGB(0,255,255),BoundColor);Scanline_seed_fill(hdc,235,270,RGB(0,0,0),BoundColor);Scanline_seed_fill(hdc,335,270,RGB(0,0,0),BoundColor);void Scanline_seed_fill(HDC hdc,int seed_x,int seed_y,COLOR