计算机图形学第四章

1、 第4章 多边形 本章我们将讨论图形系统中本章我们将讨论图形系统中新的图元新的图元多边形，研究有多边形，研究有关多边形的概念以及多边形的关多边形的概念以及多边形的表示，学习如何判断一个点是表示，学习如何判断一个点是否在多边形内的方法，以及多否在多边形内的方法，以及多边形的各种填充方法，重点讲边形的各种填充方法，重点讲解种子填充算法。解种子填充算法。 第4章 多边形n1. 多边形的定义n2. 多边形的扫描转换n3. 区域填充(种子填充算法)n4. 反走样n定义：一系列定义：一系列首尾首尾相连的线段构成的图形。相连的线段构成的图形。n 线段线段 - 边边n 端点端点 - 顶点顶点4.1多边形的定义

2、一般情况：多边形是一般情况：多边形是封闭封闭的的n多边形分为凸多边形、凹多边形二种多边形分为凸多边形、凹多边形二种凸多边形：连多边形凸多边形：连多边形内任意内任意两点的两点的线段线段, ,该线段上的点均在多边形内。该线段上的点均在多边形内。n计算机生成的物体常常可以用若干多边形计算机生成的物体常常可以用若干多边形来描述，有些非多边形的物体，也可以用来描述，有些非多边形的物体，也可以用多边形来逼近。比如上一章二次曲线的绘多边形来逼近。比如上一章二次曲线的绘制我们了解了可以用多边形去逼近圆。在制我们了解了可以用多边形去逼近圆。在多边形生成以后，就可以利用光栅显示系多边形生成以后，就可以利用光栅显示

3、系统对其内部区域进行填充。统对其内部区域进行填充。n那么多边形是如何在系统中如何描述的呢？那么多边形是如何在系统中如何描述的呢？ 顶点表示顶点表示 点阵表示点阵表示 n顶点表示顶点表示：用多边形顶点的序列来刻划多边形。：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；缺点是不能直接直观、几何意义强、占内存少；缺点是不能直接用于面着色。用于面着色。n点阵表示点阵表示：用位于多边形内的象素的集合来刻划：用位于多边形内的象素的集合来刻划多边形。便于运用帧缓冲存储器表示图形，易于多边形。便于运用帧缓冲存储器表示图形，易于面着色。缺点是失去了许多重要的几何信息；面着色。缺点是失去了许多重要的

4、几何信息；4.2多边形的扫描转换多边形的扫描转换n在绘图过程中，仅有线条和多边形来表示在绘图过程中，仅有线条和多边形来表示是不够的，要逼真的显示一个实面图像至是不够的，要逼真的显示一个实面图像至少要解决以下三个问题：少要解决以下三个问题：n1、面的形状、面的形状n2、面上各点的色调、面上各点的色调(填充填充)n3、各个面的互相遮挡的问题、各个面的互相遮挡的问题(消隐消隐)n什么是多边形的扫描转换？什么是多边形的扫描转换？n从多边形顶点信息到该多边形点阵表从多边形顶点信息到该多边形点阵表示的转换示的转换多边形的扫描转换，多边形的扫描转换，也也就是从多边形的给定边界出发，求出就是从多边形的给定边界

5、出发，求出位于其内部的各个象素，并给帧缓冲位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度器内的各个对应元素设置相应的灰度和颜色，通常称这种过程为和颜色，通常称这种过程为多边形的多边形的扫描转换扫描转换( (又称多边形的填充又称多边形的填充) )。多边形的扫描转换多边形的扫描转换多边形的扫描转换多边形的扫描转换n常用几种方法：常用几种方法：n逐点判断法；逐点判断法；n扫描线算法；扫描线算法；n边填充法；边填充法；n栅栏填充法；栅栏填充法；n边界标志法。边界标志法。逐点判断法逐点判断法(1/7)(1/7)n算法思想：算法思想：n 逐个象素点判别，确定它们是否在多逐个象素点判别，确

6、定它们是否在多边形内，从而来决定是否进行着色。边形内，从而来决定是否进行着色。n如何判断点在多边形的内外关系？如何判断点在多边形的内外关系？1 1）累计角度法）累计角度法( (转角和法转角和法) )；2 2）射线法；）射线法；3 3）符号法；）符号法；逐点判断法逐点判断法(2/7)(2/7)1 1）累计角度法（转角和法）累计角度法（转角和法）n步骤步骤1.1.从某点向多边形顶点发出射线，形成从某点向多边形顶点发出射线，形成有向角有向角2.2.计算有向角的和，得出结论计算有向角的和，得出结论之内位于之外位于，PvPvnii,200若等于正负若等于正负180度表示度表示V在边界上。在边界上。该方法

