图形学课件第四讲多变形填充

1、 滁州学院滁州学院 国土信息工程系国土信息工程系主讲主讲 孙勇孙勇Email：sunyong_计算机图形学计算机图形学第四章第四章 多边形的扫描转换与区域填充多边形的扫描转换与区域填充4.14.1多边形扫描转换多边形扫描转换4.24.2区域填充区域填充4.14.1多边形的扫描转换与区域填充多边形的扫描转换与区域填充多边形有两种重要的表示方法：顶点表示和点阵表示。多边形有两种重要的表示方法：顶点表示和点阵表示。多边形的扫描转换多边形的扫描转换: :把多边形的顶点表示转换为点阵表示。把多边形的顶点表示转换为点阵表示。区域可采用内点表示和边界表示两种表示形式。区域可采用内点表示和边界表示两种表示形式

2、。区域填充区域填充: :指先将区域的一点赋予指定的颜色，然后将该颜色指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程扩展到整个区域的过程。多边形分为凸多边形、凹多边形、含内环的多边形多边形分为凸多边形、凹多边形、含内环的多边形。4.1.1多边形的扫描转换多边形的扫描转换扫描线算法扫描线算法基本思想：基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成再用要求的颜色显示这些区间的象素，即完成填充工作。填充工作。对于一条扫描线填充过程可以分为四个步骤：对于一条扫描线填充过程可以分为四个步骤：（1

3、1）求交（）求交（2 2）排序）排序（3 3）配对（）配对（4 4）填色）填色判断任意点是否在多边形内判断任意点是否在多边形内l算法思想算法思想 从该点（从该点（x, yx, y）向（）向（ , y, y）引直线，并计算该线与多边形的）引直线，并计算该线与多边形的交点数交点数n(n(自左向右算起自左向右算起) ) if(n%2 = 0) if(n%2 = 0) 则（则（x, yx, y）在多边形外）在多边形外 else else 则（则（x, yx, y）在多边形内）在多边形内 扫描线与多边形的顶点或边界相交时，必须正确的交点的取扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查

4、顶点的两条边的另外两个端点的舍。只需检查顶点的两条边的另外两个端点的y y值。按这两个值。按这两个y y值中大于交点值中大于交点y y值的个数是值的个数是0,1,20,1,2来决定。来决定。123P1P2P3P4l实际上将多边形的每条边与所有扫描线都求交点没有实际上将多边形的每条边与所有扫描线都求交点没有必要的。因为可能大多数扫描线与多边形根本不相交。必要的。因为可能大多数扫描线与多边形根本不相交。为了提高算法效率，应只处理与多边形相交的那些扫为了提高算法效率，应只处理与多边形相交的那些扫描线，同时，交点的计算可以通过增量法来实现描线，同时，交点的计算可以通过增量法来实现扫描线填色法扫描线填色

5、法 一个多边形与若干扫描线 0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)数据结构数据结构活性边表活性边表(AET)(AET)：把与当前扫描线相交的边称为活性边，：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点并把它们按与扫描线交点x x坐标递增的顺序存放在一个坐标递增的顺序存放在一个链表中链表中结点内容结点内容 x x：当前扫描线与边的交点坐标：当前扫描线与边的交点坐标x x：从当前扫描线到下一条扫描线间：从当前扫描线到下一条扫描线间x x的增量的增量ymaxymax：该边所交的最高

6、扫描线号：该边所交的最高扫描线号y ymaxmax 2 0 7 3.5 -1.5 7P6P1P5P6AB 7 2 8 11 0 8P4P5P3P4CDx ymaxx ymaxx ymaxx ymax新边表（新边表（NETNET）：）：存放在该扫描线第一次出现的边。若某边的较低端点为存放在该扫描线第一次出现的边。若某边的较低端点为y yminmin，则该边就放在扫描线则该边就放在扫描线y yminmin的新边表中的新边表中上图所示各条扫描线的新边表上图所示各条扫描线的新边表NETNET 7 6P4P5 P5P6 5 4 3 2 1 0P1P2 P2P3 8 5 -3 2 5 3 3 2 0 7

