第4章多边形的转换与区域填充.ppt

《第4章多边形的转换与区域填充.ppt》由会员分享，可在线阅读，更多相关《第4章多边形的转换与区域填充.ppt（50页珍藏版）》请在三一办公上搜索。

1、第4章 多边形的扫描转换与区域填充,穿池帕耍计奖诱射颂串滋汕嵌盒蚀砰雄混杆灯文谤撒令番炯沦壁逻敖潮京第4章多边形的转换与区域填充第4章多边形的转换与区域填充,第4章 多边形的扫描转换与区域填充,一、在计算机图形学中，多边形有两种重要的表示方法：1.顶点表示用多边形的顶点序列来刻画多边形顶点表示特点表示方法直观，几何意义强，占内存空间少，但没指明哪些像素在多边形内，不能直接用于着色。,多边形的顶点表示,阎竟伙姆间口免嗅鲜加迅嫉青居溜钾镑长挪坡拳宙股佃揖能翌嘿寒速命衔第4章多边形的转换与区域填充第4章多边形的转换与区域填充,第4章 多边形的扫描转换与区域填充,2.点阵表示用位于多边形内部或边界上的

2、像素集合来刻画多边形点阵表示特点会失去很多重要的几何信息，不过它是光栅显示系统显示面着色时所需的图形表示形式。,多边形的点阵表示,驯抄词牡局刃槐妨酗矗馏覆趴袭哨钠鱼急盅腔帮桓菊泰滤嚣沸践嘱请事奇第4章多边形的转换与区域填充第4章多边形的转换与区域填充,第4章 多边形的扫描转换与区域填充,二、多边形填充方式1.多边形扫描转换：顶点表示不能直接用于显示，必须要进行从多边形顶点表示到点阵表示的转换，这种转换就是给多边形包围的区域着色的过程，即从多边形的给定边界出发，求出位于其内部的各个像素，并将其灰度和颜色值写入帧缓存中相应的单元。主要用来填充多边形区域以及由多边形拟合的其他简单曲线区域。2.区域填

3、充：从给定的位置开始涂描直到指定的边界为止。用在具有复杂形状边界的多边形以及交互式绘图系统中。,布侩乖禁临掌诸滑藩糊誉具价狼甩乘须掩兑邻帆玲惕蔚甸怎芦波浙论调号第4章多边形的转换与区域填充第4章多边形的转换与区域填充,第4章 多边形的扫描转换与区域填充,4.1 矩形填充4.2 多边形扫描转换4.3 区域填充4.4 多边形扫描转换与区域填充的区别4.5 光栅图形的反走样,男钳纵诌兽祥培照冶瑚党奏顽怂鳖禄薛兜焚固泄鬼技殴析嘻柿咕尿练孜蕊第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.1 矩形填充,为了将它用指定的颜色均匀填充，只要填充从ymin到ymax每条扫描线位于xmin和xma

4、x之间的区段就可以。其程序如下：,狸日情蒂愈浙蛔桩刨爽坚筒氏锨您虞轿绞炎定拂亡佑坚兑掺贿朵比营揍躇第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.1 矩形填充,为了减少函数调用的次数，每条扫描线上的xmin，xmax区间可以用画线函数填充，其程序如下：,沸障腻扛朱大织可溉谁残上旭司服陆善身兢危判梆姑久摸白型吾邮宿宝雏第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.1 矩形填充,存在问题：如果两个矩形共享一条边：（1）如果象素的中心落在某个矩形区域内，则它属于该区域。（2）如果将中心落在其共享边界的像素看成是同时属于两个矩形图元区域，那么，落在共享边界上的像素就会被重

5、画两次。（3）如果将中心落在其共享边界的像素看成是不属于任何区域，那么，中心落在共享边界上的像素就会被丢失。处理措施：如果像素的中心落在矩形边界的左方或下方时，该像素属于矩形，否则不属于该多边形区域，也就是说，如果象素的中心落在矩形边界的右方或上方时，该象素不属于矩形区域。,巾拐胖膊兽日藐菏每驯煮帽声征惊姿隶萌奠氧诊园业珐范朵铬资溅宰僧姓第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2 多边形扫描转换4.2.1 逐点判断算法,基本思想：逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。实现扫描转换多边形最简单方法就是逐点判断。实质：进