7、适用于：凸多边形、凹多边该方法适用于：凸多边形、凹多边形形ABCDEPABCDEPABCDEPABCDEP交点数交点数=偶数（包括偶数（包括0）点在多边形之外点在多边形之外交点数交点数=奇数奇数点在多边形之内点在多边形之内逐点判断法逐点判断法(5/7)(5/7)2）射线法）射线法步骤：步骤：从从待判别点待判别点发出射线求交点个数发出射线求交点个数kK的的奇偶奇偶性决定了点与多边形的性决定了点与多边形的内内外外关系关系注意：注意：1、若射线恰好交于多边形、若射线恰好交于多边形R的端点，则如的端点，则如何处理？何处理？2、如何决定射线方向？、如何决定射线方向？逐点判断法逐点判断法(6/7)(6/7

8、)3）符号比较法（）符号比较法（ 适用于凸多边形适用于凸多边形） A基础知识基础知识二点式直线方程的表示及点与直线二点式直线方程的表示及点与直线的关系多边形各边所在方程的表示的关系多边形各边所在方程的表示方法方法nB步骤步骤n1、找多边形、找多边形内内一点一点M代入直线方代入直线方程，计算程，计算M相对于各边的符号情况。相对于各边的符号情况。n2、对待判定定、对待判定定P作同样的操作作同样的操作n3、对、对M和和P相对于各边的符号情相对于各边的符号情况作比较况作比较逐点判断法逐点判断法(7/7)#define MAX 100Typedef struct int PolygonNum; / 多边

