计算机图形学---多边形填充算法

《计算机图形学---多边形填充算法》由会员分享，可在线阅读，更多相关《计算机图形学---多边形填充算法（79页珍藏版）》请在装配图网上搜索。

1、Computer Graphics第4章 基本光栅图形生成算法4.3 多边形的填充Computer Graphics4.3.1 多边形的表示方法多边形的分类多边形的分类:凸多边形凸多边形凹多边形凹多边形含内环的多边形含内环的多边形表示方法：表示方法：顶点表示和点阵表示顶点表示和点阵表示Computer Graphics4.3.1 多边形的表示方法v该表示几何意义强、占内存少该表示几何意义强、占内存少v但它不能直观地说明哪些像素在多边形内但它不能直观地说明哪些像素在多边形内Computer Graphicsv该方法虽然没有多边形的几何信息该方法虽然没有多边形的几何信息v是面着色所需要的图像表示形

2、式是面着色所需要的图像表示形式Computer Graphics即从多边形的给定边界出发，求出位于其内即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。元素设置相应的灰度或颜色。多边形的填充方法：多边形的填充方法：扫描线方法扫描线方法边缘填充方法边缘填充方法边界标志方法边界标志方法栅栏填充方法栅栏填充方法Computer Graphics01 2 3 4 5 6 71234567yx88 9 10扫描线5P4P1P2P3P5扫描线2I1I2I3I44.3.2 多边形填充的扫描线算法算法特点：算法特点：基本

3、概念：基本概念：充分利用了相邻象素之间的连续性，避免对象素的逐点判充分利用了相邻象素之间的连续性，避免对象素的逐点判断和反复求交运算，减少了计算量，提高了算法速度，是断和反复求交运算，减少了计算量，提高了算法速度，是效率较高的多边形填充算法，处理对象为非自交多边形。效率较高的多边形填充算法，处理对象为非自交多边形。区域的连续性区域的连续性扫描线的连续性扫描线的连续性边的连续性边的连续性关于一般多边形的填充过程关于一般多边形的填充过程,对于一条扫描线对于一条扫描线,可分为四步可分为四步:v求交求交v排序排序v交点配对交点配对v区间填色区间填色奇点的处理奇点的处理Computer Graphics