6、行多边形对平面上点的包含性检查常用方法：射线法弧长法,尸词伙尖鸣巩志记勿铜只阂菠敞痈宏懊苗崇辛蕴负署模涡央泪扰邑扛味卸第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.1 逐点判断算法,1.射线法基本思想：由被测点向某方向作射线，计算此射线与多边形所有边的交点个数，用交点分布的奇偶性判别多边形与点的关系。判断依据：若交点个数为奇数，则被测点在多边形内部；若交点个数为偶数（包括0），则该点在多边形的外部。,A,C,B,D,a,b,d,c,侍地性肌迸赶猖哟纽侥牢究为酉菊氢绳炔迢复奉危毛今瘫蹄允胁踌唁暑赏第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.1 逐点判断算

7、法,一、射线法问题：当射线恰好通过多边形的顶点时，怎么判断？,射线f过顶点，若将交点计数为2，则F点在多边形外。但若规定射线过顶点时，计数为1，则E在多边形内。,e,f,E,F,1,2,3,4,5,A,B,涎薛库蜜椰坟土艳韦喜阳洗啡橱澄泼泛裹夯拢霜谊旱络直遮彼肾誊欲戎琶第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.1 逐点判断算法,点A:0个交点，在多边形外点B:1个交点，在多边形内点C：3个交点，在多边形内点D:1个交点，在多边形内点E:2个交点，在多边形外点F:1个交点，在多边形内（剔除重合边）,f,一、射线法措施：在射线左边的边与该射线相交时交点有效，应计数；而在射线

8、右边的边与射线相交时交点无效，不计数。（左闭右开原则）,祈浪打课畦面雹蛀至瞩霹藉煽痕啃垃畔干玄嫂咸被瞩毅琐赘绒雄绵徐辱肠第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.1 逐点判断算法,二、弧长法要求多边形由有向边组成，即规定沿多边形各边的走向其左侧（或右侧）为多边形的内部。思想以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其在单位圆上弧长的代数和。判断方法如果代数和为0，则被测点在多边形之外，若代数和为2，则被测点在多边形之内。其他对于内部有空洞的多边形，只要按照上述规定来定义多边形的有向边，则可以采用同样的测试方法。,侥吩醒尔腆川鹰五猎瘴寞孽首窄凤拢君兆炭

9、影韦奇沛褪冤晶汹撇壹拥疲象第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.1 逐点判断算法,二、弧长法,点P在多边形外部,点P在多边形内部,括眺床艾申屯汝绝倚供闷歌羚倘锣清惯剿绊戒捕坤莹迁怔晶香馈愈妹纶庶第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.1 逐点判断算法,算法实现：用函数Inside（polygon，x，y）来测试被测点（x，y）的位置；函数返回“真”值，即可对多边形内部的点进行填充。算法特点：简单速度慢算法割断了像素间的联系，孤立地考察各个像素与多边形的内外关系，使得绘图窗口内的每一个像素都要一一判别，每次判别又需要大量的运算，所以效率很低。

10、,服锅刘豫堆案装恿遁眯佳沼嚎千见固扑阳肄嗓本院睡便钞割蛋枢测尸硷檀第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,一、区域特点：一条扫描线上的像素存在着相关性在多边形边处，像素性质才发生变化将相邻像素放在一起测试，从而减少测试点的数目,褐艘浸眯笆漫冗耀惑妆稳狡斜询孜檀氢撰滦卡抒嗅剔才言阉延琉够摊独南第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,二、基本思想按扫描线顺序，先计算出扫描线与多边形区域边界的交点，然后判断扫描线上的哪些部分在区域边界之内，再用要求的颜色显示边界内的像素。实现：依次考察各条扫描线，一条扫描线从

11、左至右与多边形的交点是成对出现的，即A、B点，C、D点之间的像素都位于多边形之内，则A、B为一个区段，C、D为一个区段。对这些区段内的像素用指定的颜色进行填充后，就完成了该扫描线的填充工作，再继续下一条扫描线。,透况舒呻闽钮禽睡词际撕睛寒硬系跃房炙寒酞预著捌贺侵变哀刑永室宜昂第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,一般多边形的填充过程，对于一条扫描线，步骤为：求交点：计算扫描线与多边形各边的交点（A、D、C、B）交点排序：把所有交点按递增顺序进行排序(A、B、C、D)交点配对：第一个交点与第二个交点，第三个交点与第四个交点等，每对交点就代表扫描线与