9、形顶点个数多边形顶点个数 Point vertexcesMAX /多边形顶点数组多边形顶点数组 Polygon / 多边形结构多边形结构逐点判断法的算法伪码描述void FillPolygonPbyP(Polygon *P, int fillColor) int x,y; for(y = 0;y = 1023;y+) for(x = 0;x SetPixel(x,y, fillColor);else pDC- SetPixel (x,y,backgroundColor); / end of FillPolygonPbyP()假设整个屏幕区域只有一个多边形对整个屏幕假设整个屏幕区域只有一个多边形

10、对整个屏幕区域进行扫描，假设屏幕大小为区域进行扫描，假设屏幕大小为1024*768void FillPolygonPbyP(Polygon *P,int fillColor) int x,y; for(y = ymin;y = ymax;y+) for(x = xmin;x SetPixel(x,y,fillColor);else pDC- SetPixel(x,y,backgroundColor); / end of FillPolygonPbyP()对整个多边形区域进行扫描，比扫描整个屏幕对整个多边形区域进行扫描，比扫描整个屏幕肯定要节约时间，这是改进后的伪码描述肯定要节约时间，这是改进后

11、的伪码描述n逐点判断的算法的优缺点：逐点判断的算法的优缺点：n虽然程序简单，但不可取。原因是速虽然程序简单，但不可取。原因是速度太慢，主要是由于该算法割断了各度太慢，主要是由于该算法割断了各象素之间的联系，孤立地考察各象素象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚与多边形的内外关系，使得几十万甚至几百万个像素都要一一判别，每次至几百万个像素都要一一判别，每次判别又要多次求交点，需要做大量的判别又要多次求交点，需要做大量的乘除运算，花费很多时间。乘除运算，花费很多时间。n改进思想：除边界外，相邻像素几乎改进思想：除边界外，相邻像素几乎都有相同的特征。都有相同的特征。扫描线算

12、法n扫描线算法扫描线算法目标：利用相邻像素之间的连贯性，提高算法目标：利用相邻像素之间的连贯性，提高算法效率效率处理对象：非自交多边形处理对象：非自交多边形 （边与边之间除了（边与边之间除了顶点外无其它交点）顶点外无其它交点）扫描线算法扫描线算法(1/26)(1/26)n扫描线算法是多边形扫描转换的常用算法。扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利与逐点判断算法相比，扫描线算法充分利用了用了相邻象素之间的连贯性相邻象素之间的连贯性，避免了对象，避免了对象素的逐点判断和反复求交的运算，达到了素的逐点判断和反复求交的运算，达到了减少了计算量和提高速度的目的。减少了

13、计算量和提高速度的目的。n 开发和利用相邻象素之间的连贯性是光栅开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描线算法综图形算法研究的重要内容。扫描线算法综合利用了区域的连贯性、扫描线连贯性和合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性。边的连贯性等三种形式的连贯性。扫描线算法扫描线算法(2/26)(2/26) 设多边形设多边形P P的顶点的顶点P Pi i=(x=(xi i,y,yi i),i=0,1, ,n),i=0,1, ,n，又设，又设y yi0i0,y,yi1i1,y,yinin是各顶点是各顶点P Pi i的坐标的坐标y yi i的递减数列，即的递

14、减数列，即y yikikyyik+1ik+1,0kn-1,0kn-1这样，当这样，当y yikikyyik+1ik+1,0kn-1,0kn-1时，屏幕上位于时，屏幕上位于y=yy=yikik和和y=yy=yik+1ik+1两条扫描线之间的长方形区域被多边形两条扫描线之间的长方形区域被多边形P P的边分割的边分割成若干梯形（三角形可看作其中一底边长为零的梯形），成若干梯形（三角形可看作其中一底边长为零的梯形），它们具有下列性质：它们具有下列性质：区域的连贯性区域的连贯性y=yiky=yik+1扫描线算法扫描线算法(3/26)(3/26)区域的连贯性区域的连贯性n1）梯形的两底边分别在）梯形的两底

15、边分别在y=yik和和y=yik+1两条扫描线上，两条扫描线上，腰在多边形腰在多边形P的边上或在显示屏幕的边界上。的边上或在显示屏幕的边界上。n2）这些梯形可分为两类：一类位于多边形）这些梯形可分为两类：一类位于多边形P的内部；的内部；另一类在多边形另一类在多边形P的外部。的外部。n3）两类梯形在长方形区域）两类梯形在长方形区域yik,yik+1内相间的排列，即内相间的排列，即相邻的两梯形必有一个在多边形相邻的两梯形必有一个在多边形P内，另一个在内，另一个在P外。外。y=yik+1y=yik扫描线算法扫描线算法(4/26)(4/26)n求出扫描线与多边形的所有交点后，位于多边形求出扫描线与多边

16、形的所有交点后，位于多边形内的直线段就不难找到了。内的直线段就不难找到了。 n设想我们从扫描线的一端出发，这时我们在多边设想我们从扫描线的一端出发，这时我们在多边形外，因为多边形总是在有限范围内的。形外，因为多边形总是在有限范围内的。 当我们当我们沿直线前进到达第一个交点时，就开始进入多边沿直线前进到达第一个交点时，就开始进入多边形内。形内。 由于直线的另一端是在多边形外，继续沿由于直线的另一端是在多边形外，继续沿直线前进一定会走出多边形内部，因此一定会遇直线前进一定会走出多边形内部，因此一定会遇到第二个交点。到第二个交点。 这时我们可以看到，第一和第二这时我们可以看到，第一和第二个交点给出的

17、直线段就位于多边形内。个交点给出的直线段就位于多边形内。 n如果没有更多的交点，则该扫描线上只有一段直如果没有更多的交点，则该扫描线上只有一段直线段位于多边形内。线段位于多边形内。 n如果继续沿扫描线前进，遇到第三个交点后，重如果继续沿扫描线前进，遇到第三个交点后，重新进入多边形内。类似前面的分析，一定有第四新进入多边形内。类似前面的分析，一定有第四个交点。于是第三、第四个交点给出的直线段就个交点。于是第三、第四个交点给出的直线段就位于多边形内。位于多边形内。 扫描线的连贯性扫描线的连贯性扫描线算法扫描线算法(5/26)(5/26) 设设d d为一整数，并且为一整数，并且d=e-1,d=e-1

18、,并且并且 y yi0i0dydyinin。设位。设位于扫描线于扫描线y=dy=d上的交点序列为上的交点序列为x xdj1dj1,x,xdj2dj2,x,xdj3dj3,x,xdjkdjk 现在来讨论扫描线现在来讨论扫描线d d，e e交点序列之间的关系。若多交点序列之间的关系。若多边形边形P P的边的边P Pr-1r-1P Pr r与扫描线与扫描线y=e,y=dy=e,y=d都相交，则交点序列都相交，则交点序列中对应元素中对应元素x xerer,x,xdrdr满足下列关系：满足下列关系：x xerer= x= xdrdr + 1/m + 1/mr r (1) (1)其中其中m mr r为边为

19、边P Pr-1r-1P Pr r的斜率。的斜率。 边的连贯性y=ey=d扫描线算法扫描线算法(6/26)(6/26)边的连贯性边的连贯性n于是，可利用于是，可利用d的交点序列计算的交点序列计算e的交点序列，的交点序列，即先运用递推关系式即先运用递推关系式(1)求得与扫描线求得与扫描线y=e和和y=d都相交的所有多边形上的交点都相交的所有多边形上的交点xer,再求得再求得与扫描线与扫描线y=d不相交但与扫描线不相交但与扫描线y=e相交的所相交的所有边有边PqPq+1上的交点上的交点xeq。如果。如果P的顶点的坐标的顶点的坐标是整数，那么是整数，那么xeq=xq或或xeq=xq+1,然后把这两部然

20、后把这两部分按递增的顺序排列，即可得分按递增的顺序排列，即可得e的交点序列。的交点序列。y=ey=d扫描线算法扫描线算法(7/26)(7/26)边的连贯性边的连贯性n特别是当存在某一个整数特别是当存在某一个整数k,0kn-1,使得使得nyike, dyik+1n成立时，则由区域的连贯性可知成立时，则由区域的连贯性可知d的交点序列的交点序列和和e的交点序列之间有以下关系：的交点序列之间有以下关系：n 1）两序列元素的个数相等，如上图所示。）两序列元素的个数相等，如上图所示。n2）点）点(xeir,e)与与(xdjr,d)位于多边形位于多边形P的同一边上，的同一边上，于是于是 xeir= xdjr

21、 + 1/kjr (2)n这样，运用递推关系式这样，运用递推关系式(2)可直接由可直接由d的交点序的交点序列和列和e的获得的获得e的交点序列。的交点序列。n以上性质称为边的连贯性，它是区域的连贯性以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。在相邻两扫描线上的反映。扫描线算法扫描线算法(8/26)(8/26)当扫描线与多边形当扫描线与多边形P P的交点是的交点是P P的顶点时，则称的顶点时，则称该交点为奇点。该交点为奇点。以上所述多边形的三种形式的连贯性都基于这以上所述多边形的三种形式的连贯性都基于这样的几何事实：每一条扫描线与多边形样的几何事实：每一条扫描线与多边形P P的

22、边界的边界的交点个数都是偶数。但是如果把每一奇点简的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点，单地计为一个交点或者简单地计为两个交点，都可能出现奇数个交点。那么如果保证交点数都可能出现奇数个交点。那么如果保证交点数为偶数呢？为偶数呢？奇点的处理奇点的处理扫描线算法扫描线算法(9/26)(9/26)奇点的处理奇点的处理n若奇点做二个交点处理，则情况若奇点做二个交点处理，则情况A，交点，交点个数是偶数。个数是偶数。n若奇点做一个交点处理，则情况若奇点做一个交点处理，则情况B，交点，交点个数是偶数。个数是偶数。扫描线算法扫描线算法(10/26)(10/26)奇点的

23、处理奇点的处理n多边形多边形P的顶点可分为两类：极值奇的顶点可分为两类：极值奇点和非极值奇点。如果点和非极值奇点。如果(yi-1 - yi)(yi+1 - yi)0，则称顶点，则称顶点Pi为极值点；否则为极值点；否则称称Pi为非极值点。为非极值点。(yi-1 和和yi+1为相邻为相邻顶点坐标顶点坐标)n规定：奇点是极值点时，该点按两规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。个交点计算，否则按一个交点计算。扫描线算法扫描线算法(11/26)(11/26)n扫描线填充算法填充要注意的是一些与边界相扫描线填充算法填充要注意的是一些与边界相邻的点，因为根据屏幕像素点的特性，会发现邻

24、的点，因为根据屏幕像素点的特性，会发现有些点在多边形的边上，有的相交，有些点在多边形的边上，有的相交，在直线中在直线中的取整规则不适合于扫描线算法的取整规则不适合于扫描线算法，这是因为：，这是因为：单纯的取整规则会使生成的像素部分位于多边单纯的取整规则会使生成的像素部分位于多边形之外，而扫描线算法则是对多边形内部的像形之外，而扫描线算法则是对多边形内部的像素进行填充。素进行填充。见下页图所示。见下页图所示。n规则规则1 1 取整问题取整问题n规则规则2 2 边界问题边界问题n规则规则3 3 交点取舍交点取舍几条规则几条规则扫描线算法扫描线算法(12/26)(12/26)扫描线算法扫描线算法(1

25、2/26)(12/26)n规则：nX为小数，即交点落于扫描线上两个相为小数，即交点落于扫描线上两个相邻像素之间邻像素之间n(a)交点位于左边之上，向右取整交点位于左边之上，向右取整n(b)交点位于右边之上，向左取整交点位于右边之上，向左取整扫描线算法扫描线算法(13/26)(13/26)n基本思想：基本思想：n按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。颜色显示这些区间的象素，即完成填充工作。对于一条扫描线填充过程可以分为四个步骤：对于一条扫描线填充过程可以分为四个步骤：扫描线算法的基本思想

26、扫描线算法的基本思想多边形与若干扫多边形与若干扫描线图示描线图示0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)n扫描线基础算法的核心是计算扫描线扫描线基础算法的核心是计算扫描线与多边形的交点，然后配对，着色。与多边形的交点，然后配对，着色。其实求解交点这一步工作量是非常大其实求解交点这一步工作量是非常大的，所以根据前面介绍的多边形边的的，所以根据前面介绍的多边形边的连贯性，区域的连贯性规则，我们可连贯性，区域的连贯性规则，我们可以构造更简单的扫描线算法以构造更简单的扫描线算法(有的书称有的书称为

27、有序边表算法为有序边表算法)。下面是其的数据结。下面是其的数据结构实现，改进后的扫描线算法就是简构实现，改进后的扫描线算法就是简化了不断求解交点这么一个复杂的工化了不断求解交点这么一个复杂的工作。作。扫描线算法扫描线算法(14/26)(14/26)数据结构与实现步骤数据结构与实现步骤n算法基本思想：首先取算法基本思想：首先取d=yin。容易求得。容易求得扫描线扫描线y=d上的交点序列为上的交点序列为xdj1,xdj2,xdjn ，这一序列由位于扫描线，这一序列由位于扫描线y=d上的多边形上的多边形P的顶点组成。的顶点组成。n 由由yin的交点序列开始，根据多边形的的交点序列开始，根据多边形的边

28、的连贯性，按从上到下的顺序求得各边的连贯性，按从上到下的顺序求得各条扫描线的交点序列；根据扫描线的连条扫描线的交点序列；根据扫描线的连贯性，可确定各条扫描线上位于多边形贯性，可确定各条扫描线上位于多边形P内的区段，并表示成点阵形式。内的区段，并表示成点阵形式。扫描线算法扫描线算法(15/26)(15/26)数据结构与实现步骤n所有的边和扫描线求交，效率很低。因为一条所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。扫描线往往只和少数几条边相交。n如何判断多边形的一条边与扫描线是否相交？如何判断多边形的一条边与扫描线是否相交？n与当前扫描线相交的边称为活性边（与当前扫描线相交

29、的边称为活性边（active edge)，把它们按与扫描线交点，把它们按与扫描线交点x坐标递增的顺坐标递增的顺序存入一个链表中，边的活化链表序存入一个链表中，边的活化链表 （ AEL, Active edge table)。它记录了多边形边沿扫。它记录了多边形边沿扫描线的交点序列。描线的交点序列。n只需对当前扫描线的活动边表作更新，即可得只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。到下一条扫描线的活动边表。扫描线算法扫描线算法(16/26)(16/26) 关注扫描线与其相交的那些边。算法执行时关注扫描线与其相交的那些边。算法执行时要求建立一张有效边表要求建立一张有效边表(

30、AET)，AET中的内容随中的内容随每一条扫描线每一条扫描线y值的不同而变化，也即在值的不同而变化，也即在AET中，中，只保留与当前扫描线相交的所有的边。而且这些只保留与当前扫描线相交的所有的边。而且这些边按其与该扫描线交点的边按其与该扫描线交点的x坐标大小的顺序存放，坐标大小的顺序存放，以便于在一对交点之间填充。当从一条扫描线移以便于在一对交点之间填充。当从一条扫描线移到下一条扫描线时，我们利用两条扫描线间隔为到下一条扫描线时，我们利用两条扫描线间隔为1的特性，的特性， 可以简化边与扫描线交点的计算。可以简化边与扫描线交点的计算。扫描线算法扫描线算法(17/26)(17/26)n如何计算下一

