计算机图形学 CG04-3填充-4-5 .ppt

1、4.3 区域区域填充填充多边形有两种重要的表示方法：多边形有两种重要的表示方法：顶点表示和点阵表示顶点表示和点阵表示 把多边形的顶点表示转换为点把多边形的顶点表示转换为点阵表示。这种转换称为多边形阵表示。这种转换称为多边形的扫描转换。的扫描转换。4.3 区域填充在这一节中将讨论图形系统中新的图元多边形研究有关多边形的概念以及如何表示多边形学习逐点判断算法、扫描线算法、边填充算法，种子填充算法等多边形填充的方法，及区域填充图案算法。1.多边形 所谓多边形就是用一系列首尾相连的线段构成的图形，这些组成多边形边界的线段称为多边形的多边形的边边，多边形的边的端点称为多边形的顶点多边形的顶点，一般来说一

2、个多边形应是封闭封闭的。多边形又可以分成两大类：凸多边形和凹多边形。所谓凸多边形是指这样一类多边形：如果在多所谓凸多边形是指这样一类多边形：如果在多边形内任选两个点，将这两个点用线段连接后，此边形内任选两个点，将这两个点用线段连接后，此线段上所有的点都在多边形内，这就是凸多边形。线段上所有的点都在多边形内，这就是凸多边形。而凹多边形就是非凸多边形。而凹多边形就是非凸多边形。凸凹多边形2.点是否在多边形内部的检验 为了对多边形内部的象素点赋值，首先要解决如何判断一个点是否在多边形内部。判断的方法是，先在多边形外部找一个点，然后用线段连接此点和有疑问的点，计算出此线段与多边形边界相交的次数，如果交

3、点的数目为奇奇数数，则疑问点在多边形内部；如果为偶数偶数，此点在多边形外部。图示PP2324图示P11332问题 在计算交点时，如果交点恰恰就是多边形的顶点，必须小心处理。此时要观察在此顶点相遇的两条边,如果这两条边的其余二个顶点在新构成线段的:同一侧同一侧，应认为此线段与多边形相交二次二次；异侧异侧，则认为此线段与多边形相交一次一次。解决PP23242解决P11332 13.连贯性原理1）边的连贯性的连贯性 当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交。2）扫描线的连贯性扫描线的连贯性 当前线与各边的交点顺序与下 一条扫描线与各边的交点很可能相同或非常类似。3）区间的连贯性区间的

4、连贯性Yk+1yk4.填充算法 1）扫描线算法扫描线算法 充分利用了扫描线连贯性原理，避免了针对于象素点的逐点判别，有效地选择象素点来进行多边形的填充。4.填充算法-扫描线算法扫描线算法 扫描线算法扫描线算法的基本思想基本思想：对给定的多边形，用一组水平(垂直)的扫描线进行扫描扫描线进行扫描，对每一条扫描线均可求求出与多边形边的交点；交点；这些交点将扫描线分割成落在多边形内部内部和落在多边形外部外部的线段，二者相间排列；将落在多边形内部的扫描线段上的所有象素点赋以给定的色彩值。可见，算法中不需要检验每一个象素点，而只考可见，算法中不需要检验每一个象素点，而只考虑与多边形边相交的交点分割后的扫描

5、线段。虑与多边形边相交的交点分割后的扫描线段。多边形与若干扫描线A03421123456781011x5678y9P3(11,3)P4(11,8)P2(5,1)P1(2,2)P5(5,5)P6(2,7)BCDGFE返回算法求解算法求解对于一条扫描线的处理，可以分为四个步骤：（1）求交点求交点：首先求出扫描线与多边形各边的交点（2）交点排序交点排序：将这些交点按X坐标递增顺序排序（3）交点匹配交点匹配：即从左到右确定落在多边形内部的那些线段；（4）区间填充区间填充：填充落在多边形内部的线段。两个特殊问题两个特殊问题：一是当扫描线与多边形顶点相交时，交点的取舍问题；二是多边形边界上像素的取舍问题。