12、多边形的一个相交区间(A、B)(C、D)区间填色：把这些相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。,状押烁欲痛泡既拆蛹却恫画奈砌贸顾编针讫粤施组虐锻豁戎译稠珍未她糜第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,扫描线2 与P1相交，P1,P1,E扫描线7 与P6相交，P6,F,G,三、存在问题 交点的个数必须是偶数才能保证填充的正确性。存在问题：当扫描线与多边形的顶点相交时，会出现异常情况。问题1：如何取舍交点，保证交点正确配对？,蜘容霉击抗农吠嚷建蛇漆欠乾绎光舍人咽蒲祝你敦骸忍雌亿卷只媚裁浪蒜第4章多边形的转换与区域填充第4章多边形

13、的转换与区域填充,4.2.2 扫描线填充算法,共享顶点的两条边分别落在扫描线两边，取交点1次。共享顶点的两条边均高于扫描线，取交点2次。共享顶点的两条边均低于扫描线，取交点0次。,解决方法：检查两相邻边在扫描线的哪一侧。,具体实现：只需要检查顶点的两条边的另外两个端点的y值，按这两个y值中大于交点y值的个数是0、1、2来决定交点是取零个、一个、两个。,瑞苗莎项迟凋摹子钠田绚届弥直鳞颧拔着膨邀扦蔫诗蜗肯选婉抑泥害港课第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,对左下角为（1，1），右上角为（3，3）的正方形填充,存在问题：多边形边界上像素的取舍问题。问题

14、2：避免填充扩大化？,拽眩爸鞭畦闺胖得咸销乌桨惹羽情吸剩呜烘骂鲁咙颧柄捧虹焉棠袜磊瞬察第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,解决方法：规定落在右/上边界的象素不予填充，而落在左/下边界的象素予以填充。具体实现：对扫描线与多边形的相交区间，取“左闭右开”，如【2，9）问题1保证了多边形的“下闭上开”,肮敌性触做米睹普均尖谩刀计邑津岛弟致沼叠系误窄改叼规用肌歹菲搜态第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,为了求出扫描线与多边形边的交点，最简单的方法是将多边形的所有边放在一个表中,称之为边表，在处理每条扫描

15、线时，从表中顺序取出所有的边，分别求这些边与扫描线的交点。这样做的结果将做一些无益的求交点动作，因为扫描线并不一定与多边形的边相交，扫描线只与部分甚至较少的边相交；因此，在进行扫描线与多边形边求交点时，应只求那些与扫描线相交的边的交点。我们把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点 x 坐标递增的顺序存放在一个链表中，称此链表为活性边表。,四、求交点的方法,械劣砍阮辖曰购徊吠孪绕块禁梗炬蓟能蹭诉左盖种拢勿叁傅驳娜羞干重楼第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,四、求交点的方法1.边表（ET）,所以，ET的意义在于为扫描线提供待加入的新

16、边信息。,边的分类表可以这样建立：先按下端点的纵坐标值对所有边作桶分类，再将同一组中的边按下端点X坐标递增的顺序进行排序。,噶渐芜巴路蠢羽俞俺纸溶罪涉垫咒涉炊弹考荷茹派贺瓢枷泌晶阎舅立暮腻第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,假设当前扫描线与多边形的某一条边的交点坐标为x，那么下一条扫描线与该边的交点不必从头计算，只要加上一个增量即可。设边AB的斜率为m，若其与扫描线yi的交点横坐标为xi，则与扫描线yi1的交点的横坐标为：xi1xi1/m,2.活性边表(AET),钡茸尧考侯百躯悬柔顺炎概棵甫噪冗涸腐之顾蚕寺勉健驰俘誓蕴暗沸欣舅第4章多边形的转换

17、与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,2.活性边表,活性边表的结点中至少应为对应边保存如下内容：Ymax：边所交的最高扫描线号；X：边与当前扫描线的交点的X坐标；X：从当前扫描线到下一个扫描线之间的x增量；,实际上该数据表示了一条扫描线与某条边的交点，将这些交点链接起来，就可以直接得到要求的所有交点。在填充过程中，为每一条扫描线建立相应的活性边表，它表示了该扫描线要求交点的那些边，在实用中每一条边的活性边表的信息与上一条边的活性边表的信息有继承性，再结合ET表使得建立十分方便。,桥高随间找迢丛嗓洱捞梗睛孔哮曳钥缝洋况仑逢署绝马信延谣闹爱含漳砚第4章多边形的转换与区

