计算机图形学边缘填充算法

计算机图形学边缘填充算法第一页，共六十三页，2022年，8月28日基本思想:对于每一条扫描线和每条多边形边的交点(x1,y1),将该扫描线上交点右方的所有象素取补.对多边形的每条边做此处理,多边形的顺序随意.该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大.••边缘填充算法第二页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法基本思想:对于每一条扫描线和每条多边形边的交点(x1,y1),将该扫描线上交点右方的所有象素取补.对多边形的每条边做此处理,

多边形的顺序随意.第三页，共六十三页，2022年，8月28日将当前扫描线上的所有象素着上指定颜色的补色以扫描线为中心的边缘填充算法第四页，共六十三页，2022年，8月28日向右求余从1)(xa以扫描线为中心的边缘填充算法第五页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第六页，共六十三页，2022年，8月28日向右求余从2)(xc以扫描线为中心的边缘填充算法第七页，共六十三页，2022年，8月28日向右求余从2)(xc以扫描线为中心的边缘填充算法第八页，共六十三页，2022年，8月28日向右求余从3)(xd以扫描线为中心的边缘填充算法第九页，共六十三页，2022年，8月28日向右求余从3)(xd以扫描线为中心的边缘填充算法第十页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第十一页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法将当前扫描线上的所有象素着上指定颜色的补色第十二页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法将当前扫描线上的所有象素着上指定颜色的补色第十三页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第十四页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第十五页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第十六页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第十七页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第十八页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法第十九页，共六十三页，2022年，8月28日以扫描线为中心的边缘填充算法对各条扫描线循环上述处理过程。第二十页，共六十三页，2022年，8月28日以边为中心的边缘填充算法原始多边形第二十一页，共六十三页，2022年，8月28日以边为中心的边缘填充算法初始化：将绘图窗口的背景色置为多边形颜色的补色第二十二页，共六十三页，2022年，8月28日以边为中心的边缘填充算法对非水平边上的每个象素点向右求余第二十三页，共六十三页，2022年，8月28日以边为中心的边缘填充算法第二十四页，共六十三页，2022年，8月28日以边为中心的边缘填充算法第二十五页，共六十三页，2022年，8月28日以边为中心的边缘填充算法第二十六页，共六十三页，2022年，8月28日

该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大.

栅栏填充算法

基本思想:对于每个扫描线与多边形边的交点,仅将交点与栅栏之间的象素取补.边缘填充算法特点第二十七页，共六十三页，2022年，8月28日栅栏填充算法向左求余从0)(xa将当前扫描线上的所有象素着上指定颜色的补色第二十八页，共六十三页，2022年，8月28日向左求余从1)(xa栅栏填充算法第二十九页，共六十三页，2022年，8月28日向左求余从2)(xa将当前扫描线上的所有象素着上指定颜色的补色栅栏填充算法第三十页，共六十三页，2022年，8月28日向右求余从3)(xa将当前扫描线上的所有象素着上指定颜色的补色栅栏填充算法第三十一页，共六十三页，2022年，8月28日

边标志算法进一步改进了栅栏算法,使得算法对每个象素仅访问一次.

边标志算法分两步进行:

对多边形边界上的象素打上边标志;

填充.边标志算法第三十二页，共六十三页，2022年，8月28日

扫描线算法：对每条扫描线，首先计算它与扇形区域边界的交点，再把配对交点之间的像素用指定颜色填充。FillingEllipseArcs第三十三页，共六十三页，2022年，8月28日区域（种子）填充是指先将区域内的一点(种子点)赋予给定颜色,然后将颜色扩充到整个区域内的过程(染色过程).区域:已经表示成点阵形式的象素集合,具有相同颜色.区域填充(种子填充算法)第三十四页，共六十三页，2022年，8月28日区域的两种表示:内点表示、边界表示.边界表示:给位于边界上的所有象素着色,而区域内不着色.区域的表示内点表示:给区域内所有象素都着上同一种颜色

(特征值),边界上pixel不着色.第三十五页，共六十三页，2022年，8月28日要求:

区域具有一定的连通性:4连通或8连通4连通区域:取区域内任意两点,在该区域内(不能通过区域外的点),若从其中一点出发,通过上、下、左、右四种运动可到达另一点时,则称该区域为4连通区域.区域连通性（1）第三十六页，共六十三页，2022年，8月28日4连通运动方向8连通运动方向区域连通性（2）第三十七页，共六十三页，2022年，8月28日区域连通性（3）允许从4个方向搜索下一个象素的填充算法称为是四向填充算法允许从8个方向搜索下一个象素的填充算法称为是8向填充算法第三十八页，共六十三页，2022年，8月28日算法思想：

设G为一内点表示的区域，(x,y)是G内一点，以(x,y)为种子点，先将(x,y)置为newcolor，然后对(x,y)的4(或8)领域进行递归处理，逐步将整个区域G置为newcolor.(1)递归算法第三十九页，共六十三页，2022年，8月28日递归填充算法初始化：种子象素入栈第一步：栈顶象素出栈，作为种子点；第二步：种子点被置为填充色；第三步：按照上、下、左、右顺序检查与种子点相邻的象素：若非边界且未被填充，则入栈（8向连通区域需考虑更多相邻象素）。若栈不空，则重复第一步。第四十页，共六十三页，2022年，8月28日voidFloodFill4(intx,inty,intoldColor,intnewColor)

{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);}

}

