计算机图形学第3章二维基本图(4)

1、3.3.2扫描线种子填充算法扫描线种子填充算法 该算法属于种子填充算法，它是以扫描线上的区段为单位进行操作。所谓区段，就是一条扫描线上相连着的若干内部象素的集合。一、扫描线种子填充算法思想扫描线种子填充算法的基本思想是：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。二、扫描线种子填充算法实现借助于堆栈，上述算法实现步骤如下：1、初始化堆栈。2、种子压入堆栈。3、while（堆栈非空） (1)从堆栈弹出种子象素。(2)如果种子象素尚未填充，则：

2、a.求出种子区段：xleft、xright;b.填充整个区段。c.检查相邻的上扫描线的xleftxxright区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。d.检查相邻的下扫描线的xleftxxright区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。扫描线种子填充算法步骤扫描线种子填充算法步骤(1)种子种子象素象素入栈入栈。(2)栈非空栈非空时象素时象素出栈出栈，否则结束。，否则结束。(3)对出栈象素及对出栈

3、象素及左、右两边象素填充左、右两边象素填充，直到遇，直到遇边界边界XL、XR。(4)在在(XL ，XR) 内查相临的内查相临的上、下两条扫描线是否为边界或已填充上、下两条扫描线是否为边界或已填充,如不是，则将每区间的最右边的象素如不是，则将每区间的最右边的象素入栈入栈。回到回到(2)。练习：用扫描线种子填充算法，写出图中顺序进栈的种子坐标及所需最大栈空间 顺序进栈的种子坐标为： （1，2）、（2，3）、（2，1）、（4，4）、（2，4） 所需最大栈空间为：2 作业：用扫描线种子填充算法写出图中所示的顺序进栈的种子坐标和需要最大的栈空间？图中：初始种子坐标：（5，1），红点表示边界，蓝点表示种子

4、。三、扫描线种子填充算法特点1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。3、种子出栈时，则填充整个区段。4、这样有机的结合：一边对尚未填充象素的登记（象素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。 在光栅显示平面上，多边形是封闭的，它是用某一边界色围成的一个闭合区域，填充是逐行进行的，即用扫描线逐行对多边形求交，在交点对之间填充。边标志填充算法就是在逐行处理时，利用边界色作为标志来进行填充的。例如某扫描线从左到右

5、扫描时碰到边界色，立刻改变标志的状态，接下来再根据标志的状态决定某象素点是否填充。3.3.3边标志边标志填充算法填充算法 一、边标志填充算法思想扫描线具有连贯性，这种连贯性只有在扫描线与多边形相交处才会发生变化，而每次的变化结果：无非是在前景色和背景色之间相互“切换”。边标志填充算法正是基于这一发现，先在屏幕上生成多边形轮廓线，然后逐条扫描处理。处理中：逐点读取象素值，若为边界色，则对该象素值进行颜色切换。二、边标志填充算法实现 1、用边界色画出多边形轮廓线，也就是将多边形边界所经过的象素打上边标志。 2、为了缩小范围，加快填充速度，须找出多边形的最小包围盒：xmin、ymin、xmax、ym

6、ax。如下图所示。边标志填充算法3、逐条扫描线进行处理，对每条扫描线依从左往右的顺序，逐个访问该扫描线上的象素。每遇到边界象素，标志取反。然后，按照标志是否为真，决定象素是否为填充色。三、边标志填充算法特点 该算法思想简单，实现容易。既不需要求交点、交点排序、边的登记，也不需要使用链表、堆栈等数据结构。四、边标志填充算法程序EdgeMarkFill(int p2,int n,int boundarycolor,int newcolor)int i,x,y,flag,xmin,xmax,ymin,ymax;setcolor(boundarycolor); /*设置画笔色*/ for(i=0 ;i

7、n;i+)line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*画出多边形的n条边*/用求极值的算法，从多边形顶点数组p中，求出xmin,xmax,ymin,ymax;for(y=ymin;y=ymax;y+) flag=-1;for(x=xmin;x=xmax;x+) if(getpixel(x,y)=boundarycolor)flag=-flag;if(flag=1)putpixel(x,y, newcolor); 五、边标志填充算法错误处理1、该算法虽然简单，但程序运行后会出现局部错误。从下图可以发现，对于多边形顶点为局部极值点时，扫描线与多边形的相交次数不再是偶