6、问题一的解决n扫描线交于一个顶点，而共享顶点的二条边分别落在扫描线的两边。这时交点只算一个；当共享交点的二条边在扫描线的同一边，这时交点作为0个或者2个(取决于该点是多边形的局部最高点还是局部的最低点)。n具体实现时，只需检查顶点两条边的另外两个端点的y值。按这两个y值中大于顶/交点y值的个数是0、1或2来决定是取零个、一个、还是二个。问题二的解决问题二的解决n规定落在右/上边界的像素不予以填充，而落在左/下边界的像素予以填充。问题一的解决用于保证的交点正确配对，而问题二的解决用于避免填充扩大化。y321x412340算法求解02468102468XYP1P2P3P4P5P6求扫描线与多边形边

7、交点的方法最简单的方法是将多边形的所有边放在一个表中，在处理每条扫描线时，从表中顺序取出所有的边，分别求这些边与扫描线的交点。这样做的结果将做一些无益的求交点无益的求交点动作，因为扫描线并不一定与多边形的边相交，扫描线只与部分甚至较少的边相交，因此在进行扫描在进行扫描线与多边形边求交点时，应只求那些与扫描线线与多边形边求交点时，应只求那些与扫描线相交的边的交点相交的边的交点。活性边表活性边表（AEL-Active Edge List）把与当前扫描线相交的边称活化边活化边并把它们按与扫描线交点X坐标递增的顺序存放在一个链表中，称此链表为活性边表活性边表。活性边表每个节点存放对应边的有关信息。活性

8、边表（AEL-Active Edge List）根据边和扫描线的连贯性更新AEL：假定当前扫描线与多边形某一条边的交点的X坐标为x，则下一条扫描线与该边的交点只要加一个增量x。设该边的直线方程为：ax+by+c=0，当前若yyi，x=xi；则当y=yi+1时，xi+1=xi-b/a=xi+x (其中x=-b/a 为常数)活性边表（AEL-Active Edge List）使用增量法计算时，我们需要知道一条边何时何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去：边的最大Y值(最高扫描线号)扫描线号活性边表活性边表建立AEL，每个结点结构至少如下：x:当前扫描线与边交点的x坐标；x:从

9、当前扫描线到下一条扫描线之间的x增量；ymax:边的最大Y值(最高扫描线号)。若规定多边形的边不自交，则从当前扫描线延续若规定多边形的边不自交，则从当前扫描线延续到下一扫描线的边与下一扫描线的交点顺序保持到下一扫描线的边与下一扫描线的交点顺序保持不变，否则重新排序不变，否则重新排序(交点采用冒泡排序法，活交点采用冒泡排序法，活性边表采用插入排序性边表采用插入排序)。扫描线的活性边表示例扫描线的活性边表示例20 7P6P13.5-1.57P5P67281108A x ymaxB x ymaxC x ymaxD x ymax928P4P61108P3P4F x ymaxG x ymax扫描线扫描线

10、6的活性边表的活性边表扫描线扫描线7的活性边表的活性边表P3P4P4P5图扫描线的新边表扫描线的新边表8 7 6 54 3210 5 2 8P4P55-1.5 7 P5P65-3 2P1P25 33 P2P32 0 7 P3P411 0 8 存放某扫描线第一次出现的边图具体求解步骤：具体求解步骤：处理扫描线步骤为：(1)对于扫描线Y=yc，是否有新边加入AEL，若对应的AEL中非空，并对AEL中各边按X递增排序；(2)若相对于当前扫描线的活化边表AEL非空，则将 AEL中的边两两依次配对，即第1，2边为一对，第3，4 边为一对，依次类推，每一对边与当前扫描线的交点 所构成的区段位于多边形内，依

11、次将这些区段上的点 进行着色；(3)将边的活化链表AEL中满足Y=ymax的边删去；(4)将边的活化链表AEL中剩下的每一条边的X域累加 X，即X=X+X；(5)将当前的扫描线的纵坐标Y累加1，即Y=Y+1，重复执行(1)。void polyfill(polygon,color)int color;多边形 polygon;for(各条扫描线i)初始化新边表头指针NET i；把y min=i 的边放进边表NET i;y=最低扫描线号；初始化活性边表AEL为空；for(各条扫描线i)把新边表NETi中的边结点用插入排序法插入AEL表，使之按x坐标递增顺序排列；遍历AEL表，把y max=i 的结点