Algorithm第四十一页，共六十三页，2022年，8月28日12345678910111213141516171819202122Example：第四十二页，共六十三页，2022年，8月28日算法:(1)填充并确定种子点所在的区段；

(2)将种子区段压栈;(3)若堆栈非空,栈顶区段出栈;否则算法结束;(4)填充并确定新的区段,将其区段信息压栈.(2)扫描线算法第四十三页，共六十三页，2022年，8月28日扫描线种子填充算法流程（1）初始化：由指定的种子象素点(x,y)生成种子(y,xl,xr),填充并入栈。

(xl,xr分别为种子点所在扫描线上多边形内部区间的左、右端点)第一步：若种子栈空则算法终止，否则栈顶种子出栈第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈第三步：上述过程循环执行。第四十四页，共六十三页，2022年，8月28日扫描线种子填充算法流程（2）考虑到区域可以是凹的或有内环的，所以可能在该扫描线上出现多个填充区间，亦即需定义多个种子。yy+1同样考虑到凹或有孔的区域，需对扫描线y-1进行同样的处理，获得新的种子。第四十五页，共六十三页，2022年，8月28日扫描线种子填充算法的改进思路算法中的回溯过程并非总是必要的。无需进行填充回溯需要进行填充回溯第四十六页，共六十三页，2022年，8月28日Patternfilling用图象(pattern)填充区域

Definitionofthepattern:MXNbitmapspattern[i][j]:thevalueoftheposition(i,j)第四十七页，共六十三页，2022年，8月28日Twoissues

therelationoftheareaofthepatterntothatoftheprimitiveRelativeanchorAbsoluteanchorwritemodeTransparentOpaque第四十八页，共六十三页，2022年，8月28日RelativeanchorToanchorthepatternatavertexoftheprimitive:(x0,y0)value[x][y]=pattern[(x-x0)%M][(y-y0)%N](x0,y0)MN个像素定义的图案第四十九页，共六十三页，2022年，8月28日AbsoluteanchorMN个像素定义的图案

Toconsidertheentirescreenasbeingtiledwiththepatternandtothinkoftheprimitiveasconsistingofanoutlineorfilledareaoftransparentbitsthatletthepatternshowthroughvalue[x][y]=pattern[x%M][y%n](x,y)第五十页，共六十三页，2022年，8月28日writemodeFillingwithapattern:Addingextracontroltothepartofthescan-conversionalgorithmthatactuallywriteseachpixelWritemodeDoingPutPixelwithforegroundcoloratapixelfora1inthepatternIntransparentmode:

若为0，则不改变屏幕上该象素的颜色（不做任何处理）；Inopaquemode

若为0，则用背景色显示该象素第五十一页，共六十三页，2022年，8月28日PatternfillingwithoutrepeatedscanconversionRectanglewriteToscanconvertaprimitivefirstintoarectangularworkarea,andthentowriteeachpixelfromthatbitmaptotheappropriateplaceinthecanvas.TwiceasmuchworkasfillingduringscanconversionBesuitabletocharacters,iconsandapplicationsymbols第五十二页，共六十三页，2022年，8月28日(a)Mountainscene(b)Outlineofhouseicon(d)(e)(g)(c)Brickpattern(f)(d)Bitmapforsolidversionofhouseicon.(e)Clearingthescenebywritingbackground(f)Brickpatternappliedtohouseicon(g)WritingthescreentransparentlywithpatternedhouseiconAnexample:Writingapatternedobjectinopaquemodewithtwotransparentwrites第五十三页，共六十三页，2022年，8月28日Thickprimitives

在产生一定宽度的线条时,只需用一个“刷子”来替代单象素直线段中扫描生成的单象素即可.线画图元的属性控制第五十四页，共六十三页，2022年，8月28日Replicatingpixels(1)(线刷子)Usingmorethan1pixelforeachcolumn(orrow)duringscanconversionThicklinedrawnbycolumnreplicationPixelsareduplicatedincolumnforlineswith–1<slope<1Pixelsareduplicatedinrowsforallotherlines第五十五页，共六十三页，2022年，8月28日原理:假设直线斜率在[-1,+1]之间,如图(a)所示.这时可把刷子置成垂直方向图(b).首先将刷子的中点对准直线的一个端点,从该点开始,让刷子中点沿直线的轨迹往直线的另一端点平移即可“刷出”具有一定宽度的直线.如图(c).m1m2(a)(b)(c)ReplicatingPixels(2)第五十六页，共六十三页，2022年，8月28日缺点:(1)线的始末断总是水平或垂直的.(2)线的粗细不一样.水平和垂直线最粗,45斜线最细.(3)

当线宽为偶数个时,绘制的线条宽度不精确.Disadvantages第五十七页，共六十三页，2022年，8月28日

方形刷子是一个宽度为指定线宽的正方形.将正方形的中心对准直线作平移运动即可.

m1TheMovingPen(方形刷子)方形刷子第五十八页，共六十三页，2022年，8月28日TheMovingPen(方形刷子)Thicklinedrawnbytracingarecta