《计算机图形学图形填充优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学图形填充优秀课件.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机图形学 图形填充第1页，本讲稿共50页v图形分类线段图形 直线、圆以及自由曲线等，用于表现物体的几何轮廓实面积图形 封闭图形，在其封闭的区域内具有相同的颜色。既表现了物体的几何轮廓，也反映了物体表面的色彩。在计算机屏幕上表现为：处于封闭图形内部区域的屏幕象素具有相同的亮度和色彩。第2页，本讲稿共50页v实面积图形的表示顶点表示法 以封闭多边形的顶点坐标数据（或者，闭合曲线的特征数据）来描述实面积图形；其内部以用户指定的颜色填充；基本填充方法：多边形填充。点阵表示法 以点阵数组的方式描述实面积图形；图形的内部以用户指定的颜色包围或者组成，易于面着色；基本填充方法：种子填充。顶点表示顶点表示
2、点阵表示点阵表示:多边形的扫描转换多边形的扫描转换。第3页，本讲稿共50页多边形分为凸多边形、凹多边形、含内环的多边形。注意：凹、凸点的判断第4页，本讲稿共50页实区域填充算法 v确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内v解决的主要问题是什么？v图案填充还有一个什么象素填什么颜色的问题v曲线围成的区域，可用多边形逼近 第5页，本讲稿共50页v多边形的填充原理多边形填充的任务:把多边形的顶点表示转换为点阵表示。即，找出所有位于多边形内部的像素点，以所要求的像素值画这些像素点。可能的做法：遍历屏幕上的像素点，判断是否在多边形内部，然后填充。问题：问题：逐点判断，速度太慢；不是所有
3、对多边形都容易作内部判断。关键：关键：寻找一种快速而通用的内部判断方法。第6页，本讲稿共50页扫描线扫描线:点阵图形在屏幕上的像素点，可以认为是由位于一条条水平直线上的像素点构成的.对每一条切割多边形的扫描线，决定扫描线上哪些像素点是在多边形内部，并对这些相应的像素点赋以合适的值表示某种颜色或灰度，就能对整个多边形进行扫描转换。第7页，本讲稿共50页一条扫描线与一个多边形的关系:相交或不相交.若相交,则直线被多边形分割成不同的直线段,其中一些在多边形内,另外一些在多边形外.并且这些多边形内外的直线段大多数情况下相互交替出现.第8页，本讲稿共50页扫描线连贯性扫描线连贯性(scan line c
4、oherence)：当像素点位于多边形内(外)的直线段上时,它就位于多边形内(外).也就是说，与多边形相交的一条扫描线上总会有一组相互相连的像素点都位于多边形之内。每一个像素点像素点所在的直线段第9页，本讲稿共50页分析从扫描线的一端出发,当前在多边形外,当沿扫描线前进到达与多边形的第一个交点时,就进入多边形内；由于扫描线的另一端是在多边形外,继续沿扫描线前进一定会走出多边形内部,于是一定会遇到第二个交点。这时可以看到,第一和第二个交点之间的直线段就位于多边形内；如果没有更多的交点,则该扫描线上只有一段直线段位于多边形内。否则,继续沿扫描线前进,此时位于多边形外,直到遇到第三个交点后,重新进入
5、多边形内。类似前面的分析,一定有第四个交点。于是第三,第四个交点给出的直线段就位于多边形内；如果还有更多的交点,就重复这样的过程,直到没有新的交点为止。因为交点个数是有限的,这一过程是一定可以结束的。第10页，本讲稿共50页射线交点计数射线交点计数的方法：从多边形外一点，引水平射线（即扫描线）穿过多边形，记录扫描线与多边形边的交点个数情况，当交点数为奇数时，扫描线处在多边形内部，当交点数为偶数时，扫描线处在多边形外部。多边形与同一扫描线的交点按x方向大小顺序排列，并两两配对，则可得扫描线在多边形内的直线段，从而可实现多边形填充。第11页，本讲稿共50页奇点问题奇点：当扫描线与多边形的交点是顶点
6、。如果奇点存在,上述判别过程就不能正确地进行多边形顶点的潜在问题这个问题与交点的求解方法有关.所有交点通过扫描线所在直线依次与多边形各边所在直线段求解出。如果某个交点恰恰是其中一个边的端点：重复计算。水平边问题水平边重合于某一条扫描线：无数多交点，不予处理第12页，本讲稿共50页可能情况图示：第13页，本讲稿共50页奇点的处理v多边形的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)0，则称顶点Pi为极值点；否则称Pi为非极值点。v规定：奇点是极值点时，该点按两个交点计算，否则按一规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。个交点计算。第14页，
7、本讲稿共50页v奇点的计数问题 543210P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6v检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数 计数0次计数1次计数2次第15页，本讲稿共50页11/29/202215总结：简单地数交点不能解决所有的问题，需要补充规则完善此射线交点计数法射线交点计数法：（1）忽略多边形的水平边；（2）与多边形的极值点端点相交时，该点算做两个；（3）其余的非极值点端点，仅计算一次。实际操作任务：（1）判断水平边；（2）判断奇点；在求交点过程中，因为是依次计算扫描线与各条边的交点，因此奇点也自然被计算两次。但造成另一
8、个问题是非极值点的顶点也被计算了两次。第16页，本讲稿共50页对此问题的一种处理办法是，计算前，先将每条斜边的低端点在y方向上缩小一个屏幕坐标单位，这将忽略极小值第17页，本讲稿共50页另一种预处理办法是，通过判断每条斜边的端点y值是否单调来找出奇点，对极值端点不作处理，而对非极值端点则缩短其中一条斜边的端点。v此法的缺点是，填充的图形可能会出现残缺第18页，本讲稿共50页这样处理后，极值点仍计算两次，而非极值点的斜边交点只计算一次。经上述约定及处理后，可保证同一扫描线与多边形的交点成对出 现，因此只要算出交点，填充就可以利用画直线算法快速完成。第19页，本讲稿共50页扫描线算法步骤如下：（1
9、）确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。（2）从y=ymin到y=ymax，每次用一条扫描线进行填充。（3）对一条扫描线填充的过程可分为四个步骤：a、求交：计算扫描线与多边形各边的交点；b、排序：把所有交点按递增顺序进行排序；c、交点配对：第一个与第二个，第三个与第四个 等等，每对交点就 代表扫描线与多边形的一个相交区间；d、区间填色：把这些相交区间内的像素置成不同于背景色的填充色。第20页，本讲稿共50页v如何计算下一条扫描线与边的交点。如何计算下一条扫描线与边的交点。直线方程：ax+by+c=0 当前交点坐标：(xi,yi)下一交点坐标：(x
10、i+1,yi+1)xi+1=(-byi+1)-c)/a=(-byi+1)-c)/a=xi-b/a=xi+1/mi第21页，本讲稿共50页扫描线算法特点v特点：算法效率较高。v缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。第22页，本讲稿共50页填充图元生成原理v多边形扫描转换多边形扫描转换v区域填充区域填充第23页，本讲稿共50页区域填充v区域区域指已经表示成点阵形式的填充图形，它是象素的集合。v区域填充区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。第24页，本讲稿共50页区域填充v表示方法：表示方法：内点表示、边界
11、表示v内点表示内点表示枚举出区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色v边界表示边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色 第25页，本讲稿共50页区域填充区域的连通性v连通性连通性 4连通、8连通、16连通v4 4连通连通 像素（像素（P(xP(xp,p,y yp p)）v N N4 4(p)=r|d(p)=r|d4 4(p,r)=1(p,r)=1v d d4 4(p,r)=|x(p,r)=|xp p-x-xr r|+|y|+|yp p-y-yr r|v8 8连通连通 N N8 8(p)=r|d(p)=r|d8 8(
12、p,r)=1(p,r)=1v d d8 8(p,r)=max(|x(p,r)=max(|xp p-x-xr r|,|y|,|yp p-y-yr r|)|)prrrrrrrrprrrr第26页，本讲稿共50页区域填充区域的连通性16连通 N N1616(p)=N(p)=N8 8(p)(p)N Nk k(p)(p)N Nk k(p)=d(p)=dk k(p,r)=1:(p,r)=1:马步邻域马步邻域 马步距离马步距离rrrr prrrrrrrrrrrr第27页，本讲稿共50页区域填充区域的连通性v4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求第28页，本讲稿共5
13、0页区域连通方式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果第29页，本讲稿共50页区域填充区域内外测试v填充过程：确定种子点种子着色区域扩展v问题：如何判断种子合适？v方法：v 奇偶规则：射线法。判断射线与多边形边的交点数 奇数：内部点 偶数：外部点 要求：射线不过顶点 第30页，本讲稿共50页区域填充区域内外测试用于鉴别物体内外点（内部种子点）非零环绕规则v环绕数：多边形以逆时针方向环绕某一特定点的次数.多边形内部点环绕数非零 v判断方法v差乘法：v A u u*e0 环绕数+1 u*e0 环绕数+1 v e0 环绕数-1 e
14、=VB-VA第31页，本讲稿共50页区域填充边界填充算法v边界表示法中，由于边界以特殊颜色指定，填充算法可逐个像素地向外处理，直到遇到边界颜色为止。这种方法称为边界填充算法。v填充算法可以让艺术家或设计师首先勾画图的轮廓，选择填充颜色和填充模式，然后拾取内部点，系统就可以自动给图的内部涂上所需的颜色和图案v填充算法的输入是种子点坐标（x，y），填充色和边界颜色。算法从（x，y）开始检测相邻位置是否是边界颜色，若不是，就用填充色着色，并检测其相邻位置。该过程延续到已经检测完区域边界颜色范围内的所有像素为止。下面使用栈结构来实现4-连通边界填充算法。可以很容易地将它扩充成8-连通边界填充算法，只要
15、把检查4-邻接点改为检查8-邻接点即可。步骤如下：第32页，本讲稿共50页设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。区域填充边界填充算法第33页，本讲稿共50页区域填充边界填充算法递归递归算法可算法可实现实现如下如下v
16、oid FloodFill4(int x,int y,int 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);/*end of FloodFill4()*/第34页，本讲稿共50页v该该算法也可以填充有孔区域。算法也
17、可以填充有孔区域。v缺点缺点：(1)有些象素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。(3)区域内若已有具有填充色的点，递归停止。v改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法区域填充边界填充算法第35页，本讲稿共50页区域填充扫描线算法v扫描线算法扫描线算法目标：减少递归层次目标：减少递归层次适用于边界表示的适用于边界表示的4 4连通区域连通区域算算法法思思想想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻
18、的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的各区段都填充完毕。第36页，本讲稿共50页区域填充扫描线算法(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。上述算法对于
19、每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。第37页，本讲稿共50页区域填充扫描线算法（举例分析）v该算法也可以填充有孔区域。像素中的序号标指它所在区段位于堆栈中的位置第38页，本讲稿共50页区域填充扫描线算法（举例分析）第39页，本讲稿共50页区域填充扫描线算法（举例分析）第40页，本讲稿共50页区域填充扫描线算法（举例分析）第41页，本讲稿共50页区域填充泛滥填充v问题：边界有多种颜色 区域内部有多种颜色v解决：替换颜色 统一像素颜色，种子填充第42页，本讲稿共50页区域填充图像填充用一种图案来填充平面区域。均匀着色填充方式 位图不透明 位图透明 像素图填充确
20、定区域内像素点查询图案位图的对应位置写像素 透明填充 1：前景色 0：不改变 不透明填充 1：前景色 0：背景色关键：确定区域与图像间的位置关系 第43页，本讲稿共50页v填充方法:图案为M*N位图，由数组存放 确定需要填充的区域与当前扫描线的相交区间 确定相交区间内像素点(x,y),图案位图pattern(x%M,y%N)不透明填充或透明填充 用透明方式写 不透明方式写第44页，本讲稿共50页多边形扫描转换与区域填充方法比较联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界
21、表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。第45页，本讲稿共50页多边形扫描转换与区域填充方法比较v不同点：1.基本思想不同；前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。2.对边界的要求不同v前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。3.基本的条件不同v前者：从边界顶点信息出发。v后者：区域内种子点。第46页，本讲稿共50页字符生成v字符：计算机在文本方式下能够在屏幕上显示的数字、字母、音标、标点符号、数学符号、汉字等符号。v编
22、码标准v ASCII码：美国信息交换用标准代码集 7位二进制编码 v GB231280(GB18030-2000)：信息交换用汉字编码字符集基本集 94个区，94个位 采用字节的最高位来标识：0:ASCII码；1:汉字编码。字库：点阵字库，矢量字库第47页，本讲稿共50页字符生成点阵字符v字符表示：位图 1：字符的笔画经过此位，该像素置为字符颜色 0：字符的笔画不经过此位，该像素置为背景颜色v显示步骤：从字库中检索出位图位图写入帧缓冲器 第48页，本讲稿共50页字符生成矢量字符v字符表示：记录笔画信息笔画端点坐标值，连线标志，管理信息，字形信息等 字符的编码 x0 y0 0 不连线 x1 y1 1 连线 2 x2 y2 0 0 1 x3 y3 1 x4 y4 0 4 3 5 x5 y5 1 -1 字符结束标志显示步骤：从字库检索字符数据提出端点坐标几何变换根据标志位显示第49页，本讲稿共50页字符生成点阵字符和矢量字符的比较 点阵字符 矢量字符位图，对像素变换，图像失真端点坐标，对端点变换，不失真大占用空间字符变换少轮廓字形法 美观，轮廓字形法 欠缺 第50页，本讲稿共50页