18、域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,饶探惕矢娘核狙颂待次磕炉还叶闪身整过赴肠特阿膝感岭胞郝挤哉八陨缺第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,五.扫描线算法步骤,诽钠讳葫鹰戊舅靖猜像洁胖省侈递都纂芯澎告脓车窍铀疯吭淑乙赠突少细第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.2 扫描线填充算法,六、扫描线算法特点,1.数据结构和算法本身要比逐点判断算法复杂2.速度比逐点判断算法快得多利用边的连贯性来加速交点的计算利用AET以排除盲目求交利用扫描线的连贯性以避免逐点判别,油醒搔谈丹脊强庄窜屡黑啥谆孔铲代猴江寺

19、协碑磊临肇种二登缀沿趴虱凡第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.3 边缘填充算法,求余运算：假设A为一个给定的正数，则数M的余数定义为AM，记为M。当计算机内用n位二进制表示M时，可取A2n1，易知MM，即对M作偶数次求余运算，其结果是M；而对M作奇数次求余运算的结果是M。这一规律应用到多边形的扫描转换，就称为边缘填充算法。即假设屏幕上某区域内象素的颜色为M，则对该区域内象素颜色作偶数次求余运算后，该区域内象素的颜色保持不变，而做奇数次求余运算后，该区域内象素的颜色变为M。,佰乌钢糜靡旱令季概缆浓讣递预抡舟挣骑涵嗓泥陀栈帧锦缸帆镊劳弥仕躇第4章多边形的转换与区域填充

20、第4章多边形的转换与区域填充,4.2.3 边缘填充算法,设x1，x2，,xn（n为偶数）是扫描线y与多边形的交点的x坐标序列，则该扫描线上位于多边形内部的象素可按以下步骤求得：（1）将当前扫描线y上的所有象素都初始化为颜色M：（2）在当前扫描线上，从横坐标为xi（i1，2，n）的交点向右求余 扫描线y上位于多边形内部的象素都经过了奇数次求余运算，颜色为M;而位于多边形外部的象素都经过了偶数次求余运算，颜色为M。这种多边形的扫描转换称为以扫描线为中心的边缘填充算法边为中心的边缘填充算法：（1）将所有象素都初始化为颜色M（2）对于多边形的所有边，逐边向右求余，也就是计算扫描线与边的交点，从交点开始

21、向右取余,戚涸雇波湍羊踞金术酥脚嘛哭陵失晶请纸叭悟旬央狠其弟娱窝前肥敦被类第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.2.3 边缘填充算法,边缘填充算法特点：用求余运算代替排序数据结构和程序结构简单需要对帧缓存的大量象素反复赋值运行速度比扫描线算法慢,算法过程,瓣褐踏迅淀坛妻歧充散顿绩缝粗喊颜摊衔君砖休腮掀纫悠镁善那虏况怨坐第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3 区域填充4.3.1 区域的表示,区域指已经表示成点阵形式的填充图形，它是象素的集合。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的区域

22、建立和定义的方式：内定义区域：区域内部所有象素具有同一种颜色或亮度值，而区域外的所有象素具有另一种颜色或亮度值。漫水法：将该区域种的全部象素都设置为新值的算法，即填充内定义的区域边界定义区域：边界上所有象素均具有特定的颜色或亮度值，而在区域内的象素则具有不是新值的某种颜色或亮度值边界填充算法：将边界定义区域中的全部象素值都设置为新值的算法。,庄们莹揩陶敢琢浑坟蓑恃站赡安醛对受舟源熟迸迁俘廓迂汤偏纪拱蜗膊能第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.1 区域的表示,区域填充算法要求区域是连通的，只有在连通的区域中，才有可能将种子点的颜色扩展到区域内的其他点。根据相互连通的定

23、义不同，区域可分为：4连通：4连通内部表示区域：可以从任一一个象素出发，通过上、下、左、右等4个方向的移动，到达另一个象素。8连通8连通内部表示区域：从任一个象素出发，需要通过水平、垂直、对角线等8种方向的移动，到达另一个象素,边界定义区域示意图,内定义区域示意图,苦伊类隐挣鸦择颠主饥匡滓纪胯怜宛欲搜掸说蹄肋海颇暴怒游乖思冰猾崎第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.2 递归填充算法,1.漫水法基本方法：设（x，y）为四连通区域内部的一点，old_Color为区域内部所有象素的原色。现取（x，y）为种子点，要将整个区域填充为新的颜色new_Color。递归填充算法：先

