第6讲 扫描转换与区域填充

1、n多边形的扫描转换多边形的扫描转换 n扫描线算法扫描线算法 n边界标志算法边界标志算法 n区域填充区域填充 n区域填充的递归算法区域填充的递归算法 n扫描线填充算法扫描线填充算法 第6讲 扫描转换与区域填充 顶点表示（线）顶点表示（线）点阵表示（填充）点阵表示（填充） 用多边形的顶点序列来表示用多边形的顶点序列来表示用位于多边形内的象素集合来表示用位于多边形内的象素集合来表示 扫描转换扫描转换 多边形的表示方法 n顶点表示：用多边形顶点的序列来刻划多 边形。直观、几何意义强、占内存少；不 能直接用于面着色。 n点阵表示：用位于多边形内的象素的集合 来刻划多边形。失去了许多重要的几何信 息；便于

2、运用帧缓冲存储器表示图形，易 于面着色。 多边形的表示方法 n多边形的扫描转换：多边形的扫描转换：把多边形的顶点表示转换把多边形的顶点表示转换 为点阵表示为点阵表示，也就是从多边形的给定边界出发， 求出位于其内部的各个象素，并给帧缓冲器内 的各个对应元素设置相应的灰度和颜色，通常 称这种转换为多边形的扫描转换。 n两种方法：两种方法：扫描线算法；边界标志法 多边形的扫描转换 n 按扫描线顺序，计算扫描线按扫描线顺序，计算扫描线 与多边形的相交区间，再用要求与多边形的相交区间，再用要求 的颜色显示这些区间的象素，即的颜色显示这些区间的象素，即 完成填充工作。完成填充工作。 扫描线算法基本思想 用

3、水平扫描线从上到下扫描； 每根扫描线与多边形各边产生一系列交点； 这些交点按照x坐标进行分类； 将分类后的交点成对取出，作为两个端点， 以所需要填的色彩画水平直线； 多边形被扫描完毕后，填色也就完成。 n一条扫描线填充过程的步骤：一条扫描线填充过程的步骤： （1）求交（）求交（2）排序（）排序（3）配对（）配对（4）填色）填色 扫描线算法基本思想 算法描述 n扫描线的相关性扫描线的相关性：某条扫描线上相邻的象素，几乎都具有 同样的内外性质，这种性质只有遇到多边形边线与该扫描 线的交点时才会发生改变。 n边的相关性边的相关性：由于相邻扫描线上的交点是与多边形的边线 相关的。对同一条边，前一条扫描

4、线yi与该边的交点为xi， 而后一条扫描线yi+1=yi+1与该边的交点则为 xi+1=xi+1/m，利用这种相关性可以省去大量的求交运算。 n扫描线的相关性 扫描线的相关性 边的相关性边的相关性 当扫描线与多边形P的交点是P的顶点时，则称该 交点为奇点。 以上所述多边形的的连贯性都基于这样的几何事 实：每一条扫描线与多边形P的边界的交点个数都 是偶数。但是如果把每一奇点简单地计为一个交点 或者简单地计为两个交点，都可能出现奇数个交点。 那么如果保证交点数为偶数呢？ 奇异点的处理 奇异点的处理 将多边形的顶点分为两大类： 局部极值点局部极值点 进入该点的边线和离开该点的边线位于过该点 扫描线的

5、同一侧。点P1、P2、P4和P6。 非极值点非极值点 对于这些点来说，进入该点的边线和离开该点的 边线位于过该点扫描线的两侧。点P3、P5。 处理奇异点规则：处理奇异点规则： 对于局部极值点，看成两个点；对于局部极值点，看成两个点； 对于非极值点，看成一个点。对于非极值点，看成一个点。 活性边表活性边表(AET)(AET)：把与当前扫描线相交的边称为活：把与当前扫描线相交的边称为活 性边，并把它们按与扫描线交点性边，并把它们按与扫描线交点x x坐标递增的顺序坐标递增的顺序 存放在一个链表中存放在一个链表中 第一项：当前扫描线与边的交点坐标第一项：当前扫描线与边的交点坐标x x 第二项：从当前扫

