《计算机图形学教学资料6ppt课件》由会员分享，可在线阅读，更多相关《计算机图形学教学资料6ppt课件（60页珍藏版）》请在金锄头文库上搜索。
1、边缘填充算法n思思绪：利利用用求求余余运运算算代代替替交交点点排排序序、配配对、构构造填充区造填充区间。n原原理理：象象素素点点颜色色值经过偶偶数数次次求求余余运运算算后后保保持不持不变，经过奇数次求余运算后奇数次求余运算后变为其余数。其余数。n算法：算法：n以以扫描描线为中心的中心的边缘填充算法填充算法n以以边为中心的中心的边缘填充算法填充算法以扫描线为中心的边缘填充算法基本思想基本思想:对于每一条扫描线和每条多边形边的对于每一条扫描线和每条多边形边的交点交点(xi,yi),将该扫描线上交点右方的所有将该扫描线上交点右方的所有象素取补象素取补.对多边形的每条边做此处理，边对多边形的每条边做此
2、处理，边的顺序随意。的顺序随意。以扫描线为中心的边缘填充算法(1)先将当前扫描线上的所有象素着上指定颜色的补色(2) 当前扫描线上的各交点依次将右方的象素颜色取补色以扫描线为中心的边缘填充算法以扫描线为中心的边缘填充算法以扫描线为中心的边缘填充算法以扫描线为中心的边缘填充算法以扫描线为中心的边缘填充算法以扫描线为中心的边缘填充算法以扫描线为中心的边缘填充算法以扫描线为中心的边缘填充算法对各条扫描线循环上述处理过程。以边为中心的边缘填充算法原始多边形以边为中心的边缘填充算法初始化：将绘图窗口的背景色置为多边形颜色的补色以边为中心的边缘填充算法对非水平边上的每个象素点向右求余以边为中心的边缘填充算
3、法以边为中心的边缘填充算法以边为中心的边缘填充算法优点：与点：与扫描描线算法相比，算法相比，边缘填充算法的填充算法的数据数据结构和程序构和程序结构构简单。缺陷：但缺陷：但该算法需要算法需要对帧缓存的大量象素反存的大量象素反复复赋值，速度，速度较慢。慢。边缘填充算法特点栅栏填充算法栅栏：一条与扫描线垂直的直线，过多边形的某个栅栏：一条与扫描线垂直的直线，过多边形的某个顶点，并把多边形分为左右两半。顶点，并把多边形分为左右两半。基本思想基本思想:对于每条扫描线与多边形边的交点对于每条扫描线与多边形边的交点,仅将交点仅将交点与栅栏之间的象素取补与栅栏之间的象素取补.栅栏填充算法向左求余从0)(xa将
4、当前扫描线上的所有象素着上指定颜色的补色向左求余从1)(xa栅栏填充算法向左求余从2)(xa将当前扫描线上的所有象素着上指定颜色的补色栅栏填充算法向右求余从3)(xa将当前扫描线上的所有象素着上指定颜色的补色栅栏填充算法边标志填充算法(1)n原理：n 当一条直线穿越多边形时，其上各点针对多边形的归属状态将交替变化；若点在多边形外，则在直线与多边形相交一次后，点在多边形内；边标志填充算法(2)n算法步骤：n第一步：多边形各边界线段经扫描转换过程后，对应象素打上边标志；n第二步：n对每一扫描线，由左至右逐点访问：每访问到标志点，则进行一次多边形内/外部的转换，直至扫描线末。n对判别为多边形内部的象
5、素点进行填充；n第三步：第二步循环至扫描结束。n优点：边标志算法进一步改进了栅栏算法,使得算法对每个象素仅访问一次，用硬件实现时速度优势更明显。 扫描线算法：对每条扫描线，首先计算它与扇形区域边界的交点，再把配对交点之间的像素用指定颜色填充。Filling Ellipse Arcs 区域种子填充是指先将区域内的一点(种子点)赋予给定颜色,然后将颜色扩充到整个区域内的过程(染色过程).区域:已经表示成点阵形式的象素集合,具有相同颜色.与多边形扫描转换的比较基本思想边界要求基于的条件区域填充(种子填充算法)n区域的两种表示:内点表示、边界表示.n边界表示:给位于边界上的所有象素着同一种颜色(特征值
6、),而区域内着不同的颜色.区域的表示v 内点表示:给区域内所有象素都着上同一种颜色v (特征值),边界上pixel着不同的颜色. 种子填充算法要求: 区域具有一定的连通性:4连通或8连通。4连通区域: 取区域内任意两点,在该区域内(不能通过区域外的点),若从其中一点出发,通过上、下、左、右 四种运动可到达另一点时,则称该区域为4连通区域.区域连通性区域连通性1）4连通运动方向8连通运动方向区域连通性区域连通性2）区域连通性区域连通性3）边界连通性：边界连通性：4连通区域虽可看作是连通区域虽可看作是8连通区域，连通区域，但其作但其作4连通区域或是连通区域或是8连通区域时其边界不同。连通区域时其边
7、界不同。区域连通性区域连通性4）允许从4个方向搜索下一个象素的填充算法称为是四向填充算法.允许从8个方向搜索下一个象素的填充算法称为是8向填充算法.种子填充算法种子填充算法n递归填充算法填充算法n扫描描线算法算法算法思想：算法思想： 设设G为一内点表示的区域，为一内点表示的区域，(x,y)是是G内一内一点，以点，以(x,y)为种子点，先将为种子点，先将(x,y)置为置为newcolor，然后对，然后对(x,y)的的4(或或8)领域领域进行递归处理，逐步将整个区域进行递归处理，逐步将整个区域G置为置为newcolor.(1)递归算法void FloodFill4(int x, int y, in
8、t oldColor, int newColor) if (GetPixel(x,y)=oldColor) PutPixel(x,y,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); Algorithm12345678910111213141516171819202122Example：优点：算法原理和程序都很简单优点：算法原理和
9、程序都很简单缺陷：效率不高，原因是递归次数太多，区缺陷：效率不高，原因是递归次数太多，区域内的每个象素都引起一次递归，即系统域内的每个象素都引起一次递归，即系统堆栈的一次进出操作，费时费内存。堆栈的一次进出操作，费时费内存。递归算法思想: (1)填充并确定种子点所在的区段； (2)将种子区段压栈; (3)若堆栈非空,栈顶区段出栈;否则算法 终了; (4)填充并确定新的区段, 将其区段信息 压栈，返回第(3)步。(2)扫描线种子填充算法扫描线种子填充算法流程1）n初始化：由指定的种子象素点(x,y)生成种子区段(y,xl,xr),填充并入栈。n (xl,xr分别为种子点所在扫描线上多边形内部区间
10、的左、右端点)n第一步：若种子栈空则算法终止，否则栈顶种子出栈n第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈，n第三步：上述过程循环执行。扫描线种子填充算法流程2）n新种子的确定：在y+1扫描线的xl,xr区间内遍历象素点，对其上非边界且未被填充的象素点，确定其左、右端点并定义为新种子。扫描线种子填充算法流程3）考虑到区域可以是凹的或有内环的，所以可能在该扫描线上出现多个填充区间，亦即需定义多个种子。yy+1同样考虑到凹或有孔的区域，需对扫描线y-1进行同样的处理，获得新的种子。扫描线种子填充算法的改进思路n算法中的回溯过程并非
11、总是必要的。无需进行填充回溯需要进行填充回溯Pattern fillingn用图像(pattern)填充区域v Definition of the pattern:v M X N bitmapsv patternij: the value of the position (i,j)Two issues n the relation of the area of the pattern to that of the primitivenRelative anchor相对锚定）nAbsolute anchor绝对锚定）n write modenTransparent透明写）nOpaque不透明写）
12、Relative anchor(相对锚定）To anchor the pattern at a vertex of the primitive: (x0,y0)valuexy=pattern(x-x0)%M(y-y0)%N(x0,y0)M*N个像素定义的图案Absolute anchor （绝对锚定）M*N个像素定义的图案 To consider the entire screen as being tiled with the pattern and to think of the primitive as consisting of an outline or filled area of
13、 transparent bits that let the pattern show through valuexy=patternx%My%N(x,y)write mode写模式）nFilling with a pattern:n Adding extra control to the part of the scan-conversion algorithm that actually writes each pixelnWrite modenDoing PutPixel with foreground color at a pixel for a 1 in the patternnIn
14、 transparent mode透明写）: n 若图案为0，则不改变屏幕上该象素的颜色不做任何处理）；nIn opaque mode不透明写）：n 若图案为0，则用背景颜色显示该象素：Pattern filling without repeated scan conversionnRectangle writenTo scan convert a primitive first into a rectangular work area, and then to write each pixel from that bitmap to the appropriate place in the
15、canvas.nBe suitable to characters, icons and application symbols(a) Mountain scene(b) Outline of house icon(d)(e)(g)(c) Brick pattern(f)(d) Bitmap for solid version of house icon. (e) Clearing the scene by writing background(f) Brick pattern applied to house icon(g) Writing the screen transparently
16、with patterned house iconAn example: Writing a patterned object in opaque mode with two transparent writesThick primitives 在产生一定宽度的线条时,只需用一个“刷子来替代单象素直线段中扫描生成的单象素即可.线画图元的属性控制Replicating pixels(1) (线刷子)nUsing more than 1 pixel for each column (or row) during scan conversionThick line drawn by column r
17、eplicationvPixels are duplicated in column for lines with 1slope1vPixels are duplicated in rows for all other lines原理:假设直线斜率在-1,+1之间,如图(a)所示.这时可把刷子置成垂直方向图(b).首先将刷子的中点对准直线的一个端点,从该点开始,让刷子中点沿直线的轨迹往直线的另一端点平移即可“刷出具有一定宽度的直线.如图(c).m1m2(a)(b)(c)Replicating Pixels(2)缺陷:(1)线的始末端总是水平或垂直的. (2)线的粗细不一样.水平和垂直线最粗,4
18、5斜线最 细. (3) 当线宽为偶数个时,绘制的线条宽度不精确.Disadvantages 方形刷子是一个宽度为指定线宽的正方形.将正方形的中心对准直线作平移运动即可. m1The Moving Pen(方形刷子)方形刷子The Moving Pen(方形刷子)Thick line drawn by tracing a rectangular pen.Thick line drawn by column replication 该方法将会重复的写象素.为避免重复,可采用与活化边表类似的技术. Disadvantages jj+1 j+2j+3 j+4i-1ii+1i+2i+3i+4jj+1 j
19、+2j+3 j+4i-1ii+1i+2i+3i+4ii+1i+2i+3j, j+2 j, j+2j, j+2(a)ii+1i+2i+3j, j+2 j, j+3j, j+3j+1, j+3(b)Recording spans of the rectangular pen: (a) footprint at x = j + 1; (b) x = j + 2Recording the spans 先算出直线的四个角点的坐标,将其顺序连接成一个四边形,再用区域填充的方法将四边形填充.Filling Areas Between Boundariesn 圆弧线宽的处理n 圆弧线宽的处理与直线类似. 如虚线、实线、点划线等不同线型的处理.Line Style And Pen Style上机作业填充任意多边形或任意扇形区域。对于多边形：要求由用户输入多边形顶点坐标；对于扇形：要求由用户输入扇形的起始角和终止角。（圆心和半径可自定，也可由用户指定）可采用以下几种算法之一：扫描线算法；边标志算法；种子的扫描线算法；
