第5章基本图形生成算法第四讲

1、多边形的扫描转换l算法实施区域填充字符和矢量图形的显示反走样基础l扫描线算法原理回顾l求交l排序l交点配对l区间填色lX扫描线算法缺点 实际上一条扫描线只和少数边相交，甚至没有和任意边相交，造成大量冗余计算。l计算交点时提取所有边与扫描线求交l有序边表算法活性边表算法l改进原理：l处理一条扫描线时，仅对与它相交的边求交；l利用扫描线的连贯性l利用多边形边的连贯性如一条扫描线排序后与多边形边的交点x坐标依次是x0, x1, x2,x2n+1，则对特殊点处理后，(x2i, x2i+1)(i=0,n)组成的区间为多边形内的区间。我们把与当前扫描线相交的多边形边称为活性边(Active Edge，AE

2、)l多边形边的连贯性：l某条边和当前扫描线相交时，它很可能也与下一条扫描线相交，并且交点坐标遵循下面的规律。(xi, yi)(xi+dx, yi+1)11/kl即对一条边y=kx+b来说，如果当前扫描线得到的交点为(xi, yi), 则下一条扫描线交点为(xi+1/k, yi+1)直线方程y=kx+bdy/dx=k, 即dx=dy/k微分形式：微分形式：此时dy=1, 则dx=1/k找到一条边上前后扫描线交点的关系，如何加以利用？l增量算法思想：l扫描线改变时，同一条边上的后一个交点，可以利用上一次求交点的结果，直接加上一个增量来得到。x的增量dx =1/k, y的增量dy=1 l使用一个数据

3、结构来表示与当前扫描线相交的边，扫描线改变时，只要相交边活性边不变，则不需要对该数据结构中的内容修改。l有初始值，有算法结束的限制条件。对于任意一条相交边其交点的初始值为Y值小的端点；终止于Y值较大的端点。l数据结构：l活性边表（Active Edge Table， AET） 把活性边按照与扫描线交点x坐标递增的顺序存放在一个链表中，该链表称为活性边表。l活性边表的结构和存储内容：l一个活性边表对应多个节点，一个节点对应一条边，多个节点之间按照x从小到大规则，进行排序。x0 ymax0next1/k0 x1 ymax1null1/k1具有两条边的活性链表l活性边表的操作根据边的连贯性，当前扫描

4、线发生改变时：l如果没有新的活性边加入，也没有边到达终点，此时新扫描线和边相交的交点序列不发生改变。l处理下一条扫描线时，如有新边加入，则新边需要作为新节点插入适当位置适合插入排序。l当某个相交边到达终点，则需要将该边从活性边表中删除。l边表（Edge Table， ET）/新边表 对于每个扫描线，建立一个最小y坐标位于该扫描线上的活性边的链表，来表示从下到上扫描到该扫描线时，新增加的活性边。全体扫描线就对应了一个（新）边表。 从下到上扫描过程中，只有下一条扫描线具有一个对应的活性边的链表时，才需要对当前的活性边表进行插入新边的操作。l边表的构造(1)首先构造一个纵向线性表，表的长度为多边形所

5、占有的最大扫描线数，表的每个结点，称为一个桶，对应多边形覆盖的每一条扫描线。(2)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x ymax 1/k NEXT(4)同一桶中若干条边按X由小到大排序，若X相等，则按照1/k由小到大排序。(3)将每条边的对应结点链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边的结点就放在相应的扫描线桶中。xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a) 多边形P0P1P2P3P4P5P6P0p2p0

6、p6边表构造示例12111098765432137-1/3353/485-1/2891/27 12-17951 122/5边表构造示例xy213 4 5 6 7 8 9111234567891011121012(a) 多边形P0P1P2P3P4P5P6P0ly=8时，活性边1.4122/5712-179511.5 91/2l算法实现(1) 初始化：构造边表ET，如果边表为空则返回；活性边表AET置空；(2) 初始化：将ET表中第一个非空桶中边插入AET；(3) 处理当前扫描线：由AET表中取出交点对进行填充。(4) 令yi+1=yi+1,删除ymax=y的边；(5) 根据xi+1=xi+1/k

7、计算并（通过排序）修改AET表，同时将ET表中y=yi+1桶中的边，按次序插入到AET表中，形成下一条扫描线的新AET表；(6)AET表不为空则转(3)，否则结束。算法演示l活性边表法优点和缺点优点：l采用链表实现，节约存储空间l充分利用了边连贯性和扫描线连贯性，减少了求交计算量，提高了排序的效率，从而大大减少了程序算法的复杂度。l对显示的每个像素只访问一次，输入输出量少缺点：l对链表的维持和排序开销较大。l不适合硬件实现。l边缘填充算法l基本思想：l对于每一条扫描线和每条多边形边的交点(xi, yi), 将该扫描线上交点右方的所有像素取补。对多边形的每条边都依次处理一次，顺序随意。所有边完成

