【文档说明】计算机图形学教学-6课件.ppt，共(60)页，945.523 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77504.html

以下为本文档部分文字说明：

边缘填充算法思路：利用求余运算代替交点排序、配对、构造填充区间。原理：象素点颜色值经过偶数次求余运算后保持不变，经过奇数次求余运算后变为其余数。算法：1.以扫描线为中心的边缘填充算法2.以边为中心的边缘填充算法以扫描线为中心的边缘填充算法基本思想:对于每一条扫描线和每条多边形边的交点(

xi,yi),将该扫描线上交点右方的所有象素取补.对多边形的每条边做此处理，边的顺序随意。以扫描线为中心的边缘填充算法0x1x2x3x向右求余从0)(xa(1)先将当前扫描线上的所有象素着上指定颜色的补色(2

)当前扫描线上的各交点依次将右方的象素颜色取补色以扫描线为中心的边缘填充算法向右求余从0)(xa0x1x2x3x以扫描线为中心的边缘填充算法向右求余从1)(xb0x1x2x3x以扫描线为中心的边缘填充算法向右求余从1)(xb0x1x2x3x以扫描线为中心的边缘填充算法向右求

余从2)(xc0x1x2x3x以扫描线为中心的边缘填充算法向右求余从2)(xc0x1x2x3x以扫描线为中心的边缘填充算法0x1x2x3x向右求余从3)(xd以扫描线为中心的边缘填充算法0x1x2x3x向右求余从3)(xd以扫描线为中心的边缘填充算法对各条扫描线循环上述处理过程。以边为中心的

边缘填充算法原始多边形以边为中心的边缘填充算法初始化：将绘图窗口的背景色置为多边形颜色的补色以边为中心的边缘填充算法对非水平边上的每个象素点向右求余以边为中心的边缘填充算法以边为中心的边缘填充算法以边为中心的边缘填充算法优点：与扫描线算法相比，边缘填充算法的数据结构和程序结构

简单。缺点：但该算法需要对帧缓存的大量象素反复赋值，速度较慢。边缘填充算法特点栅栏填充算法栅栏：一条与扫描线垂直的直线，过多边形的某个顶点，并把多边形分为左右两半。基本思想:对于每条扫描线与多边形边的交点,仅将交点与

栅栏之间的象素取补.栅栏填充算法0x1x2x3x向左求余从0)(xa将当前扫描线上的所有象素着上指定颜色的补色0x1x2x3x向左求余从1)(xa栅栏填充算法0x1x2x3x向左求余从2)(xa将当前扫描线上的所有象素着上指定颜

色的补色栅栏填充算法0x1x2x3x向右求余从3)(xa将当前扫描线上的所有象素着上指定颜色的补色栅栏填充算法边标志填充算法(1)原理：当一条直线穿越多边形时，其上各点针对多边形的归属状态将交替变化

；若点在多边形外，则在直线与多边形相交一次后，点在多边形内；边标志填充算法(2)算法步骤：第一步：多边形各边界线段经扫描转换过程后，对应象素打上边标志；第二步：•对每一扫描线，由左至右逐点访问：每访问到标志点，则进行一次多边形内/外部的转换，直至扫描线末。•对判别为多边形内部的象素

点进行填充；第三步：第二步循环至扫描结束。优点：边标志算法进一步改进了栅栏算法,使得算法对每个象素仅访问一次，用硬件实现时速度优势更明显。扫描线算法：对每条扫描线，首先计算它与扇形区域边界的交点，再把配对交点之间的像素用指定颜色填充。FillingEll

ipseArcs区域（种子）填充是指先将区域内的一点(种子点)赋予给定颜色,然后将颜色扩充到整个区域内的过程(染色过程).区域:已经表示成点阵形式的象素集合,具有相同颜色.与多边形扫描转换的比较基本思想边界要求基于的条件区域填充(种子

填充算法)区域的两种表示:内点表示、边界表示.边界表示:给位于边界上的所有象素着同一种颜色(特征值),而区域内着不同的颜色.区域的表示内点表示:给区域内所有象素都着上同一种颜色(特征值),边界上pixel着不同的颜色.种子填充算法要求:区域具有一定的连通性:4连通或8连

通。4连通区域:取区域内任意两点,在该区域内(不能通过区域外的点),若从其中一点出发,通过上、下、左、右四种运动可到达另一点时,则称该区域为4连通区域.区域连通性（1）4连通运动方向8连通运动方向区域连通性（2）区域连通性（

3）边界连通性：4连通区域虽可看作是8连通区域，但其作4连通区域或是8连通区域时其边界不同。区域连通性（4）允许从4个方向搜索下一个象素的填充算法称为是四向填充算法.允许从8个方向搜索下一个象素的填充算法称为是8向填充算法.种子填充算法递归填充算法扫

描线算法算法思想：设G为一内点表示的区域，(x,y)是G内一点，以(x,y)为种子点，先将(x,y)置为newcolor，然后对(x,y)的4(或8)领域进行递归处理，逐步将整个区域G置为newcolor.(1)递归算法voidFloodFill4(intx,inty,intoldC

olor,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1234567891

0111213141516171819202122Example：优点：算法原理和程序都很简单缺点：效率不高，原因是递归次数太多，区域内的每个象素都引起一次递归，即系统堆栈的一次进出操作，费时费内存。递归算法思想:(1)填充并确定种子点所在的区段；(2)

将种子区段压栈;(3)若堆栈非空,栈顶区段出栈;否则算法结束;(4)填充并确定新的区段,将其区段信息压栈，返回第(3)步。(2)扫描线种子填充算法扫描线种子填充算法流程（1）初始化：由指定的种子象素点(x,y)生成种子区段(y,xl,xr),填充并入栈。(xl,xr分别为种子点

所在扫描线上多边形内部区间的左、右端点)第一步：若种子栈空则算法终止，否则栈顶种子出栈第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈，第三步：上述过程循环执行。扫描线种子填充算法流程（2）新种

子的确定：在y+1扫描线的[xl,xr]区间内遍历象素点，对其上非边界且未被填充的象素点，确定其左、右端点并定义为新种子。扫描线种子填充算法流程（3）•考虑到区域可以是凹的或有内环的，所以可能在该扫描线上出

现多个填充区间，亦即需定义多个种子。yy+1•同样考虑到凹或有孔的区域，需对扫描线y-1进行同样的处理，获得新的种子。扫描线种子填充算法的改进思路算法中的回溯过程并非总是必要的。无需进行填充回溯需要进

行填充回溯Patternfilling用图像(pattern)填充区域Definitionofthepattern:MXNbitmapspattern[i][j]:thevalueoftheposition(i,j)Two

issuestherelationoftheareaofthepatterntothatoftheprimitive•Relativeanchor（相对锚定）•Absoluteanchor（绝对锚定）writemode•Transparent（透明写）

•Opaque（不透明写）Relativeanchor(相对锚定）Toanchorthepatternatavertexoftheprimitive:(x0,y0)value[x][y]=pattern[(x-x0)%M][(y-y0)%N](x0,y0)M*N个像素

定义的图案Absoluteanchor（绝对锚定）M*N个像素定义的图案Toconsidertheentirescreenasbeingtiledwiththepatternandtothinkoftheprim

itiveasconsistingofanoutlineorfilledareaoftransparentbitsthatletthepatternshowthroughvalue[x][y]=pattern[x%M][y%N](x,y)writemode（写模式）Fillingwithapat

tern:Addingextracontroltothepartofthescan-conversionalgorithmthatactuallywriteseachpixelWritemodeDoingPutPixelwithforegroundcoloratapixelfora1i

nthepatternIntransparentmode（透明写）:若图案为0，则不改变屏幕上该象素的颜色（不做任何处理）；Inopaquemode（不透明写）：若图案为0，则用背景颜色显示该象素：Patternfilli

ngwithoutrepeatedscanconversionRectanglewriteToscanconvertaprimitivefirstintoarectangularworkarea,andthento

writeeachpixelfromthatbitmaptotheappropriateplaceinthecanvas.Besuitabletocharacters,iconsandapplicationsymbols(a)

Mountainscene(b)Outlineofhouseicon(d)(e)(g)(c)Brickpattern(f)(d)Bitmapforsolidversionofhouseicon.(e)Clearingthescenebywriti

ngbackground(f)Brickpatternappliedtohouseicon(g)WritingthescreentransparentlywithpatternedhouseiconAne

xample:WritingapatternedobjectinopaquemodewithtwotransparentwritesThickprimitives在产生一定宽度的线条时,只需用一个“刷子”来替代单象素直线段中扫描生成的单象素即可.线画图元的属性控制Replicatin

gpixels(1)(线刷子)Usingmorethan1pixelforeachcolumn(orrow)duringscanconversionThicklinedrawnbycolumnreplicationPixelsareduplic

atedincolumnforlineswith–1<slope<1Pixelsareduplicatedinrowsforallotherlines原理:假设直线斜率在[-1,+1]之间,如图(a)所示.这时可把刷子置成垂直方向图(b).首先将刷子的中点对准直线的

一个端点,从该点开始,让刷子中点沿直线的轨迹往直线的另一端点平移即可“刷出”具有一定宽度的直线.如图(c).m1m2(a)(b)(c)ReplicatingPixels(2)

缺点:(1)线的始末端总是水平或垂直的.(2)线的粗细不一样.水平和垂直线最粗,45斜线最细.(3)当线宽为偶数个时,绘制的线条宽度不精确.Disadvantages方形刷子是一个宽度为指定线宽的正

方形.将正方形的中心对准直线作平移运动即可.m1TheMovingPen(方形刷子)方形刷子TheMovingPen(方形刷子)Thicklinedrawnbytracingarectangularpen.Thickl

inedrawnbycolumnreplication该方法将会重复的写象素.为避免重复,可采用与活化边表类似的技术.Disadvantagesjj+1j+2j+3j+4i-1ii+1i+2i+3i+4j

j+1j+2j+3j+4i-1ii+1i+2i+3i+4ii+1i+2i+3[j,j+2][j,j+2][j,j+2](a)ii+1i+2i+3[j,j+2][j,j+3][j,j+3][j+1,j+3](b)Recordingspansoftherectangula

rpen:(a)footprintatx=j+1;(b)x=j+2Recordingthespans先算出直线的四个角点的坐标,将其顺序连接成一个四边形,再用区域填充的方法将四边形填充.FillingAreasBetweenBoundaries圆弧线宽的处理圆弧线宽的处理与直线类似

.如虚线、实线、点划线等不同线型的处理.LineStyleAndPenStyle上机作业填充任意多边形或任意扇形区域。1.对于多边形：要求由用户输入多边形顶点坐标；2.对于扇形：要求由用户输入扇形的起始角和终止角。（圆心和半径可自定，也可由用户指定）可采用以下几种算法之一：1.扫描线算法；2.边标

志算法；3.种子的扫描线算法；