31、条扫描线与边的交点。如何计算下一条扫描线与边的交点。直线方程：直线方程：ax+by+c = 0ax+by+c = 0当前交点坐标：当前交点坐标：( (x xi i, , y yi i) )下一交点坐标：下一交点坐标：( (x xi+1i+1,y,yi+1i+1) )x xi+1i+1= = (-by(-byi+1i+1)-c)/a = (-by)-c)/a = (-byi i-b)-c)/a =x-b)-c)/a =xi i-b/a-b/a活动边表中需要存放的信息：活动边表中需要存放的信息：x x：当前扫描线与边的交点：当前扫描线与边的交点dxdx-b/a-b/a：从当前扫描线到下一条扫描线之

32、间的：从当前扫描线到下一条扫描线之间的x x增量增量ymaxymax：边所交的最高扫描线：边所交的最高扫描线扫描线算法扫描线算法(18/26)(18/26)n增加哪一条边呢？增加哪一条边呢？n为了方便边的活化链表的更新，建立另为了方便边的活化链表的更新，建立另一个表一个表-边表，存放在该扫描线第一次出边表，存放在该扫描线第一次出现的边。现的边。n存放的信息：存放的信息：nx：扫描线与该边的初始交点：扫描线与该边的初始交点ndx：x的增量的增量nymax：该边的最大：该边的最大y值值扫描线算法扫描线算法(19/26)(19/26)n 即算法中采用较灵活的数据结构。它由即算法中采用较灵活的数据结构