7、11 0 8 5 2 8 5 -1.5 7P6P1P3P4假定当前扫描线与多边形某一条边的交点的假定当前扫描线与多边形某一条边的交点的x x坐标为坐标为x x，则下一条，则下一条扫描线与该边的交点不要重计算，只要加一个增量扫描线与该边的交点不要重计算，只要加一个增量x x。设该边的直线方程为：设该边的直线方程为：ax+by+c=0ax+by+c=0；若若y yy yi i，x=xx=x i i；则当；则当y = yy = y i+1 i+1时，时，其中其中 为常数为常数;)(111abxcybaxiiiiabx FDC E AB975312468多边形扫描转换多边形扫描转换算法过程(伪代码)v

8、oid polyfillvoid polyfill (polygon, color) (polygon, color) int int color; color; 多边形多边形 polygon;polygon; for ( for (各条扫描线各条扫描线i )i ) 初始化新边表头指针初始化新边表头指针NET iNET i； 把把y y min min = i = i 的边放进边表的边放进边表NET i; NET i; y = y = 最低扫描线号；最低扫描线号； 初始化活性边表初始化活性边表AETAET为空；为空； for (for (各条扫描线各条扫描线i )i ) 把新边表把新边表NET

9、 i NET i 中的边结点用插入排序法插入中的边结点用插入排序法插入AETAET表，使之按表，使之按x x坐标递增顺序排列；坐标递增顺序排列；遍历遍历AETAET表，把配对交点区间表，把配对交点区间( (左闭右开左闭右开) )上的象素上的象素(x, (x, y)y)，用，用drawpixeldrawpixel (x, y, color) (x, y, color) 改写象素颜色值；改写象素颜色值；遍历遍历AETAET表，把表，把y y max max= i = i 的结点从的结点从AETAET表中删除，并把表中删除，并把y y max max i i 结点的结点的x x值递增值递增 x x；

10、若允许多边形的边自相交，则用冒泡排序法对若允许多边形的边自相交，则用冒泡排序法对AETAET表表重新排序；重新排序； / /* * polyfill polyfill * */ /边界标志算法边界标志算法基本思想：基本思想：帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。个区段着上所需颜色。使用一个布尔量使用一个布尔量insideinside来指示当前点是否在多

11、边形内的状来指示当前点是否在多边形内的状态。态。算法过程算法过程void edgemark_fill(polydefvoid edgemark_fill(polydef, color), color)多边形定义多边形定义 polydefpolydef； intint color; color; 对多边形对多边形polydefpolydef 每条边进行直线扫描转换；每条边进行直线扫描转换； inside = FALSE;inside = FALSE; for ( for (每条与多边形每条与多边形polydefpolydef相交的扫描线相交的扫描线y )y ) for ( for (扫描线上每个

12、象素扫描线上每个象素x )x ) if( if(象素象素 x x 被打上边标志被打上边标志) ) inside = ! (inside); inside = ! (inside); if(inside if(inside！= FALSE)= FALSE) drawpixel drawpixel (x, y, color); (x, y, color); else drawpixel else drawpixel (x, y, background); (x, y, background); 用软件实现时，扫描线算法与边界标志算法的执行速度用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同

13、，几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。行速度比有序边表算法快一至两个数量级。2.3.2区域填充算法区域填充算法区域指已经表示成点阵形式的填充图形，它是象素的集合。区域指已经表示成点阵形式的填充图形，它是象素的集合。区域可采用内点表示和边界表示两种表示形式。区域可采用内点表示和边界表示两种表示形式。区域可分为区域可分为4 4向连通区域和向连通区域和8 8向连通区域。向连通区域。区域填充指先将区域的一

14、点赋予指定的颜色，然后将该颜色区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的扩展到整个区域的过程。区域填充算法要求区域是连通的4 4向连通区域和向连通区域和8 8向连通区域向连通区域 四个方向运动四个方向运动 八个方向运动八个方向运动 四连通区域四连通区域 八连通区域八连通区域表示内点表示边界点区域填充的递归算法区域填充的递归算法内点表示的内点表示的4 4连通区域的递归填充算法连通区域的递归填充算法: :void FloodFill4(int x,int y,int oldcolor,int newcolorvoid FloodFill4

15、(int x,int y,int oldcolor,int newcolor) ) if(getpixel(x,y)=oldcolor if(getpixel(x,y)=oldcolor) /) /属于区域内点属于区域内点oldcoloroldcolor drawpixel(x,y,newcolordrawpixel(x,y,newcolor););FloodFill4(x,y+1,oldcolor,newcolor);FloodFill4(x,y+1,oldcolor,newcolor);FloodFill4(x,y-1,oldcolor,newcolor);FloodFill4(x,y-1

16、,oldcolor,newcolor);FloodFill4(x-1,y,oldcolor,newcolor);FloodFill4(x-1,y,oldcolor,newcolor);FloodFill4(x+1,y,oldcolor,newcolor);FloodFill4(x+1,y,oldcolor,newcolor); 边界表示的边界表示的4 4连通区域的递归填充算法连通区域的递归填充算法: :void BoundaryFill4(int x,int y,int boundarycolor,int void BoundaryFill4(int x,int y,int boundaryc

17、olor,int newcolornewcolor) ) int int color; color;if(color!=newcolor & color!=boundarycolorif(color!=newcolor & color!=boundarycolor) ) drawpixel(x,y,newcolordrawpixel(x,y,newcolor););BoundaryFill4 (x,y+1, boundarycolor,newcolorBoundaryFill4 (x,y+1, boundarycolor,newcolor););BoundaryFill4 (x

18、,y-1, boundarycolor,newcolorBoundaryFill4 (x,y-1, boundarycolor,newcolor););BoundaryFill4 (x-1,y, boundarycolor,newcolorBoundaryFill4 (x-1,y, boundarycolor,newcolor););BoundaryFill4 (x+1,y, boundarycolor,newcolorBoundaryFill4 (x+1,y, boundarycolor,newcolor);); 区域填充的扫描线算法区域填充的扫描线算法算法步骤：算法步骤：首先填充种子点所在

19、扫描线上的位于给定区域的首先填充种子点所在扫描线上的位于给定区域的一个区段一个区段然后确定与这一区段相连通的上、下两条扫描线然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。反复这个过程，直到填充结束。(1)(1)初始化：堆栈置空。将种子点（初始化：堆栈置空。将种子点（x x，y y）入栈。）入栈。(2)(2)出栈：若栈空则结束。否则取栈顶元素（出栈：若栈空则结束。否则取栈顶元素（x x，y y），以），以y y作为当作为当前扫描线。前扫描线。(3)(3)填充并确定种子点所在区段：从种子点（填充

20、并确定种子点所在区段：从种子点（x x，y y）出发，沿当前）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为右端点坐标为xlxl和和xrxr。(4)(4)并确定新的种子点：在区间并确定新的种子点：在区间xlxl，xrxr 中检查与当前扫描线中检查与当前扫描线y y上、上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（则把每一区间的最右象素作为种子点压入堆栈，返回第（2 2）步。）步。上述算法

21、对于每一个待填充区段，只需压栈一次；因此，扫描线上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。填充算法提高了区域填充的效率。2.4 字字 符符字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。“美国信息交换用标准代码集”简称ASCII码。它是用7位二进制数进行编码表示128个字符汉字编码的国家标准字符集。每个符号由一个区码和一个位码（2字节）共同标识。区分ASCII码与汉字编码，采用字节的最高位来标识 点阵字符点阵字符:每个字符由一个位图表示矢量字符矢量字符:记录字符的笔画信息点阵字符 点阵字库中的位图表示 矢量轮廓字符111111000

22、1010101010101010111110001010101010101011111110000000000特点：点阵字符：存储量大，易于显示矢量字符：存储量小，美观，变换方便需要光栅化后才能显示。字符属性字符属性字体 宋体 仿宋体 楷体 黑体 隶书字高 宋体 宋体 宋体 宋体字宽字倾斜角倾斜 倾斜对齐 (左对齐、中心对齐、右对齐)字色 红色、绿色、蓝色红色、绿色、蓝色写方式：替换方式。与方式大 海 大 海 大 海 大 海2.5 裁剪裁剪裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪裁剪。2.5.1直线段裁剪2.5.2 多边形裁剪2.5.1直线段裁剪直线段裁剪直线段裁剪算法是复杂图元裁剪的基础。直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而复杂的曲线可