12、从AEL表中删除，并把y max i结点的x值递增D x；若允许多边形的边自相交，则用冒泡排序法对AEL表重新排序；遍历AEL表，把配对交点区间(左闭右开)上的象素(x,y)，用Putpixel(x,y,color)改写象素颜色值；/*polyfill*/示例扫描线Y=1时，建立的活化边表：(5,-3,2)-(5,3,11)得到交点为（5，1），（5，1）扫描线Y=Y+1=2时，有边退出，有新边加入，修改后的活化边表为：(5-3,-3,2)-(2,0,7)-(5+3,3,11)(2,-3,2)-(2,0,7)-(8,3,11)(2,0,7)-(8,3,11)得到交点为（2，2），（2，2），（

13、2，8）示例扫描线Y=3时，没有新边加入，修改后的AEL为：(2,0,7)-(8+3,3,11)-(11,0,8)(2,0,7)-(11，3,11)-(11,0,8)(2,0,7)-(11,0,8)得到交点为（2，3），（11，3），（11，3）依次类推，直到边表EL和活化边表均为空为止。2）边填充算法）边填充算法基本思想是：针对每一条扫描线和每条多边形边的交点(x，y)，将该扫描线上交交点右方的所有象素取补点右方的所有象素取补。2）边填充算法）边填充算法 P5P4P3P2P1P2P3P3P4P4P5P5P1边填边填充算充算法示法示意图意图2）边填充算法特点）边填充算法特点 简单简单 但是对于

14、复杂图形，可能多次多次访问某些象素访问某些象素，要大量的输入输出。这是它的缺点。2）边填充算法）边填充算法引入栅栏，可以减少边填充算法访问象素的次数栅栏栅栏指的是一条与扫描线垂直的直线，通常把栅栏取成过多边形顶点、且把多边形分为左右两半的直线。思想：把每个扫描线与多边形边的交点与栅栏之间的象素取补。若交点位于栅栏左边，则将交点之右，栅栏之左的所有象素取补；若交点位于栅栏右边，则将栅栏之右，交点之左的象素取补。2）边填充算法）边填充算法栅栏填充算法不能完全避免象素会被重复访问，只能减少被重复访问的象素的数目。P5P4P3P2P1栅栏线P2P3P3P4P4P5P5P1栅栏填充算法示意图栅栏填充算法

15、示意图边填充算法边填充算法-边界标志算法边界标志算法 改进的方式是边界标志算法边界标志算法:对边打上标志;填充765432101234567890 1 2 3 4 5 6 7 8 9边标志算法示意图边标志算法示意图3）边界标志填充算法填充算法 vs 扫描线算法扫描线算法用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同；但由于边界标志算法不必建立维护边表不必建立维护边表以及对它进行排序排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。3）种子填充算法）种子填充算法前面讨论的填充算法都是按扫描线的顺序进行象素点的填充的，种子填充算法是根据已知的一个多边形

16、区域内部的一个象素点一个象素点来找到区域内其它的象素点进行填充的。02468102468XY3）种子填充算法）种子填充算法 区域可分为四连通区域四连通区域和八连通区域八连通区域两种:四连通区域四连通区域，区域内每一个象素可以通过四个方向(上、下、左、右)组合到达;八连通区域八连通区域，区域内的每个象素可通过上、下、左、右以及四个对角线方向的移动组合到达。四连通区域四连通区域 八连通区域八连通区域3）种子填充算法）种子填充算法四连通区域四连通区域八连通区域八连通区域算法基本思想简单的种子填充算法如下：(1)将种子象素压入栈中；(2)当栈非空时,重复执行以下三步操作：a)从栈中弹出一个象素；b)将

17、该象素置成所要求的色彩值；c)检查每个与当前象素邻接的四连接象素是否是边界色或已置成所要求的色彩值，否则将该象素入栈。示例示例:如图，种子为(5,5)02468102468XY(5,5)(5,4)(6,5)(5,6)(4,5)(Y,X)栈底示例示例:如图，种子为(5,5)(Y,X)栈底02468102468XY(5,4)(6,5)(5,6)(4,4)(3,5)示例出栈的情况02468102468XY(y,x)(5,5)(4,5)(3,5)(2,5)(2,6)(3,4)(4,4)(5,4)(6,4)(6,5)(6,6)(5,6)(5,7)(3,3)(4,4)(5,6)(6,5)(5,4)结论结论