33、。它由边的分类表边的分类表EL（Edge List）和边的活化链）和边的活化链表表AEL（Active Edge List）两部分组成。两部分组成。n 表结构表结构EL和和AEL中的基本元素为多边形中的基本元素为多边形的边。边的结构由以下四个域组成：的边。边的结构由以下四个域组成：n ymax 边的上端点的边的上端点的y坐标；坐标；n x 在在EL中表示边的下端点的中表示边的下端点的x坐标，坐标，在在AEL中则表示边与扫描线的交点的坐标；中则表示边与扫描线的交点的坐标；n x 边的斜率的倒数；边的斜率的倒数；n next 指向下一条边的指针。指向下一条边的指针。扫描线算法扫描线算法(20/26

34、)(20/26)n 边的分类表边的分类表EL是按边的下端点的是按边的下端点的y坐标对坐标对非水平边进行分类的指针数组。下端点的非水平边进行分类的指针数组。下端点的y坐标的值等于坐标的值等于i的边归入第的边归入第i类。有多少条扫类。有多少条扫描线，就设多少类。同一类中，各边按描线，就设多少类。同一类中，各边按x值值（x值相等时，按值相等时，按x的值）递增的顺序排列的值）递增的顺序排列成行。成行。扫描线算法扫描线算法(21/26)(21/26)n已知多边形已知多边形P=(P1P2P3P4P5P6P1)；其各边坐；其各边坐标分别为标分别为n（2，2）（）（5，1）（）（11，3）（）（11，8）（）

35、（5，5）（2，7）n建立其边表和边的活性边表建立其边表和边的活性边表0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)扫描线算法扫描线算法(22/26)(22/26) 7 6P4P5 P5P6 5 4 3 2 1 0P1P2 P2P3 8 5 -3 2 5 3 3 2 0 7 11 0 8 5 2 8 5 -1.5 7P6P1P3P4各扫描线的新边表各扫描线的新边表扫描线算法扫描线算法(23/26)(23/26)活动边表的例子(a) 扫描线y=1的活性边表；(b) 扫描线y=2的活性边表5 -3

36、25 3 3p1p2p2p32 -3 28 3 3p1p2p2p3扫描线算法扫描线算法(23/26)(23/26)活动边表的例子(c) 扫描线y=3的活性边表；(d) 扫描线y=4的活性边表2 0 711 3 3p6p1p2p32 0 711 0 8p6p1p3p4扫描线算法扫描线算法(23/26)(23/26)活动边表的例子(e) 扫描线y=6的活性边表；(f) 扫描线y=7的活性边表 2 0 7 3.5 -1.5 7P6P1P5P6AB 7 2 8 11 0 8P4P5P3P4CDx ymaxx ymaxx ymaxx ymax扫描线算法扫描线算法(24/26)(24/26)算法实现步骤n

