【文档说明】计算机图形学课件第4章二维填充图元的生成.ppt，共(51)页，332.000 KB，由小橙橙上传

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

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

计算机图形学课件第4章二维填充图元的生成4.1扫描转换矩形（1/2）voidFillRectangle(Rectangle*rect,intcolor){intx,y;for(y=rect->ymin;y<=rect->ymax;

y++)for(x=rect->xmin;x<=rect->xmax;x++)PutPixel(x,y,color);}/*endofFillRectangle()*/方法：yminxminymaxxmax4.1扫描转换矩形（2/2）属于谁？问题：矩形是简单的多边形，为什么要单独处理矩形

？共享边界如何处理？比一般多边形可简化计算。应用非常多，窗口系统。原则：左闭右开，下闭上开4.2扫描转换多边形多边形的表示方法顶点表示点阵表示扫描转换多边形：将顶点表示形式转换成点阵表示形式方法：逐点判断法；扫描线算法；边缘填充法；栅栏填充算法

等。voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++)if(IsInside(P,x,y))PutPixel(x,y,p

olygonColor);elsePutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP()*/#defineMAX100Typedefstruct{intPolygonNum;//多边形顶点个数Pointvertexces[MAX]//多边形顶

点数组}Polygon//多边形结构逐点判断法程序段9/3/2022•华东交大信息学院软件教研室点的包含判断逐个判断绘图窗口内的像素：如何判断点在多边形的内外关系？1）射线法：2）累计角度法3）编码法；1）射线法步骤：1.从待判别点v发出射线2.求交点个数k3.K的奇偶性决定了点与多

边形的内外关系奇异情况处理p1p0p2p3v0v1步骤1.从v点向多边形P顶点发出射线，形成有向角2.计算有向角的和，得出结论预处理离散计算方法：编码方法2）累计角度法之内位于之外位于，PvPvnii,200iP0P1P2v3）编码方法：累计角度方法的离散

方法Step:a.预处理，测试点在边上否？b.V为中点作局部坐标系，对其象限按逆时针（或顺时针）编码；c.顶点编码Ipi，d.边编码。PiPi+1:△PiPi+1=Ipi+1-Ipi△PiPi+1=3→△PiPi+1=-1△PiPi+1=-3→△PiPi+1=1△P

iPi+1=±2→V在PiPi+1之上,△PiPi+1=-2,否则为2e.计算∑△PiPi+1（其中△PnPn+1=△PnP0)：若∑△PiPi+1为0，V在P外；若∑△PiPi+1为±4，V在P内；逐点判断法程序简单，速度太慢，效率低。0123扫描线算法扫描线算法(1/7)目标：利用相邻像素

之间的连贯性，提高算法效率处理对象：非自交多边形（边与边之间除了顶点外无其它交点）扫描线算法(2/7)基本原理一条扫描线与多边形的边有偶数个交点步骤(对于每一条扫描线):(1)求交点(2)交点排序(3)交点配对，填充区段。扫描转换多

边形(3/7)边的连贯性为了减少求交的计算量，可利用边的连贯性第一类交点：新出现的边与扫描线的交点（不用计算）第二类交点：位于同一条边上的后继交点扫描转换多边形(4/7)交点的取整规则要求：使生成的像素全部位于多边形之内用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之

外，从而不可用假定非水平边与扫描线y=e相交，交点的横坐标为x,规则如下：扫描线算法(5/7)●规则1：X为小数，即交点落于扫描线上两个相邻像素之间(a)交点位于左边之上，向右取整(b)交点位于右边之上，向左取整扫描线算法(6/7)●规则2：边界

上象素的取舍问题，避免填充扩大化。●解决方法：边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭右开扫描线算法(7/7)●规则3：扫描线与多边形的顶点相交时，交点的取舍，保证交

点正确配对。●解决方法：检查两相邻边在扫描线的哪一侧。只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0,1,2，来决定取0,1,2个交点。1个1个2个0个边缘填充算法▼求余运算：假定A为

一个正整数，则M的余定义为A–M,记为。计算机中取A为n位能表示的最大整数。即，A=0xFFFFFFFF▼由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变

为值为的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。▼算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。MM1、将当前扫描线上的所有象素着上颜色；2、求余：for(i=0;i<=m;i++)在当前扫描线上，从横坐标为Xi的交点向右求余；M

算法1（以扫描线为中心的边缘填充算法）1、将绘图窗口的背景色置为；2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；算法2（以边为中心的边缘填充算法）M算法2（以边为中心的边缘填充算法）边缘填充算法适合用于具有帧缓存的图形

系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。优点：算法简单缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比有序边表算法大得多。引入栅栏，以减少填充算法访问象素的次数。栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。基本思想：扫描线与多边形

的边求交，将交点与栅栏之间的象素取补。减少了象素重复访问数目，但不彻底。栅栏填充算法4.3扫描转换扇形区域(1/5)按点p1和p2点所处象限的不同，需要将扇形区域分成4×5=20种情况扇形区域的描述:原理：同扫描转换多边形问题：如何确定扫描线与直线段和圆弧段的相交顺序方法：分类4.3扫描

