《维填充图元生成》PPT课件.ppt
《《维填充图元生成》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《维填充图元生成》PPT课件.ppt(83页珍藏版)》请在三一办公上搜索。
1、1,第4章 二维填充图元生成,2,第4章 二维填充图元生成,4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法4.1.3 其它算法4.2 区域填充4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 图案填充4.4 字符,3,第4章 二维填充图元生成,二维填充图元用颜色或图案填充一个二维区域(由封闭的轮廓线包围)。轮廓线通常是多边形。如果是曲线的话:求出边界像素区域填充;可以采用直线段逼近多边形的扫描转换。,4,第4章 二维填充图元生成,多边形的两种表示方法:,顶点表示(多边形)用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少、易于几何变换;不能直接用于光栅系统显示。
2、,点阵表示(区域)用象素的集合(边界/内部)来刻画多边形。失去了许多重要的几何信息;便于光栅系统显示。,5,第4章 二维填充图元生成,多边形分类:,6,第4章 二维填充图元生成,4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法4.1.3 其它算法4.2 区域填充4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 图案填充4.4 字符,7,4.1.1 概述多边形的扫描转换,多边形的扫描转换:把多边形的顶点表示转换为点阵表示。也就是从多边形的给定边界出发,求出位于其内部的各个象素,并给帧缓冲器内对应元素设置相应的灰度,通常称这种转换为多边形的扫描转换。方法:逐点判断法、扫描线算
3、法、边缘填充法、栅栏填充法、边界标志法,8,1.扫描转换矩形,设矩形的四条边分另为xmin,xmax,ymin,ymax。只要填充从ymin到ymax的每条扫描线上位于xmin和xmax之间的象素。,void FillRectangle(Rectangle*rect,int color)int x,y;for(y=rect-ymin;y ymax;y+)for(x=rect-xmin;x xmax;x+)SetPixel(x,y,color);/*end of FillRectangle()*/,9,1.扫描转换矩形,矩形也是多边形,那么为什么要单独处理矩形?扫描转换多边形的算法复杂,而矩形的
4、应用非常多(窗口),所以对其单独处理以提高效率。共享边界将会被重绘两次,如何处理?,原则:左、下边的象素属于矩形,而右、上边的象素不属于矩形。左闭右开,下闭上开。边界像素重绘问题;填充扩大化问题。,10,1.扫描转换矩形,考虑填充从BL(x,y)到TR(x+5,y+5)的矩形。,void FillRectangle(Rectangle*rect,int color)int x,y;for(y=rect-ymin;y ymax;y+)for(x=rect-xmin;x xmax;x+)SetPixel(x,y,color);/*end of FillRectangle()*/,11,1.扫描转换
5、矩形,Area=6*6=36 pixels,Area=5*5=25 pixels,矩形面积为:6*636 pixels矩形实际面积应为:(x+5)-x*(y+5)-y25 pixels采用左闭右开,下闭上开的原则对边界象素进行处理可保证矩形的面积不被扩大。对FillRectangle()进行修改。,12,1.扫描转换矩形,设矩形的四条边分另为xmin,xmax,ymin,ymax。,void FillRectangle(Rectangle*rect,int color)int x,y;for(y=rect-ymin;y ymax;y+)for(x=rect-xmin;x xmax;x+)Set
6、Pixel(x,y,color);/*end of FillRectangle()*/,13,2.逐点判断法,它是扫描转换多边形的最简单算法,即逐个判断绘图窗口内的象素是否在多边形内部。如何判断点在多边形的内外?,14,2.逐点判断法,逐点判断的算法虽然程序简单,但不可取。原因是速度太慢。主要是由于该算法割断了各象素之间的联系,孤立地考察各象素与多边形的内外关系,使得几十万甚至几百万个象素都要一一判别,每次判别又要多次求交点,花费很多时间。不适于实际使用,很少采用。,15,第4章 二维填充图元生成,4.1 多边形的扫描转换4.1.1 概述4.1.2 扫描线算法4.1.3 其它算法4.2 区域填
7、充4.2.1 简单种子填充4.2.2 扫描线种子填充4.3 图案填充4.4 字符,16,4.1.2 扫描线算法,扫描线算法是扫描转换多边形的常用算法,它充分利用了相邻像素之间的连贯性,避免了逐点判断和反复求交计算,达到了减少计算量和提高算法效率的目的。处理对象:非自交多边形(边与边之间除了顶点外无其它交点)。,17,4.1.2 扫描线算法,开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。,18,4.1.2 扫描线算法,区域的连贯性:相邻两条扫描线构成一个水平长方形区域,并被多边形的边分割为若干梯形(一类位
8、于多边形的内部;另一类在多边形的外部,且间隔排列)。只需知道该区域内任一梯形中一点关于多边形的内外关系,即可确定区域内所有梯形关于多边形的内外关系。扫描线的连贯性:区域的连贯性在一条扫描线上的反映;边的连贯性:某条边与当前扫描线相交,也可能与下一条扫描线相交。可通过与当前扫描线的交点计算与下一扫描线的交点(利用斜率)。(区域的连贯性在相邻两扫描线上的反映),19,根据扫描线的连贯性可知:一条扫描线与多边形的交点中,入点和出点之间所有点都是多边形的内部点。所以,对所有的扫描线填充入点到出点之间的点就可填充多边形。如何具体实现(如何找到入点、出点)?,4.1.2 扫描线算法原理,20,4.1.2
9、扫描线算法原理,根据区域的连贯性,分为3个步骤:(1)求出扫描线与多边形所有边的交点;(2)把这些交点按x坐标值以升序排列;(3)对排序后的交点进行奇偶配对,对每一对交点间的区域进行填充。,步骤(3)如上图:对y8的扫描线,对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13),然后对交点2与4之间、9与13之间的所有象素点进行填充。求交点、排序、配对、填色,21,4.1.2 扫描线算法数据结构及实现,算法中采用较灵活的数据结构。它由边分类表ET(Edge Table)和活化边表AEL(Active Edge List)两部分组成。,求交点、排序、配对、填色利用链表:与当前扫描线相交的
10、边称为活化边(Active Edge),把它们按与扫描线交点x坐标递增的顺序存入一个链表中,称为活化边表AEL(AEL,Active Edge List)。它记录了多边形边沿扫描线的交点序列。,y=6,AEL:,e2,e5,AEL中每个对象需要存放的信息:ymax:边所交的最高扫描线;x:当前扫描线与边的交点;x:从当前扫描线到下一条扫描线之间的x增量next:指向下一对象的指针。,活化边表AEL,求交、排序、配对、填色随扫描线的递增如何更新AEL?边的加入、删除,交点的更新。,y=6,AEL:,y=7,AEL:,e2,e5,e2,e3,e4,e5,建立一个新的数据结构:边分类表ET,活化边表
11、AEL,边分类表ET(Edge Table):按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫描线第一次出现的边)。同一类中,各边按x值(x值相等时,按x的值)递增的顺序排列。有多少条扫描线,就设多少类。,ET中每个对象需要存放的信息:ymax:边所交的最高扫描线;x:边的下端点的x坐标;x:从当前扫描线到下一条扫描线之间的x增量(边的斜率的倒数);next:指向下一对象的指针。,边分类表ET(Edge Table):按扫描线i对非水平边进行分类的指针数组。下端点的y坐标值等于i的边归入第i类(在该扫描线第一次出现的边)。同一类中,各边按x值(x值相等时,按
12、x的值)递增的顺序排列。有多少条扫描线,就设多少类。,e2,e5,e1,e6,e3,e4,ET(桶),同一类中的边按x、x的递增顺序排列,26,4.1.2 扫描线算法数据结构及实现,算法中采用较灵活的数据结构。它由边分类表ET(Edge Table)和活化边表AEL(Active Edge List)两部分组成。ET和AEL中的基本元素称为“边”(Edge)。边的结构“Edge”由以下四个域组成:ymax:边的上端点的y坐标;x:在ET中表示边的下端点的 x坐标;在AEL中则表示边 与扫描线的交点的x坐标;x:边的斜率的倒数;next:指向下一“边”的指针。,typedef struct in
13、t ymax;float x,deltax;Edge*next;Edge;,27,4.1.2 扫描线算法几点规则,求交点、排序、配对、填色交点与多边形顶点重合时,会导致“配对”失败,如何处理?下闭上开,28,4.1.2 扫描线算法几点规则,扫描线与多边形的顶点相交时,交点的取舍(保证交点正确配对)。检查该顶点的两相邻边在扫描线的哪一侧:只要检查顶点的两条边的另外两个端点的Y值,两个Y值中大于交点Y值的个数是0,1,2,来决定取0,1,2个交点。(下闭上开),29,4.1.2 扫描线算法算法描述,建立ET,置y为ET中非空桶的最小序号;置AEL表为空,且把y桶中ET表的边加入AEL表中;whil
14、e AEL表中非空 dobegin 对AEL表中的x、x按升序排列;按照AEL表中交点前后次序,在每对奇偶交点间的x段予 以填充;计算下一条扫描线:y=y+1;if 扫描线 y=ymaxthen 从AEL表中删除这些边;对在AEL表中的其他边,计算与下一条扫描线的交点:x=x+x 按照扫描线y值把ET表中相应桶中的边加入AEL表中;endend of algorithm,e2,e5,e1,e6,e3,e4,:ET,AEL=空,y=1 AEL=,(7,1)(7,1),(4.5,2)(8.5,2),(2,3)(10,3),(2,4)(11.5,4),(2,5)(13,5),(2,6)(13,6),
15、AEL:,y=2 AEL=,y=3 AEL=,y=4 AEL=,y=5 AEL=,y=6 AEL=,算法示例,e2,e5,e1,e6,e3,e4,:ET,y=7 AEL=,(2,7)(7,7),(7,7)(13,7),(2,6)(13,6),AEL:,y=6 AEL=,y=8 AEL=,(2,8)(4.5,8),(8.5,8)(13,8),y=9 AEL=,(10,9)(13,9),算法示例,e2,e5,e1,e6,e3,e4,:ET,y=10 AEL=,(11.5,10)(13,10),AEL:,y=9 AEL=,(10,9)(13,9),y=11 AEL=空,算法示例,33,练习,写出如图
16、所示的多边形的边分类表(ET)及y=7和y=1对应的活性边表(AEL),e3,e5,e1,e2,e4,y=7,AET:,y=1,AET:,e4,e3,e1,e2,36,4.1.2 扫描线算法几点规则,求交点、排序、配对、填色还需解决的问题:交点x坐标可能是小数,如何取整?填充扩大化的问题,及边界像素的取舍问题。,37,交点的取整利用连贯性计算出的交点可能导致部分像素位于多边形之外。目的:使生成的像素尽量位于多边形之内,并且避免填充扩大化。,4.1.2 扫描线算法几点规则,38,4.1.2 扫描线算法几点规则,假定非水平边与扫描线y=e相交,交点的横坐标为x。若x为小数,即交点落于扫描线上两个相
17、邻像素之间时,规则如下:(a)交点位于左边之上(入点),向右取整;(b)交点位于右边之上(出点),向左取整;,39,4.1.2 扫描线算法几点规则,边界象素的取舍问题,避免填充扩大化。若x为整数,即交点落于像素点上(边界象素)。落在右边界的象素(出点)不予填充;“左闭右开”,40,4.1.2 扫描线算法几点规则,1.边界上的象素:“左闭右开”,将左边界的点算为内部,而将右边界的点算为外部。2.顶点:“下闭上开”,即丢弃上顶点。,扫描线交于一顶点,共享交点的两条边分另处于扫描线的两边,这时交点只取1个,如扫描线y=3,根据“下闭上开”原则,该点被填充1次。,共享交点的两条边处于扫描线的上方,这时
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 维填充图元生成 填充 生成 PPT 课件
链接地址:https://www.31ppt.com/p-5641667.html