37、这样，当建立了边的分类表这样，当建立了边的分类表EL后，扫描后，扫描线算法可按下列步骤进行：线算法可按下列步骤进行：n （1）取扫描线纵坐标）取扫描线纵坐标y的初始值为的初始值为EL中非空元素的最小序号。中非空元素的最小序号。n （2）将边的活化链表）将边的活化链表AEL设置为空。设置为空。n （3）按从下到上的顺序对纵坐标值为）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，的扫描线（当前扫描线）执行下列步骤，直到边的分类表直到边的分类表ET和边的活化链表都变和边的活化链表都变成空为止。成空为止。扫描线算法扫描线算法(25/26)(25/26)n1）如边分类表）如边分类表E

38、L中的第中的第y类元素非空，则将属于该类类元素非空，则将属于该类的所有边从的所有边从EL中取出并插入边的活化链表中，中取出并插入边的活化链表中，AEL中中的各边按照的各边按照x值（当值（当x值相等时，按值相等时，按x值）递增方向排值）递增方向排序。序。n2）若相对于当前扫描线，边的活化链表）若相对于当前扫描线，边的活化链表AEL非空，则非空，则将将AEL中的边两两依次配对，即中的边两两依次配对，即1，2边为一对，边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点所构成的区段位于多边形内，依次

39、对这些区段上的点（象素）按多边形属性着色。（象素）按多边形属性着色。n3）将边的活化链表）将边的活化链表AEL中满足中满足y=ymax的边删去。的边删去。n4）将边的活化链表）将边的活化链表AEL剩下的每一条边的剩下的每一条边的x域累加域累加x，即即x:=x+x。n5）将当前的扫描线的纵坐标值）将当前的扫描线的纵坐标值y累加累加1，即，即y=y+1。算法实现步骤扫描线算法扫描线算法(26/26)(26/26)特点：算法效率比逐点填充法高很多。特点：算法效率比逐点填充法高很多。缺点：对各种表的维持和排序开销太大，缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。适合软件实现而不适

40、合硬件实现。存在问题：存在问题：如何处理多边形的水平边？如何处理多边形的水平边？如何修改扫描线算法，使它能处理边自交如何修改扫描线算法，使它能处理边自交的多边形？的多边形？扫描线算法总结扫描线算法总结 基本思想：光栅图形中，如果某区基本思想：光栅图形中，如果某区域已着上值为域已着上值为M M的颜色值做的颜色值做偶偶数次数次求余运算，该区域颜色不变；而做求余运算，该区域颜色不变；而做奇奇数次求余运算，则该区域颜色变数次求余运算，则该区域颜色变为值为新的颜色。这一规律应用于为值为新的颜色。这一规律应用于多边形扫描转换，就为边填充算法。多边形扫描转换，就为边填充算法。边填充算法边填充算法P5P1P2

41、P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)边填充算法实例边填充算法实例边填充算法小结边填充算法小结n适合用于具有帧缓存的图形系统。按任适合用于具有帧缓存的图形系统。按任意顺序处理多边形的边后，再按扫描线意顺序处理多边形的边后，再按扫描线顺序读出帧缓存的内容，送入显示设备。顺序读出帧缓存的内容，送入显示设备。n优点：算法简单，易于实现；优点：算法简单，易于实现；n缺点：对于复杂图形，每一象素可能被缺点：对于复杂图形，每一象素可能被访问多次，输入访问多次，输入/输出的量比扫描线算法输出的量比扫描线算法大得多。大得多。n改进

42、：引入栅栏，见栅栏填充算法改进：引入栅栏，见栅栏填充算法n引入栅栏，以减少填充算法访问象素的引入栅栏，以减少填充算法访问象素的次数。次数。n栅栏：与扫描线垂直的直线，通常过一栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。顶点，且把多边形分为左右二半。栅栏填充算法栅栏填充算法 基本思想基本思想：扫描线与多边形：扫描线与多边形的边求交，将交点与栅栏之的边求交，将交点与栅栏之间的象素取补。间的象素取补。P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)P4栅栏线 优缺点：减少了象素重复访优缺点：减少了象

43、素重复访问数目，但不彻底问数目，但不彻底。引入边标志：以克服象素被重复访问的缺点。引入边标志：以克服象素被重复访问的缺点。边界标志算法边界标志算法算法思想：算法思想：1. 1. 轮廓线轮廓线：对多边形的每一条边进行扫描：对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个转换，即对多边形边界所经过的象素作一个边界边界标志标志。2.2.填充填充：对每条与多边形相交的扫描线，按：对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象从左到右的顺序，逐个访问该扫描线上的象素。素。边界标志算法边界标志算法n实现细节：实现细节：n 取一个布尔变量取一个布尔变量inside来指示