转换扇形区域(2/5)假设p1点落在第一象限，扇形区域的扫描转换分五种情况1、p2落在第一象限•在区域OP1A中，扫描线从左到右分别与OA和OP1相交；•在区域AP1P2中，扫描线从左到右分别与AP2和P1P2相交；4.3

扫描转换扇形区域(3/5)2、p2落在第二象限，此时又分为两种情况当y1≤y2时当y1>y2时4.3扫描转换扇形区域(4/5)3、p2落在第三象限4、p2落在第四象限4.3扫描转换扇形区域(5/5)遗留问题：当p1落在其它区域时?其

它方法：多边形迫近方法p1p2ABCDo5、p2落在第一象限且∠p1op2≥3/24.4区域填充区域：点阵表示的图形，像素集合表示方法：内点表示、边界表示内点表示枚举处区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同

的颜色边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色区域填充–对区域重新着色的过程将指定的颜色从种子点扩展到整个区域的过程区域填充算法要求区域是连通的连通性4连通、8连通4连通：8连通区域填充(种子填充法)区域填充(种

子填充法)4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求区域填充(种子填充法)voidFloodFill4(intx,inty,intoldColor,intnewColor){//先判断像素点(x,y)的颜色，若≠oldco

lor，则说明该像素//位于区域之外或已被置为newcolor，不需要填充。if(GetPixel(x,y)==oldColor){PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);Floo

dFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);}}/*endofFloodFill4()*/1）递归填充算法

内点表示的4连通区域，取(x,y)为种子点区域填充(种子填充法)区域填充(种子填充法)voidBoundaryFill4(intx,inty,intoldColor,intnewColor){intcolor;color=GetPixel(x,y);if((color!=boun

daryColor)&&(color!=newColor)){PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,ne

wColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);}}/*endofBoundaryFill4()*/边界表示的4连通区域区域填充(种子填充法)

缺点：(1)有些象素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。改进算法，减少递归次数，提高效率。方法之一使用扫描线填充算法；区域填充（扫描线算法)扫描线算法目标：减少递

归层次适用于内点表示的4连通区域基本过程：当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。1、填充并确定种子区段；2、初始

化：将种子区段压入堆栈；3、出栈：如果堆栈为空，则算法结束；否则取栈顶元素（y,xLeft,xRight），以纵坐标为y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间；4、填充并确定新的区段。•算法步骤区域填充（扫描线算法）演示9/3/2022•华东交大信息学

院软件教研室区域填充（扫描线算法)像素中的序号标指它所在区段位于堆栈中的位置。扫描线算法也可以填充有孔区域像素中的序号标指它所在区段位于堆栈中的位置续续续多边形扫描转换与区域填充方法比较联系：都是光栅图形面着色，用于

真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用直线扫描转换算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。多边

形扫描转换与区域填充方法比较不同点：1.基本思想不同；前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。2.对边界的要求不同前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。3.基本的条件不同前者：从边界顶点信

息出发。后者：区域内种子点。4.5以图象填充区域四种填充方法：(1)均匀着色方法：将图元内部像素置成同一颜色(2)位图不透明：若像素对应的位图单元为1，则以前景色显示该像素；若为0，则以背景色显示该像素；(3)位图透明：若像素对应的位图单元为1，则以前景色显示该像素；若为0，则不做

任何处理。(4)像素图填充：以像素对应的像素图单元的颜色值显示该像素。以图像填充区域图像（纹理）基本问题关键是建立区域与图像间的对应关系方法1：建立整个绘图空间与图像空间的1-1映射以图像填充区域适用：动画中漫游图像–例，透过车窗看外景以图像填充区域适用：图像作为区域表面属性的情况，例如

，桌面与其上的木纹。方法2：建立区域局部坐标空间与图像空间的1-1映射4.6字符的表示与输出字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。我国除采用ASCII码外，还另外制定了汉字编码的国家标准字符集GB2312－80。该字符集分为94个区，94个位，每个符号由一个区码

和一个位码共同标识。区码和位码各用一个字节表示。为了能够区分ASCII码与汉字编码，采用字节的最高位来标识：最高位为0表示ASCII码；最高位为1表示表示汉字编码。为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库。字库中存储了每个字符的形状信息，字库分为

矢量和点阵型两种。一、点阵字符点阵字符的显示分为两步。首先从字库中将它的位图检索出来。然后将检索到的位图写到帧缓冲器中。(a)点阵字符(b)点阵字库中的位图表示(c)矢量轮廓字符二、矢量字符矢量字符记录字符的笔画信息而不是整个位图

，具有存储空间小，美观、变换方便等优点。对于字符的旋转、缩放等变换，点阵字符的变换需要对表示字符位图中的每一象素进行；而矢量字符的变换只要对其笔画端点进行变换就可以了。矢量字符的显示也分为两步。首先从字库中将它的字符信息。然后取出端点坐标，对其进行适当的几何变换，再根据各端点

的标志显示出字符。