6、描线到下一条扫描线间第二项：从当前扫描线到下一条扫描线间x x的增量的增量x x 第三项：该边所交的最高扫描线号第三项：该边所交的最高扫描线号y ymax max 第四项：指针。用来指向同一条扫描线相交的其它第四项：指针。用来指向同一条扫描线相交的其它 边，如果其它边不存在，则该项置空。边，如果其它边不存在，则该项置空。 第一项第一项第三项第三项第二项第二项第四项第四项 扫描线算法数据结构 活性边表 01 1 2 23 3 4 45 5 6 67 7 8 891011 P2(5,1) E P3(11,3) D P4(11,8) G F CB P5(5,5) P6(2,7) A P1(2,2)

7、2 0 7 3.5 -1.5 7 P6P1 P5P6 AB 7 2 8 11 0 8 P4P5 P3P4 CDx ymaxx ymaxx ymaxx ymax n扫描线为扫描线为6的活性表的活性表 假定当前扫描线与多边形某一条边的交点的x坐标 为x，则下一条扫描线与该边的交点不要重计算， 只要加一个增量x。 设该边的直线方程为：ax+by+c=0； 若yyi，x=x i；则当y = y i+1 yi 1 时， 其中 为常数，是斜率的倒数 ;)( 1 11 a b xcyb a x iiii a b x iii cby a x 1 活性边表 n为了方便边的活化链表的更新，建立另一个表 -边表，存

8、放在该扫描线第一次出现的边。 存放的信息： x：扫描线与该边的初始交点 dx：x的增量 ymax：该边的最大y值 新边表 新边表（新边表（NETNET）：）： 存放在该扫描线第一次出现的边。存放在该扫描线第一次出现的边。 若某边的较低端点为若某边的较低端点为y ymin min， ， 则该边就放在扫描线则该边就放在扫描线y ymin min的新边表中 的新边表中 7 6 P4P5 P5P6 5 4 3 2 1 0 P1P2 P2P3 8 5 -3 2 5 3 3 2 0 7 11 0 8 5 2 8 5 -1.5 7 P6P1 P3P4 01 1 2 23 3 4 45 5 6 67 7 8

9、891011 P2(5,1) E P3(11,3) D P4(11,8) G F CB P5(5,5) P6(2,7) A P1(2,2) 新边表 规则1： X X为小数，即交点落于扫描线上两个相邻像素之间为小数，即交点落于扫描线上两个相邻像素之间 (a)(a)交点位于左边之上，向右取整交点位于左边之上，向右取整 (b)(b)交点位于右边之上，向左取整交点位于右边之上，向左取整 扫描线算法 规则2 2： 边界上象素的取舍问题，避免填充扩大化。 解决方法：解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭右开 扫描线算法 void polyfi

10、ll (polygon, color) int color; 多边形多边形 polygon; for (各条扫描线各条扫描线i ) 初始化新边表头指针初始化新边表头指针NET i； 把把y min = i 的边放进边表的边放进边表NET i; y = 最低扫描线号；最低扫描线号； 初始化活性边表初始化活性边表AET为空；为空； for (各条扫描线各条扫描线i ) 扫描线算法 把新边表把新边表NET i 中的边结点用插入排序法插中的边结点用插入排序法插 入入AET表，使之按表，使之按x坐标递增顺序排列；坐标递增顺序排列； 遍历遍历AET表，把配对交点区间表，把配对交点区间(左闭右开左闭右开)上

11、的上的 象素象素(x, y)，用，用drawpixel (x, y, color) 改写象改写象 素颜色值；素颜色值； 遍历遍历AET表，把表，把y max= i 的结点从的结点从AET表中删除，表中删除， 并把并把y max i 结点的结点的x值递增值递增 x； 若允许多边形的边自相交，则用冒泡排序法对若允许多边形的边自相交，则用冒泡排序法对 AET表重新排序；表重新排序； /* polyfill */ 扫描线算法 n特点：对于顶点表示的多边形，算法 效率较高。 n缺点：对各种表的维持和排序开销太 大，适合软件实现而不适合硬件实现。 扫描线算法 边界标志算法 n扫描线的相关性 n某条扫描线上

12、相邻的某条扫描线上相邻的 象素，几乎都具有同样象素，几乎都具有同样 的内外性质，这种性质的内外性质，这种性质 只有遇到多边形边线与只有遇到多边形边线与 该扫描线的交点时才会该扫描线的交点时才会 发生改变。发生改变。 边界标志算法 n基本思想 n先在屏幕上生成多边形轮廓线，然后逐条扫描先在屏幕上生成多边形轮廓线，然后逐条扫描 处理。处理中：逐点读取象素值，若为边界色，处理。处理中：逐点读取象素值，若为边界色， 则对该象素值进行颜色切换。则对该象素值进行颜色切换。 边界标志算法 n算法实现 1、用边界色画出多边形轮廓线，也就是将多边形边界所 经过的象素打上边标志。 2、为了缩小范围，加快填充速度，

13、须找出多边形的最小 包围盒：xmin、ymin、xmax、ymax。 3、逐条扫描线进行处理， 对每条扫描线依从左往右的顺序， 逐个访问该扫描线上的象素。每 遇到边界象素，标志取反。然后， 按照标志是否为真决定象素是否 为填充色。 演示 边界标志算法 n算法特点 该算法思想简单，实现容易。既不需要求交点、该算法思想简单，实现容易。既不需要求交点、 交点排序、边的登记，也不需要使用链表、堆栈交点排序、边的登记，也不需要使用链表、堆栈 等数据结构。等数据结构。 用软件实现时，扫描线算法与边界标志算法的执用软件实现时，扫描线算法与边界标志算法的执 行速度几乎相同，但由于边界标志算法不必建立行速度几乎

14、相同，但由于边界标志算法不必建立 维护边表以及对它进行排序，所以边界标志算法维护边表以及对它进行排序，所以边界标志算法 更适合硬件实现，这时它的执行速度比有序边表更适合硬件实现，这时它的执行速度比有序边表 算法快一至两个数量级。算法快一至两个数量级。 二 区域填充 n区域的含义 这里讨论的区域指已经表示成点阵形式 的填充图形，它是像素的集合 区域填充 n区域表示方法：区域表示方法： 表示内点 表示边界点 区域填充 n区域表示方法：区域表示方法： 内点表示、边界表示 n内点表示内点表示 n枚举出区域内部的所有像素 n内部的所有像素着同一个颜色 n边界像素着与内部像素不同的颜色 n边界表示边界表示

15、 n枚举出边界上所有的像素 n边界上的所有像素着同一颜色 n内部像素着与边界像素不同的颜色 表示内点 表示边界点 n区域填充的含义 n n 是指先将区域的一点赋予指定的颜色，是指先将区域的一点赋予指定的颜色， n 然后将该颜色扩展到整个区域的过程。然后将该颜色扩展到整个区域的过程。 n 区域填充 区域填充算法要求区域是连通的。区域填充算法要求区域是连通的。 八连通八连通：区域内部从一个象素到达另：区域内部从一个象素到达另 一个象素的移动路径，除了上、下、一个象素的移动路径，除了上、下、 左、右四个方向外，还允许沿着对角左、右四个方向外，还允许沿着对角 线方向线方向。 区域的连通性 四连通四连通

16、：从区域内一点出发，可通过：从区域内一点出发，可通过 四个方向：上、下、左、右到达该区四个方向：上、下、左、右到达该区 域内部的任意象素。域内部的任意象素。 n八连通区域四连通区域 区域的连通性 区域填充算法 已知条件：已知条件： G G为一内点表示的区域为一内点表示的区域 ( (x x, ,y y) )为区域内一点为区域内一点 old old_ _colorcolor为为G G的原色的原色 如何对如何对G G进行填充？进行填充？ 区域填充的递归算法 已知条件：已知条件： G G为一内点表示的区域为一内点表示的区域 ( (x x, ,y y) )为区域内一点为区域内一点 old old_ _c

17、olorcolor为为G G的原色的原色 现取现取( (x x, ,y y) )为种子点对区域为种子点对区域G G进行填充：进行填充： 即先置像素即先置像素( (x x, ,y y) )的颜色为的颜色为newnew_ _colorcolor 然后逐步将整个区域然后逐步将整个区域G G都置为同样的颜色。都置为同样的颜色。 区域填充的递归算法 步骤如下： 种子像素入栈，当栈非空时，执行如下 三步操作： n （1）栈顶像素出栈； n （2）将出栈像素置成多边形色； n （3）按上、下、左、右的顺序检查与出 栈像素相邻的四个像素，若其中某个像素 不在边界上且未置成多边形色，则把该像 素入栈。 s12

18、3 4 9 8 7 6 5 11 12 13 14 10 递归算法 n例：多边形例：多边形P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1) 种子点为（种子点为（3 3，3 3） 搜索的方向是上、下、左、右。搜索的方向是上、下、左、右。 内点表示的四连通区域的递归填充算法 void FloodFill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) /属于区域内点oldcolor drawpixel(x,y,newcol

19、or); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); 递归算法 边界表示的四连通区域的递归填充算法 void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) int color; if(color!=newcolor BoundaryFill4 (x,y+1, boundaryc

20、olor,newcolor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); 递归算法 递归算法 假设在多边形内一个像素已知，由此出发假设在多边形内一个像素已知，由此出发 利用连通性找到区域内的所有像素。利用连通性找到区域内的所有像素。 内点检测条件 用来判断任何一个检测像素点(x,y)是不是尚未填充 内点表示内点表示 边界表示边界表示 if(getpixel(

21、x,y)!=if(getpixel(x,y)!=边界色边界色 b.填充整个区段。 c.检查相邻的上扫描线的xleftxxright区间内,是否存在 需要填充的新区段，如果存在的话，则把每个新区段在 xleftxxright范围内的最右边的象素，作为新的种子象素依次压入 堆栈。 d.检查相邻的下扫描线的xleftxxright区间内，是否存 在需要填充的新区段，如果存在的话，则把每个新区段在 xleftxxright范围内的最右边的象素，作为新的种子象素依次压入 堆栈。 算法演示 扫描线填充算法 1、该算法考虑了扫描线上象素的相关性，种子象素不再、该算法考虑了扫描线上象素的相关性，种子象素不再

22、代表一个孤立的象素，而是代表一个尚未填充的区段。代表一个孤立的象素，而是代表一个尚未填充的区段。 2、进栈时，只将每个区段选一个象素进栈（每个区段最、进栈时，只将每个区段选一个象素进栈（每个区段最 右边或最左边的象素），这样解决了堆栈溢出的问题。右边或最左边的象素），这样解决了堆栈溢出的问题。 3、种子出栈时，则填充整个区段。、种子出栈时，则填充整个区段。 4、这样有机的结合：一边对尚未填充象素的登记（象素、这样有机的结合：一边对尚未填充象素的登记（象素 进栈），一边进行填充（象素出栈），既可以节省堆栈空进栈），一边进行填充（象素出栈），既可以节省堆栈空 间，又可以实施快速填充。间，又可以实施快速填充。 算法特点算法特点 多边形扫描转换与区域填充方法比较 基本思想不同：基本思想不同： 前者：前者： 后者：后者： 多边形扫描转换与区域填充方法比较 基本思想不同：基本思想不同： 前者：顶点表示转换成点阵表示前者：顶点表示转换成点阵表示 后者：只改变区域内填充颜色，没有改变表示方法。后者：只改变区域内填充颜色，没有改变表示方法。 多边形扫描转换与区域填充方法比较 基本思想不同：基本思想不同： 前者：顶点表示转换成点阵表示前者：顶点表示转换成点阵表示 后者：只改变区域内填充颜色，没有改变表示方法。后者：只改变区域内填充颜