4、区域的连续性区域的连续性 设多边形设多边形P的顶点的顶点,1,0),(niyxPiiiniiiyyy1010 ,1nkyykkii各顶点各顶点Pi的纵坐标的纵坐标yi的递减数列的递减数列p0p1p7p2p3p4p5p6p8p1,p7,p3,p6,p2,p5,p0,p4,p8p1,p7,p3,p6,p2,p5,p0,p4,p8Computer Graphics (1)梯形的两底边分别在梯形的两底边分别在y=和和y=两条扫描线上，腰在多边两条扫描线上，腰在多边 形形P的边上或在显示屏幕的边界上。的边上或在显示屏幕的边界上。kiy1kiy),(iiyx它们具有下列性质它们具有下列性质(设设 为整数为

5、整数)：(2)梯形可分为两类：一类位于多边形梯形可分为两类：一类位于多边形P的内部；另一的内部；另一类在多边形类在多边形P的外部。的外部。1kiykiy(3)两类梯形在长方形区域两类梯形在长方形区域 ，内相间的排列。内相间的排列。位于位于y=y=和和y=y=两条扫描线之间的长方形区域被多边形两条扫描线之间的长方形区域被多边形P的边的边分割成若干梯形分割成若干梯形kiy1kiyp0p1p7p2p3p4p5p6p8由区域的相关性知由区域的相关性知当知道一个区域内一点与多边形的位置关系，即可确定该区域当知道一个区域内一点与多边形的位置关系，即可确定该区域内所有点与多边形之间的内外关系内所有点与多边形

6、之间的内外关系kiyy 1kiyyComputer Graphics扫描线的连续性扫描线的连续性扫描线的连续性是区域连续性在扫描线上的体现扫描线的连续性是区域连续性在扫描线上的体现012345678设设e为一整数为一整数 e 若扫描线若扫描线y=e与多边形与多边形P的边的边Pi-1Pi相交，则记其交点的横相交，则记其交点的横坐标为坐标为0iyniyeixy=eleieieieixxxx,321该扫描线与该扫描线与P的边界各交点横坐标的递增序列的边界各交点横坐标的递增序列1ex8ex7ex2ex3ex4ex此交点序列具有以下性质：此交点序列具有以下性质：(1)l是偶数是偶数(2)(2)扫描线被分

7、成好多区段扫描线被分成好多区段,一部一部分在多边形内分在多边形内,一部分在多边形外一部分在多边形外(3)(3)两类线段间隔排列两类线段间隔排列由区域的连贯性和由区域的连贯性和扫描线的连续性知扫描线的连续性知:若已知某一点与多边形的位置关系若已知某一点与多边形的位置关系,就可知该点所在线段与就可知该点所在线段与多边形的位置关系多边形的位置关系Computer Graphics边的连续性边的连续性若若d为一整数，为一整数，d=e1，且，且yi0yyin；设位于扫描线；设位于扫描线y=d上的交点序列为上的交点序列为kdidididixxxx,321012345678y=e1ex8ex7ex2ex3e

8、x4exy=d1dx8dx7dx2dx3dx4dx则两交点则两交点序列之间有以下关系序列之间有以下关系:1 两序列元素的个数相等两序列元素的个数相等2 点点()与与()位于多边形位于多边形P的同的同一边上，即一边上，即exrei,dxrdi,rrridieimxx1以上性质称为以上性质称为边的连续性边的连续性Computer Graphicsv奇点定义奇点定义 如果如果 ，则称顶点则称顶点Pi为极值点；为极值点；否则称否则称Pi为非极值点。为非极值点。0)(11iiiiyyyy奇点的处理奇点的处理当扫描线与多边形当扫描线与多边形P的边界的的边界的交点是交点是P的顶点的顶点时，时，则称该交点为则

9、称该交点为奇点奇点p0p1p7p2p3p4p5p6p8要把奇点作为几个交点来处理呢要把奇点作为几个交点来处理呢?v多边形多边形P P的顶点可分为两类：的顶点可分为两类：极值点极值点和和非极值点非极值点Computer Graphics 如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数。若如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数。若将每一奇点都简单地计为两个交点，同样会导致反常的结果将每一奇点都简单地计为两个交点，同样会导致反常的结果 为了使为了使交点个数交点个数保持保持为偶数为偶数,规定当规定当奇点奇点是是P P的的极值点极值点时，该点按时，该点按两个两个交点计算；交点

10、计算；否则否则按按一个一个交点计算。交点计算。预处理预处理:若若Pi是非极值点，则将是非极值点，则将 两边中位于扫描线两边中位于扫描线y=yi上方的那条边在上方的那条边在Pi点处截去点处截去一单位长一单位长 11,iiiippppComputer Graphics扫描线算法的数据结构和实现步骤扫描线算法的数据结构和实现步骤Computer Graphics扫描线算法的数据结构扫描线算法的数据结构多边形P0P1P2P3P4P5P6P0数据结构数据结构边的边的分类表分类表ETET和边的和边的活化链表活化链表AELAELET和AEL中的多边形的边由四个域四个域组成：ymax 边的上端点的边的上端点的

11、y坐标坐标在在ET中为边的下端点的中为边的下端点的x坐标坐标x在在 AEL中是边与扫描线交点的中是边与扫描线交点的x坐标坐标x边的斜率的倒数边的斜率的倒数next指向下一条边的指针指向下一条边的指针Computer GraphicsP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)多边形P0P1P2P3P4P5P6P0Computer GraphicsP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)对奇点采用了预处理的边y筒分类表分类表ETET是按边下端点的纵坐标是按边

