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

第五章基本图形生成算法多边形的扫描转换算法实施区域填充字符和矢量图形的显示反走样基础扫描线算法扫描线算法原理回顾求交排序交点配对区间填色X扫描线算法缺点 实际上一条扫描线只和少数边相交，甚至没有和任意边相交，造成大量冗余计算。计算交点时提取所有边与扫描线求交有序边表算法－－活性边表算法改进原理：处理一条扫描线时，仅对与它相交的边求交；利用扫描线的连贯性利用多边形边的连贯性

如一条扫描线排序后与多边形边的交点x坐标依次是x0,x1,x2,…,x2n+1，则对特殊点处理后，(x2i,x2i+1)(i=0,…,n)组成的区间为多边形内的区间。

我们把与当前扫描线相交的多边形边称为活性边(ActiveEdge，AE)多边形边的连贯性：某条边和当前扫描线相交时，它很可能也与下一条扫描线相交，并且交点坐标遵循下面的规律。(xi,yi)(xi+dx,yi+1)11/k即对一条边y=kx+b来说，如果当前扫描线得到的交点为(xi,yi),则下一条扫描线交点为(xi+1/k,yi+1)直线方程y=kx+bdy/dx=k,即dx=dy/k微分形式：此时dy=1,则dx=1/k找到一条边上前后扫描线交点的关系，如何加以利用？增量算法思想：扫描线改变时，同一条边上的后一个交点，可以利用上一次求交点的结果，直接加上一个增量来得到。x的增量dx=1/k,y的增量dy=1使用一个数据结构来表示与当前扫描线相交的边，扫描线改变时，只要相交边－－活性边不变，则不需要对该数据结构中的内容修改。有初始值，有算法结束的限制条件。对于任意一条相交边

其交点的初始值为Y值小的端点；终止于Y值较大的端点。数据结构：活性边表（ActiveEdgeTable，AET） 把活性边按照与扫描线交点x坐标递增的顺序存放在一个链表中，该链表称为活性边表。活性边表的结构和存储内容：一个活性边表对应多个节点，一个节点对应一条边，多个节点之间按照x从小到大规则，进行排序。x0ymax0next1/k0x1ymax1null1/k1具有两条边的活性链表活性边表的操作根据边的连贯性，当前扫描线发生改变时：如果没有新的活性边加入，也没有边到达终点，此时新扫描线和边相交的交点序列不发生改变。处理下一条扫描线时，如有新边加入，则新边需要作为新节点插入适当位置适合插入排序。当某个相交边到达终点，则需要将该边从活性边表中删除。边表（EdgeTable，ET）/新边表 对于每个扫描线，建立一个最小y坐标位于该扫描线上的活性边的链表，来表示从下到上扫描到该扫描线时，新增加的活性边。全体扫描线就对应了一个（新）边表。

从下到上扫描过程中，只有下一条扫描线具有一个对应的活性边的链表时，才需要对当前的活性边表进行插入新边的操作。边表的构造

(1)首先构造一个纵向线性表，表的长度为多边形所占有的最大扫描线数，表的每个结点，称为一个桶，对应多边形覆盖的每一条扫描线。(2)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。xymax1/kNEXT(4)同一桶中若干条边按X由小到大排序，若X相等，则按照1/k由小到大排序。(3)将每条边的对应结点链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边的结点就放在相应的扫描线桶中。边表构造示例12111098765432137-1/3353/485-1/2891/2712-17951122/5边表构造示例y=8时，活性边1.4122/5712-179511.591/2算法实现(1)初始化：构造边表ET，如果边表为空则返回； 活性边表AET置空；(2)初始化：将ET表中第一个非空桶中边插入AET；(3)处理当前扫描线：由AET表中取出交点对进行 填充。(4)令yi+1=yi+1,删除ymax=y的边；(5)根据xi+1=xi+1/k计算并（通过排序）修改AET表， 同时将ET表中y=yi+1桶中的边，按次序插入 到AET表中，形成下一条扫描线的新AET表；(6)AET表不为空则转(3)，否则结束。算法演示活性边表法优点和缺点优点：采用链表实现，节约存储空间充分利用了边连贯性和扫描线连贯性，减少了求交计算量，提高了排序的效率，从而大大减少了程序算法的复杂度。对显示的每个像素只访问一次，输入输出量少缺点：对链表的维持和排序开销较大。不适合硬件实现。边缘填充算法基本思想：对于每一条扫描线和每条多边形边的交点(xi,yi),将该扫描线上交点右方的所有像素取补。对多边形的每条边都依次处理一次，顺序随意。所有边完成以后，像素结果即为该多边形的填充区域。算法演示算法优点和缺点优点：该算法最适用于具有帧缓冲器的图形系统，按任意顺序处理多边形的边，在处理每条边时，仅访问与该边相交的扫描线上交点右方的像素。当所有边处理完成后，直接按照扫描线顺序读出帧缓冲器的内容，送入显示设备。简单，易于硬件实现。缺点：对于复杂图形，每个像素被访问多次，输入输出量过大。边缘填充算法的改进－－栅栏填充算法基本思想：栅栏－－一条与扫描线垂直的直线，通常取其位置过多边形顶点，且把多边形分成两半。对于每个扫描线与边的交点，将交点与栅栏之间的像素取补。算法演示算法优缺点该算法相比边缘填充算法，减少了像素的重复访问数量，但仍然有很多像素被重复访问。边标志法基本思想：首先，对多边形的每条边进行直线扫描转换，即对多边形边界所经过的像素，打上边标志；然后，对每条与多边形相交的扫描线，逐个访问该扫描线上的像素，使用一个Bool量Inside来指示当前点的状态，以取值为真表示点在多边形内部。扫描开始时，Inside初始值为假，每当遇到打上了边标志的像素，则对Inside取反。Inside取值为真的像素全部为多边形内部需要着色的像素。算法演示错误处理对于局部极值点，扫描线与多边形的相交次数是奇数，填充时会出现“抽丝”现象。即某扫描线上不该填充的区段填上色，而应该填充的区段却没有填上色。当扫描线y遇到斜率小于1的边界线时，会连续碰到几个边界点，引起标志的无序改变，导致填充的错误。解决办法：判断多边形顶点的性质，如果是局部极值点，那么扫描线碰上它则不改变标志（可以建立边表）。解决办法：对于不同斜率的边界，都要使用斜率大于1的直线扫描转换方法：每次y方向增长一步，x方向增长1/m步距，以保证扫描线y遇到斜率小于1的边界时，只能遇到一个点。该算法与有序边表算法的比较：使用软件实现时，两者执行速度几乎相同。边标志法在直接使用硬件实现时，因为不需要建立和维护边表以及排序的运算，其执行速度比有序边表算法快的多。1.多边形的扫描转换2.区域填充3.字符和矢量图形的显示4.反走样基础2.区域填充2.1区域的定义区域是指已经表示成点阵形式的填充图形，是一个像素集合。2.区域填充2.2区域填充和扫描线填充算法的区别区域填充－－假设区域内部至少有一个像素，其颜色已经给定，由此出发找到区域内的所有像素并填充颜色。所处理的对象是点阵表示的区域。扫描线算法则没有对刷新缓冲器的初始值有任何假设。所处理的是几何表示的多边形。2.3区域的表示边界表示法：把位于给定区域的边界上的像素一一列举出来的方法，此时区域外部像素取值可以和内部一样，但不能和边界像素一样枚举出区域内所有像素的表示方法称为内点表示法2.区域填充像素的4-邻接点和8-邻接点

一个结论4-连通区域的边界是8-连通的：边界点可以通过8-邻接点遍历反之，8-连通区域的边界是4-连通的：边界点可以通过4-邻接点遍历2.区域填充2.4边界填充算法算法思想：从内部一个种子像素出发，通过四连通（四向算法）或者八连通方向（八向算法）对所有像素进行遍历和着色操作，直到所有像素都完成着色操作为止。边界填充算法实现（4-邻接点）需要的数据结构堆栈：后进先出。123首先，种子像素入栈，然后，当栈顶元素非空时，重复执行下面的操作：(1)栈顶像素出栈；(2)将出栈像素置成填充色；(3)检查出栈像素的4-邻接点，若其中某个像素点不是边界色且未置成多边形色，则把该像素入栈。返回到(1)。算法演示算法输入的初始数据：种子点坐标，填充色，边界像素颜色。算法具体实现种子填充算法实现（8-邻接点）算法演示种子填充算法的优缺点优点：可以填充带有内孔的区域缺点：太多的像素被压入堆栈，同一像素被重复入栈。种子算