计算机图形学完整课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机图形学,第一章、绪论,第二章、基本图形生成原理,第三章、图形几何变换,第四章、多边形及多边形填充算法,第五章、图案及动画程序设计,第六章、裁剪算法,第七章、自由曲线,第一章、绪论,1.1,、概述,1.2,、计算机图形学的发展,1.3,、计算机图形学的应用,1.4,、计算机图形系统,1.5,、计算机图形标准,1.1,概述,1.1.1,计算机图形学的概念,计算机图形学,Computer Graphics,是一门新兴学科，国际标准化组织,ISO,定义为,:,计算机图形学是一门研究通过计算机将数据转换成图形，并在专门显示设备上显示的原理方法和技术的学科。它是建立在传统的图学理论，应用数学及计算机科学基础上的一门边缘学科。,计算机图形学的研究内容,1.,基于图形设备的基本图形元素的生成算法。,2.,图形元素的几何变换。,3.,自由曲线和曲线的插值、拟合、拼接、分解、过渡、光顺、整体和局部修改等。,4.,三维几何造型技术。,5.,三维形体的实时显示。,6.,真实感图形的生成算法。,7.,山、水、花、草、烟云等模糊景物的模拟生成和虚拟现实环境的生成。,8.,科学计算可视化和三维或高维数据场的可视化。,1.1.3,计算机图形学与图象处理的关系,计算机图形学的基本含义是使用计算机通过算法和程序在显示设备上构造出图形来。也就是说，图形是人们通过计算机设计和构造出来的，不是通过摄象机和扫描仪等设备输入的图象。所设计和构造的图形可以是现实世界已经存在的物体的图形，也可以显示完全虚构的物体。因此，计算机图形学是真实的物体或虚构物体图形的综合技术。,与此相反，图象处理是景物或图象的分析技术，它所研究的是计算机图形学的逆过程，图象增加、模式识别、景物分析、计算机视觉等，并研究如何从图象中提取二维或三维物体的模型。,尽管计算机图形学和图象处理所涉及的都是用计算机来处理图形和图象，但是长期以来却属于不同的两个技术领域。近年来，由于多媒体技术、计算机动画、三维空间数据场显示及纹理映射等的迅速发展，计算机图形学和图象处理的结合日益紧密，并相互渗透。,1.2,计算机图形学的发展,1.2.1,计算机图形学的发展简史,年代准备阶段,年代发展阶段,年代推广应用阶段,年代系统实用化阶段,年代标准化智能化阶段,1.2.2,计算机图形学的发展方向,造型技术的发展,真实图形生成技术的发展,人,机交互技术的发展,模拟艺术的仿真,计算机动画,1.3,计算机图形学的应用,1.,用户接口,2.,计算机辅助设计与制造（,CAD/CAM,）,3.,地形地貌和自然资源图,4.,计算机动画和艺术,5.,科学计算可视化,6.,游戏,1.4,计算机图形系统,计算机图形系统硬件,计算机图形系统软件,计算机图形显示原理,光栅扫描式图形显示器,1.5,计算机图形标准,GKS,PHIGS,CGM,CGI,第二章、基本图形生成原理,2.1,直线的生成,2.2,圆与椭圆的生成,2.1,直线的生成,2.1.1,数值微分法,(DDA,法,),2.1.2,中点画线法,2.1.3 Bresenham,画线算法,2.1.4 Turboc 2.0,图形函数介绍,数值微分法,:,直线方程,y=k,x+b ,给出线段的两个端点,(x1,y 1),和,(x2,y2),可以算出,k,和,b,k=y/x=(y2-y1)/(x2-x1),b=y1-k,x1,再用,setpixel(x,int (y0.5),color),输出该系统的颜色值便可画出直线,.,但是画线效率太低,这是因为每步都需浮点乘法运算和一个四舍五入,.,数值微分算法的描述,对任何沿直线给定的,x,的增量,x,可以从下中计算出,y,的增量 ,y=k,x ,同样可以得出对应于指定的 ,x= y/k ,当对于斜率的绝对值,|k|1,的线段怎么实现呢,?,算法演示,中点画线法,那么，下一个与直线最近的像素只能是正右方的,p1(,，,),或右上方,p2,（ ， ）用空心小圆表示。再以,M,表示,P1,与,p2,的中点，即,M=,（ ， ）。又设,Q,是理想直线与垂线 交点。显然，若,M,在,Q,的下方，则,p2,离直线近，应取为下一个像素；否则应取,p1,。这就是中点画线法的基本原理。,为了讨论方便，这里假定直线斜率在,0-1,之间，其它两种情况可参照下述讨论进行相应处理。,如图所示，若直线在,x,方向增加一个单位，则在,y,方向的增量只能在,0-1,之间。假设直线上当前已确定的一个像素点坐标为（,x,p,，,y,p,），用实心小圆表示。,P=(x,p,y,p,),G,算法推导：,下面我们来讨论中点画线算法的实现。假设直线的起点和终点分别为（,x1,y1,）和（,x2,y2,）则直线方程为,F(x,y)=a,x+b,y+c=0,其中，,a=y1-y2,，,b=x2-x1, c=x1,y2-x2,y1,。对于直线上的点,F(x,y)=0;,对于直线上方的点,F(x,y)0;,对于直线下方的点,F(x,y)0,。因此，欲判前述,Q,在,M,的上方还是下方，只要把,M,代入,F(x,y),并判断它的符号。构造判别式,d=F(M)=F( , )=a( )+b( )+c,当,d0,则应取正右方的,p1,。,当,d=0,是，二者一样合适，可以随便取一个。,我们约定取正右方的,p1,。 对每一个象素计算判别式,d,，根据它的符号确定下一象素。由于,d,是,x,p,和,y,p,的线性函数，可采用增量计算，以便提高运算效率。,在,d0,的情况下，取正右方的象素,p1,，欲判断再下一个象素应取哪个，应计算,d1=F( +2, +0.5) =a( +2)+b( +0.5)+c,=(a( +1)+b( +0.5)+c)+a =d+a,故,d,的增量为,a,。,而若,d0,，则取右上方象素,p2,。要判断再下一个象素，则要计算,d2=F( +2, +1.5) =a( +2)+b( +1.5)+c =(a( +1)+b( +0.5)+c)+a+b =d+a+b,故在第二种情况，,d,的增量为,a,b,。,再看,d,的初始值。显然，第一个象素应取左端点（,x1,，,y1,），相应的判别式值为,d,0,=F( +1, +0.5) =a( +1)+b( +0.5)+c =(a,x1+b,y1+c)+a+0.5,b,=F(x1,y1)+a+0.5,b,但由于（,x1,y1,）在直线上，故,F(x1,y1)=0,。因此,d,的初始值为,d0=a+0.5,b,由于我们使用的只是,d,的符号，而且,d,的增量都是整数，只是其初始值包含小数。因此，我们可以用,2d,代替,d,，来摆脱小数，写出仅包含整数运算的算法：,void MidpointLine(x1,y1,x2,y2,color)int x1,y1,x2,y2,color; int a,b,d1,d2,dx,y; a=y1-y2; b=x2-x1; d=2*a+b; d1=2*a; d2=2*(a+b); x=x1; y=y1;,setpixel(x,y,color);while(xx2)If(d0)x+;y+d+=d2;elsex+;d+=d1;setpixel(x,y,color);,2.1.3 Bresenham,画线算法,算法分析,算法推导,可视化效果图,2.1.4,图形环境的设置,#include,”,graphics.h,”,图形方式初始化函数：,initgraph(*gdriver,*gmode,*path);,gdriver:,是一个空型指针，用来指定要装入的图形驱动程序，该值在头文件中定义；,gmode:,是一个空型指针，用来指定显示模式,path:,图形驱动程序所在的路径,若用,VGA,图形驱动程序,图形显示模式为,VGAHI,则调用方式如下,:,int gdriver,gmode;,gdriver=VGA,gmode=VGAHI,initgraph(&gdriver,&gmode,”,c:TC,”,);,关闭图形方式函数为,closegraph(),直线类绘图函数,line(x1,y1,x2,y2);,lineto(x,y);,moveto(x,y);,line(dx,dy);,几个直线段组成的图形,图一,图二,2.2,圆与椭圆的生成,由于圆是图形和图像中经常使用的元素，因此在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的绘图函数。,圆的特性,圆被定义为所有离一中心位置（,x,c,y,c,）距离为给定值,r,的点集，可用如下方程式表示：,(x-x,c,),2,+(y-y,c,),2,=r,2,利用这个方程，我们可以沿,x,轴从,x,c,-r,到,x,c,+r,以单位步长计算对应的,y,值来得到圆周上每点的位置：,y=y,c, (r,2,-(x,c,-x),2,),但这并非是生成圆的最好方法。这个方法的第一个问题是每一步包含很大的计算量。,第二个问题是所画像素位置间的间距是不一样的，在靠近,x,轴的,0,o,180,o,处像素点之间的间距越来越大。 当然可以在圆斜率的绝对值大于,1,后，交换,x,和,y,（即步进,y,值，计算,x,值）来调整间距。但这样增加了算法所需的计算量和处理过程。,另一种消除不等间距的方法是使用极坐标,r,和,来计算沿圆周的点。以参数极坐标形式表示圆方程可得到方程组：,x=x,c,+r cosy=y,c,+r sin,使用上述方法以固定角度为步长生成显示时，圆就可沿圆周等距点绘制出来。但这个方法使用了三角函数调用和浮点运算，运算速度太慢。 必须寻找只需做一些简单的 整数运算和判别运算的方法即可确定圆上的象素点的算法。,考虑到圆的对称性可以减少计算量。只要能生成,8,分圆，那么圆的其它部分可以通过一系列的简单映射变换得到。如图所示，假设已知一个圆心在原点的圆上一点,(x,，,y),，,根据对称性可得另外七个,8,分圆上的对应点,(y, x),，,(y, -x),，,(x, -y),，,(-x,-y),，,(-y,-x),，,(-y, x),，,(-x, y),。 因此，只需讨论,8,分圆的生成算法。,另外，为了方便起见，我们只考虑中心在原点，半径为整数,R,的圆,x,2,+y,2,=R,2,。对于中心不在原点的圆，可先通过平移变换，化为中心在原点的圆，再进行扫描转换，把所得的像素坐标加上一个位移量即得所求像素坐标。,中点画圆法,考虑中心在原点，半径为,R,的圆的第二,8,分圆。我们来讨论如何从（,0,，,R,）到（,R/,），（,R/,）顺时针的确定最佳逼近于该圆弧的像素序列。,假定当前已确定了一个象素点为,p(x,p,y,p,),那么 下一个象素只能是正右方的,p1(x,p,+1,y,p,),或右下方的,p2(x,p,+1,y,p,-1),。,p,1,P=(x,y),x,p,x,p+1,x,p+2,y,p,y,p-1,y,p-2,p,2,M,如图所示，构造函数：,F(x,y)=x,2,+y,2,-R,2,对于圆上的点，,F(x,y)=0;,对于圆外的点，,F(x,y),0;,而对于圆内的点,F(x,y),0.,假设,M,是,P1,和,P2,的中点，即,M,（,x,p,+1,y,p,-0.5,）,P=(x,y),x,p,x,p+1,x,p+2,p,2,M,y,p,y,p-1,y,p-2,p,1,那么当,F(M)0,时，,p2,离圆弧更近，应取,p2,。,当,F(M)=0,时，在,p1,与,p2,之中随便取一个即可，我们约定取,p2,P=(x,y),x,p,x,p+1,x,p+2,p,2,M,y,p,y,p-1,y,p-2,p,1,与中点画线法一样，构造判别式,d=F(M) =F(x,p,+1, y,p,-0.5) = (x,p,+1),2,+ (y,p,-0.5),2,-R,2,当,d0,，则应取,p1,为下一象素，而且再下一个象素的判别式为,d=F(x,p,+2,y,p,-0.5) =(x,p,+2)2+(y,p,-0.5),2,-R,2,=d+2x,p,+3,p,1,P=(x,y),x,p,x,p+1,x,p+2,p,2,M,y,p,y,p-1,y,p-2,所以，沿正右方，,d,的增量为,2x,p,+3,。而若,d0,，则,p2,是下一象素，而且下一象素的判别式为,: d=F(x,p,+2,y,p,-1.5) =(x,p,+2),2,+(y,p,-1.5),2,-R,2,=d+(2x,p,+3)+(-2y,p,+2),=d+2(x,p,-y,p,)+5,P=(x,y),x,p,x,p+1,x,p+2,p,2,M,y,p,y,p-1,y,p-2,p,1,所以，沿右下方向判别式,d,的增量为,2(x,p,-y,p,)+5,。 由于我们这里讨论的是用顺时针方向生成第二个,8,分圆，因此第一个象素点是,(0,R),判别式,d,的初值为：,d,0,=F(1,R-0.5) =1+(R-0.5),2,-R,2,=1.25-R,由于使用了浮点数来表示判别式,d,，为了简化运算，摆脱浮点数，在算法中全部使用整数，我们使用,e=d-0.25,代替,d,。显然，初始化运算,d=1.25-r,对应于,e=1-r,。判别式,d0,对应于,e-0.25,。,算法中其它与,d,有关的式子可把,d,直接换成,e,。又由于,d,的初值为整数，且在运算过程中的增量也是整数，故,e,始终是整数，所以,e-0.25,等价于,e0,）。讨论：,若,a=d=1,，为恒等变换，即变换后点的坐标不变。,若,a=d1,，则为等比变换，变换结果是图形等比例放大（,a=d1,）后等比例缩小（,a=d0,时沿,+x,向错切；,c0,时，沿,+y,方向错切；,b0,），以使其与正投影面处于同一平面，使水平投影图和正面投影图拉开一个距离,，变换过程为：,变换结果为（,x,，,y,，,z,，,1,）*,Th =,（,x,，,0,，,-y-d3,，,1,）,=,（,x,，,y,，,z,，,1,）,设立体图的点集矩阵为（,Dj,），各投影图之间的距离为,10,，求立体的三面投影。,已知：,2,1,3,5,6,7,8,9,10,4,y,x,z,解：,1,）正面投影,(2),水平投影,(3),侧面投影,用变换后的 ， ， ，画出的三视图如下图,x,z,正轴测投影图,轴测图是一种简单的立体图形,能给人一种直观的形象,以帮助建立空间的概念,.,由于它的绘制方法比较简单,所以在工程制图中经常用到,.,1.,正轴测投影图的形成过程是这样的,:,先将空间一立体绕,z,轴正向旋转,角,然后再绕,x,轴反向旋转,角,最后让经过两次旋转后的立体向正立投影面做正投影。,整个形成过程可以用矩阵表示为,式子中，,和,均取大于,0,的值,。,上面的矩阵,T,是经过,3,个单步简单矩阵变换的级联形成的，它是一个正轴测投影交换矩阵的一般形式。因此，只要任意给定一组,和,角，代入矩阵,T,，就可以产生一种正轴测投影矩阵，由此，可用以生成正轴测投影图。,在正轴测变换过程中：,x,y,z,1=x y z 1 T=xcos-ysin 0 -sin(xsin+ycos)+zcos 1,从上式可以看到，交换的结果使,y,坐标为,0,，所以对于一般的二维坐标系来说，,y,坐标就相应于现在的,z,坐标。,2.,正等测和正二测 正等轴测投影图和正二等轴测投影图是正轴测投影图中常用的两种，其中正等测用手工绘制方法简便；正二测的立体感较好，但手工绘制方法没有正等测方便。当用计算机来生成的时候，就不存在方法上的差别，区别只是变换矩阵中的元素值不同而已。,（,1,）正等测的变换矩阵任一组,和,的角，可以产生一种正轴测投影变换矩阵。当取,=45,o,，,=35,o,16,时，代入矩阵,T,，就可以得到正等轴测投影的变换矩阵,T,。,（,2,）正二测的变换矩阵,形成正二等轴测投影的一组角度,和,的取值为：,=20,o,42,；,=19,o,28,。将此,和,的值代入正轴测矩阵，便可得到正二测的变换矩阵,。,3.,轴测图的编程步骤,下面，我们通过一个简单的立体例子，来说明设计和编写绘制轴测图的绘图程序的步骤。设所需绘制的立体如下图,则工作步骤如下：在草纸上绘制出草图，并确定各顶点的序号和相应顶点的坐标值，建立顶点表和边表，如下二个表。,1,2,3,4,5,6,7,8,9,10,11,12,z,y,x,顶点表,顶点号,x y z 1 0 0 0 2 0 0 200 3 200 0 200 4 0 50 40 5 0 50 40 6 0 50 200 7 200 50 200 8 200 50 40 9 200 150 40 10 0 150 0 11 0 150 0 12 200 150 0,边号 连边顶点,1 1 2 2 2 3 3 3 4 4 4 1 5 1 11 6 11 12 7 12 4 8 5 6 9 6 7 10 7 8 11 8 5 12 5 10 13 10 9 14 9 8 15 9 12 16 10 11 17 3 7 18 2 6,在程序中定义两个数组，用于定义顶点表和连边表。通过数组的初始化给两个数组赋初值。 实施对立体进行正轴测投影变换，即用正轴测投影变换矩阵顶点表实现。这样，可以得到一个变换后的新的顶点表。,用新顶点表的顶点坐标值，注意此时只有,x,坐标轴和,z,坐标轴，,y,坐标轴已在投影中消掉，所以是以,x,坐标为绘图的,x,坐标，以,z,坐标为绘图的,y,坐标。按连边表中的连边规则，用,line,函数在顶点之间两两连线。,在绘图程序中要注意两点： 在建立立体坐标时，为了取顶点坐标值简便，我们把立体的一个顶点放置在坐标的原点，所以，整个轴测投影变换后的图形是以该原点为中心。但图形输出时的中心应以屏幕中心为宜，比如，对于,VGA,来说，这个中央点在（,320,，,240,）处。 该绘图程序目前只能按连边表把立体的所有棱边都画出来，而不考虑是否可见，即没有经过消除隐藏线处理。,四,.,透视投影图,1.,透视变换矩阵,在前面讲的三维变换矩阵,中，已经说过， 所产生透视投影的效果。现在我们来具体讨论，当其中的,p,，,q,，,r,三个参数为非全,0,时，这样的变换矩阵会对变换产生什么样的影响。,（,1,）一点透视,先设,q0,，,p=r=0,。然后对点（,x,，,y,，,z,，,1,）进行变换，结果如下：,对其结果进行齐次化处理，得：,当,y,取值不同时，上式会产生如下不同的结果：,当,y=0,时，得：,而原来处于,y=0,的平面内的点，经过变换以后没有变化。,当,y ,时，得：,这说明，当,y ,时，所有的点的变换结果都集中到了,y,轴上的,1/q,处。,即所有平行与,y,轴的直线最终延伸将相交（,0,，,1/q,，,0,）的点，该点称为“灭点”。而象这样形成的一个灭点的透视变换称为“一点透视”。为了取得较好的效果，我们取,q0,，让灭点位于,y,轴的负半轴上。一点透视的效果如下,z,y,x,根据同样的道理，当,p0,，,q=r=0,时，则将含在,x,轴上的,1/q,处产生一个灭点，其坐标值为（,1/q,，,0,，,0,）。在这种情况下，所有平行于,x,轴的直线将延伸交于该点。,当,r 0,，,p=q=0,时，产生的一个灭点位于,z,轴上的,1/r,处，灭点的坐标为（,0,，,0,，,1/r,）。所有平行与这轴的直线将延伸交于该点。,（,2,）多点透视,根据一点透视的原理予以推广，如果在,p,，,q,，,r,三个元素中有两个为非零元素时，这将会产生两个灭点，因此得到两点透视。,经过齐次处理结果为：,从以上结果可以得到：,当,x ,时，一个灭点在,x,轴上的,1/p,处。,当,z ,时，另一个灭点在,z,轴上的,1/r,处。,这时，立体上所有平行于,x,轴的棱线，延伸时将相交于,x,轴上点（,0,，,0,，,1/r,）处。,同理，当,p,，,q,，,r,三个元素全为零时，结果将会产生三个灭点，从而形成三点透视。产生的三个灭点分别在,x,轴上的,1/p,处，,y,轴上的,1/q,处和,z,轴的,1/r,处。,2.,生成透视投影图的方法,生成透视投影图的过程分为两步：先是对立体进行透视变换；然后是将其投影到正面投影面上， 形成投影面上，形成正投影图。用矩阵形式表示为：,（,1,）一点透视图的生成,在生成一点透视图时，为了避免把图所属立体安置在坐标系的原点而产生如下图所示的透视效果,z,x,o,x,z,o,通常是在进行透视投影变换前，先将立体平移到一个合适的位置，然后再进行透视投影变换，使得产生的透视图效果较好。,生成一点透视投影的变换矩阵为,:,当,d1,，,d2,，,d3,和,q,取确定的非零值后，该矩阵中包含的三个透视变换参数中有一个为非零，所以该变换矩阵能产生一点透视图。在,q,的取值时，一般取,-1q0,）；,c.,进行透视变换；,d.,往正投影面进行正投影。,用矩阵的形式表示这个变换过程为：,从以上的变换矩阵,T,可以看到，矩阵中的三个透视变换参数均非,0,，因此可以变换生成三点透视图。,第四章、多边形及多边形填充算法,在这一节中将讨论图形系统中的新图元多边形，研究有关多边形的概念以及如何表示多边形，学习如何判断一个点是否在多边形内的方法，以及多边形填充的各种方法。,一、多边形的概念,所谓多边形，就是用一系列首尾相连的线段构成图形。这些组成多边形边界的线段称为多边形的边，多边形的边的端点称为多边形的顶点。一般来说，一个多边形应是封闭的。,1.,凸多边形与凹多边形,多边形又分为两大类：凸多边形与凹多边形。 所谓凸多边形，是指这样一类多边形：如果在多边形内任找两个点，将这两个点用线段连接后，此线段上所有的点都在多边形内，这就是凸多边形。而凹多边形就是非凸多边形。,下面给出了凸多边形与凹多边形的例子，可见，三角形总是凸多边形。,凸多边形,凹多边形,2.,多边形的描述,考虑到多边形的特征属性：顶点和边，在描述多边形时，既要指明组成多边形的顶点，又要指出组成多边形的边。 一般来说，用顶点的序列来表示多边形，其中的边即指两顶点所构成的线段，这样来表示的多边形如下：,p1,p2,p3,p4,p5,p6,p7,图中多边形顶点序列为,p1 p2 p3 p4 p5 p6 p7,。可以根据这种方法写出在计算机上绘制多边形的算法：,draw_polygon(int N,int pN2) if(N=2) return(); else for(i=1;iN;i+) line(pi0,p i1,pi+10,pi+11); line(p10,p11,pN0,pN1); ,二多边形的填充,1.,点是否在内部的检验,p1,p2,p4,p3,p5,s1,p1,s2,p2,p3,s5,S,3(s4),Pi+1,p,i,P,i-1,Y,i+1,Y,i,Y,i-1,Pi+1,pi,Pi-1,Y,i+1,Y,i,Y,i-1,2,连贯性原理,p2,p1,p3,p4,p5,p6,p7,p8,p9,x,2,x,1,x,3,x,4,x,5,x,6,梯形的两底边分别在,y=y,k,和,y=y,k+1,两条扫描线上，腰在多边形,p,的边上或在显示屏幕的边界上。,区域的连贯性,Y,k+1,y,k,这些梯形分为两类：一类位于多边形内部（图中粉色部分），另一类位多边形外部。 两类梯形在长方形区域上相间排列，即相邻的两个梯形必有一个在多边形内，一个在多边形外。,交点数为偶数；相邻交点间的线段也分为两类：一类线段上所有点均在多边形内部，另一类线段上所有点均在多边形外部；,两类线段在扫描线上相间排列。,扫描线的连贯性,对于多边形与扫描线,y=y,k,相交,交点序列,x1,x2,x3,x4,x5,x6,由连贯性可知,，此交点序列具有下列性质,边的连贯性,A,B,Y,i+1,Y,i,x,i,x,i+1,三、多边形填充算法,1,、扫描线算法,76543210,1 2 3 4 5 6 7 8,r,1,r,2,r,3,r,4,r,5,r,6,扫描线算法的步骤为：在,EL,中找出非空元素的最小序号：将边的活化链表置空；按从下至上的顺序分别处理每一条扫描线，直到边的分类表,EL,和边的活化链表均为空为止。,处理扫描线步骤为：,对于扫描线,y=y,c,若,EL,中非空，则将其所有的边从,EL,中取出，并且插入到边的活化链表中，并将,AEL,中各边按,x,递增顺序； 若相对于当前扫描线，边的活化链表,AEL,非空，则将,AEL,中的边两两依次配对，即第,1,，,2,边为一对，第,3,，,4,边为一对，依次类推，每一对边与当前扫描线交点所构成的线段位于多边形内，依次将这些线段上的点进行着色；,将边的活化链表中满足,y=y,max,的边删去； 将边的活化链表,AEL,中