12、下端点的纵坐标y y对边进行分类的对边进行分类的指针数组指针数组同一类中，各边按同一类中，各边按x值递增的顺序排列成行值递增的顺序排列成行下端点的纵坐标下端点的纵坐标y y等于等于i i的边归入第的边归入第i i类，水平边除外类，水平边除外Computer GraphicsP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)多边形P0P1P2P3P4P5P6P0对奇点采用了预处理的边y筒Computer Graphics边的活化链表边的活化链表AELAEL由与由与当前扫描线相交的当前扫描线相交的所有多边形的边组成所有多边形的边组成-5

13、/357AELe7e54212AEL在在y=2扫描线上扫描线上的当前状态的当前状态它记录了多边形它记录了多边形沿扫描线的交点序列沿扫描线的交点序列,并根据递推关系并根据递推关系,不断地更新交点序列不断地更新交点序列它是一个它是一个动态动态列表，新边插入，旧边删除列表，新边插入，旧边删除P0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)Computer GraphicsP0P1P2P3P4P5 P6=(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)-5/35AELe7e54214AEL在在y=3扫描线上

14、扫描线上的当前状态的当前状态163-5/35AELe7e54216AEL在在y=4扫描线上扫描线上的当前状态的当前状态E4边做了预处理边做了预处理(也也可以不做预处理，但可以不做预处理，但要清楚的知道此点要要清楚的知道此点要在在AEL中计几次中计几次)113Computer Graphics扫描线算法实现步骤扫描线算法实现步骤 步骤步骤1:(AEL1:(AEL初始化初始化)将边的活化链表将边的活化链表AELAEL设置为空设置为空。步骤步骤2:(y初始化初始化)取扫描线取扫描线纵坐标纵坐标y的初始值为的初始值为ET中非空元素的中非空元素的最小序号最小序号 步骤步骤3：按：按从下到上的顺序从下到上

15、的顺序对纵坐标值为对纵坐标值为y的扫描线的扫描线(当前扫描线当前扫描线)执执行下列步骤，直到边的分类表行下列步骤，直到边的分类表ET和边的活化链表和边的活化链表AEL都都变成空为止变成空为止。v(1)如边分类表如边分类表ET中的第中的第y类元素非空，则将类元素非空，则将属于该类的所有属于该类的所有边从边从ET中取出并插入边的活化链表中取出并插入边的活化链表AEL中，中，AEL中的各边按照中的各边按照x值值(当当x的值相等时，按的值相等时，按x值值)递增方向排序递增方向排序。v(2)若相对于当前扫描线，边的活化链表若相对于当前扫描线，边的活化链表AEL非空，则非空，则将将AEL中中的边两两依次配

16、对的边两两依次配对，即第，即第1，2边为一对，第边为一对，第3，4边为一对，依此边为一对，依此类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点依次对这些区段上的点(象素象素)按多边形属性按多边形属性着色着色。v(3)将边的活化链表将边的活化链表AEL中满足中满足y=ymax的边删去的边删去。v(4)将边的活化链表将边的活化链表AEL剩下的剩下的每一条边的每一条边的x域累加域累加x，即，即x=x+x。v(5)将当前的扫描线的将当前的扫描线的纵坐标值纵坐标值y累加累加，即，即y=y+1Computer Grap

17、hics扫描线算法实现步骤伪代码扫描线算法实现步骤伪代码Polygonfill(polydef,color)Polygonfill(polydef,color)Int colorInt color多边形定义多边形定义 polydefpolydef for(for(各条扫描线各条扫描线I)I)初始化新边表表头指针初始化新边表表头指针ETI;ETI;把把ymin=Iymin=I的边放进边表的边放进边表ETI;ETI;y=y=最低扫描线号最低扫描线号;初始化活化边表初始化活化边表AELAEL为空为空;for(for(各条扫描线各条扫描线I)I)把新边表把新边表ETIETI中的边结点用插入排序法插入中

18、的边结点用插入排序法插入AELAEL表表,使使 之按之按x x递增顺序排列递增顺序排列;遍历遍历AETAET表表,把配对交点之间的区间上的各像素把配对交点之间的区间上的各像素(x,y)(x,y)用待填颜色改写用待填颜色改写 遍历遍历AETAET表表,把把ymax=Iymax=I的结点从的结点从AELAEL中删除中删除,并把并把ymaxIymaxI的结点的的结点的 x x递增递增dx;dx;若允许多边形的边自交若允许多边形的边自交,则用冒泡排序法对则用冒泡排序法对AELAEL表重新排序表重新排序;Computer Graphics扫描线算法特点扫描线算法特点v数据结构较复杂数据结构较复杂v但充分

19、利用了扫描线、多边形边的连续性但充分利用了扫描线、多边形边的连续性,避免避免了反复求交点的运算了反复求交点的运算,是一种较快的填充方法是一种较快的填充方法v对各种表的维持和排序开销太大，适合软件对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现实现而不适合硬件实现Computer Graphics 优点：优点：对每个像素只访问一次对每个像素只访问一次 与设备无关与设备无关v缺点：缺点：数据结构复杂数据结构复杂 只适合软件实现只适合软件实现Computer Graphicsyx0123456789101112345678P6P4P1P5P2P3例习题例习题1：用扫描线算法来扫描转换一个多

20、边形Computer Graphics边的Y筒ET5432125-3353720811075-3/2852yx0 1 2 3 4 5 6 7 8 9 10 1112345678P6P4P1P5P2P3Computer Graphics边的活化链表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 Graphicsyx0123456789101112345678P6P4P1P5P2P3例习题例习题1：Computer Graphics 设现在要用扫描线算法来

21、扫描转换一个多边形，该多边形的顶点分别为，如图所示。先写出边y桶，然后试给出边的活化链表AEL,AEL,完成扫描转换完成扫描转换12345(1,1),(8,1),(8,6),(5,3),(1,7)PPPPPComputer GraphicsComputer Graphics4.3.3 边缘填充算法采用对图像进行逐位求反逐位求反的方法，免去对边排序的工作量算法特点算法特点:预备知识：预备知识：对图像对图像M M作偶数次求反运算，其结果还是作偶数次求反运算，其结果还是M M;而对而对M M作奇数次作奇数次求反运算的结果是反的求反运算的结果是反的在光栅图形中，如某区域已着上值为在光栅图形中，如某区域

22、已着上值为M的某种颜色，则上述的某种颜色，则上述求反运算得到的结果是：求反运算得到的结果是：对区域作偶数次求反运算后，该区域的颜色不变对区域作偶数次求反运算后，该区域的颜色不变；作奇数次求反运算后，该区域的颜色则变成值为作奇数次求反运算后，该区域的颜色则变成值为 的颜色。的颜色。MComputer Graphics边缘填充算法的实现边缘填充算法的实现对多边形对多边形P的的每一非水平边每一非水平边（i=0,1,n）上的各像素）上的各像素做向右求反运算即可做向右求反运算即可01234122334340Computer GraphicsComputer Graphics边缘填充算法分析边缘填充算法分

23、析 优点：优点：最适合于有帧缓存的显示器可按任意顺序处理多边形的边仅访问与该边有交点的扫描线上右方的像素，算法简单 缺点：缺点：对复杂图形，每一像素可能被访问多次，输入/输出量大图形输出不能与扫描同步进行，只有全部画完才能打印Computer Graphics4.3.4 栅栏填充算法此算法是为了减少边缘算法访问像素的次数而提出的此算法是为了减少边缘算法访问像素的次数而提出的栅栏栅栏:是一条与扫描线垂直的直线是一条与扫描线垂直的直线,栅栏的位置通常栅栏的位置通常取过多边形顶点取过多边形顶点,能把多边形分为左右两半能把多边形分为左右两半栅栏填充的基本思想栅栏填充的基本思想:对于每个扫描线与多边形边

24、的交点,就将交点与栅栏之间的像素取补.若交点位于栅栏若交点位于栅栏左左边边,则将则将交点之右交点之右,栅栏之左栅栏之左的所有像素取补的所有像素取补若交点位于栅栏若交点位于栅栏右右边边,则将则将交点之左交点之左,栅栏之右栅栏之右的所有像素取补的所有像素取补Computer Graphics栅栏填充的具体实现栅栏填充的具体实现:01234栅栏线12栅栏线34栅栏线23栅栏线4栅栏线0Computer Graphics边界标志法:先画边界后填色，使对帧缓冲器中的每个元素的赋值次数不超过2次。基本思想是：先用一种特殊的颜色在帧缓冲器中将多边形的边界(水平边的部分边界除外)勾画出来。然后再采用和扫描线算

25、法类似的方法将位于多边形内的各个区段着上所需的颜色 图边界标志算法的运行过程4.3.5 边界标志算法Computer Graphics边界标志法具体实现图边界标志算法的运行过程步骤1：以值为boundary-color 的特殊颜色勾画多边形P的边界。设多边形顶点为Pi=(xi,yi),0in，xi,yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。步骤2：设interior_point 是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形P内，则interior_point=true，需要填上值为polygon_color的颜色；否

26、则该像素在多边 形 P 外，需 要 填 上 值 为background_color的颜色 Computer Graphics边界标志算法实例边界标志算法实例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=6 Y=7 Y=8 Y=9 Y=10Computer Graphics算法实现算法实现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(y

27、i=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,RGB(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

28、);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,255,255);/在多边形外部填充色白色 Computer Graphics算法特点分析：算法特点分析：1 1 本算法避免了对帧缓存的大量元素的赋值本算法避免了对帧缓存的大量元素的赋值2 2 但需逐条扫描线并对帧缓存中的元素进行搜索和比较但需逐条扫描线并对帧缓存中的元素进行搜索和比较

29、3 3 当算法生成的边界不封闭时，在一条扫描线上必须当算法生成的边界不封闭时，在一条扫描线上必须有偶数个具有边界颜色的点有偶数个具有边界颜色的点Computer Graphics第4章 基本光栅图形生成算法4.4 区域填充Computer Graphics4.4.1 区域的基本概念 是指已经表示成点阵形式的像素集合。是指已经表示成点阵形式的像素集合。区域区域区域的表示方式区域的表示方式在光栅图形中，有在光栅图形中，有内点内点表示法和表示法和边界边界表示法表示法Computer Graphics：把位于给定把位于给定区域内的所有像素一一列举区域内的所有像素一一列举出来出来的方法称为内点表示法的方

30、法称为内点表示法。：把位于把位于给定区域给定区域边界上的像素边界上的像素一一列举出来一一列举出来的方法称的方法称为边界表示法为边界表示法。Computer Graphics是指先将区域内的一点是指先将区域内的一点(常称种子点常称种子点)赋予给定赋予给定颜色，然后将这种颜色扩展颜色，然后将这种颜色扩展到整个区域内的到整个区域内的过程。过程。区域填充区域填充一个封闭区域确定以后一个封闭区域确定以后,填充要解决的问题是填充要解决的问题是如何确定填充的像素以及如何高效地填充。如何确定填充的像素以及如何高效地填充。Computer Graphics 4连通的区域连通的区域:取区域内任意两点取区域内任意两

31、点，在该区域内若从其中一点出发通过在该区域内若从其中一点出发通过、四种四种运动可到达另运动可到达另一点一点。四个方向的运动8连通区域连通区域:取区域内取区域内任意两点任意两点，若从其中任一点出发，在该区若从其中任一点出发，在该区域内通过沿域内通过沿方向、方向、方方向和向和方向的方向的八种八种运动可运动可到达另一点到达另一点。8个方向的运动区域的连通性区域的连通性Computer Graphics4连通区域可理解为连通区域可理解为8连通区域，但他们的连通区域，但他们的边界边界不尽相同不尽相同。四连通区域的边界是八连通的四连通区域的边界是八连通的八连通区域的边界是四连通的八连通区域的边界是四连通的

32、Computer Graphics4.4.2 简单的种子填充算法基本思想：1 1 给定区域给定区域G一种子点（一种子点（x,y）2 2 判断该点是否是区域内的一点判断该点是否是区域内的一点如果是，则将该点填充为新的颜色如果是，则将该点填充为新的颜色3 3 然后将该点周围的四个点（四连通）或八个然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理点（八连通）作为新的种子点进行同样的处理4 4 通过这种扩散完成对整个区域的填充通过这种扩散完成对整个区域的填充 Computer Graphics简单的种子填充算法简单的种子填充算法（4连通）连通）v种子像素入栈种子像素入栈v

33、当栈非空时，重复以下步骤：当栈非空时，重复以下步骤：栈顶像素出栈栈顶像素出栈 将出栈象素置成填充色将出栈象素置成填充色 按左、上、右、下顺序检查与出栈象素相邻的按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈填充色，则将其入栈 算法演示算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799Computer Graphics按右、上、左、下的顺序进栈Computer GraphicsComputer Graphics区域连通方

34、式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果Computer Graphics算法分析：算法分析：1有些象素会入栈多次，降低算法效率；栈结构占空间。2递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。种子算法充分利用了递归调用递归调用的机理，在前一种子点确定并变为新颜色后，按照自身调用的八(四）向顺序依次查找新的种子点，找到即变为新颜色，继续下一种子的查找。未查的方向被压栈保存，等退栈时继续查找，最终完成蔓延至整个区域所有点都变为新颜色。改进算法，减少递归次数，提高效率。改进算法，减少递归次数，

35、提高效率。方法之一使用扫描线填充算法；方法之一使用扫描线填充算法；Computer Graphics4.4.3 扫描线种子填充算法v从给定的种子点开始，填充当前扫描线上种从给定的种子点开始，填充当前扫描线上种子点所在的区间子点所在的区间基本思想：基本思想：v然后确定与这一区间相邻的上下两条扫描线然后确定与这一区间相邻的上下两条扫描线上需要填充的区间上需要填充的区间v从这些区间上各取一个种子点并把他们保存从这些区间上各取一个种子点并把他们保存起来，作为下次填充的种子点起来，作为下次填充的种子点v反复这个过程，直到所保存的各区间都填充反复这个过程，直到所保存的各区间都填充完毕完毕Computer

36、Graphics算法步骤：算法步骤：步骤步骤 1：将算法设置的堆栈置为空。将给定的种子点将算法设置的堆栈置为空。将给定的种子点（x,y）压入堆栈）压入堆栈步骤步骤 2：如果堆栈为空，算法结束；否则取栈顶元素（如果堆栈为空，算法结束；否则取栈顶元素（x,y）作为种子点作为种子点步骤步骤 3：从种子点（从种子点（x,y）开始，沿纵坐标为）开始，沿纵坐标为y的当前扫描的当前扫描线线逐个像素用新的颜色值进行填充，直到逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为边界为止。设区间两边界的横坐标分别为xleft 和和xright。步骤步骤4 4：在与当前扫描线相邻的上下两条扫描线上

37、，在与当前扫描线相邻的上下两条扫描线上，求出需要填充的各小区间，把各小区，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤间中最右边的点并作为种子点压入堆栈，转到步骤2 2。Computer Graphics具体实现过程具体实现过程图3.32扫描线种子填充算法的执行过程1212123对于每一个待填充区段，只需压栈一次；而在递归算法中，每个对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。12Computer Graphics种子点位置不同种子点位置

38、不同3Computer Graphicswhile 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*保存线段的左端

39、点保存线段的左端点*x:=xleft;y:=y+1;while x=xright do spanneedfill:=false;算法程序：算法程序：Computer Graphicswhile 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(FB,x,y)=N-color)

40、and xxright do x:=x+1 ;*在上一条扫描上检查完在上一条扫描上检查完*y:=y2;*在扫描线在扫描线y1上从左向右地检查位于区间上从左向右地检查位于区间 xletft,xright上的象素，其方法与在扫描线上的象素，其方法与在扫描线 y+1上检查的情况完全一样，故略去详情上检查的情况完全一样，故略去详情*出栈完出栈完*算法程序：算法程序：Computer Graphics123Computer Graphics扫描线种子点填充算法的具体应用。红色圆点代表种子点，扫描填充过程中，在要进栈的像素点的网格上依次标出他们的序号(进栈次序)；或是建立坐标系，写出每一步栈中所有像素的坐

41、标值(有次序)。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16109 8 7 6 5 4 3 2 1Computer Graphics 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 Graphics4.5.1 光栅图形的走样现象图形的边界呈阶梯形图形的边界呈阶梯形,图形的细节失真图形的细节失真,狭小图形遗失狭小图形遗失 造成走样的原因：用离散量表示连续量造成走样的原因：用离散量表示连

42、续量引起的引起的因为直线因为直线、多边形多边形、色彩边界等是连续的色彩边界等是连续的,而光栅图形则是由离散的像素点组成而光栅图形则是由离散的像素点组成常见走样形式常见走样形式Computer Graphics 不光滑不光滑(阶梯状阶梯状)的图形边界的图形边界Computer Graphics 图形细节失真图形细节失真Computer Graphics 狭小图形的遗失狭小图形的遗失Computer Graphics4.5.2 提高分辨率的反走样方法提高分辨率的方法：提高分辨率的方法：采用硬件:采用高分辨率的光栅图形显示器，花费的代价大。为了提高图形质量,需要克服或减少走样现象,减少这种现象的算法

43、,称为光栅图形的反走样算法反走样算法反走样算法:采用软件:花费的代价小，也容易实现。Computer Graphics 1.从硬件角度提高分辨率高分辨率显示器v 显示器点距减少一倍v 帧缓存容量增加到原来的4倍v 输带宽提高4倍v 扫描转换花4倍时间v 代价高Computer Graphics 2.从软件角度提高分辨率高分辨率计算，低分辨率显示像素细分技术，相当于后置滤波1 11 11 11 1算术平均1 1 2 22 21 14 42 21 12 21 1加权平均v 只能减轻，不能消除Computer Graphics低分辨率显示：将一象素内的各个子象素的颜色值或灰度值的平均值作为该象素的颜

44、色值或灰度值。求平均值时可取算术平均，也可取加权平均。用软件提高分辨率的方法是：高分辨率计算，低分辨率显示高分辨率计算，低分辨率显示高分辨率计算：将低分辨的图形显示象素划分为许多子象素，如22划分，33划分等，然后按通常的算法计算出各个子象素的颜色值或灰度值。Computer Graphics 3.区域采样技术（多边形反走样）改变边或直线的外观，模糊淡化阶梯相当于图像的前置滤波点有限区域直线有宽度Computer Graphics根据相交的面积值决定像素显示的亮度级别根据相交的面积值决定像素显示的亮度级别8级灰度0面积1/87/8面积1Computer Graphics第4章 简单光栅图形生成

45、算法4.6 线画图元的属性控制Computer Graphics(a)(b)(c)线宽控制线宽控制v线宽控制线宽控制 像素复制方法：产生具有宽度的线状图形，可以顺像素复制方法：产生具有宽度的线状图形，可以顺着扫描所生成的单像素线条轨迹，通过像素复制法着扫描所生成的单像素线条轨迹，通过像素复制法来获得来获得 优点：优点：实现简单实现简单 缺点：缺点：线段两端要么为水平的，要么是竖直的线段两端要么为水平的，要么是竖直的 折线顶点处有缺口折线顶点处有缺口Computer Graphics 图元的宽度不均匀图元的宽度不均匀Computer Graphics 移动刷子移动刷子Computer Graphics线型控制线型控制v线型控制线型控制1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0例子：PowerPointComputer Graphics本本 章章 结结 束！束！