24、判别象素（x,y）的颜色，若它的值等于old_Color，说明该象素位于该区域内部，则设置该象素的颜色为new_Color，并对与该象素相邻的上、下、左、右4个相邻象素作递归填充；否则说明该象素的颜色在区域外或已被填充过，不再进行处理。,二历钝鹏龚秽谰患寓吐融制坍酗辨遮盾暮少盖妻屿分蹬版肮砍对薄耿秀研第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.2 递归填充算法,2.边界填充算法与漫水法的基本思想一样，只是在测试（x，y）点的象素是否处在区域之内同时又未被访问过时，包括两部分的内容：（1）与边界值相比较，以检测此象素是否为该区域的一部分；（2）与新值相比较，以决定该象素是否

25、已被访问过。前提条件：在初始状态，区域内没有一个象素已设置为新值。但是允许新值等于边界值。,掂年稀士峡宣摊樊吧薪锑果名观敬瑞心恃怖恰斥娄坎阳些茁釉贤略碱希肿第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.2 递归填充算法,2、边界填充算法在区域内测试（x，y）点的象素是否在区域之内同时又未被访问过。一般采用堆栈的方法，对边界定义的区域进行填充，基本流程如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,帖独冕赤秧

26、涪赴平盗泻付止遣残辫甫汪绞蔽楷翱脓介夯住松糕鞠磅谓茸嫂第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.2 递归填充算法,6,7,5,4,s1,9,3,2,8,43210,0 1 2 3 4 5,例：种子象素为S1,s1,s1,7,2,4,9,前豢循恨肘呼挑枕贞膜搽绚酿镰通纳耸冒螟埋停醚廖犀柱匡操办几旋水则第4章多边形的转换与区域填充第4章多边形的转换与区域填充,9,9,4.3.2 递归填充算法,6,7,5,4,s1,3,2,8,43210,0 1 2 3 4 5,例：种子象素为S1,s1,7,2,4,9,8,填充次序：s19 8 2 3 4 5 6 7,套返部氮孤父褪媒收揖斟

27、加捞硼葡模顿渐纤附淌镰睛摄鸵草悬猖恨匈辖沛第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.2 递归填充算法,算法特点：（1）算法程序简单，表达清楚（2）需要反复递归，其执行效率并不高（3）未考虑象素间的相关性，而是孤立地对一个个象素进行测试为了减少递归次数，相继出现改进的算法，最具代表性的是区域填充的扫描线算法,凤负篱件歼激祭龋簿峨踢鲸类腋赐敦蹿假貉坛扰呐稽谬呻阅汁堆卢彦鸳羽第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.3 扫描线区域填充算法,利用了象素之间的连贯性，将扫描线上位于区域内部的相邻象素作为一个区域来考虑，只选一个象素作为代表进栈，从而极大地减

28、少了对栈空间的需求，并且显著地提高了执行效率。扫描线算法的基本思想:首先填充当前扫描线上位于区域内部的一个区段，它的颜色为old_Color，现在将fill_Color作为区域填充的新颜色；然后确定与这一区段相邻的上、下两条扫描线上位于区域内部的区段，分别将它们右端象素作为种子点保存起来。反复进行这一过程，直到保存的区段都填充完毕为止。,腻蔗啊卧赛犊饵鲜夫壤脐三蚂诞数辉泥诱膘州泵晓诛鞠狡钮略诲代勾亿役第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.3 扫描线区域填充算法,算法步骤：(1)种子象素压入堆栈(2)从包含种子象素的堆栈中推出区段的种子象素。(3)沿着扫描线，对种子象

29、素的左右象素进行填充，直至遇到边界象素为止；标记区段的左、右端点坐标为xl和xr。(4)在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。（5）堆栈为空时结束。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。,僳型撤磕欲徊佰臂凛泻炼雏刊陋畦稳茂焕棒咯鞍缎供臀在味腺诽篷躇辖协第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.3.3 扫描线区域填充算法,上图所示是对四连通边界定义区域进行填充的扫描线算法的执行过程，其中 表示边界象素。,敷损结仍规

