扫描线填充种子填充线宽和线型.ppt

学习内容,3.4 区域填充算法 3.5 线宽与线型的处理,学习要点,1、理解掌握面域填充的概念，区域多边形的分类，面域填充的步骤；,2、理解扫描线填充算法的实质，掌握扫描线填充算法的过程；,3、了解种子填充算法和图案填充算法。,4、掌握线宽的处理以及线型的分类。,一、扫描线填充算法,区域是指相互连通的一组像素的集合。通常是由一个封闭的轮廓来定义，处于一个封闭轮廓线内的所有像素点即构成了一个区域。 例如：矩形、圆、椭圆、多边形等等。,1、扫描线填充算法的实质,区域-多边形（凸、凹）、圆、椭圆、带孔的。,区域填充-如何用一种颜色或图案填充二维区域。,区域填充分两步：,确定需要填充那些像素,确定需要那些颜色值（图案）,逐点判断法,逐个判断绘图窗口内的像素：,逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。,交点配对，1与2，3 ，每对表示一个区间。,排序，由于交点不一定由左 到右求出，因此将求出的交点按 x 坐标值排序。,算出交点；划分区间；分配颜色。,求交点，即计算扫描线与多 边形各边的交点。,(4) 区间填充,扫描线填充步骤,问题一：,9,9,1,2,3,4,5,6,8,7,10,0,0,1,8,7,6,4,5,3,2,11,交点的取舍: 比较交点与两边上其余两顶点y值大小，确定交点个数取0、1、2。,如果大于交点y值个数为2，则交点取两次，该点填充。,如果大于交点y值个数为0，则交点取零次，该点不填充。,2次,如果大于交点y值个数为1，则交点取一次。,0次,0次,1次,扫描线与顶点相交时，交点个数的取舍？,0,1,2,1,2,3,4,3,长方形面积S=(4-1)*(3-1)=6,按照扫描线填充算法填充后,为什么扩大化？,图形对象是用有限多个离散的像素表示，图形有大小、面积，但是点只有位置，而像素不仅有位置，还有大小。对于边界象素全部填充造成扩大化。,S1=4*3=12,S2=3*2=6,问题二：,多边形边界象素的取舍？,“左闭右开”、“下闭上开”,两个连贯性,当前扫描线与各边的交点顺序，与下一条扫描线与各边的交点顺序很可能相同或类似。,边的连贯性,扫描线的连贯性,xer= xdr + 1/kr yer= ydr + 1 kr为边的斜率,减少求扫描线和多边形各边的交点的计算量,2、扫描线填充算法具体实现,如何刻画多边形的边,一、边的分类,活化边表（活性边表）AEL（Active Edge List）按活化边与扫描线交点x坐标递增的顺序存放在一个链表中。对应于一条扫描线。,有序边在当前扫描线第一次出现的边。,有序边表ET（Edge Table）按有序边与扫描线交点x坐标递增的顺序存放在一个链表中。仅对非水平边分析，对应于一条扫描线。,活化边（活性边）与当前扫描线相交的多边形的边。,二、边的结构,边的结构有四个域组成（除指针外顺序可以相互交换）： ymax 边的上端点的y坐标（y的最大值）； x 在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线的交点的x坐标； x 边的斜率的倒数(到下一条扫描线x的增量）； next 指向下一条边的指针。,算法：活化边表法 通过 单向链接表 的操作得到扫描线与边的交点。,原理：建立在图形的空间连贯性（边的连贯性）和扫描线的连贯性基础上，计算图形封闭区域边界与扫描线交点，将扫描线分成区间，并对区间进行填充。,有序边表的建立,注意： 1 边的分类； 2 边的排序（如果x坐标相等，则按x排序）； 3 边的结构；,通过有序边，利用边的连贯性建立活化边表。它记录了多边形边沿扫描线的交点序列。,注意： 1 边的删除(将满足 ymax=y的边删除）； 2 边的增加； 3 边的排序； 4 X值的累加； 5 边的结构；,活化边表的建立,活化边表的建立,有序边表,活化边表,活化边表的建立,有序边表,活化边表,活化边表的建立,有序边表,活化边表,活化边表的建立,有序边表,活化边表,活化边表的建立,有序边表,活化边表,活化边表,算法具体实现步骤,一、建立扫描线的有序边表(ET),二、根据有序边表建立活化边表(AEL),(3)按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，直到有序边表ET和活化边表AEL都变成空为止。,(1)取扫描线纵坐标y的初始值为ET中非空元素的最小序号。,(2)将扫描线的活化边表AEL设置为空。,a)如有序边表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入第y类扫描线的活化边表中，AEL中的各边按照x值（当x值相等时，按x值）递增方向排序。边的增加和排序,b)将活化边表AEL中满足y=ymax的边删去。边的删除,c)将活化边表AEL剩下的每一条边的x域累加x，即x:=x+x。x的增加,d)将当前扫描线的纵坐标值y累加1，即y:=y+1。y的增加,e)若相对于当前扫描线，活化边表AEL非空，则将AEL中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。象素填充,Polygonfill(polydef,color) Int color; 多边形定义，polydef; for(各条扫描线I) 初始化新边表表头指针NETi; 把 =I的边放进表NETi； y=最低扫描线号； 初始化活化边表AET为空； for(各条扫描线i) 把新边表NETi中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列； 遍历AET表，把配对交点之间的区间(左闭右开)上的各象素（x,y），用 drawpixel(x,y,color)改写象素颜色值； 遍历AET表，把 i的结点从AET表中删除，并把 I结点的x值递增dx； 若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； /*Polygonfill*/,算法伪程序,扫描线填充算法小结,扫描线填充算法实质，基本概念，具体实现：,区域填充的过程（2W）、扫描线填充的基本过程，两个问题、两个连贯性、有序边（表）、活化边（表）、边的结构、判断顺序。,二、种子填充算法,多边形表示方法 顶点表示 点阵表示,顶点表示：用多边形顶点的序列来刻划多边形 特点：直观、几何意义强、占内存少；不能直接用于面着色；广泛应用于各种几何造型系统；,点阵表示：用位于多边形内的象素的集合来刻划多边形 特点：失去了许多重要的几何信息（边界、顶点等）；易于面着色；光栅显示系统显示时所需的表示形式；,光栅系统中两种基本的区域填充算法 针对采用顶点表示的多边形 通过确定横越区域的扫描线的覆盖间隔来填充的多边形扫描转换区域填充算法，主要填充简单多边形、圆、椭圆以及其它简单的曲线。 扫描线填充算法,针对采用点阵表示的多边形 从给定的位置开始图描着色直到达制定的边界条件为止的区域填充算法，主要具有复杂情况的边界情况。种子填充算法,1、简单种子填充算法,基本原理：从多边形区域内部的一点出发找到区域内的所有像素，常用于交互式绘图。,基本思路：程序开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否是边界色和填充色，若不是，就填充该相邻点。这个过程延续到已经检测完区域边界范围内的所有像素为止。,从当前点检测相邻像素有两种方法：,（1）四向连通方法：指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动和组合，在不越出区域的前提下，到达区域内的任意像素；,（2）八向连通方法：指的是区域内每一个像素，可以通过左、右、上、下、左上、右上、左下、右下这八个方向的移动的组合来到达。,种子填充算法（四向算法）：允许从四个方向寻找下一象素，栈结构实现。,算法：种子象素入栈（先进后出），当栈非空时，重复执行：,栈顶象素出栈；,将出栈象素置成多边形色；,按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,可用于填充带内孔的平面区域。,例：多边形由P0P1P2P3P4构成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1) 设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示 （画图）,缺点： (1) 有些象素会入栈多次，降低算法效率；栈结构占空间。,(2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。,改进算法，减少递归次数。 解决方法是用扫描线种子填充算法；,2、扫描线种子填充算法,目标：减少递归层次 适用于边界表示的4连通区域,算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻像素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的个区段都填充完毕。,算法步骤：,Step1：栈顶象素出栈，,Step2：沿扫描线对出栈象素的左右象素进行填充，直到遇到边界象素为止，即填充区间。,算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。,举例分析,该算法也可以填充有孔区域。,像素中的序号标指它所在区段位于堆栈中的位置,三、图案填充算法,图案填充算法,实际应用中，有时需要用一种图案来填充多边形区域。这可以通过对前述填充算法中写像素的那部分代码稍作修改来实现。,填充步骤：,1 确定区域内一个填充位置。,2 查询图案位图的对应位置。,图案表的对应位置为1,其余,透明方式 填充图案,不透明方式 填充图案,图案位图对应位置为1,图案位图对应位置为0,把图案原点与填充区域边界或内部的某点对齐；,对齐方式,把图案原点与填充区域外部的某点对齐,第一种方式填充的图案，将随着区域的移动而跟着移动，看起来很自然。,第二种方法比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果，但当区域移动时，图案不会跟着移动。结果是区域内的图案变了,四、线宽与线型的处理,1、画笔或画刷的选择,在图形处理软件中，可通过选择设置笔和刷的方式来画线。 这种类型的选项包括形状、尺寸和式样（画笔或画刷的图案）。,线刷子 方形刷子 圆形刷子 棱形刷子,线宽的选择和实现取决于输出设备的能力,2、线宽的处理,光栅设备（视频监视器） 用相邻的平行线进行显示,矢量设备（笔式绘图仪） 可能需要更换画笔,光栅实现 标准线宽是用像Bresenham算法那样在每个放样位置处用一个象素来生成。 其它线宽是作为标准线的正整数倍通过沿相邻平行线路径画额外的象素而显示的。,常用的线宽的处理方法有 重复像素法 移动画笔法 区域填充法,（1）重复像素法,对扫描转换算法的内循环作修改， 将原来绘制单个像素的语句改写 成以该像素为中心绘制水平或垂直 排列的多个像素，即可产生具有一 定线宽的线条。,当斜率的绝对值小于1，即线段接近水平时，绘制垂直排列的多个像素；,当斜率的绝对值大于1，即线段接近垂直时，绘制水平排列的多个像素。,对于圆，在第一象限的圆弧，第一卦限部分在垂直方向重复像素，第二卦限部分在水平方向重复像素。,重复像素法的特点：,1、算法简单、执行效率高，适合比较小的线宽；,2、当线宽较大时，用该方法有比较明显的缺点：,如用该方法绘制线段时，两个端点处总是水平的或垂直的，线段不自然；,当接近水平的线段和接近垂直的线段会聚于一点时，该点有缺口；,线条的粗细（线条垂直方向上线条边界之间的距离）在水平方向上和垂直方向上不变，在45时，线条的粗细只1/ ，线条的粗细与所在位置的切线方向一致，圆弧上45最细。,（2）移动画笔法,绘制线条时，可以选择不同形状的画笔。画笔的形状一般存贮在 一个正方形0、1位图中，对扫描转换算法的内循环作修改，将原来绘制单个像素的语句改成以该像素为中心绘制画笔位图，即可产生具有一定线宽的线条。常用画笔的形状有矩形、圆形等。（如前面所说的笔和刷子）,移动画笔法的特点：,用正方形画笔产生的线条比在水平或垂直方向重复像素产生的线条粗；两端点处总是方的； 当线条水平或垂直时，线条粗细一致为w，为45时是 w；圆弧时，45处最粗。,（3）区域填充法 根据线条的宽度，计算出线条的外轮廓，再用区域填充的方法，产生具有一定线宽的线条。采用区域填充的方法可以方便地产生两端粗细不同的线条。为了改善线条端点处的形状，在线条端点处加上线帽（Line Cap）。,平帽butt cap - 线条端点处的宽度方向与线条在端点处的切线方向垂直；,圆帽round cap - 在平帽的基础上再加两个半圆；,突方帽projecting sauare cap - 线条向两端延伸后的平帽。,平滑连接解决第三个问题,粗折线连接处，其水平段变成垂直段时会留下间隙;,连接的类型 斜角连接 miter join 圆连接 round join 斜切连接 bevel join,斜角连接 通过延伸两条线的外边界直