《计算机图形学课件 第9讲 区域填充和字符处理》由会员分享，可在线阅读，更多相关《计算机图形学课件 第9讲 区域填充和字符处理（42页珍藏版）》请在金锄头文库上搜索。
1、第9讲 区域填充和字符处理Date1信息科学与工程学院 5.4.1 多边形的扫描转换多边形的两种表示方法：顶点表示：用多边形的顶点序列来刻划多边形。直观、几 何意义强、占内存少；不能直接用于面着色。点阵表示是用位于多边形内的像素的集合来刻划多边形。 失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形， 易于面着色。1. 什么是多边形的扫描转换P5P0 P1P2P3P4上节回顾Date2信息科学与工程学院 2. x-扫描线算法基本思想:按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工作。上节回顾从多边形顶点表示到点阵表示的转换，称为扫描转换多边形或多边
2、形的填充，Date3信息科学与工程学院 算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。对一条扫描线填充的过程可分为四个步骤：a. 求交：计算扫描线与多边形各边的交点；b. 排序：把所有交点按x值递增顺序排序；c. 配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;d. 填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。上节回顾Date4信息科学与工程学院 存在问题和解决方法：当扫描线与多边形顶点相交时，交点的取舍问题。上节回
3、顾Date5信息科学与工程学院 3. 改进的有效边表算法（Y连贯性算法）改进原理： 处理一条扫描线时，仅对有效边求交 利用扫描线的连贯性 利用多边形边的连贯性上节回顾Date6信息科学与工程学院 有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点：x ymax 1/k nextx为当前扫描线与边的交点ymax为边所在的最大扫描线值 1/k为从当前扫描线到下一条扫描线间x的增量 上节回顾Date7信息科学与工程学院
4、1.4122/5P2P1y=8712-1P0P1795P0P611.591/2P5P6上节回顾Date8信息科学与工程学院 边表（Edge Table）方便有效边的建立和更新边表的构造：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，其对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。上节回顾Date9信息科学与工程学院 (3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大
5、y值ymax。x|ymin ymax 1/k next(4)同一桶中若干条边按x|ymin由小到大排序，若x|ymin 相等，则按照1/k由小到大排序。上节回顾Date10信息科学与工程学院 上节回顾Date11信息科学与工程学院 上节回顾Date12信息科学与工程学院 算法步骤： (1)初始化：构造边表，AET表置空； (2)将第一个不空的ET表中的边与AET表合并；(3)由AET表中取出交点对进行填充。填充时设一布尔变量b(初值为假)，令指针从AET中 第一个结点到最后一个结点遍历一次，每访问一个结点 ，把b取反一次，若b为真，则把从当前结点的x值到下 一结点的x值结束的区间用多边形色填充
6、。填充之后删 除y=ymax的边。（期间，x=round(x) ） (4)yi+1=yi+1,根据xi+1=xi+1/k计算并修改AET表，同时合并 ET表中y=yi+1桶中的边，按次序插入到AET表中，形成 新的AET表；(5)AET表不为空则转(3)，否则结束。上节回顾Date13信息科学与工程学院 5.4.2 边缘填充算法 边缘填充算法基本思想 按任意顺序处理多边形的每条边。在处理每条边时，首先 求出该边与扫描线的交点，然后将每一条扫描线上交点 右方的所有像素取补。上节回顾Date14信息科学与工程学院 5.4.3 区域填充区域填充是指从区域内的一个点（种子）开始，由内向外将填充色扩展到
7、整个区域内的过程。区域是指已经表示成点阵形式的填充图形，它是像素集合。通常有内点表示和边界表示两种形式。Date15信息科学与工程学院 边界表示法边界表示法：把位于给定区域的边界上像素一一列举出 来的方法。在边界表示法中，区域边界上的像素着同一颜色，而区 域内的像素点不能着这种颜色。由于边界以特殊颜色指定，填充算法可逐个像素地向外处理，直到遇到边界颜色为止。以此为基础的区域填 充算法称为边界填充算法(Boundary-fill Algorithm)。Date16信息科学与工程学院 内点表示法内点表示：枚举出给定区域内所有像素的表示方法 。在内点表示法中，区域内的所有像素点着同一颜色 ，而区域边
8、界上的像素着不同的颜色。以内点表示法为基础的区域填充算法称为泛填充算 法(Flood-fill Algorithm)。Date17信息科学与工程学院 区域通常分为4-连通区域和8-连通区域两类。一个点p的4-邻接点是指上、下、左、右四个相邻的点。一个点p的8-邻接点是指上、下、左、右、左上、右上、左下、右下八个相邻的点。Date18信息科学与工程学院 4-连通区域是指从区域上一点出发，通过访问已知点的4-邻接点，在不越出区域的前提下，遍历区域内的所有像素。8-连通区域是指从区域上一点出发，通过访问已知点的8-邻接点，在不越出区域的前提下，遍历区域内的所有像素。Date19信息科学与工程学院 1
9、. 边界填充算法算法的输入：种子点坐标(x,y)，填充色和边界颜色。栈结构实现4-连通边界填充算法的算法步骤为：种子像素入栈；当栈非空时重复执行如下三步操作：(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的4-邻接点，若其中某个像素点不是边界色且未置成多边形色，则把该像素入栈。Date20信息科学与工程学院 栈结构实现8-连通边界填充算法的算法步骤为：种子像素入栈；当栈非空时重复执行如下三步操作：(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的8-邻接点，若其中某个像素点不是边界色且未置成多边形色，则把该像素入栈。Date21信息科学与工程学院 特点：
10、可以用于填充带有内孔的平面区域。 把太多的像素压入堆栈改进通过沿扫描线填充水平像素段，来代替处理4-邻接点和8-邻接点。Date22信息科学与工程学院 沿扫描线填充水平像素段的4-连通边界填充算法步骤：种子像素入栈；当栈非空时作如下三步操作：(1)栈顶像素出栈；(2)填充出栈像素所在扫描行的连续像素段，直到遇到边界像素为止，即每出栈一个像素，就对包含该像 素的整个扫描线区间进行填充；(3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素，若 存在非边界、未填充边界的像素，则把每一区间的 最左像素取作种子像素入栈。Date23信息科学与工程学院 2. 泛填充算
11、法算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。算法原理：算法从指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的像素点。Date24信息科学与工程学院 8-连通泛填充算法步骤如下：种子像素入栈；当栈非空时重复执行如下三步操作：(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的8-邻接点，若其中某个像素点不是给定内部点的颜色且未置成新的填充色，则把该像素入栈。Date25信息科学与工程学院 注意：当以边界表示时，4-连通边界填充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。当以内点表示时，8-连通泛填充算法可以填充8-连
12、通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域。Date26信息科学与工程学院 5.4.4 其他相关的概念1. 内-外测试不自交的多边形 、自相交的多边形奇-偶规则（Odd-even Rule）从任意位置p作一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。Date27信息科学与工程学院 非零环绕数规则（Nonzero Winding Number Rule） 首先使多边形的边变为矢量。 将环绕数初始化为零。 再从任意位置p作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多 边形的边从右到左穿过射线时，环绕
13、数加1，从左到右时，环绕数减1。 处理完多边形的所有相关边之后，若环绕数为非零 ，则p为内部点，否则，p是外部点。Date28信息科学与工程学院 2. 曲线边界区域的填充相交计算Date29信息科学与工程学院 5.5 字符处理字符：指数字、字母、汉字等符号，用于图形的标注、说明等。计算机中，字符由一个数字编码唯一标识，对于一个字符来说，它所对应的编码是由它所属的字符集决定。常用的字符集：qASCII码q国标码Date30信息科学与工程学院 ASCII码：“美国信息交换用标准代码集”(American Standard Code for Information Interchange)，简称AS
14、CII码。它是用七位二进制数进行编码，共能表示128个字符，其中编码031表示控制字符（不可显示），编码32127表示英文字母、数字、标点符号等可显示字符。一个字符的ASCII码用一个字节（8位）表示，其最高位不用或者作为奇偶校验位。Date31信息科学与工程学院 国标码：“中华人民共和国国家标准信息交换编码，简称为国标码，代号GB231280。该字符集共收录常用汉字6763个，图形符号682个。它规定所有汉字和图形符号组成一个9494的矩阵，在此方阵中，每一行称为“区”，用区码来标识；每一列称为“位”，用位码来标识，一个符号由一个区码和一个位码共同标识。区码和位码分别需要7个二进制位，同样，
15、为了方便，各采用一个字节表示。所以在计算机中，汉字（符号）国标码占用两个字节。 Date32信息科学与工程学院 两种编码的区别那么，给定一个字节，如何来确定它代表的是ASCII码，还是国标码的区码和位码呢？通常采用字符中冗余的最高位来标识：最高位为0时，表示ASCII码；最高位为1时，表示汉字编码的区码（高位字节）或位码（低位字节）。Date33信息科学与工程学院 为了在显示器等输出设备上输出字符，除了字符 编码外，还必须要有每个字符的图形信息，这 些信息保存在系统的字库中。字符的图形表示方法有两种：点阵表示矢量表示字符的图形表示方法Date34信息科学与工程学院 5.5.1 点阵字符在字符的
16、点阵表示中，每个字符由一个点阵位图 来表示，对于西文字符的点阵位图一般不小于57， 而定义汉字的点阵位图一般不小于1616。一个字符的点阵数越多，字符越清晰、美观。点阵位图经过一些简单转换即可形成一个字符的像素图案。如：点阵字符的显示要经历两个步骤：1从字库中将它的位图检索出来。2将检索到的位图写到帧缓存中。点阵字符的特点：1定义和显示直接、简单。2需要耗费大量存储空间。如：保存1616型号的点阵汉字需256位，即32Byte常用汉字有6763个，则676332 211KB在实际应用中，需要多种字体，每种字体有十多种型号解决方案：1、从一组点阵字符生成不同尺寸和不同字体的其它字符。2、采用压缩技术，压缩存储字库，使用是还原后读入内存。5.5.2 矢量字符矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记
