《基本图形生成算法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《基本图形生成算法PPT讲稿.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基本图形生成算法第1页，共48页，编辑于2022年，星期六3.2 实区域填充算法 确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内解决的主要问题是什么？图案填充还有一个什么象素填什么颜色的问题曲线围成的区域，可用多边形逼近 第2页，共48页，编辑于2022年，星期六点在多边形内的包含性检验检验夹角之和射线法检验交点数第3页，共48页，编辑于2022年，星期六检验夹角之和若夹角和为0，则点p在多边形外若夹角和为360，则点p在多边形内ABCDEPABCDEP第4页，共48页，编辑于2022年，星期六射线法检验交点数ABCDEPABCDEP交点数=偶数（包括0）点在多边形之外交点数=奇数
2、点在多边形之内zx左闭右开第5页，共48页，编辑于2022年，星期六包围盒法凸多边形凹多边形逐点测试效率低不实用怎么办？第6页，共48页，编辑于2022年，星期六实区域填充算法分类扫描线填充算法-扫描线顺序有序边表算法边填充算法种子填充算法-内部一个点出发简单种子算法扫描线种子算法第7页，共48页，编辑于2022年，星期六扫描线填充算法求交：I4,I3,I2,I1排序：I1,I2,I3,I4交点配对：(I1,I2),(I3,I4)区间填色利用图形的空间连贯性和扫描线的连贯性第8页，共48页，编辑于2022年，星期六填充扩大化问题解决方法：取中心扫描线y+0.5检查交点右方像素的中心是否落在区间
3、内 xlx+0.5xryxy012345671234567012345671234567xP1P2P3P4x第9页，共48页，编辑于2022年，星期六顶点交点的计数问题 543210P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数 计数0次计数1次计数2次10第10页，共48页，编辑于2022年，星期六有序边表算法影响一般扫描线填充算法效率的因素？所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。如何提高效率？建立每条扫描线的活性边表何谓活性边？求交和排序目标是简化交点计算第1
4、1页，共48页，编辑于2022年，星期六有序边表算法 与当前扫描线相交的边称为活性边（active edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，边的活性边表（AEL,Active edge table)。它记录了多边形边沿扫描线的交点序列。只需对当前扫描线的活性边表作更新，即可得到下一条扫描线的活性边表。第12页，共48页，编辑于2022年，星期六有序边表算法如何计算下一条扫描线与边的交点。如何计算下一条扫描线与边的交点。直线方程：ax+by+c=0当前交点坐标：(xi,yi)下一交点坐标：(xi+1,yi+1)xi+1=(-byi+1)-c)/a=(-byi-b)-c)/
5、a=xi-b/a=xi+1/k活动边表中需要存放的信息：x x：当前扫描线与边的交点x x-b/a-b/a：从当前扫描线到下一条扫描线之间的x增量y ymaxmax：边所交的最高扫描线y=yi+1y=yiPjPj+1(xi,yi)(xi+1,yi+1)第13页，共48页，编辑于2022年，星期六有序边表算法活性边表的更新为了方便边的活性边表的更新，建立另一个表-新边表，存放在该扫描线第一次出现的边。存放的信息：x：扫描线与该边的初始交点x x：x的增量 y ymaxmax：该边的最大y值新边插入、旧边删除第14页，共48页，编辑于2022年，星期六 即算法中采用较灵活的数据结构。它由新边表ET
6、（Edge Table）和活性边表AEL（Active Edge List）两部分组成。表结构ET和AEL中的基本元素为多边形的边。边的结构由以下四个域组成：x:在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线的交点的坐标；x:边的斜率的倒数；ymax:边的上端点的y坐标；next:指向下一条边的指针。有序边表算法第15页，共48页，编辑于2022年，星期六yx0 1 2 3 4 5 6 7 8 9 101112345678P6P4P1P5P2P3新边表8.57.56.55.54.53.52.51.50.5528.5-1.5 711082075-32.533P4P5P5P6P3P4P
7、6P1P1P2P2P3活性边表活性边表5-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5528.P4P51108P3P45-1.5 7P5P6207.P6P1y=5.5728.P4P51108P3P43.5-1.5 7P5P6207.P6P1y=6.5928.P4P51108P3P4y=7.5207.1108P6P1P3P4y=4.5第16页，共48页，编辑于2022年，星期六step1：把新边表ETi中的边结点，用插入排序法 插入活性边表AET，使之按X坐标递增顺序排序；step2：遍历AET表，把配对交点之间的区间(
8、左闭右开)上的各 象素(X，Y)，用drawpixel(x,y,color)改写象素颜色值；step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把 Ymaxi的结果点的X值递增X；step4：重复各扫描线算法：(对每一条扫描线i)第17页，共48页，编辑于2022年，星期六有序边表算法优点：对每个像素只访问一次与设备无关缺点：数据结构复杂只适合软件实现第18页，共48页，编辑于2022年，星期六边填充算法边填充算法第19页，共48页，编辑于2022年，星期六边填充算法边填充算法优点：优点：最适合于有帧缓存的显示器可按任意顺序处理多边形的边仅访问与该边有交点的扫描线上右方的像素，算
9、法简单缺点：缺点：对复杂图形，每一像素可能被访问多次，输入/输出量大图形输出不能与扫描同步进行，只有全部画完才能打印第20页，共48页，编辑于2022年，星期六栅栏填充算法栅栏填充算法引入栅栏的目的？引入栅栏的目的？第21页，共48页，编辑于2022年，星期六种子填充算法种子填充算法种子填充种子填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。种子种子填充算法要求区域是连通的6754S9328第22页，共48页，编辑于2022年，星期六种子填充算法种子填充算法假设多边形区域内至少有一个像素已知假设多边形区域内至少有一个像素已知区域定义法：区域定义法：Interior-def
10、inedBoundary-definedFlood-fill algorithmBoundary-fill algorithm区域连通方式：区域连通方式：4-connected8-connected23第23页，共48页，编辑于2022年，星期六区域连通方式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果第24页，共48页，编辑于2022年，星期六简单的种子填充算法简单的种子填充算法（4连通边界）连通边界）种子像素入栈种子像素入栈,当栈非空时，重复以下步骤：当栈非空时，重复以下步骤：(1)栈顶像素出栈栈顶像素出栈(2)将出栈象素置成填
11、充色将出栈象素置成填充色(3)按右、上、左、下顺序检查与出栈象素相邻的按右、上、左、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈填充色，则将其入栈 第25页，共48页，编辑于2022年，星期六填充算法演示填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺点？第26页，共48页，编辑于2022年，星期六4-connected boundary-fill void BoundaryFill4(int x,int y,int fi
12、ll,int boundary)int current;current=getpixel(x,y);if(current!=boundary)&(current!=fill)putpixel(x,y,fill);BoundaryFill4(x+1,y,fill,boundary);BoundaryFill4(x-1,y,fill,boundary);BoundaryFill4(x,y+1,fill,boundary);BoundaryFill4(x,y-1,fill,boundary);4-connected boundary-fill void FloodFill4(int x,int y,
13、int fillColor,int oldColor)int current;current=getpixel(x,y);if(current=oldColor)putpixel(x,y,fillColor);BoundaryFill4(x+1,y,fillColor,oldColor);BoundaryFill4(x-1,y,fillColor,oldColor);BoundaryFill4(x,y+1,fillColor,oldColor);BoundaryFill4(x,y-1,fillColor,oldColor);第27页，共48页，编辑于2022年，星期六该该算法也可以填充有孔区域
14、。算法也可以填充有孔区域。缺点缺点：(1)有些象素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。改进算法，减少递归次数，提高效率。解决方法是用扫描线种子填充算法简单的种子填充算法简单的种子填充算法第28页，共48页，编辑于2022年，星期六扫描线种子填充算法目标：减少递归层次目标：减少递归层次适用于边界表示的适用于边界表示的4 4连通区域连通区域算法思想算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于
15、区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的各区段都填充完毕。第29页，共48页，编辑于2022年，星期六扫描线种子填充算法种子像素入栈种子像素入栈,当栈非空时，重复以下步骤：当栈非空时，重复以下步骤：(1)栈顶像素出栈栈顶像素出栈(2)沿扫描线对出栈像素的左右像素进行填充，沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止直到遇到边界像素为止(3)将上述区间内最左、最右像素记为将上述区间内最左、最右像素记为xl和和xr(4)在区间在区间xl,xr中中检查与当前扫描线相邻的上检查与当前扫描线相邻的上下两条扫描线下两条扫描线是否全为边界像素、或已填充是否全为边界像素
16、、或已填充的像素，若为非边界、未填充的像素，则的像素，若为非边界、未填充的像素，则把把每一区间的最右像素取为种子像素入栈每一区间的最右像素取为种子像素入栈 第30页，共48页，编辑于2022年，星期六扫描线算法分析（举例分析）该算法也可以填充有孔区域。像素中的序号标指它所在区段位于堆栈中的位置第31页，共48页，编辑于2022年，星期六扫描线算法分析（举例分析）第32页，共48页，编辑于2022年，星期六扫描线算法分析（举例分析）第33页，共48页，编辑于2022年，星期六扫描线算法分析（举例分析）第34页，共48页，编辑于2022年，星期六第3章基本图形生成算法3.1 图元扫描转换图元扫描转
17、换3.23.2实区域填充算法实区域填充算法3.33.3图形反走样技术图形反走样技术第35页，共48页，编辑于2022年，星期六3.3反走样用离散量表示连续量引起的失真现象称之为走样走样(aliasing)。光栅图形的走样现象光栅图形的走样现象阶梯状边界；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生闪烁。第36页，共48页，编辑于2022年，星期六走样现象举例不光滑不光滑(阶梯状）的图形边界阶梯状）的图形边界例子：PaintBrush第37页，共48页，编辑于2022年，星期六走样现象举例图形细节失真图形细节失真第38页，共48页，编辑于2022年，星期六走样现象举例狭小图形的遗失与动态
18、图形的闪烁狭小图形的遗失与动态图形的闪烁第39页，共48页，编辑于2022年，星期六反走样概念及方法用于减少或消除走样现象的技术称为反反走样走样(antialiasing)提高分辨率(硬件、软件方法）简单区域取样第40页，共48页，编辑于2022年，星期六提高分辨率把显示器分辨率提高一倍（硬件方法）直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。第41页，共48页，编辑于2022年，星期六提高分辨率方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的
19、图元却要花4倍时间。而且它也只能减轻而不能消除锯齿问题第42页，共48页，编辑于2022年，星期六提高分辨率高分辨率计算低分辨率显示（软件方法）用较高的分辨率的显示模式下计算，（对各自像素下计算，再求加权平均的颜色值），在较低的分辨率模式下显示。只能减轻而不能消除锯齿问题。第43页，共48页，编辑于2022年，星期六高分辨率计算低分辨率显示把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素的灰度值。1111算术平均1 22142121加权平均第44页，共48页，编辑于2022年，星期六简单区域取样方法由来方法由来两点假设两点假设1、象象素素是是
20、数数学学上上抽抽象象的的点点，它它的的面面积积为为0，它它的的亮亮度度由由覆盖该点的图形的亮度所决定；覆盖该点的图形的亮度所决定；2、直线段是数学上抽象直线段，它的宽度为、直线段是数学上抽象直线段，它的宽度为0。现实现实像素的面积不为像素的面积不为0；直线段的宽度至少为直线段的宽度至少为1个像素；个像素；假设与现实的矛盾是导致混淆出现的原因之一假设与现实的矛盾是导致混淆出现的原因之一第45页，共48页，编辑于2022年，星期六简单区域取样解决方法：改变直线段模型，由此产生算法解决方法：改变直线段模型，由此产生算法方法步骤方法步骤：1、将直线段看作具有一定宽度的狭长矩形、将直线段看作具有一定宽度
21、的狭长矩形2、当直线段与某象素有交时，求出两者相交区域的面积、当直线段与某象素有交时，求出两者相交区域的面积3、根据相交区域的面积，确定该象素的亮度值、根据相交区域的面积，确定该象素的亮度值 第46页，共48页，编辑于2022年，星期六简单区域取样缺点：象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。第47页，共48页，编辑于2022年，星期六作业(1)已知多边形各顶点坐标(6,1),(8,5),(6,7),(2,6)和(2,3),写出有序边表填充算法中的ET及全部AET的内容。(2)已知区域边界各顶点坐标(1,1),(7,1),(7,3),(5,5),(1,5),设种子点为（3，3）,试用4连通种子填充算法描述填充过程，写出像素被选中并填充的次序。(3)已知区域边界，外环边界为：(4,4),(4,26),(20,26),(28,18),(28,4),(21,4),(21,8),(10,8)和(10,4)；内环边界为：(10,12),(10,20),(17,20),(21,16)和(21,12)，种子为(16,22)。试用扫描线种子填充算法描述填充过程，写出区段种子的出栈顺序。第48页，共48页，编辑于2022年，星期六