8、数，而是奇数，填充时会出现“抽丝”现象。即某扫描线上不该填充的区段填上色，而应该填充的区段却没有填上色。解决的办法：判断多边形顶点的性质，如果是局部极值点，那么扫描线碰上它则不改变标志。2、特别当心多边形边界的扫描转换。在这里就不能考虑：不同的斜率产生的直线要亮度均匀，如下图(a)所示。否则当扫描线y遇到斜率小于1的边界线时，碰到几个边界点，会引起标志的无序改变，将导致填充的错误。在边标志填充算法中要注意多边形边界的扫描转换解决的办法：对于不同斜率的边界，都要使用斜率大于1的直线扫描转换方法：每次y方向增长一步，x方向增长1/m步距，以保证扫描线y遇到斜率小于1的边界时，只能遇到一个点。请看图

9、(b)。3.3.4 图案填充图案填充 前面介绍的区域填充算法，都是把区域内部的象素全部置成同一种颜色。但在实际应用中，有时需要用图案来填充平面区域。这可以将前面的填充算法中写象素的那部分代码稍加修改来实现: 在确定了区域内点后，不是马上对该象素填色，而是先将该象素映射到图案位图的对应位置。根据图案该位置的象素值，决定填充颜色。一、图案填充方式： 1、透明方式:若是以透明方式填充图案，则当图案位图的对应位置为1时，用前景色写象素，否则，不改变该象素的值。 2、不透明方式: 而若是以不透明方式填充图案，则当图案位图的对应位置为1时，用前景色写象素，否则，用背景色写象素。二、图案定位法： 1、相对定

10、位法、相对定位法:把图案原点与填充区域边界或内部的某点对齐。这样，当被填充的多边形移动时，图案也跟着移动，看起来比较自然。对于多边形，可取边界上最左边的顶点，而对于圆和椭圆这样具有光滑边界的区域，则最好取区域内部某一点，如取中心与图案原点对齐。2、绝对定位法：、绝对定位法：把图案原点与屏幕原点对齐。该方法可以将整个屏幕看成被要填充的图案布满，只是要填充的区域是透明的，可以让图案显露出来，其它区域对此图案却是不透明的，图案被全部挡住。这种方法比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果。但它有一个潜在的毛病，即当区域移动时，图案不会跟着移动。其效果是区域内的图案变。 三、图案

11、填充算法实现下面讨论在第二种绝对定位法下用不透明方式对平面区域填充图案：假设填充图案是一个MN的位图，用MN的数组存放。M、N一般比需要填充区域的尺寸小得多（88、1616、3232），所以图案总是设计成周期性的，使之能通过重复使用来构成任意尺寸的图案。当确定了区域内点p（x,y）后，则图案位图上的对应位置为p（x%M，y%N），其中%为C语言整除取余运算符,然后取出图案位图该位置的象素进行填充。四、图案填充算法程序/ / 采用不透明方式绝对定位法填充图案的程序伪代码采用不透明方式绝对定位法填充图案的程序伪代码: :maskpixel(int x,int y,int newcolor,int

12、backgroundcolor) maskpixel(int x,int y,int newcolor,int backgroundcolor) int xx,yy;int xx,yy;int maskcode88= 0,0,0,0,1,0,0,0,int maskcode88= 0,0,0,0,1,0,0,0,/ /* *砖缝图案砖缝图案* */ / 0,0,0,0,1,0,0,0, 0,0,0,0,1,0,0,0, 0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,1,0,0,

13、0,0,0,0,0, 1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,11,1,1,1,1,1,1,1;xx=x%8; xx=x%8; / /* *多边形区域内点坐标多边形区域内点坐标x x映射到图案坐标映射到图案坐标xxxx* */ /yy=y%8; yy=y%8; / /* *多边形区域内点坐标多边形区域内点坐标y y到图案坐标到图案坐标yyyy* */ /if(maskcodeyyxx)if(maskcodeyyxx)putpixel(x,y, newcolor); /putp