44、当前点的来指示当前点的状态，状态，Inside 的初始值为假，每当当前访的初始值为假，每当当前访问象素为被打上标志的点，就把问象素为被打上标志的点，就把inside取取反。对未打标志的点，反。对未打标志的点，inside不变。不变。n若若inside为真，则点在多边形内，着色。为真，则点在多边形内，着色。n若若inside为假，则点在多边形外，着背景为假，则点在多边形外，着背景色色 边界标志算法边界标志算法:算法描述算法描述nvoid edgemark_fill(polydef, color)n多边形定义多边形定义 polydef； int color;n 对多边形对多边形polydef 每条

45、边进行直线扫描转换；每条边进行直线扫描转换；n inside = FALSE;n for (每条与多边形每条与多边形polydef相交的扫描线相交的扫描线y )n for (扫描线上每个象素扫描线上每个象素x )n if(象素象素 x 被打上边标志被打上边标志)n inside = ! (inside);n if(inside！= FALSE)n drawpixel (x, y, color);n else drawpixel (x, y, background);n n边界标志算法小结边界标志算法小结n处理每一条扫描线时，象素点只被访问处理每一条扫描线时，象素点只被访问一次；一次；n用软件实

46、现时，边界标志算法与扫描线用软件实现时，边界标志算法与扫描线算法的执行速度几乎相同；算法的执行速度几乎相同； 课后思考题课后思考题：如何处理边界的交点个数：如何处理边界的交点个数使其成为偶数？使其成为偶数？ 用硬件实现时，它的执行速度比扫描线算用硬件实现时，它的执行速度比扫描线算法快一至两个数量级，这是由于边界标志法快一至两个数量级，这是由于边界标志算法不必建立维护边表以及对它进行排序，算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现；所以边界标志算法更适合硬件实现；n上一节我们讲述了多边形的扫描转换，在上一节我们讲述了多边形的扫描转换，在实际应用中，我们可能会遇到任意的区

47、域，实际应用中，我们可能会遇到任意的区域，如下图所示。如下图所示。4.3区域填充区域填充(种子填充算法种子填充算法) 扫描线填色扫描线填色(Scan-Line Filling)(Scan-Line Filling)算法。算法。这类算法建立在多边形边界的矢量形式数这类算法建立在多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互据之上，可用于程序填色，也可用于交互填色。填色。 种子填色种子填色(Seed Filling)(Seed Filling)算法算法。这类算法。这类算法建立在任意封闭边界的图像形式数据之上，建立在任意封闭边界的图像形式数据之上，并还需提供填色，而难以用于程序填色。并还

48、需提供填色，而难以用于程序填色。区域内一点的坐标。所以，它一般只能用区域内一点的坐标。所以，它一般只能用于人机交互于人机交互n种子填充算法思想种子填充算法思想 前面介绍的扫描线，边填充算法等都前面介绍的扫描线，边填充算法等都是直接考虑多边形的边，最后进行着色，是直接考虑多边形的边，最后进行着色，因为多边形的边是直线，是规则的，所以因为多边形的边是直线，是规则的，所以计算起来也比较容易，但是对于任何不规计算起来也比较容易，但是对于任何不规则区域，考虑到边的不规则性，使用扫描则区域，考虑到边的不规则性，使用扫描线类填充算法更麻烦。线类填充算法更麻烦。 种子填充算法思想是只考虑边界的颜种子填充算法思

49、想是只考虑边界的颜色结构，从被填充区域内部任意一点出发，色结构，从被填充区域内部任意一点出发，通过判断周边像素是不是边界而进行填充，通过判断周边像素是不是边界而进行填充，直到填充完毕。直到填充完毕。n区域填充的概念n4连通：从区域内任意一点出发，可通过上、连通：从区域内任意一点出发，可通过上、下、左、右四个方向到达区域内的任意象下、左、右四个方向到达区域内的任意象素；素； n8连通：从区域内任意一点出发，可通过上、连通：从区域内任意一点出发，可通过上、下、左、右、左上、左下、右上、右下八下、左、右、左上、左下、右上、右下八个方向到达区域内的任意象素；个方向到达区域内的任意象素； n区域连通方式

50、：区域连通方式：4-connected8-connected区域连通方式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界连通区域边界4方向方向填充算法的填充结果填充算法的填充结果4连通区域边界连通区域边界8方向方向填充算法的填充结果填充算法的填充结果简单的种子填充算法简单的种子填充算法（4连通边界）连通边界）n种子像素入栈种子像素入栈n当栈非空时，重复以下步骤：当栈非空时，重复以下步骤：栈顶像素出栈栈顶像素出栈将出栈象素置成填充色将出栈象素置成填充色 按按右、上、左、下右、上、左、下顺序检查与出栈象素相邻的顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成四象素，若其中

51、某象素不在边界上且未被置成填充色，则将其入栈填充色，则将其入栈 ，若其中某个像素值与填若其中某个像素值与填充色相同，说明该像素已填充过或者该像素就充色相同，说明该像素已填充过或者该像素就是边界上的像素是边界上的像素(当填充色与边界色相同时当填充色与边界色相同时)，这时像素不入栈。这时像素不入栈。6754S9328S247938479484795684796847978479847994794796754S9328S799缺点？假设如上多边形，取种子点(3,3),按上，下，左，右这样的方向搜索，最后像素被选中并填充的次序如图中箭头所示 ，不同的方向搜索，得到不同的结果。简单种子填充算法递归描述v