8、以后，像素结果即为该多边形的填充区域。算法演示l算法优点和缺点优点：l该算法最适用于具有帧缓冲器的图形系统，按任意顺序处理多边形的边，在处理每条边时，仅访问与该边相交的扫描线上交点右方的像素。当所有边处理完成后，直接按照扫描线顺序读出帧缓冲器的内容，送入显示设备。简单，易于硬件实现。缺点：l对于复杂图形，每个像素被访问多次，输入输出量过大。l边缘填充算法的改进栅栏填充算法l基本思想：l栅栏一条与扫描线垂直的直线，通常取其位置过多边形顶点，且把多边形分成两半。l对于每个扫描线与边的交点，将交点与栅栏之间的像素取补。算法演示l算法优缺点l该算法相比边缘填充算法，减少了像素的重复访问数量，但仍然有很

9、多像素被重复访问。l边标志法l基本思想：l首先，对多边形的每条边进行直线扫描转换，即对多边形边界所经过的像素，打上边标志；l然后，对每条与多边形相交的扫描线，逐个访问该扫描线上的像素，使用一个Bool量Inside来指示当前点的状态，以取值为真表示点在多边形内部。l扫描开始时，Inside初始值为假，每当遇到打上了边标志的像素，则对Inside取反。Inside取值为真的像素全部为多边形内部需要着色的像素。算法演示对于局部极值点，扫描线与多边形的相交次数是奇数，填充时会出现“抽丝”现象。即某扫描线上不该填充的区段填上色，而应该填充的区段却没有填上色。当扫描线y遇到斜率小于1的边界线时，会连续碰

10、到几个边界点，引起标志的无序改变，导致填充的错误。解决办法：判断多边形顶点的性质，如果是局部极值点，那么扫描线碰上它则不改变标志（可以建立边表）。解决办法：对于不同斜率的边界，都要使用斜率大于1的直线扫描转换方法：每次y方向增长一步，x方向增长1/m步距，以保证扫描线y遇到斜率小于1的边界时，只能遇到一个点。l该算法与有序边表算法的比较：l使用软件实现时，两者执行速度几乎相同。l边标志法在直接使用硬件实现时，因为不需要建立和维护边表以及排序的运算，其执行速度比有序边表算法快的多。1. 多边形的扫描转换2. 区域填充3. 字符和矢量图形的显示4. 反走样基础l2.1 区域的定义l区域是指已经表示

11、成点阵形式的填充图形，是一个像素集合。l2.2 区域填充和扫描线填充算法的区别l区域填充假设区域内部至少有一个像素，其颜色已经给定，由此出发找到区域内的所有像素并填充颜色。所处理的对象是点阵表示的区域。l扫描线算法则没有对刷新缓冲器的初始值有任何假设。所处理的是几何表示的多边形。l2.3 区域的表示l边界表示法：把位于给定区域的边界上的像素一一列举出来的方法，此时区域外部像素取值可以和内部一样，但不能和边界像素一样l枚举出区域内所有像素的表示方法称为内点表示法44p44(b)p的8-邻接点8 8 888p88 8(a)p的4-邻接点邻接点的定义图5-32 区域的边界表示和内点表示(a)以边界表

12、示的4-连通区域(b)以内点表示的4-连通区域(c)以边界表示的8-连通区域(d)以内点表示的8-连通区域l一个结论l4-连通区域的边界是8-连通的：边界点可以通过8-邻接点遍历l反之，8-连通区域的边界是4-连通的：边界点可以通过4-邻接点遍历l2.4 边界填充算法l算法思想：从内部一个种子像素出发，通过四算法思想：从内部一个种子像素出发，通过四连通（四向算法）或者八连通方向（八向算法）连通（四向算法）或者八连通方向（八向算法）对所有像素进行遍历和着色操作，直到所有像对所有像素进行遍历和着色操作，直到所有像素都完成着色操作为止。素都完成着色操作为止。l边界填充算法实现（4-邻接点）l需要的数

13、据结构需要的数据结构l堆栈：后进先出。堆栈：后进先出。123l首先，种子像素入栈，然后，当栈顶元素非空首先，种子像素入栈，然后，当栈顶元素非空时，重复执行下面的操作：时，重复执行下面的操作：(1)栈顶像素出栈；栈顶像素出栈；(2)将出栈像素置成填充色；将出栈像素置成填充色；(3)检查出栈像素的检查出栈像素的4-邻接点，若其中某个邻接点，若其中某个像素点不是边界色且未置成多边形色，则像素点不是边界色且未置成多边形色，则把该像素入栈。返回到把该像素入栈。返回到(1)。算法演示l算法输入的初始数据：算法输入的初始数据： 种子点坐标，填充色，边界像素颜色。种子点坐标，填充色，边界像素颜色。l算法具体实现算法具体实现l种子填充算法实现（8-邻接点）算法演示l种子填充算法的优缺点l优点：可以填充带有内孔的区域l缺点：太多的像素被压入堆栈