14、ixel(x,y, newcolor); /* * newcolor newcolor 为前景色为前景色* */ /elseelseputpixel(x,y, backgroundcolor); /putpixel(x,y, backgroundcolor); /* * backgroundcolor backgroundcolor为背景色为背景色* */ / 3.4字符的表示与输出字符的表示与输出 我们讨论的字符是指字母、数字、汉字、标点等符号。计算机中，字符由一个数字编码唯一标识，对于一个字符来说，它所对应的编码是由它所属的字符集决定。1、ASCII码目前，国际上普遍采用的字符编码是ASC

15、II码（American Standard Code for Information Interchange）美国信息交换标准代码。它是用七位二进制数进行编码，共能表示128个字符，其中编码031表示控制字符（不可显示），编码32127表示英文字母、数字、标点符号等可显示字符。一个字符的ASCII码用一个字节（8位）表示，其最高位不用或者作为奇偶校验位。2、国标码我国除了采用ASCII码外，还制定了汉字编码的国家标准字符集:中华人民共和国国家标准信息交换编码，代号为“GB231280”。该字符集共收录常用汉字6763个，图形符号682个。它规定所有汉字和图形符号组成一个9494的矩阵，在此方阵

16、中，每一行称为“区”，用区码来标识；每一列称为“位”，用位码来标识，一个符号由一个区码和一个位码共同标识。区码和位码分别需要7个二进制位，同样，为了方便，各采用一个字节表示。所以在计算机中，汉字（符号）国标码占用两个字节。3、两种编码的区别那么，给定一个字节，如何来确定它代表的是ASCII码，还是国标码的区码和位码呢？通常采用字符中冗余的最高位来标识：最高位为0时，表示ASCII码；最高位为1时，表示汉字编码的区码（高位字节）或位码（低位字节）。4、机内码机内码： 计算机内表示字符的编码 1、西文字符西文字符的机内码就是ASCII码。2、中文字符国标码为：2020H+区位码的十六进制表示机内码

17、为：8080H+国标码 即：A0A0H+区位码的十六进制表示3、举例“啊”字的区位码为1601，转换为十六进制表示应为1001H（区码16转为10H，位码01转为01H）。于是，“啊”字的机内码为：A0A0H+1001H=B0A1H4、附加说明除了机内码外，还有一个概念，即汉字输入码。汉字输入码是为了方便人工输入汉字而设计的人机界面编码。用户将汉字输入码输入到计算机中，然后通过汉字系统将其转为机内码。 为了在显示器等输出设备上输出字符，必须要有每个字符的图形信息，这些信息保存在系统的字库中。字符的图形表示方法有两种：点阵表示和矢量表示。3.4.1点阵字符点阵字符 就目前来说，用得最多的是点阵字

18、符。在字符的点阵表示中，每个字符由一个位图（字符掩模）来表示，对于西文字符的掩模矩阵一般不小于57，而定义汉字的掩模矩阵一般不小于1616。一个字符的点阵数越多，字符越清晰、美观。一、点阵字符的存储点阵字符是由位图表示，保存字符就是保存位图。即点阵字符的存储就是按行或按列进行编码。如下图(a)，每行右边的二进制或十六制的代码就是对该行的编码。 二、点阵字符的显示从给定的字符编码到在屏幕上将它显示出来要经历两个步骤：1从字库中将它的位置找到。2将该位置上的位图读到二维数组中进行显示，见图(b)。矢量字符由于其占空间少、美观、变换方便等优点得到越来越广泛的应用，特别在排版软件、工程绘图软件中，它几乎完全取代了传统的点阵字符。在字符的矢量表示方法中，保存的是字符的笔画信息而不是整个位图。一、字符坐标系 字符处于局部坐标系中，见图(a)。对一个字符来说，它由构成它的笔画组成，而每一笔画又由其两端点坐标和端点间是否连线的标志确定。例如，汉字“士”有三画，六个端点，可以按图(b)的结构保存该汉字。3.4.2矢量字符矢量字符 二、矢量字符的变换点阵字符的表示是位图，点阵字符的变换是图像变换，当将点阵字符旋转或者放大时，会发现显示结果粗糙而难看；而用来表示矢量字符的是端点坐标，对矢量字符的变换就是对这些端点进行变换，是图形的几何变换，它可以对矢量字符进行任意变换而不影响显示结果。此外，点阵字