《计算机图形学---多边形填充算法知识讲解.ppt》由会员分享，可在线阅读，更多相关《计算机图形学---多边形填充算法知识讲解.ppt（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Computer Computer GraphicsGraphics计算机图形学-多边形填充算法Computer Computer GraphicsGraphics4.3.1 多边形的表示方法顶点表示顶点表示顶点表示顶点表示是用多边形的顶点的序列来描述多边形是用多边形的顶点的序列来描述多边形是用多边形的顶点的序列来描述多边形是用多边形的顶点的序列来描述多边形v该表示几何意义强、占内存少该表示几何意义强、占内存少v但它不能直观地说明哪些像素在多边形内但它不能直观地说明哪些像素在多边形内Computer Computer GraphicsGraphics点阵表示点阵表示点阵表示点阵表示是是是是用位
2、于多边形内的像素的集合来刻划用位于多边形内的像素的集合来刻划用位于多边形内的像素的集合来刻划用位于多边形内的像素的集合来刻划 多边形多边形多边形多边形v该方法虽然没有多边形的几何信息该方法虽然没有多边形的几何信息v是面着色所需要的图像表示形式是面着色所需要的图像表示形式Computer Computer GraphicsGraphics 多边形填充多边形填充就是把多边形的顶点表示转就是把多边形的顶点表示转换为点阵表示换为点阵表示即从多边形的给定边界出发，求出位于其内即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰
3、度或颜色。元素设置相应的灰度或颜色。多边形的填充方法：多边形的填充方法：扫描线方法扫描线方法边缘填充方法边缘填充方法边界标志方法边界标志方法栅栏填充方法栅栏填充方法Computer Computer GraphicsGraphics4.3.2 多边形填充的扫描线算法算法特点：算法特点：基本概念：基本概念：充分利用了相邻象素之间的连续性，避免对象素的逐点判断充分利用了相邻象素之间的连续性，避免对象素的逐点判断和反复求交运算，减少了计算量，提高了算法速度，是效率和反复求交运算，减少了计算量，提高了算法速度，是效率较高的多边形填充算法，处理对象为非自交多边形。较高的多边形填充算法，处理对象为非自交多
4、边形。区域的连续性区域的连续性扫描线的连续性扫描线的连续性边的连续性边的连续性关于一般多边形的填充过程关于一般多边形的填充过程,对于一条扫描线对于一条扫描线,可分为四步可分为四步:v求交求交v排序排序v交点配对交点配对v区间填色区间填色奇点的处理奇点的处理Computer Computer GraphicsGraphics区域的连续性区域的连续性 设多边形设多边形P的顶点的顶点各顶点各顶点Pi的纵坐标的纵坐标yi的递减数列的递减数列p0p1p7p2p3p4p5p6p8p1,p7,p3,p6,p2,p5,p0,p4,p8p1,p7,p3,p6,p2,p5,p0,p4,p8Computer Com
5、puter GraphicsGraphics (1)梯梯形形的的两两底底边边分分别别在在y=和和y=两两条条扫扫描描线线上上，腰腰在在多多边边 形形P的边上或在显示屏幕的边界上。的边上或在显示屏幕的边界上。它们具有下列性质它们具有下列性质(设设 为整数为整数)：(2)梯形可分为两类：一类位于多边形梯形可分为两类：一类位于多边形P的内部；另一的内部；另一类在多边形类在多边形P的外部。的外部。(3)两类梯形在长方形区域两类梯形在长方形区域 ，内相间的排列。内相间的排列。位于位于y=y=和和y=y=两条扫描线之间的长方形区域被多边形两条扫描线之间的长方形区域被多边形P的边的边分割成若干梯形分割成若干
6、梯形p0p1p7p2p3p4p5p6p8由区域的相关性知由区域的相关性知当知道一个区域内一点与多边形的位置关系，即可确定该区域当知道一个区域内一点与多边形的位置关系，即可确定该区域内所有点与多边形之间的内外关系内所有点与多边形之间的内外关系Computer Computer GraphicsGraphics扫描线的连续性扫描线的连续性扫描线的连续性是区域连续性在扫描线上的体现扫描线的连续性是区域连续性在扫描线上的体现012345678设设e为一整数为一整数 e 若扫描线若扫描线y=e与多边形与多边形P的边的边Pi-1Pi相交，则记其交点的横相交，则记其交点的横坐标为坐标为y=e该扫描线与该扫描
7、线与P的边界各交点横坐标的递增序列的边界各交点横坐标的递增序列此交点序列具有以下性质：此交点序列具有以下性质：(1)l是偶数是偶数(2)(2)扫描线被分成好多区段扫描线被分成好多区段,一部一部分在多边形内分在多边形内,一部分在多边形外一部分在多边形外(3)(3)两类线段间隔排列两类线段间隔排列由区域的连贯性和由区域的连贯性和扫描线的连续性知扫描线的连续性知:若已知某一点与多边形的位置关系若已知某一点与多边形的位置关系,就可知该点所在线段与就可知该点所在线段与多边形的位置关系多边形的位置关系Computer Computer GraphicsGraphics边的连续性边的连续性若若d为一整数，为
8、一整数，d=e1，且，且yi0yyin；设位于扫描线；设位于扫描线y=d上的交点序列为上的交点序列为012345678y=ey=d则两交点则两交点序列之间有以下关系序列之间有以下关系:1 两序列元素的个数相等两序列元素的个数相等2 点点()与与()位于多边形位于多边形P的同的同一边上，即一边上，即以上性质称为以上性质称为边的连续性边的连续性Computer Computer GraphicsGraphicsv奇点定义奇点定义 如果如果 ，则称顶点则称顶点Pi为极值点；为极值点；否则称否则称Pi为非极值点。为非极值点。奇点的处理奇点的处理当扫描线与多边形当扫描线与多边形P的边界的的边界的交点是交
9、点是P的顶点的顶点时，时，则称该交点为则称该交点为奇点奇点p0p1p7p2p3p4p5p6p8要把奇点作为几个交点来处理呢要把奇点作为几个交点来处理呢?v多边形多边形P P的顶点可分为两类：的顶点可分为两类：极值点极值点和和非极值点非极值点Computer Computer GraphicsGraphics 如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数。若如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数。若将每一奇点都简单地计为两个交点，同样会导致反常的结果将每一奇点都简单地计为两个交点，同样会导致反常的结果 为了使为了使交点个数交点个数保持保持为偶数为偶数,规定当规定当奇
10、点奇点是是P P的的极值点极值点时，该点按时，该点按两个两个交点计算；交点计算；否则否则按按一个一个交点计算。交点计算。预处理预处理:若若Pi是非极值点，则将是非极值点，则将 两边中位于扫描线两边中位于扫描线y=yi上方的那条边在上方的那条边在Pi点处截去点处截去一单位长一单位长 Computer Computer GraphicsGraphics扫描线算法的数据结构和实现步骤扫描线算法的数据结构和实现步骤Computer Computer GraphicsGraphics扫描线算法的数据结构扫描线算法的数据结构多边形P0P1P2P3P4P5P6P0数据结构数据结构边的边的分类表分类表ETET
11、和边的和边的活化链表活化链表AELAELET和AEL中的多边形的边由四个域四个域组成：ymax 边的上端点的边的上端点的y坐标坐标在在ET中为边的下端点的中为边的下端点的x坐标坐标x在在 AEL中是边与扫描线交点的中是边与扫描线交点的x坐标坐标x边的斜率的倒数边的斜率的倒数next指向下一条边的指针指向下一条边的指针Computer Computer GraphicsGraphicsP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)多边形P0P1P2P3P4P5P6P0Computer Computer GraphicsGraphi
12、csP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)对奇点采用了预处理的边y筒分类表分类表ETET是按边下端点的纵坐标是按边下端点的纵坐标y y对边进行分类的对边进行分类的指针数组指针数组同一类中，各边按同一类中，各边按x值递增的顺序排列成行值递增的顺序排列成行下端点的纵坐标下端点的纵坐标y y等于等于i i的边归入第的边归入第i i类，水平边除外类，水平边除外Computer Computer GraphicsGraphicsP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(
13、7,2)多边形P0P1P2P3P4P5P6P0对奇点采用了预处理的边y筒Computer Computer GraphicsGraphics边的活化链表边的活化链表AELAEL由与由与当前扫描线相交的当前扫描线相交的所有多边形的边组成所有多边形的边组成-5/357AELe7e54212AEL在在y=2扫扫描描线线上上的当前状态的当前状态它记录了多边形它记录了多边形沿扫描线的交点序列沿扫描线的交点序列,并根据递推关系并根据递推关系,不断地更新交点序列不断地更新交点序列它是一个它是一个动态动态列表，新边插入，旧边删除列表，新边插入，旧边删除P0P1P2P3P4P5 P6=(2,5)(2,10)(9
14、,6)(16,11)(16,4)(12,2)(7,2)Computer Computer GraphicsGraphicsP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)-5/35AELe7e54214AEL在在y=3扫扫描描线线上上的当前状态的当前状态-5/35AELe7e54216AEL在在y=4扫扫描描线线上上的当前状态的当前状态E4边边做做了了预预处处理理(也也可可以以不不做做预预处处理理，但但要要清清楚楚的的知知道道此此点点要要在在AEL中计几次中计几次)Computer Computer GraphicsGraphic
15、s扫描线算法实现步骤扫描线算法实现步骤步骤步骤1:(AEL1:(AEL初始化初始化)将边的活化链表将边的活化链表AELAEL设置为空设置为空。步骤步骤2:(y初始化初始化)取扫描线取扫描线纵坐标纵坐标y的初始值为的初始值为ET中非空元素的中非空元素的最小序号最小序号 步骤步骤3：按：按从下到上的顺序从下到上的顺序对纵坐标值为对纵坐标值为y的扫描线的扫描线(当前扫描线当前扫描线)执执行下列步骤，直到边的分类表行下列步骤，直到边的分类表ET和边的活化链表和边的活化链表AEL都都变成空为止变成空为止。v(1)如边分类表如边分类表ET中的第中的第y类元素非空，则将类元素非空，则将属于该类的所有属于该类
16、的所有边从边从ET中取出并插入边的活化链表中取出并插入边的活化链表AEL中，中，AEL中的各边按照中的各边按照x值值(当当x的值相等时，按的值相等时，按x值值)递增方向排序递增方向排序。v(2)若若相相对对于于当当前前扫扫描描线线，边边的的活活化化链链表表AEL非非空空，则则将将AEL中中的的边边两两两两依依次次配配对对，即即第第1，2边边为为一一对对，第第3，4边边为为一一对对，依依此此类类推推。每每一一对对边边与与当当前前扫扫描描线线的的交交点点所所构构成成的的区区段段位位于于多多边边形形内，依次对这些区段上的点内，依次对这些区段上的点(象素象素)按多边形属性按多边形属性着色着色。v(3)
17、将边的活化链表将边的活化链表AEL中满足中满足y=ymax的边删去的边删去。v(4)将边的活化链表将边的活化链表AEL剩下的剩下的每一条边的每一条边的x域累加域累加x，即，即x=x+x。v(5)将当前的扫描线的将当前的扫描线的纵坐标值纵坐标值y累加累加，即，即y=y+1Computer Computer GraphicsGraphics扫描线算法实现步骤伪代码扫描线算法实现步骤伪代码Polygonfill(polydef,color)Polygonfill(polydef,color)Int colorInt color多边形定义多边形定义 polydef polydef for(for(各条
18、扫描线各条扫描线I)I)初始化新边表表头指针初始化新边表表头指针ETI;ETI;把把ymin=Iymin=I的边放进边表的边放进边表ETI;ETI;y=y=最低扫描线号最低扫描线号;初始化活化边表初始化活化边表AELAEL为空为空;for(for(各条扫描线各条扫描线I)I)把新边表把新边表ETIETI中的边结点用插入排序法插入中的边结点用插入排序法插入AELAEL表表,使使 之按之按x x递增顺序排列递增顺序排列;遍历遍历AETAET表表,把配对交点之间的区间上的各像素把配对交点之间的区间上的各像素(x,y)(x,y)用待填颜色改写用待填颜色改写 遍历遍历AETAET表表,把把ymax=Iy
19、max=I的结点从的结点从AELAEL中删除中删除,并把并把ymaxIymaxI的结点的的结点的 x x递增递增dx;dx;若允许多边形的边自交若允许多边形的边自交,则用冒泡排序法对则用冒泡排序法对AELAEL表重新排序表重新排序;Computer Computer GraphicsGraphics扫描线算法特点扫描线算法特点v数据结构较复杂数据结构较复杂v但充分利用了扫描线、多边形边的连续性但充分利用了扫描线、多边形边的连续性,避免避免了反复求交点的运算了反复求交点的运算,是一种较快的填充方法是一种较快的填充方法v对各种表的维持和排序开销太大，适合软件对各种表的维持和排序开销太大，适合软件实
20、现而不适合硬件实现实现而不适合硬件实现Computer Computer GraphicsGraphics优点：优点：对每个像素只访问一次对每个像素只访问一次与设备无关与设备无关v缺点：缺点：数据结构复杂数据结构复杂只适合软件实现只适合软件实现Computer Computer GraphicsGraphicsyx0123456789101112345678P6P4P1P5P2P3例习题例习题1：用扫描线算法来扫描转换一个多边形Computer Computer GraphicsGraphics边的Y筒ET5432125-3353720811075-3/2852yx0 1 2 3 4 5 6
21、7 8 9 10 1112345678P6P4P1P5P2P3Computer Computer GraphicsGraphics边的活化链表Y=125-3353(5,1)(5,1)Y=222-3383(2,2)(8,2)yx0 1 2 3 4 5 6 7 8 9 10 1112345678P6P4P1P5P2P3Computer Computer GraphicsGraphicsyx0123456789101112345678P6P4P1P5P2P3例习题例习题1：Computer Computer GraphicsGraphics习题习题习题习题 设现在要用扫描线算法来扫描转换一个多边形，
22、该多边形的顶点分别为，如图所示。先写出边y桶，然后试给出边的活化链表AEL,AEL,完成扫描转换完成扫描转换Computer Computer GraphicsGraphicsComputer Computer GraphicsGraphics4.3.3 边缘填充算法采用对图像进行逐位求反逐位求反的方法，免去对边排序的工作量算法特点算法特点:预备知识：预备知识：对图像对图像M M作偶数次求反运算，其结果还是作偶数次求反运算，其结果还是M M;而对而对M M作奇数次求作奇数次求反运算的结果是反的反运算的结果是反的在光栅图形中，如某区域已着上值为在光栅图形中，如某区域已着上值为M的某种颜色，则上述
23、的某种颜色，则上述求反运算得到的结果是：求反运算得到的结果是：对区域作偶数次求反运算后，该区域的颜色不变对区域作偶数次求反运算后，该区域的颜色不变；作奇数次求反运算后，该区域的颜色则变成值为作奇数次求反运算后，该区域的颜色则变成值为 的颜色。的颜色。Computer Computer GraphicsGraphics边缘填充算法的实现边缘填充算法的实现对多边形对多边形P的的每一非水平边每一非水平边（i=0,1,n）上的各像素）上的各像素做向右求反运算即可做向右求反运算即可01234122334340Computer Computer GraphicsGraphicsComputer Compu
24、ter GraphicsGraphics边缘填充算法分析边缘填充算法分析优点：优点：最适合于有帧缓存的显示器可按任意顺序处理多边形的边仅访问与该边有交点的扫描线上右方的像素，算法简单缺点：缺点：对复杂图形，每一像素可能被访问多次，输入/输出量大图形输出不能与扫描同步进行，只有全部画完才能打印Computer Computer GraphicsGraphics4.3.4 栅栏填充算法此算法是为了减少边缘算法访问像素的次数而提出的此算法是为了减少边缘算法访问像素的次数而提出的栅栏栅栏:是一条与扫描线垂直的直线是一条与扫描线垂直的直线,栅栏的位置通常栅栏的位置通常取过多边形顶点取过多边形顶点,能把多
25、边形分为左右两半能把多边形分为左右两半栅栏填充的基本思想栅栏填充的基本思想:对于每个扫描线与多边形边的交点,就将交点与栅栏之间的像素取补.若交点位于栅栏若交点位于栅栏左左边边,则将则将交点之右交点之右,栅栏之左栅栏之左的所有像素取补的所有像素取补若交点位于栅栏若交点位于栅栏右右边边,则将则将交点之左交点之左,栅栏之右栅栏之右的所有像素取补的所有像素取补Computer Computer GraphicsGraphics栅栏填充的具体实现栅栏填充的具体实现:01234栅栏线12栅栏线34栅栏线23栅栏线4栅栏线0Computer Computer GraphicsGraphics边界标志法:先画
26、边界后填色，使对帧缓冲器中的每个元素的赋值次数不超过2次。基本思想是：先用一种特殊的颜色在帧缓冲器中将多边形的边界(水平边的部分边界除外)勾画出来。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需的颜色 图边界标志算法的运行过程4.3.5 边界标志算法Computer Computer GraphicsGraphics边界标志法具体实现图边界标志算法的运行过程步骤1：以值为boundary-color 的特殊颜色勾画多边形P的边界。设 多 边 形 顶 点 为 Pi=(xi,yi),0in，xi,yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(
27、包括零)。步骤2：设interior_point 是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形P内，则interior_point=true，需要填上值为polygon_color的颜色；否则该像素在多边 形 P外，需 要 填 上 值 为background_color的颜色 Computer Computer GraphicsGraphics边界标志算法实例边界标志算法实例XXXXXXXXXXXXP2(8,5)Y=2 Y=3XXXXXXY=1P0(1,4)P1(1,10)P3(14,8)P4(14,2)P5(11,0)P6(6,0)XXXXXX Y=4 Y=5 Y=
28、6 Y=7 Y=8 Y=9 Y=10Computer Computer GraphicsGraphics算法实现算法实现int i=0;double x,y;double dy,dx;int ymin,ymax;for(i=0;i 0)x=x i;else x=x i+1;if(yi=y i+1)/获得多边形边的端点ymin=y i+1;ymax=y i;elseymin=y i;ymax=y i+1;for(y=ymin;y GetPixel(x,y);if(k=n)dc-SetPixel(x+1,y,RGB(0,0,255);/标志边界并处理奇点else dc-SetPixel(x,y,R
29、GB(0,0,255);/maxx、maxy、minx、miny是获得的多边形最小矩形包围盒边界值double x1,y1;for(y1=miny-1;y1=maxy-1;y1+)in_flag=0;/多边形内部标志变量 for(x1=minx-1;x1GetPixel(x1,y1);m=RGB(0,0,255);/多边形边界颜色 if(l=m)if(in_flag=0)in_flag=1;else in_flag=0;if(in_flag)dc-SetPixel(x1,y1,RGB(0,0,255);/在多边形内部填充色蓝色 else dc-SetPixel(x1,y1,RGB(255,25
30、5,255);/在多边形外部填充色白色 Computer Computer GraphicsGraphics算法特点分析：算法特点分析：1 1 本算法避免了对帧缓存的大量元素的赋值本算法避免了对帧缓存的大量元素的赋值2 2 但需逐条扫描线并对帧缓存中的元素进行搜索和比较但需逐条扫描线并对帧缓存中的元素进行搜索和比较3 3 当算法生成的边界不封闭时，在一条扫描线上必须当算法生成的边界不封闭时，在一条扫描线上必须有偶数个具有边界颜色的点有偶数个具有边界颜色的点Computer Graphics第4章 基本光栅图形生成算法4.4 区域填充Computer Computer GraphicsGraph
31、ics4.4.1 区域的基本概念 是指已经表示成点阵形式的像素集合。是指已经表示成点阵形式的像素集合。区域区域区域的表示方式区域的表示方式在光栅图形中，有在光栅图形中，有内点内点表示法和表示法和边界边界表示法表示法Computer Computer GraphicsGraphics内点表示法内点表示法内点表示法内点表示法：把位于给定把位于给定区域内的所有像素一一列举区域内的所有像素一一列举出来出来的方法称为内点表示法的方法称为内点表示法。边界表示法边界表示法边界表示法边界表示法：把位于把位于给定区域给定区域边界上的像素边界上的像素一一列举出来一一列举出来的方法称的方法称为边界表示法为边界表示法
32、。Computer Computer GraphicsGraphics是是指指先先将将区区域域内内的的一一点点(常常称称种种子子点点)赋赋予予给给定定颜颜色色，然然后后将将这这种种颜颜色色扩扩展展到到整整个个区区域域内内的过程。的过程。区域填充区域填充一个封闭区域确定以后一个封闭区域确定以后,填充要解决的问题是填充要解决的问题是如何确定填充的像素以及如何高效地填充。如何确定填充的像素以及如何高效地填充。Computer Computer GraphicsGraphics 4连连通通的的区区域域:取取区区域域内内任任意意两两点点，在在该该区区域域内内若若从从其其中中一一点点出出发发通通过过上上上
33、上、下下下下、左左左左、右右右右四四种种运运动动可可到到达达另另一点一点。四个方向的运动8连通区域连通区域:取区域内取区域内任意两点任意两点，若从其中任一点出发，在该区若从其中任一点出发，在该区域内通过沿域内通过沿水平水平水平水平方向、方向、垂直垂直垂直垂直方方向和向和对角线对角线对角线对角线方向的方向的八种八种运动可运动可到达另一点到达另一点。8个方向的运动区域的连通性区域的连通性Computer Computer GraphicsGraphics4连通区域可理解为连通区域可理解为8连通区域，但他们的连通区域，但他们的边界边界不尽相同不尽相同。四连通区域的边界是八连通的四连通区域的边界是八连
34、通的八连通区域的边界是四连通的八连通区域的边界是四连通的Computer Computer GraphicsGraphics4.4.2 简单的种子填充算法基本思想：1 1 给定区域给定区域G一种子点（一种子点（x,y）2 2 判断该点是否是区域内的一点判断该点是否是区域内的一点如果是，则将该点填充为新的颜色如果是，则将该点填充为新的颜色3 3 然后将该点周围的四个点（四连通）或八个然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理点（八连通）作为新的种子点进行同样的处理4 4 通过这种扩散完成对整个区域的填充通过这种扩散完成对整个区域的填充 Computer Com
35、puter GraphicsGraphics简单的种子填充算法简单的种子填充算法（4连通）连通）v种子像素入栈种子像素入栈v当栈非空时，重复以下步骤：当栈非空时，重复以下步骤：栈顶像素出栈栈顶像素出栈将出栈象素置成填充色将出栈象素置成填充色 按左、上、右、下顺序检查与出栈象素相邻的按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈填充色，则将其入栈 算法演示算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799Computer
36、 Computer GraphicsGraphics按右、上、左、下的顺序进栈Computer Computer GraphicsGraphicsComputer Computer GraphicsGraphics区域连通方式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果Computer Computer GraphicsGraphics算法分析：算法分析：1有些象素会入栈多次，降低算法效率；栈结构占空间。2递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。种子算法充分利用了递归调用递归调用的机理，
37、在前一种子点确定并变为新颜色后，按照自身调用的八(四）向顺序依次查找新的种子点，找到即变为新颜色，继续下一种子的查找。未查的方向被压栈保存，等退栈时继续查找，最终完成蔓延至整个区域所有点都变为新颜色。改进算法，减少递归次数，提高效率。改进算法，减少递归次数，提高效率。方法之一使用扫描线填充算法；方法之一使用扫描线填充算法；Computer Computer GraphicsGraphics4.4.3 扫描线种子填充算法v从给定的种子点开始，填充当前扫描线上种从给定的种子点开始，填充当前扫描线上种子点所在的区间子点所在的区间基本思想：基本思想：v然后确定与这一区间相邻的上下两条扫描线然后确定与这
38、一区间相邻的上下两条扫描线上需要填充的区间上需要填充的区间v从这些区间上各取一个种子点并把他们保存从这些区间上各取一个种子点并把他们保存起来，作为下次填充的种子点起来，作为下次填充的种子点v反复这个过程，直到所保存的各区间都填充反复这个过程，直到所保存的各区间都填充完毕完毕Computer Computer GraphicsGraphics算法步骤：算法步骤：步骤步骤 1：将算法设置的堆栈置为空。将给定的种子点将算法设置的堆栈置为空。将给定的种子点（x,y）压入堆栈）压入堆栈步骤步骤 2：如果堆栈为空，算法结束；否则取栈顶元素（如果堆栈为空，算法结束；否则取栈顶元素（x,y）作为种子点作为种子
39、点步骤步骤 3：从种子点（从种子点（x,y）开始，沿纵坐标为）开始，沿纵坐标为y的当前扫描的当前扫描线线向左右两个方向向左右两个方向向左右两个方向向左右两个方向逐个像素用新的颜色值进行填充，直到逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为边界为止。设区间两边界的横坐标分别为xleft 和和xright。步步骤骤4 4：在在与与当当前前扫扫描描线线相相邻邻的的上上下下两两条条扫扫描描线线上上，以以以以区区区区间间间间 x xleftleft,x,xrightright 为为为为搜搜搜搜索索索索范范范范围围围围，求求出出需需要要填填充充的的各各小小区区间间，把把各各小小区
40、区间中最右边的点并作为种子点压入堆栈，转到步骤间中最右边的点并作为种子点压入堆栈，转到步骤2 2。Computer Computer GraphicsGraphics具体实现过程具体实现过程图3.32扫描线种子填充算法的执行过程1212123对于每一个待填充区段，只需压栈一次；而在递归算法中，每个对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。12Computer Computer GraphicsGraphics种子点位置不同种子点位置不同3Computer Comput
41、er GraphicsGraphicswhile stacknotempty do pop(x,y)；*从堆栈中取一种子象素从堆栈中取一种子象素*savex:=x:*保存横坐标保存横坐标x的值的值*while getpixel(FB,x,y),Bcolor do setpixel(FB,x,y,Ncolor);x:=x+1 xright:=x1*保存线段的右端点保存线段的右端点*x:=savex1;*向种子的左边填充向种子的左边填充*while getpixel(FB,x,y)Bcolor do setpixel(FB,x,y,Ncolor);x:=x1 xleft:=x+1*保存线段的左端点
42、保存线段的左端点*x:=xleft;y:=y+1;while x=xright do spanneedfill:=false;算法程序：算法程序：Computer Computer GraphicsGraphicswhile getpixel(FB,x,y)Ncolor and getpixel(FB,x,y),Bcolor do spanneedfill:=true;x:=x+1;if spanneedfill then push(x1,y);右端点进栈右端点进栈 span-needfill:=false;while(getpixel(FB,x,y)=B-color or getpixel(
43、FB,x,y)=N-color)and xxright do x:=x+1 ;*在上一条扫描上检查完在上一条扫描上检查完*y:=y2;*在扫描线在扫描线y1上从左向右地检查位于区间上从左向右地检查位于区间 xletft,xright上的象素，其方法与在扫描线上的象素，其方法与在扫描线 y+1上检查的情况完全一样，故略去详情上检查的情况完全一样，故略去详情*出栈完出栈完*算法程序：算法程序：Computer Computer GraphicsGraphics123Computer Computer GraphicsGraphics扫描线种子点填充算法的具体应用。红色圆点代表种子点，扫描填充过程中
44、，在要进栈的像素点的网格上依次标出他们的序号(进栈次序)；或是建立坐标系，写出每一步栈中所有像素的坐标值(有次序)。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16109 8 7 6 5 4 3 2 1Computer Computer GraphicsGraphics 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1611 10 9 8 7 6 5 4 3 2 1Computer Graphics第4章 简单光栅图形生成算法4.5 光栅图形的反走样算法Computer Computer GraphicsGraphics4.5.1 光栅图形
45、的走样现象图形的边界呈阶梯形图形的边界呈阶梯形,图形的细节失真图形的细节失真,狭小图形遗失狭小图形遗失 造成走样的原因：用离散量表示连续量造成走样的原因：用离散量表示连续量引起的引起的因为直线因为直线、多边形多边形、色彩边界等是连续的色彩边界等是连续的,而光栅图形则是由离散的像素点组成而光栅图形则是由离散的像素点组成常见走样形式常见走样形式Computer Computer GraphicsGraphics不光滑不光滑(阶梯状阶梯状)的图形边界的图形边界Computer Computer GraphicsGraphics图形细节失真图形细节失真Computer Computer Graphic
46、sGraphics狭小图形的遗失狭小图形的遗失Computer Computer GraphicsGraphics4.5.2 提高分辨率的反走样方法提高分辨率的方法：提高分辨率的方法：采用硬件:采用高分辨率的光栅图形显示器，花费的代价大。为了提高图形质量,需要克服或减少走样现象,减少这种现象的算法,称为光栅图形的反走样算法反走样算法反走样算法:采用软件:花费的代价小，也容易实现。Computer Computer GraphicsGraphics1.从硬件角度提高分辨率高分辨率显示器v显示器点距减少一倍v帧缓存容量增加到原来的4倍v输带宽提高4倍v扫描转换花4倍时间v代价高Computer C
47、omputer GraphicsGraphics2.从软件角度提高分辨率高分辨率计算，低分辨率显示像素细分技术，相当于后置滤波1 11 11 11 1算术平均1 1 2 22 21 14 42 21 12 21 1加权平均v只能减轻，不能消除Computer Computer GraphicsGraphics低分辨率显示：将一象素内的各个子象素的颜色值或灰度值的平均值作为该象素的颜色值或灰度值。求平均值时可取算术平均，也可取加权平均。用软件提高分辨率的方法是：高分辨率计算，低分辨率显示高分辨率计算，低分辨率显示高分辨率计算：将低分辨的图形显示象素划分为许多子象素，如22划分，33划分等，然后按
48、通常的算法计算出各个子象素的颜色值或灰度值。Computer Computer GraphicsGraphics3.区域采样技术（多边形反走样）改变边或直线的外观，模糊淡化阶梯相当于图像的前置滤波点有限区域直线有宽度Computer Computer GraphicsGraphics根据相交的面积值决定像素显示的亮度级别根据相交的面积值决定像素显示的亮度级别8级灰度0面积1/87/8面积1Computer Graphics第4章 简单光栅图形生成算法4.6 线画图元的属性控制Computer Computer GraphicsGraphics(a)(b)(c)线宽控制线宽控制v线宽控制线宽控制
49、像素复制方法：产生具有宽度的线状图形，可以顺像素复制方法：产生具有宽度的线状图形，可以顺着扫描所生成的单像素线条轨迹，通过像素复制法着扫描所生成的单像素线条轨迹，通过像素复制法来获得来获得 优点：优点：实现简单实现简单缺点：缺点：线段两端要么为水平的，要么是竖直的线段两端要么为水平的，要么是竖直的折线顶点处有缺口折线顶点处有缺口Computer Computer GraphicsGraphics图元的宽度不均匀图元的宽度不均匀Computer Computer GraphicsGraphics移动刷子移动刷子Computer Computer GraphicsGraphics线型控制线型控制v线型控制线型控制1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0例子：PowerPointComputer Computer GraphicsGraphics本本 章章 结结 束！束！Computer Computer GraphicsGraphics此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