18、 分析该算法不难发现，在进行填充过程中堆栈会变得很大，而且在堆栈中还常常包含有一些重复的和不必要的信息：一方面算法的效率效率降低降低，另一方面还要有很大的存储空间很大的存储空间来实现栈结构。为此提出了扫描线种子填充算法。所谓扫描线种子填充算法扫描线种子填充算法，是在任意不间断扫描线区间中只取一个种子象素。不间断区间即指在一条扫描线上一组相邻的元素。扫描线种子填充算法种子象素入栈；当栈非空时做以下几步：1)栈顶象素出栈；(算法结束条件为栈空)2)沿着扫描线对出栈象素的左、右象素进行填充，直到遇到边界象素为止，即对包含该象素的整个区间进行填充；3)区间内最左、最右元素为Xleft Xright;则

19、在XleftXXright中检查与当前扫描线相邻的上、下两条扫描线是否全为边界象素或已填充过的象素。若不是，则把每一区间的最右象素作为种子压入栈中。示例02468102468XY圆域的填充圆域的填充 n圆域的填充的原理是上面所讨论的多边圆域的填充的原理是上面所讨论的多边形区域的填充原理的推广。形区域的填充原理的推广。n它的做法是：先对每条扫描线，计算它它的做法是：先对每条扫描线，计算它与圆域的相交区间，再把区间内圆域的与圆域的相交区间，再把区间内圆域的象素用指定颜色填充象素用指定颜色填充 区域填充图案区域填充图案 n填充平面区域的是一种图案:确定了区域内一象素之后，先查询图案位图的对应位置，而

20、不是象普通区域填充算法那样，马上往该象素填色。n区域填充图案有两种方式：透明方式和不透明方式。区域填充图案区域填充图案 n如果用透明方式填充图案，当图案表的对应位置为1时，用前景色写象素，否则，不改变该象素的值。n如果用不透明方式填充图案，则视图案位图对应位置为1或0来决定是用前景色还是背景色去写象素。区域填充图案区域填充图案 在不考虑图案旋转的情况下，图案填充时，必须确定区域与图案之间的位置关系。做法是对齐对齐，即通过把图案原点与图形区某点对齐的办法来实现(对齐方法有两种):第一种第一种，是把图案原点与填充区域边界或内部的某点对齐。第二种第二种，是把图案原点与填充区域外部的某点对齐。P188

21、 4.4 线宽与线型的处理线宽与线型的处理任何影响图元显示方法的参数称为属性参数。线段的基本属性有线型、宽度和颜色。线型：线型：实线、虚线、点线等。通过设置沿直线路径显示的实线线段的长度和间通过设置沿直线路径显示的实线线段的长度和间距来修改画线算法，产生各种类型的直线。距来修改画线算法，产生各种类型的直线。14:584.4.1直线宽处理在显示器上实现：产生具有一定宽度的直线，可以沿着生成直线时获得的象素点，通过移动一把具有一定宽度的“刷子”来实现。O OA A4.4.1 直线宽的处理直线宽的处理线线“刷子刷子”算法算法斜率斜率m在在-1，1之间，用垂直刷子，之间，用垂直刷子，否则用水平刷子否则

22、用水平刷子 算法简单、效率高算法简单、效率高4.4.1 直线宽的处理直线宽的处理线刷子线刷子缺点：缺点：始末端总是水平或垂直的；直线交点有始末端总是水平或垂直的；直线交点有缺口；斜线细；线宽为偶数个象素时缺口；斜线细；线宽为偶数个象素时4.4.1 直线宽的处理直线宽的处理方形刷子算法方形刷子算法特点特点:斜率为斜率为1时，线宽最大，为垂直或水平的时，线宽最大，为垂直或水平的 倍倍24.4.1 直线宽的处理直线宽的处理区域填充算法区域填充算法特点：生成图形质量高，但计算量大；且有些特点：生成图形质量高，但计算量大；且有些图形的等距线不容易图形的等距线不容易4.4.2 圆弧线宽的处理圆弧线宽的处理

