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