计算机图形学课程论文

1、计算机图形学课程论文课程名称计算机图形学授课教师XXX专业软件工程年级2013姓名XXX学号2013XXXXXXX学期20152016学年第二学期成绩授课教师签名计算机图形学期末综合理论摘要:计算机图形学直线变换算法二维图形算法图形填充算法31言：计算机图形学是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。虽然通常认为CG是指三维图形的处理，事实上也包括了二维图形及图像的处理。狭义地理解，计算机图形学是数字图象处理或计算机视觉的逆过程：计算机图形学

2、是用计算机来画图像的学科，数字图象处理是把外界获得的图象用计算机进行处理的学科，计算机视觉是根据获取的图像来理解和识别其中的物体的三维信息及其他信息。实际上，计算机图形学、数字图象处理和计算机视觉在很多地方的区别不是非常清晰，很多概念是相通的，而且随着研究的深入，这些学科方向不断的交叉融入，形成一个更大的学科方向，可称之为“可视计算”。计算机图形学主要包含四大部分的内容：建模(Modeling卜渲染(Rendering)动画(Animation)和人机交互(Human-computerInteraction,HCI)。目录1、概论41.1 什么是计算机图形学41.2 计算机图形学的研究内容41

3、.3 什么是计算机图形学41.4 计算机中表示图形的方法52、直线生成算法42.1 直线数值微分算法52.1.1 数值微分算法基本原理62.1.2 数值微分算法基本原理62.1.3 数值微分算法设计与代码实现72.1.4 数值微分算法设计与代码实现82.1.5 小结92.2 直线中点画线算法92.2.1 直线中点画线算法基本原理92.2.2 数值微分算法描述与步骤102.2.3 中点划线算法设计与代码实现122.2.4 小结102.3 直线Breseham画线算法122.3.1 直线Breseham画线基本原理132.3.2 直线Breseham画线算法描述与步骤132.3.3 直线Brese

4、ham画线算法设计与代码实现172.3.4 小结183、二维图形变换193.1 二维图形平移变换193.1.1 二维图形平移变换基本原理193.1.2 二维图形平移变换算法描述与步骤193.1.3 二维图形平移变换算设计与代码实现213.2 二维图形缩放变换213.2.1 二维图形缩放变换基本原理213.2.2 二维图形缩放变换算法描述与步骤213.2.3 二维图形缩放变换算法设计与代码实现223.3 二维图形对换变换233.3.1 二维图形对换变换基本原理233.3.2 二维图形对换变换算法描述与步骤233.3.3 二维图形对换变换算设计与代码实现253.4 二维图形旋转变换263.4.1

5、二维图形旋转变换基本原理263.4.2 二维图形旋转变换算法描述与步骤263.4.3 二维图形旋转变换算设计与代码实现264、图形填充算法274.1 种子填充算法304.1.1 种子填充算法基本步骤304.1.2 种子填充算法设计与代码实现304.2 边标志填充算法304.2.1 边标志填充算法基本步骤314.2.2 种子填充算法设计与代码实现314.3 小结325、总结和展望326、参考文献331、概论1.1 什么是计算机图形学计算机图形学是利用计算机研究图形的表示、生成、处理、显示的学科。计算机图形学计算机科学中，最为活跃、得到广泛应用的分支之一。1.2 计算机图形学的研究内容如何在计算机

6、中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法，构成了计算机图形学的主要研究内容。图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。1.3 基本概念1.3.1 怎样用计算机生成、处理和显示图形的学科(1)图形的输入如何开发利用图形输入设备及软件将图形输入到计算机中去，以便作各种处理(2)图形的处理包括对图形进行变换(几何变换，投影变换)和运算(集合运算)，裁减，着色，形变等(3)图形的输出如何将图形特定的表示形式转换成图形输出系统便于接受的表示形式，并将图形在显示

7、屏或打印机等输出设备上输出，或以文件的形式保存在磁盘上。1.3.2 相关的概念(1)图形：计算机图形学的研究对象，能在人的视觉系统中产生视觉印象的客观对象，包括自然景物、拍摄到的图片、用数学方法描述的图形等等构成图形的要素(2)几何要素：刻画对象的轮廓、形状等(3)非几何要素：刻画对象的颜色、材质等1.4 计算机中表示图形的方法1.4.1 点阵表示枚举出图形中所有的点（强调图形由点构成）简称为图像（数字图像）1.4.2 参数表示由图形的形状参数（方程或分析表达式的系数，线段的端点坐标等）以及属性参数（颜色、线型等）来表示图形简称为图形2.直线生成算法2.1 直线数值微分算法2.1.1 数值微分

8、算法基本原理设直线的起点坐标为（x0,y0）,终点坐标为（x1,y1）,二者均为整数坐标值,令dx=x1-x0,dy=y1-y0,则直线斜率k为：k=dy/dx目标是能快速地求出能很好地表示直线的像素，涉及到大量的重复性的运算，因此，尽量用加法代替乘法运算，因为计算机中：加法运算比乘法运算效率高2.1.2 数值微分算法描述与步骤当|k|01时，从x的左端点x0开始，向x右端点步进。步长=1个像素（即Dx=1）,计算相应的y坐标y=kx+B；取像素点（x,round（y）作为当前点的坐标。注意到：yi+1=kxi+1+B=k（xi+Dx）+B=kxi+B+kDx=yi+kDx=yi+k即：当x每

9、递增1,y递增k（即直线斜率）；上述分析的算法仅适用于|k|<1的情形。在这种情况下，x每增加1,y最多增加1当|k|>1时，必须把x,y地位互换2.1.3 数值微分算法设计与代码实现线段DDA算法伪代码描述下面用伪代码给出DDA算法。ProcedureDDA-line(x1,y1,x2,y2)BEGIN/求线段在两坐标轴方向改变量的较大者/IFabs(x2-x1)>=abs(y2-y1)THENlength=abs(x2-x1)ELSElength=abs(y2-y1)ENDIF/定义dx或dy中的较大值为1/dx=(x2-x1)/lengthdy=(y2-y1)/leng

10、thx=x1+0.5*Sign(dx)y=y1+0.5*Sign(dy)i=1WHILE(i<length)PLOT(Integer(x),Integer(y)x=x+dxy=y+dyi=i+lENDWHILEEND2.1.4 小结这种方法计算方法的缺点是计算量大。考虑到在计算机上实时编辑修改图形时，连续不断的需要在显示器上显示出大量的直线段，画线的速度就会非常地慢。因此需要对上述结果详细分析已给出较快的算法。2.2 直线中点画线算法2.2.1 数值微分算法基本原理原理假设直线的斜率0<k<1；当前像素点为P(xp,yp),下一个像素为Pi或P2设M=(xp+1,yp+0.5

11、),为pi与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较：M在Q的下方，则P2为下一点；M在Q的上方，则R为下一点。图2.1a图2.1b2.2.2 数值微分算法描述与步骤构造直线方程F(x,y)=ax+by+c=0调整方程参数，使得：点(x,y淞于直线上方：F(x,y)>0;点(x,y淞于直线下方：F(x,y)<0;把中点M的坐标带入方程，构造判别式：=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c因此：当d>0时，点M位于Q点上方，取R为下一点；当d<0时，点M位于Q点下方，取P2为下一点；d=0时，Q和M

12、重叠，任取R、P20如果取R,则可合并为d0时取Pi判别式d的增量算法:设确定Pi(xi,y)位置时判别式的值为di,则:如果di斗，贝UXi=Xi-1+1,yi=yi-1di=F(Xi-i+1,yi-i+0.5)=F(xi,yi+0.5)=axi+b(yi+0.5)+cdi+1=F(Xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c=axi+b(yi+0.5)+c+a=di+adi洲Ti+1=di+a如果di<0,则xi=xi-1+1,yi=yi-1+1di=F(xi-1+1,yi-1+0.5)=F(xi,yi-0.5)=axi+b(yi-0.5)+cdi+1=F(xi+

13、1,yi+0.5)=a(xi+1)+b(yi+0.5)+c=axi+b(yi-0.5)+c+a+b=di+(a+b)di<0di+1=di+a+b直线的起始端点坐标为(x0,y0),则:di=F(x0+1,y0+0.5)=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b(F(x0,y0)=0)=a+0.5b(存在0.5b,为浮点运算)整数算法:算法中仅用到判别式d的符号，所以可用2d代替d进行递增运算:2.2.3 中点划线算法设计与代码实现voidMidpointLine(intx0,inty0,intxi,intyi,intcolor)inta,b,di,d2,d,x,

14、y;a=y0-yi,b=xi-x0,d=2*a+b;di=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<xi)if(d<0)x+,y+,d+=d2;elsex+,d+=d1;drawpixel(x,y,color);2.2.4 小结如上面代码所示，DDA算法中的y和k都必须用浮点数表示，并且每一步运算都要对y进行舍入取整，这不利于硬件实现。中点画线法只包含整数变量，并且不含乘除法，因而解决了上述问题2.3 直线Breseham画线算法2.3.1 直线Breseham画线基本原理Bresenham直线算法最初是为数字绘图仪

15、而设计的。它的目标是选择表示直线的最佳像素点位置.为此,算法根据直线的斜率确定在x或y方向上每次递增一个单位，而另一方向上根据理论直线段与最近像素点的距离每次的增量为0或1。我们首先讨论直线斜率m0,1耳x2>xi时的整数Bresenham算法，然后再推广到画任意线段的算法。2.3.2 直线Breseham画线算法描述与步骤当直线斜率m60,1,且x2>xi时,根据式(2.2.9府:(叫+1=Xi+1%+i=yi+m又由于显示直线的像素点只能取整数值坐标，可以假设直线上第i个像素点坐标为(Xi,yi),它是直线上点(Xi,yi)的最近似并且Xi=xio于是，要表达的直线上下一个(X

16、i+i,yi+i)=(Xi+1,yi+m)的最近似的像素点的可能位置是(Xi+1,yi)或(Xi+1,yi+1)。在x=Xi+1处，直线上点的坐标y=m(Xi+1)+b.该点与点(Xi+1,yi)和(Xi+1,yi+1)的距离分别是d1和d2：d1=y-yi=m(Xi+1)+b-yi?d2=(yi+1)-y=(yi+1)-m(Xi+1)-b这两个距离的差为：d1-d2=2m(Xi+1)-2yi+2b-1这个差有如下几何意义:?当此值为正时，真正的直线上点离像素点(Xi+1,yi+1)较近，说明下一个直线上的像素点应取(Xi+1,yi+1)。(2)当此值为负时，真正的直线上离像素点(Xi+1,y

17、i)较近，说明下一个直线像素点应取(Xi+1,yi)。(3)当此值为零时，真正的直线上离上、下两个像素点的距离相等，我们规定取(Xi+1,yi)作为下一个直线像素点。？因止匕，只要利用(di-d2)的符号就可以决定下一个像素点的选择。如果我们定义一个新的判别式：?Pi=?x?(di-d2)=2?y-i-2?xiy+c(2.2.18)因此式中的?x=(X2-xi)>0,pi与(di-d2)有相同符号；?y=y2-yi；常数c=2?y+?x(2b-i)。pi的一个优点是省去了(di-d2)中为了计算m所需要的除法运算。我们知道除法运算用硬件实现是比较复杂的。现在我们要进一步化简上述误差判别式

18、以得到递推公式，消除常数c.以i+i代换此式中的i,得到：Pi+i=2?y-i+i-2?xi+i+c与前式相减，并利用xi+i=xi+i,可得，Pi+i=pi+2?y-2?xi(y-yi)再假设直线的初始端点恰好是其像素点的坐标,即满足：于是可得Pi的初值yi=mxi+bpi=2?y-?x这样，利用误差判别变量，并注意到每一步x的增量为xi+i-xi=i就可得到如下算法表示：(1) .(2) .如果R>0,pi=2?y-?xxi+i=xi+i(2.2.23)2.2. 直线点阵转换算法(3).如果pi<0,yi+i=yi?pi+i=pi+2?y从式(2.2.20)可以看出，第i+1步

19、的判别变量*仅与第i步的判别变量p直线的两个端点坐标分增量？x和？y有关,计算也很简单，只用整数相加和乘2运算，没有四舍五入处理，而乘2可利用左移一位来实现，因此这个算法速度快并易于硬件实现。该算法的主要步骤如下：？(1)输入线段的两个端点分别存于(xs,ys)和(xe,ye)中,(2)将第一点作为起始点，即有(xi,yi)=(xs,ys),(3)分别计算？x、?y>pi,pi<0,下一点为(xi+1,yi),否则，取(xi+1,yi+i),?(4)以单位步长增加x坐标，按式(2.2.24)或(2.2.25)计算pi。若pi<0,下一点的y坐标不变，否则y坐标加1。？(5)重

20、复步骤直到x逐步增加到xe为此。？在前面的处理中，我们假设m60,1。这一假设的几何意义是要绘的直线段与x-轴的夹角不超过与y-轴的夹角。或者更直观地，直线段的方向更靠近x-轴方向，如果有m>1,则说明直线段的方向更靠近y-轴方向。如果我们互换两个坐标轴，则直线段就满足前面的假设条件.因此，只要将算法中的x和y对换,则上述两个公式依然有效。如果m<0,则相应的只是x或y的方向的改变后，上述两个公式依然有效。这时实际上只是改变？x或?y的符号即可.2.3.3 直线Breseham画线算法设计与代码实现ProcedureBresenham-line(xs,ys,xe,ye)BEGINd

21、x=ABS(xe-xs);dy=ABS(ye-ys);x=xs;y=yss1=SIGN(xe-xs),s2=SIGN(ye-ys)Ifdy>dxTHENtemp=dx;dx=dy:dy=tempinterchange=1ELSEinterchange=OENDIFp=2*dy-dxFORi=1TOdxPLOT(x,y)IFp>=OTHENIFinterchange=1x=x+s1ELSEy=y+s2ENDIFp=p-2*dxENDIFIFinterchange=1THENy=y+s2ELSEx=x+s1ENDIFp=p+2*dyNEXTiEND2.3.4 小结以下是近似图形和真实直

22、线之间的差距，可以看得出来，其实实际上图形差距已经很小了。(2).实际要求的直线及其近似点3 .二维图形变换3.1 二维图形平移变换3.1.1 二维图形平移变换基本原理平移是指点从一个位置到另一个位置的直线移动，即把点P(x,y)平移到P(x'，y),在x-方向移动了距离Tx,在y-方向移动了距离Ty。于是可得平移公式冷范(621)平移变换用向量解释更清晰：平面上每一点都对应着一个从坐标原点到这一点的向量，平移变换实际上就是把整幅图形沿某个方向移动一段距离，这就是每个点加上一个向量.用坐标表示出的这个向量就是Tm=(Tx,Ty),称为平移矢量或位移矢量。用向量表示的平移变换公式就是1

23、k*¥>OPf=OP+PPf=OP+Tm(622)3.1.2 二维图形平移变换算法描述与步骤显然多边形的平移变换是由构成多边形的每一条线的始、末点的坐标都加上相应的平移量而得到的。如图6.1所示,多边形从一个位置平移至另一个位置时，其平移量为(Tx,Ty)o由此可见。多边形的平移是通过改变定义其边的坐标值实现的，不需要对多边形边上的每一点都作变换。而圆和椭圆的平移则需要通过移动其园心坐标和依据其半径来实现。平移坐标系的平移变换最后要说明的是如果认为坐标系在X-方向移动了距离Tx,在y-方向移动了距离Ty,得到新的坐标系O'x'Y:则在新的坐标系下，相当于点在X-

24、方向反向移动了距离Tx,在y-方向反向移动了距离Tyo于是可得平移公式(6.2.4)y=y-Ty而不是(6.2.1).用向量表示的平移变换公式就是(yp=OP-OOf(625)3.1.3 二维图形平移变换算设计与代码实现voidmyDrawl(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/将当前矩阵设为单位矩阵glColor3f(1.0,0.0,0.0);drawSquare();/在原点处绘制边长为2红色正方形glTranslatef(2.0,3.0,0.0);向右移动2单位，向上移动3单位glColor3f(0.0,1.0,

25、0.0);drawSquare();/绘制边长为2绿色正方形glTranslatef(0.0,-3.0,0.0);/再向下移动3单位glColor3f(0.0,0.0,1.0);drawSquare();/绘制边长为2蓝色正方形glFlush();3.2 二维图形缩放变换3.2.1 二维图形缩放变换基本原理一个图形的尺寸，变换前、后成比例变化，即称之为比例变换。通过x-和y-坐标轴方向的比例变换因子Sx和Sy使点P(x,y)变换为P'(x'，y),则(627)3.2.2 二维图形缩放变换算法描述与步骤如果选择一个能控制图形比例变换的点，使该点在变换后仍保持不变,则称其为基点。可

26、以选择图形的顶点、中心点或其他任何位置的点为基点。上述比例变换只适合基点在坐标原点的比例变换对于一个指定基点（xF,yF）（见图6.3）的比伊J变换,首先把坐标系原点平移到基点,来的原在新坐标系下作基点在原点的比例变换，然后再把坐标系的原点平移回原点。这时的比例变换公式为：.X图6.3图形相对于基点年冉学尸）的比例变换(629)工=工+(工-HF)Sc/=yr+(I/-既3.2.3 二维图形缩放变换算法设计与代码实现voidmyDraw12(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/将当前矩阵设为单位矩阵glColor3f(

27、1.0,0.0,0.0);drawSquare();/在原点处绘制边长为2红色正方形glScalef(1.0,1.5,1.0);/X和Z方向保持不变，Y方向放大为原来的1.5倍glColor3f(0.0,1.0,0.0);drawSquare();/绘制边长为2绿色正方形glTranslatef(0.0,-3.0,0.0);/再向下移动3单位glColor3f(0.0,0.0,1.0);drawSquare();/绘制边长为2蓝色正方形glFlush();)3.3 二维图形对称变换3.3.1 二维图形对称变换基本原理对称变换又可称为反射变换，镜像变换，从几何直观上表现为不同的类型：有关于x-轴

28、，y-轴的对称变换，以及关于直线y=x,y=-x的直线对称变换，当然也有关于任意一条直线的对称变换。3.3.2 二维图形对称变换算法描述与步骤(1)关于x-轴的对称变换?设对点P(x,y)乍关于x-轴的对称变换后，得到点'''一、一，、一一P(x,y),则变换的特点是x坐标不变，y坐标由正变负，由负变正，即改变了符号.于是变换公式为：(6218)J=T虱=-y这一变换的矩阵表示如下:(6,2.19)(2)关于y-轴的对称变换设对点P(x,y)作关于y-轴对称变换后，得到点P'(x'，y'),则变换的特点是y坐标不变，x坐标由正变负，由负变正，即改

29、变了符号.于是变换公式为这一变换的矩阵表示如下:Tf=Xyf=y(6220)(6221)图63点（招引的各种对祢点位置示意图(一E,（4）关于任意直线，任意点的对称变换上述对称变换是对特定的直线和点的对称变换.对于任意点（这一点称对称中心）的对称变换，类似于前面的一般的比例变换和旋转变换，先要把坐标系原点平移到对称中心，再进行坐标系原点的对称变换，然后把坐标系平移回原来的坐标系原点。关于以任意指定直线作对称轴的对称变换，可先把坐标系原点平移到对称轴线上,再旋转坐标系，使x-轴（或上述其它三种轴对称变换的轴线）重合于这里的轴线；这时作相应的轴对称变换；然后，反向旋转坐标系到原来的坐标系方向，并把

30、坐标系原点平移回原来的坐标系原点即可把关于坐标系原点及两条坐标轴的对称变换和比例变换结合起来考虑，我们可以看出比例变换的比例系数也可以是负数，这时的变换结果实际上相当于同时进行了比例变换和对称变换.如果两个比例系数都是负数，则对称变换是关于原点的对称变换；如果只有一个比例系数是负数，则对称变换是关于负数比例因子对应的坐标轴的对称变换。3.3.3 二维图形对称变换算法设计与代码实现voidmyDraw3(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/将当前矩阵设为单位矩阵glColor3f(1.0,0.0,0.0);drawSqu

31、are();/在原点处绘制边长为2红色正方形glScalef(1.0,1.5,1.0);/X和Z方向保持不变，Y方向放大为原来的1.5倍glColor3f(0.0,1.0,0.0);drawSquare();/绘制边长为2绿色正方形glSymmetry(0.0,-3.0,0.0);/对称变换glColor3f(0.0,0.0,1.0);drawSquare();/绘制边长为2蓝色正方形glFlush();3.4 二维图形旋转变换3.4.1 二维图形旋转变换基本原理图形上的点以坐标原点为中心旋转一定角度产生的变换称为旋转变换。设点P(x,y流转至P'(x',y'),旋转角

32、为0(为确定起见设逆时针方向为旋转的正方向)3.4.2 二维图形旋转变换算法描述与步骤角小是P(x,y)点在xy-平面内与x-轴的夹角，用来定义对点P(x,y)乍旋转变换时的起始位置，即有x=rcos2/=rsind(6212)3.4.3 二维图形变换算法设计与代码实现voidmyDraw4(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/将当前矩阵设为单位矩阵glColor3f(1.0,0.0,0.0);drawSquare();/在原点处绘制边长为2红色正方形glScalef(1.0,1.5,1.0);/X和Z方向保持不变，Y

33、方向放大为原来的1.5倍glColor3f(0.0,1.0,0.0);drawSquare();/绘制边长为2绿色正方形glRotatef(30,0.0,0.0,1.0);/顺时针旋转30角度glColor3f(0.0,0.0,1.0);drawSquare();/绘制边长为2蓝色正方形glFlush();4 .图形填充算法4.1 种子填充算法4.1.1 种子填充算法基本步骤(1)多边形的表示方法表小方法：顶点表小和点阵表小顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。点阵表示是用位于多边形内的像素的集合来刻划多边形，该方法虽然没

34、有多边形的几何信息，是面着色所需要的图像表示形式。多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。多边形顶点表示多边形点阵表示(2)活性边表算法扫描线算法基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。对于一条扫描线填充过程可以分为四个步骤：(1)求交(2)排序(3)配对(4)填色存在问题多边形顶点与扫描线相交，交点数量计算不当会产生交点配对错误。解决方式：下闭上开边界像素是否填充，处理不当造成填充不足或填充范围扩大化。解决方式：左闭右开

35、数据结构活性边表(AET):把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，结点内容包括:x:当前扫描线与边的交点x坐标x:从当前扫描线到下一条扫描线间x的增量ymax该边所交的最高扫描线号ymax指向链表中下一单元的指针(该结构中隐含了y值为当前的扫描线号)P6P1P5P6P4P5P3P42-o207Axymax例5-I.。7Bxymax72I108CxymaxDxymax算法步骤：1. （AET初始化）将边的活性边表AET设置为空；2. （y初始化）取扫描线纵坐标y的初始值为新边表NET中非空元素的最小序号；3. 按顺序对纵坐标值为y的扫描线（当前

36、扫描线）执行下列步骤，直到NET和AET都变成空为止：将AET中满足y=ymax的边删去； 如果NET中的第y行元素非空，则将属于该行的所有边从NET中取出并插入AET中，AET中的各边按照x值（当x的值相等时，按Ax值）递增方向排序； 若相对于当前扫描线，AET非空，则将AET中的边两两依次配对，即第1,2边为一对，第3,4边为一对，依此类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（像素）按多边形属性着色； 将AET剩下的每一条边的x域累加Ax,即令x=x+Ax; 将当前的扫描线的纵坐标值y累加，即y=y+1。4.1.2种子填充算法设计与代码实现voidFl

37、oodSeedFill(intx,inty,intold_color,intnew_color)if(GetPixelColor(x,y)=old_color)(SetPixelColor(x,y,new_color);for(inti=0;i<COUNT_OF(direction_8);i+)(FloodSeedFill(x+direction_8i.x_offset,y+direction_8i.y_offset,old_color,new_color);4.2 边标志填充算法4.2.1 边标志填充算法基本步骤与代码边界填充算法与注入填充算法的本质其实是一样的，都是递归和搜索，区别只在于对边界的确认，也就是递归的结束条件不一样。注入填充算法没有边界的概念，