23、线刷子算法线刷子算法K=1时，线刷子在水平与垂直方向之时，线刷子在水平与垂直方向之间切换间切换在接近水平或垂直地方，线条更粗一些，在接近水平或垂直地方，线条更粗一些，面在面在K=1时，线条更细一些。时，线条更细一些。(见课见课本图本图4.4.5)方形刷子方形刷子区域填充算法区域填充算法4.4.3 线型的处理线型的处理以32个像素为周期重复，在程序实现时将无条件写像素putpixel(x,y,color)改为：if(位串i%32)putpixel(x,y,color);缺点：线型中的笔划长度与直线长度有关，斜线上的笔划长度比横向或竖向上的笔划更长。用一个32位整数表示一个位串，当对应为1时，显示

24、像素，否则不显示4.5 字符字符矢量字符矢量字符*133,11,DIODE 040,044,04C,042,04C,040,048,04C,046,04C,0矢量方向编码4.5 字符字符矢量字符矢量字符*65,11,UCA 024,043,04D,02C,2,047,1,040,2,02E,0其中其中“2”和和“1”高四位为零，分别表示抬笔和落笔高四位为零，分别表示抬笔和落笔矢量方向编码矢量方向编码4.5 字符字符点阵字符点阵字符演示演示西文字符:5*7的点阵描述汉文字符:16*16的点阵描述4.5 字符字符字型技术字型技术：TrueType字型字型方正，轮廓矢量法方正，轮廓矢量法4.5 字符

25、字符字符的输出字符的输出(字符属性控制字符属性控制)*字体字体 宋体宋体 仿宋体仿宋体 楷体楷体 黑体黑体 隶书隶书*字高字高 宋体宋体 宋体宋体 宋体宋体 宋体宋体*字宽因子字宽因子(扩展扩展/压缩压缩)大海大海 大海大海 大海大海*字倾斜角字倾斜角 倾斜倾斜 倾斜倾斜*对齐对齐(左对齐、中心对齐、右对齐左对齐、中心对齐、右对齐)*字色字色*写方式：替换方式时，对应字符掩模写方式：替换方式时，对应字符掩模中空白区被置成背景色。与方式时，这中空白区被置成背景色。与方式时，这部分区域颜色不受影响部分区域颜色不受影响思考题思考题1.举出计算机图形学的应用实例2.简述计算机图形学的研究对象、研究内容

26、及图形在计算机中的表示方法3.简述图形显示设备的发展历程4.比较随机扫描显示系统与光栅扫描显示系统的不同5.简述帧缓存与显示器分辨率的关系，分辨率分别为640*480、1280*1024、2560*2048的显示器各需要多少字节位平面数为24（真彩色）的帧缓存。6.画直线的算法有哪几种？画圆弧的算法有那几种？写一个画带线宽的虚线的程序。直线、圆直线、圆(弧弧)生成算法生成算法一、实验教学目标与基本要求一、实验教学目标与基本要求1.1.了解光栅图形显示器的工作原理和特点；了解光栅图形显示器的工作原理和特点；2.通过实习通过实习C C语言的基本绘图方法；语言的基本绘图方法；3.3.实践直线和圆实践

27、直线和圆(弧弧)的基本生成算法；的基本生成算法；4.4.掌握课本所介绍的图形算法的原理和实现掌握课本所介绍的图形算法的原理和实现。二、实验课程内容二、实验课程内容(4学时，记成绩学时，记成绩5分分)基于光栅图形显示器，在基于光栅图形显示器，在C环境中使用基本图形生成环境中使用基本图形生成算法生成粗细不同的任意直线和圆（弧）。算法生成粗细不同的任意直线和圆（弧）。了解光栅图形显示器的特点；练习TC/VC环境下图形程序的绘图方法；实习中点法和Bresenham法生成直线和圆(弧)；实习改进方法，并实现线宽和线型的控制；(选做)MS-Windows下窗口、菜单交互界面实现。区域填充与裁剪算法区域填充与裁剪算法一、实验教学目标与基本要求一、实验教学目标与基本要求1.掌握区域填充的基本算法原理；2.熟悉裁剪算法的基本原理；3.会使用字符的图形输出。二、实验课程内容二、实验课程内容 (4(4学时，记成绩学时，记成绩5 5分分)1.多边形的扫描线、边标志及扫描线种子填充算法(至少实现两种算法)；2.裁剪算法(至少实现一种算法)；3.(选做)在屏幕上输出矢量或点阵字符。