四讲二维图形填充ppt课件.ppt
《四讲二维图形填充ppt课件.ppt》由会员分享,可在线阅读,更多相关《四讲二维图形填充ppt课件.ppt(34页珍藏版)》请在三一文库上搜索。
1、,第四讲:二维图形填充,内容摘要,区域填充 有序边表算法 边填充算法 边标志算法 种子填充算法 圆域的填充 线宽与线型的处理 直线线宽的处理(笔型:线、方形) 圆弧线宽的处理(笔型:线、方形) 线型的处理,内容摘要,字符 矢量字符 点阵字符 字型技术 字符裁剪 反走样基础 提高分辩率 简单的区域反走样算法 卷积积分与反走样算法 半色调技术,有序边表算法,一般多边形的填充过程,对于一条扫描线Y值,可以分为四个步骤: 求交点X:计算扫描线与多边形各边的交点X的值; 排序:把所有相交点x按递增顺序进行排序; 交点配对:第一个与第二个,第三个与第四个等等。每对交点就代表扫描线与多边形的一个相交区间;
2、区间填色:把这些相交区间内的象素置成多边形色,把相交区间外的象素置成背景色。 特殊顶点处理: P1、P3情况:相同交点取1个; P2、P5情况:相同交点取2个; P4、P6情况:相同交点取0个; (下闭上开原则,防止填充扩大化),填充扩大化问题的解决,采用下闭上开、左闭右开原则,防止填充扩大化。 例如填充左下角为(1,1),右上角为(3,3)的区域,得到的图形如图所示九个象素被点亮,而实际区域应是黄区所示。 采取的措施:在具体实现时,只要对扫描线与多边形的相交区间取“左闭右开”。在上述讨论中,当扫描线与多边形顶点相交时,所使用的交点取舍的方法,保证了多边形的“下闭上开”,丢弃上方水平边以及上方
3、非水平边上作为局部最高点的顶点。,如左图,活性边与活性边表处理方法,一个多边形与若干扫描线。,为了计算每条扫描线与多边形各边的交点,最简单的方法是把多边形的所有边放在一个表中。在处理每条扫描线时,按顺序从表中取出所有的边,分别与扫描线求交点。这样处理效率很低。这是因为一条扫描线往往只与少数几条边相交,甚至与整个多边形都不相交。若在处理每条扫描线时,不分青红皂白地把所有边都拿来与扫描线求交点,则其中绝大多数都是徒劳无用的。如果采用活性边表,则可减少许多计算。 扫描线依次变化为1,2,3,4,5,6,7,8,. x是边与当前扫描线的交点; x是该边从当前扫描线到下一扫描线之间x增量; ymax是边
4、所交的最高扫描线号。 在上述的交点x坐标更新和新边插入之前,必须把那些与当前扫描线相交,而与下一条扫描线不再相交的边,从活性边表(AET)中删除出去。,新边表处理方法,为了方便活性边表的建立与更新,为每一条扫描线建立一个新边表,在该扫描线第一次出现的边保留与此。也就是说,若某边的较低端点为ymin,则该边就放在扫描线ymin的新边表中。这样,当按扫描线号从小到大顺序处理扫描线时,该边在该扫描线第一次出现。新边表的每个结点存放对应边的初始信息,比如该扫描线与该边的初始交点x(即较低端点的x值),x的增量x,以及该边的最大y值ymax。图3-18所示,为左图中各扫描线的新边表。区间填充需设置一个布
5、尔变量b, 在多边形内b为真, 在多边形外b为假,b的初值为假。当指针从活性边表中第一个结点(交点)到最后一个结点遍历一次时,每访问一个结点,把b取反一次。若b为真,则把从当前结点的x值开始到下一结点的x值结束的左闭右开区间,用多边形色填充。利用区间连贯性,即同一区间上的象素取同一颜色属性。 多边形外的点用背景色填充。,边填充算法,基本思想:对于每一条扫描线和每一条多边形边的交点(xi,yi),将该扫描线上交点右方的所有象素取补。对多边形的每条边均作此处理,多边形的顺序随意。右图为采用最简单的边填充算法填充一个多边形的示意图。 边填充算法最适用于具有帧缓冲存储器的图形系统,按任意顺序处理的边。
6、,在处理每条边时,仅访问与该边相交的扫描线上交点右方的象素。当所有的边都被处理之后,按扫描线顺序读出帧缓冲存储器的内容,送入显示设备。可见本算法的优点是简单,缺点是对于复杂图形,每一象素可能被访问多次,输入输出的量比有序边表算法大得多。为了减少边填充算法访问象素的次数,可引入栅栏。所谓栅栏指的是一条与扫描线垂直的直线,栅栏位置通常取过多边形 顶点、且把多边形分为左右两半。,栅栏填充算法,基本思想是:当扫描线与多边形边有交点,就将交点与栅栏之间的象素取补。若交点位于栅栏左边,则将交点之右,栅栏之左的所有象素取补;若交点位于栅栏右边,则将栅栏之右,交点之左的象素取补。如图所示,为采用栅栏填充算法填
7、充多边形的示意图。,栅栏填充算法只是减少了被重复访问的象素的数目,但仍有一些象素会被重复访问。从图中很容易看出这一点。下面介绍的边标志算法进一步改进了栅栏填充算法,使得算法对每个象素仅访问一次。算法示意图如下页所示。,边标志算法,基本思想是:分为两步骤,第一步,对多边形的每条边进行直线扫描变换,亦即对多边形边界所经过的象素打上标志;第二步,填充。对每条与多边形相交的扫描线,依从左到右顺序,逐个访问该扫描线上象素。使用一个布尔量inside来指示当前点的状态,若点在多边形内,则inside为真。若点在多边形外,则inside为假。inside的初始值为假,每当访问到象素为被打上边标志的点时,就把
8、inside取反。对未打标志的象素,inside不变。若访问象素时,inside为真,则把该象素置为多边形色。用软件实现时,有序边表算法与边标志算法的执行速度几乎相同,但由于在帧缓冲存储器中应用边标志算法时,不必建立、维护边表以及对它进行排序,所以边标志算法更适合于硬件实现,这时它的执行速度比有序边表算法快到一至两个数量级。,种子填充算法的连通区域,基本思想是前面讨论的填充算法都是按扫描线的顺序进行象素点的填充的,种子填充算法是根据已知的一个多边形区域内部的一个象素点来找到区域内其它的象素点进行填充的。 前面讨论的填充算法都是按扫描线的顺序进行象素点的填充的,种子填充算法是根据已知的一个多边形
9、区域内部的一个象素点来找到区域内其它的象素点进行填充的。,一般都采用边界定义区域,即边界区域上所有象素被置为特定值,而区域内部所有的象素均不取这个值。区域可以分为四连通或八连通两种,如果区域是四连通的,那么区域内每一个象素可以通过四个方向(上、下、左、右)组合到达,而对八连通区域,区域内的每个象素可通过上、下、左、右以及四个对角线方向的移动组合到达。 八连通算法可以填充四连通区域,而四连通算法不能填充八连通区域。两类连通区域如图所示。图 (b)中八连通区域的子区域是四连通的,然而从一个子区域到另一个子区域需用八连通算法,若每个子区域看成是分离的二个四连通区域,并且每个区域填上不同的色彩值,如果
10、用八连通算法会让两个区域均被错误地填上同样的色彩。下面仅讨论四向连通算法,只要把搜索方向从四个该为八个,即可得到八向算法。,简单种子填充算法,简单的种子填充算法如下: (1) 将种子象素压入栈中; (2)当栈非空时 从栈中弹出一个象素; 将该象素置成所要求的色彩值; 检查每个与当前象素邻接的四连通象素是否是边界色或已置成所要求的色彩值,若是则返回(2),否则将该象素压入栈中回到(2)。 例 简单的种子填充算法。 多边形由顶点P0、P1、P2、P3、P4构成,见图3-23。P0(1,5)、P1(5,5) 、P2(7,3) 、P3(7,1) 、P4(1,1),可设种子点为(3,3);四连通的组合方
11、向是上、下、左、,右。初始时栈中只有(3,3)象素;弹出(3,3),由于该象素未置成色彩值且也不是边界色,故填色彩值;同时将(3,4) (3,2) (2,3) 及(4,3)压入栈中;栈中有四个元素;弹出(4,3)并置上要求的色彩值,再将(4,4) (4,2) (5,3)压入栈中;栈中有6个元素;依次类推,象素被选中并填充的次序如图中箭头所示。当栈为空时,算法终止。分析该算法不难发现,在进行填充过程中堆栈会变得很大,而且在堆栈中还常常包含有一些重复的和不必要的信息。为此提出了扫描线种子填充算法。,(3,3),弹出(3,3),(4,3) (2,3) (3,2) (3,4),弹出(4,3) (2,3
12、) (3,2) (3,4),(5,3) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(5,3) (4,2) (4,4) (2,3) (3,2) (3,4),(6,3) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(6,3) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(6,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(6,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(5,2) (5,2) (5,4
13、) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(5,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(4,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(4,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(3,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(3,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(2,2) (5,2) (5,4) (4,2
14、) (4,4) (2,3) (3,2) (3,4),弹出(2,2) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(2,3) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(2,3) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(2,4) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(2,4) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(3,4) (5,2) (5,4) (4,2) (4,4
15、) (2,3) (3,2) (3,4),弹出(3,4) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(4,4) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(4,4) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),(5,4) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),弹出(5,4) (5,2) (5,4) (4,2) (4,4) (2,3) (3,2) (3,4),扫描线种子填充算法,所谓扫描线种子填充算法,是在任意不间断扫描线区间
16、中只取一个种子象素。不间断区间即指在一条扫描线上一组相邻的元素。 算法可分为以下几步: 1) 从包含种子象素的栈中弹出种子象素; 2)沿着扫描线对种子象素进行填充,直到遇到边界象素为止,这样就填充了种子所在的扫描线中的元素; 3)区间内最左、最右元素为Xleft,Xright; 则在Xleft X Xright区间中检查与当前扫描线相邻的上、下两条扫描线是否全为边界象素或已填充过的象素。若不是,则对于Xleft X Xrigh,把与当前扫描线相邻的上、下两条扫描线中该区间的最右象素作为种子压入栈中。 算法结束条件为栈空。此算法适用于用边界定义的区域。,圆域的填充,上面所讨论的多边形区域的填充原
17、理也可以推广到圆域的填充。对每条扫描线,先计算它与圆域的相交区间,再把区间内象素用指定颜色填充。,在实际应用中,除了使用单象素宽的线条,还经常使用指定线宽和线型的直线与弧线。欲产生具有宽度的线,可以顺着扫描所生成的单象素线条轨迹,移动一把具有一定宽度的“刷子”来获得。“刷子”的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接地产生有宽度的线。假设直线斜率在1,1之间,这里可以把刷子置成垂直方向,刷子的中点对准直线一端点,然后让刷子中心往直线的另一端移动,即可“刷出“具有一定宽度的线。当直线斜率不在1,1之间时,把刷子置成水平方向。具体实现线刷子时,只要对直线扫描变换算法的内循环稍作
18、修改即可。例如,当直线斜率在1,1之间时,把每步迭代所得的点的上下方半线宽之内的象素全部置成直线颜色。如右上图所示为线宽是5个象素的情形。线刷子的优点是算法简单、效率高。但是,线的始末端总是水平或垂直的。因此,当线宽较大时,看起来很不自然。当比较接近水平的线与比较接近垂直的线汇合时,汇合处外角将有缺口,如左上图所示。斜线与水平(或垂直)线不一样粗。对于水平线或垂直线,刷子与线条垂直,因而最粗。其粗细与指定线宽相等。而对于45斜线,刷子与线条成45角,粗细仅为指定线宽的1/ 2 0.7倍。,直线线宽的处理 线刷子原理,为用正方形刷子绘制的具有宽度的线条。用方形刷子所得的线条比用线刷子所绘制的线条
19、要粗一些。与线刷子类似,用方刷子绘制的线条始末端也是水平或垂直的,且线宽与线条方向有关。与线刷子的情形相反,对于水平线与垂直线,线宽最小,而对于斜率为1的线条,线宽最大,为垂直(水平)的2 倍。实现正方形刷子最简单的办法是,把方形中心对准单象素宽的线条上各个象素,并把方形内的象素全部置成线条颜色。这种简单方法将会重复地写象素。这是因为对应于相邻象素的方形一般会重迭。为了避免重复写象素,可以采用与活性边表类似的技术。,方形刷子的原理,线刷子还有另一个问题:当线宽为偶数个象素时,用上述方法绘制的线条要么粗一个象素,要么细一个象素。为了生成有宽度的线,还可以用方形的刷子,把边宽为指定线宽的正方形的中
20、心沿直线作平行移动,即可获得具有线宽的线条,如图所示,方刷子的活性边表技术,为每条扫描线建一个表,存放该扫描线与线条的相交区间左右端点位置。在每个象素使用方形刷子时,用该方形与各扫描线的相交区间端点坐标去更新原表内端点数据,右图为刷子移动的相邻两步与有关扫描线的临时数据结构所保存的对应于各步的区间端点坐标。 生成具有宽度的线条还可以采用区域填充的算法。先算出线条各角点,再用直线段把相邻角点连接起,来,最后调用多边形填充算法把所得的四边形进行填色,即得到具有宽度的线条。用这种方法还可以生成两端粗细不一样的线条,圆弧线宽的处理(笔),为了生成具有宽度的圆弧,可采用与直线情形类似的方法,当采用线刷子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二维 图形 填充 ppt 课件
链接地址:https://www.31doc.com/p-3214164.html