52、oid FloodFill4(int x,int y,int oldColor,int void FloodFill4(int x,int y,int oldColor,int newColor)newColor) if(GetPixel(x,y) = oldColor) if(GetPixel(x,y) = oldColor) pDC-setpixel(x,y,newColor); pDC-setpixel(x,y,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x,y+1,oldColor,newColor); Floo

53、dFill4(x,y-1,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); /* *end of FloodFill4()end of FloodFill4()* */ / 简单递归算法简单递归算法存在的问题 boundary_color

54、未被填充种子点 fill_color (a) 填充前 (b) 填充后 当区域内部某些像素的颜色为当区域内部某些像素的颜色为fill_colorfill_color时，上述边时，上述边界填充算法可能无法正确工作。界填充算法可能无法正确工作。 解决方法解决方法: :首先建立一个与帧缓冲区对应的临时缓冲首先建立一个与帧缓冲区对应的临时缓冲区，帧缓冲区中颜色为区，帧缓冲区中颜色为boundary_colorboundary_color的像素在临时缓冲的像素在临时缓冲区中用区中用0 0来表示，颜色不为来表示，颜色不为boundary_colorboundary_color的像素在临时的像素在临时缓冲区中

55、用缓冲区中用1 1来表示，再用上述算法在临时缓冲区中用来表示，再用上述算法在临时缓冲区中用2 2进进行填充，最后在帧缓冲区中将对应于临时缓冲区中为行填充，最后在帧缓冲区中将对应于临时缓冲区中为2 2的的像素填充为像素填充为fill_colorfill_color。n该算法也可以填充有孔区域。该算法也可以填充有孔区域。 n优缺点：优缺点：n(1)递归执行，算法简单；递归执行，算法简单；n(2)有些象素会入栈多次，栈结构占空间较大，有些象素会入栈多次，栈结构占空间较大，效率不高；效率不高；n(3)区域内每一象素都引起一次递归，进区域内每一象素都引起一次递归，进/出栈，出栈，费时费内存费时费内存;n

56、改进算法方向，减少递归次数，提高效率。改进算法方向，减少递归次数，提高效率。简单种子填充算法小结简单种子填充算法小结简单种子填充算法简单种子填充算法VC源码源码n建立程序的基础是在前面画直线，画圆，建立程序的基础是在前面画直线，画圆，画椭圆，画抛物线的基础之上。建立在第画椭圆，画抛物线的基础之上。建立在第二章第三章的基础之上。比如我们使用边二章第三章的基础之上。比如我们使用边界的颜色，便是我们绘制图形的颜色。界的颜色，便是我们绘制图形的颜色。n程序实现达到鼠标捕捉种子点，然后填充，程序实现达到鼠标捕捉种子点，然后填充，实现填充任意直线和曲线围成的区域。实现填充任意直线和曲线围成的区域。n首先用

57、类向导在首先用类向导在VIEW类中建立一个鼠标按类中建立一个鼠标按下事件下事件ON_WM_LBUTTONDOWN，这是，这是MFC中的一个消息处理事件。加入代码：中的一个消息处理事件。加入代码：简单种子填充算法简单种子填充算法VC源码源码nvoid CDddView:OnLButtonDown(UINT nFlags, CPoint point) nnfillpoint=point;nCView:OnLButtonDown(nFlags, point);nn/黄色所表示的为加入的代码，注意在类的声明中(该类h头文件)加入变量声明 (我们使用了MFC中定义的CPoint类)：npublic:nC

58、Point fillpoint;简单种子填充算法简单种子填充算法VC源码源码n除了建立一个鼠标捕捉的功能外，我们还要加一个形参形式的真正的递归算法，在类头文件中加入：nafx_msg void OnFillapp(int x,int y,COLORREF fillcolor); n这样的函数声明，可以在 protect:下面，也可以在public:下面。n在类执行文件cpp下面，加入如下函数代码：简单种子填充算法简单种子填充算法VC源码源码nvoid CDddView:OnFillapp(int x,int y,COLORREF fillcolor) nn COLORREF current;

59、n current=pDC-GetPixel(x,y);n if (current=color&current=fillcolor) n return;n if (current!=color&current!=fillcolor) n n pDC-SetPixel(x,y,fillcolor); n CDddView:OnFillapp(x,y+1,fillcolor);n CDddView:OnFillapp(x-1,y,fillcolor); n CDddView:OnFillapp(x+1,y,fillcolor); n CDddView:OnFillapp(x,y-1

60、,fillcolor);n n /注意我这注意我这view类为类为CdddView类，所以函数名为类，所以函数名为CDddView:OnFillapp简单种子填充算法简单种子填充算法VC源码源码n做了前面二步准备工作后，我们使用类向导建立做了前面二步准备工作后，我们使用类向导建立一个菜单映射一个菜单映射(种子填充种子填充)，在，在view类添加一个成类添加一个成员函数，添加如下代码。员函数，添加如下代码。nvoid CDddView:OnFill() nnpDC=GetDC();n /pDC已经声明为该类成员变量已经声明为该类成员变量nint x=fillpoint.x;nint y=fillpoint.y;nCDddView: