第四章多边形的扫描转换 与区域填充4.1多边形扫描转换 4.2区域填充n多边形分为凸多边形、凹多边形、含内环的多 边形。4.14.1多边形的扫描转换多边形的扫描转换4.1多边形的扫描转换n多边形的表示方法n顶点表示n点阵表示n顶点表示：用多边形顶点的序列来刻划多边形 。直观、几何意义强、占内存少；不能直接用于 面着色。n点阵表示：用位于多边形内的象素的集合来刻 划多边形。失去了许多重要的几何信息；便于运 用帧缓冲存储器表示图形，易于面着色。4.1多边形的扫描转换n多边形的扫描转换：把多边形的顶点表示转 换为点阵表示，也就是从多边形的给定边界出 发，求出位于其内部的各个象素，并给帧缓冲 器内的各个对应元素设置相应的灰度和颜色， 通常称这种转换为多边形的扫描转换。n两种方法：扫描线算法；边界标志法。扫描线算法扫描线算法n扫描线算法n目标：利用相邻像素之间的连贯性，提高算 法效率n处理对象：非自交多边形 （边与边之间除了 顶点外无其它交点）扫描线算法n交点的取整规则n要求：使生成的像素全部位于多边形之内n用于线画图元扫描转换的四舍五入原则导致 部分像素位于多边形之外，从而不可用n假定非水平边与扫描线y=e 相交，交点的横坐标为x, 规则如下扫描线算法 规则1：X为小数，即交点落于扫描线上两个相邻像素之间(a)交点位于左边之上，向右取整(b)交点位于右边之上，向左取整规则2：边界上象素的取舍问题，避免填充扩大化。 解决方法：边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭右开扫描线算法规则3：扫描线与多边形的顶点相交时，交点的取舍，保证交点正确 配对。 解决方法： 检查两相邻边在扫描线的哪一侧。只要检查顶点的两条边的另外两个端点的Y值，两个Y值中 大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。扫描线算法扫描线算法是多边形扫描转换的常用算法。 与逐点判断算法相比，扫描线算法充分利用了相 邻象素之间的连贯性，避免了对象素的逐点判断 和反复求交的运算，达到了减少了计算量和提高 速度的目的。开发和利用相邻象素之间的连贯性是光栅图 形算法研究的重要内容。扫描转换算法综合利用 了区域的连贯性、扫描线连贯性和边的连贯性等 三种形式的连贯性。扫描线算法设多边形P的顶点Pi=(xi,yi),i=0,1, ,n，又设 yi0,yi1,yin 是各顶点Pi的坐标yi的递减数列，即yikyik+1,0kn-1 这样，当yikyik+1,0kn-1时，屏幕上位于y=yik和 y=yik+1两条扫描线之间的长方形区域被多边形P的边分割 成若干梯形（三角形可看作其中一底边长为零的梯形）， 它们具有下列性质：区域的连贯性y=yiky=yik+1区域的连贯性1）梯形的两底边分别在y=yik和y=yik+1两条扫描线上，腰 在多边形P的边上或在显示屏幕的边界上。 2）这些梯形可分为两类：一类位于多边形P的内部；另 一类在多边形P的外部。 3）两类梯形在长方形区域yik,yik+1内相间的排列，即 相邻的两梯形必有一个在多边形P内，另一个在P外。y=yik+1y=yik区域的连贯性根据这些性质，实际上只需知道该长方形 区域内任一梯形内一点关于多边形P的内 外关系后，即可确定区域内所有梯形关于 P的内外关系。设e为一整数，yi0eyin。若扫描线y=e与多边形P的 Pi-1Pi相交，则记其交点的横坐标为xei。现设xei1,xei2,xei3,xeil 是该扫描线与P的边界各交 点横坐标的递增序列，称此序列为交点序列。由区域的连 贯性可知，此交点序列具有以下性质： 扫描线的连贯性扫描线的连贯性1）设L是偶数。 2）在该扫描线上，只有区段(xeik,xeik+1） ,k=1,3,5,L-1位于多边形P内，其余区段都在P 外。以上性质称为扫描线的连贯性，它是多边形 区域连贯性在一条扫描线上的反映。设d为一整数，并且d=e-1,并且 yi0dyin。设位于 扫描线y=d上的交点序列为xdj1,xdj2,xdj3,xdjk现在来讨论扫描线d，e交点序列之间的关系。若多 边形P的边Pr-1Pr与扫描线y=e,y=d都相交，则交点序列 中对应元素xer,xdr满足下列关系： xer= xdr + 1/mr (1) 其中mr为边Pr-1Pr的斜率。边的连贯性y=e y=d边的连贯性于是，可利用d的交点序列计算e的交点序列，即 先运用递推关系式(1)求得与扫描线y=e和y=d都 相交的所有多边形上的交点xer,再求得与扫描线 y=d不相交但与扫描线y=e相交的所有边PqPq+1上 的交点xeq。如果P的顶点的坐标是整数，那么 xeq=xq或xeq=xq+1,然后把这两部分按递增的顺序 排列，即可得e的交点序列。y=e y=d边的连贯性特别是当存在某一个整数k,0kn-1,使得 yike, dyik+1 成立时，则由区域的连贯性可知d的交点序列和e 的交点序列之间有以下关系：1）两序列元素的个数相等，如上图所示。2）点(xeir,e)与(xdjr,d)位于多边形P的同一 边上，于是 xeir= xdjr + 1/kjr (2) 这样，运用递推关系式(2)可直接由d的交点序列 和e的获得e的交点序列。 以上性质称为边的连贯性，它是区域的连贯性在 相邻两扫描线上的反映。当扫描线与多边形P的交点是P的顶点时，则称该 交点为奇点。 以上所述多边形的三种形式的连贯性都基于这样 的几何事实：每一条扫描线与多边形P的边界的交 点个数都是偶数。但是如果把每一奇点简单地计为 一个交点或者简单地计为两个交点，都可能出现奇 数个交点。那么如果保证交点数为偶数呢？奇点的处理奇点的处理n若奇点做一个交点处理，则情况A，交点 个数不是偶数。n若奇点做两个交点处理，则情况B，交点 个数不是偶数。奇点的处理n多边形P的顶点可分为两类：极值奇点和非极 值奇点。如果(yi-1 - yi)(yi+1 - yi)0，则称 顶点Pi为极值点；否则称Pi为非极值点。n规定：奇点是非极值点时，该点按两个交点计 算，否则按一个交点计算。数据结构与实现步骤算法基本思想：首先取d=yin。容易求 得扫描线y=d上的交点序列为 xdj1,xdj2,xdjn ，这一序列由位于扫描线 y=d上的多边形P的顶点组成。由yin的交点序列开始，根据多边形的 边的连贯性，按从上到下的顺序求得各条 扫描线的交点序列；根据扫描线的连贯性 ，可确定各条扫描线上位于多边形P内的 区段，并表示成点阵形式。数据结构与实现步骤所有的边和扫描线求交，效率很低。因为一条扫 描线往往只和少数几条边相交。如何判断多边形的一条边与扫描线是否相交？与当前扫描线相交的边称为活性边（active edge)，把它们按与扫描线交点x坐标递增的顺序 存入一个链表中，边的活化链表 （ AEL, Active edge table)。它记录了多边形边沿扫描 线的交点序列。只需对当前扫描线的活动边表作更新，即可得到 下一条扫描线的活动边表。数据结构与实现步骤n如何计算下一条扫描线与边的交点。直线方程：ax+by+c = 0当前交点坐标：(xi, yi)下一交点坐标：(xi+1,yi+1) xi+1= (-byi+1)-c)/a = (-byi+1)-c)/a =xi-b/a=xi+1/mi活动边表中需要存放的信息：x：当前扫描线与边的交点dx-b/a：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线数据结构与实现步骤n为了方便边的活化链表的更新，建立另一个表 -边表，存放在该扫描线第一次出现的边。存放的信息：x：扫描线与该边的初始交点dx：x的增量ymax：该边的最大y值即算法中采用较灵活的数据结构。它由边的分 类表ET（Edge Table）和边的活化链表AEL（Active Edge List）两部分组成。表结构ET和AEL中的基本元素为多边形的边。边 的结构由以下四个域组成：ymax 边的上端点的y坐标；x 在ET中表示边的下端点的x坐标，在 AEL中则表示边与扫描线的交点的坐标；x 边的斜率的倒数；next 指向下一条边的指针。数据结构与实现步骤数据结构与实现步骤 边的分类表ET是按边的下端点的y坐标对非 水平边进行分类的指针数组。下端点的y 坐标的值等于i的边归入第i类。有多少条 扫描线，就设多少类。同一类中，各边按 x值（x值相等时，按x的值）递增的顺 序排列成行。边表724P5 P178-1P2 P1620P4 P536-2P3 P4560.5P3 P2(Ymax, x,x, next) 活动边表的例子34-2P3 P456.50.5P3 P2扫描线2AET指针620P4 P5570.5P3 P2扫描线3AET指针(Ymax, x,x, next)36-2P3 P4560.5P3 P2扫描线2AET指针活动边表的例子活动边表的例子620P4 P557.50.5P3 P2扫描线4AET指针620P4 P578-1P2 P1扫描线5AET指针724P5 P178-1P2 P1扫描线6AET指针算法实现步骤这样，当建立了边的分类表ET后，扫描线算法可 按下列步骤进行：（1）取扫描线纵坐标y的初始值为ET中非空 元素的最小序号。（2）将边的活化链表AEL设置为空。（3）按从下到上的顺序对纵坐标值为y的扫 描线（当前扫描线）执行下列步骤，直到边的分 类表ET和边的活化链表都变成空为止。算法实现步骤1）如边分类表ET中的第y类元素非空，则将属于该类的 所有边从ET中取出并插入边的活化链表中，AEL中的各边 按照x值（当x值相等时，按x值）递增方向排序。 2）若相对于当前扫描线，边的活化链表AEL非空，则将 AEL中的边两两依次配对，即1，2边为一对，3，4边为一 对，依次类推。每一对边与当前扫描线的交点所构成的 区段位于多边形内，依次对这些区段上的点（象素）按 多边形属性着色。 3）将边的活化链表AEL中满足y=ymax的边删去。 4）将边的活化链表AEL剩下的每一条边的x域累加x， 即x:=x+x。 5）将当前的扫描线的纵坐标值y累加1，即y:=y+1。扫描线算法n特点：算法效率较高。n缺点：对各种表的维持和排序开销 太大，适合软件实现而不适合硬件实 现。扫描线算法问题：如何处理多边形的水平边？如何修改扫描线算法，使它能处理边 自交的多边形？1. 对多边形的每一条边进行扫描转换，即对多边 形边界所经过的象素作一个边界标志。2.填充。对每条与多边形相交的扫描线，按从左 到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态，若 点在多边形内，则inside为真。若点在多边形外 ，则inside为假。Inside 的初始值为假，每当当前访问象素为被打 上标志的点，就把inside取反。对未打标志的点 ，inside不变。边界标志算法边界标志算法:算法过程void edgemark_fill(polydef, color) 多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换；inside = FALSE;for (每条与多边形polydef相交的扫描线y )for (扫描线上每个象素x ) if(象素 x 被打上边标志)inside = ! (inside);if(inside！= FALSE)drawpixel (x, y, color);else drawpixel (x, y, background);边界标志算法n用软件实现时，扫描线算法与边界标志 算法的执行速度几乎相同，n但由于边界标志算法不必建立维护边表 以及对它进行排序，所以边界标志算法更 适合硬件实现，这时它的执行速度比有序 边表算法快一至两个数量级。边界标志算法n思考：如何处理边界的交点个数使其成 为偶数？第四章多边形的扫描转