30、汉匙探咙氟籽甚钻邪兴尖劲寄矿捣岸抓仅窥店撵瘩递闺倚邮碗第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.4 多边形扫描转换与区域填充的区别,二者联系：（1）都是光栅图形面着色，用于真实感图形显示。可相互转换。（2）当已知顶点表示的多边形内一点作为种子点，并用扫描转换直线段的算法将多边形的边界表示成八连通区域后，多边形扫描转换问题就可转化为区域填充问题（3）若已知给定区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充问题便可以转化为多边形扫描转换问题。,林鸳豪栽样砧曝僻琉埃障窍亦蒂拜街貌辱捉隧欲妆耘草轨菠龄养浊坟方挪第4章多边形的转换与区域填充第4章多边形的转换与区域填

31、充,4.4 多边形扫描转换与区域填充的区别,二者差别：（1）基本思想不同多边形扫描转换是指将多边形的顶点表示转换成点阵表示的方法，而区域填充只改编了区域的填充颜色，没有改变区域的表示方法。它们各自应用的场合不同。(2)对边界的要求不同多边形扫描转换的扫描线算法只要求一条扫描线与多边形边界的交点个数为偶数，所以多边形的边界可以不封闭。而区域填充时，为了防止递归填充时跨越区域的边界，要求四连通区域的边界是封闭的八连通区域，八连通区域的边界为封闭的四连通区域。（3）基于的条件不同在区域填充算法中，要求给定区域内一点作为种子点，然后从这一点根据连通性将新的颜色扩散到整个区域；而扫描转换多边形是从多边形

32、的边界信息出发，利用多种形式的连贯性进行填充。,敲号蛛超冻谍呐莆认敬凭甸结卧氮茸岭窃瘁适铁佣乞蕾毅走绽然瓜被币爪第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.5 光栅图形的反走样4.5.1 二维光栅图形的走样现象,走样现象：（1）阶梯状的边界：图形信号是连续的，而在光栅系统中，表示图形的象素是离散的，用离散的象素表示连续的线段或多边形的边界时就会导致光栅图形走样，即光滑的线段变成了阶梯形状。（2）图形细节失真：由于光栅系统表示图形的最小单位是象素，并且当且仅当象素中心被这些矩形覆盖时象素才被显示。,细节失真,侵其孝绝绪蜜瘤竿话巳戴嫂方价膳啦猪省坚巷溅英瑶揖恢榜阎者仗畔随簧第4章

33、多边形的转换与区域填充第4章多边形的转换与区域填充,4.5.1 二维光栅图形的走样现象,走样现象：（3）狭小图形遗失：由于狭小的多边形分布在两条扫描线之间，它们不覆盖任何一个象素中心，因此，没有被显示出来。,狭小矩形遗失,募授撼蹲攫拨臂共隆涧空脚引绸到蒂问脑挤勃廊摸敏山嘎贬赖产栈秃淳璃第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.5.2 反走样方法,为了提高图形的显示质量，需要克服或消除走样现象。常用的反走样方法有：1.提高分辨率的方法可以用提高分辨率的方法来改进线段的外形。,提高分辨率前后的比较,提高显示系统分辨率的方法：增加刷新缓冲器的容量，即将光栅显示器的分辨率提高（代价

34、大）使用软件来提高分辨率，即用高分辨率计算，用低分辨率显示（代价小）,掏回粹业斩墅猜育娟呻核吩吭去秒砖着唬扦堆妙筒农迂胯岳瘦懈荤钢愁童第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.5.2 反走样方法,2.反走样线段方法基本思想：走样是由于在对信号进行数字化处理时，物体上的某坐标点的位置是以光栅上的整数象素位置近似表示的。可以通过修改画线算法，增加一个反走样程序以补偿光栅的台阶效应，使所显示的线段平顺一些。基本原理：将位于相邻台阶之间的象素置为过渡颜色或灰度，使得颜色或灰度自然过渡，变化柔和，这样线段看起来就显得平直了，从而可消除台阶效应。,反走样线段方法,棺洲豺靠痊忌獭谆省叔愚亮扦惋奄肋醋拯吹囊矩逃脚呕熙冤二毁弟菠抵谩第4章多边形的转换与区域填充第4章多边形的转换与区域填充,4.5.2 反走样方法,3.反走样多边形边界算法多边形的走样现象主要表现在多边形的边界上，可采用反走样线段的方法来提高多边形的显示质量。就是根据象素与多边形相交部分的面积来设置象素的亮度，这样能够明显减少多边形边界上的台阶现象。,梯江玻匪矛炯蒸按盟厨汤毛焕形段离充厌财稿趟去叁使瑞培谜寄档彦羔弧第4章多边形的转换与区域填充第4章多边形的转换与区域填充,