计算机图形学 图形填充

计算机图形学图形填充第一页，共五十页，2022年，8月28日图形分类线段图形

直线、圆以及自由曲线等，用于表现物体的几何轮廓实面积图形封闭图形，在其封闭的区域内具有相同的颜色。既表现了物体的几何轮廓，也反映了物体表面的色彩。 在计算机屏幕上表现为：处于封闭图形内部区域的屏幕象素具有相同的亮度和色彩。第二页，共五十页，2022年，8月28日实面积图形的表示顶点表示法

以封闭多边形的顶点坐标数据（或者，闭合曲线的特征数据）来描述实面积图形；其内部以用户指定的颜色填充；基本填充方法：多边形填充。点阵表示法

以点阵数组的方式描述实面积图形；图形的内部以用户指定的颜色包围或者组成，易于面着色；基本填充方法：种子填充。顶点表示点阵表示:多边形的扫描转换。第三页，共五十页，2022年，8月28日多边形分为凸多边形、凹多边形、含内环的多边形。注意：凹、凸点的判断第四页，共五十页，2022年，8月28日实区域填充算法确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内解决的主要问题是什么？图案填充还有一个什么象素填什么颜色的问题曲线围成的区域，可用多边形逼近第五页，共五十页，2022年，8月28日多边形的填充原理多边形填充的任务:把多边形的顶点表示转换为点阵表示。即，找出所有位于多边形内部的像素点，以所要求的像素值画这些像素点。可能的做法：遍历屏幕上的像素点，判断是否在多边形内部，然后填充。问题：逐点判断，速度太慢；不是所有对多边形都容易作内部判断。关键：寻找一种快速而通用的内部判断方法。第六页，共五十页，2022年，8月28日扫描线:点阵图形在屏幕上的像素点，可以认为是由位于一条条水平直线上的像素点构成的.对每一条切割多边形的扫描线，决定扫描线上哪些像素点是在多边形内部，并对这些相应的像素点赋以合适的值表示某种颜色或灰度，就能对整个多边形进行扫描转换。第七页，共五十页，2022年，8月28日一条扫描线与一个多边形的关系:相交或不相交.若相交,则直线被多边形分割成不同的直线段,其中一些在多边形内,另外一些在多边形外.并且这些多边形内外的直线段大多数情况下相互交替出现.第八页，共五十页，2022年，8月28日扫描线连贯性(scanlinecoherence)：当像素点位于多边形内(外)的直线段上时,它就位于多边形内(外).也就是说，与多边形相交的一条扫描线上总会有一组相互相连的像素点都位于多边形之内。每一个像素点—像素点所在的直线段第九页，共五十页，2022年，8月28日分析 从扫描线的一端出发,当前在多边形外,当沿扫描线前进到达与多边形的第一个交点时,就进入多边形内；由于扫描线的另一端是在多边形外,继续沿扫描线前进一定会走出多边形内部,于是一定会遇到第二个交点。这时可以看到,第一和第二个交点之间的直线段就位于多边形内； 如果没有更多的交点,则该扫描线上只有一段直线段位于多边形内。否则,继续沿扫描线前进,此时位于多边形外,直到遇到第三个交点后,重新进入多边形内。类似前面的分析,一定有第四个交点。于是第三,第四个交点给出的直线段就位于多边形内； 如果还有更多的交点,就重复这样的过程,直到没有新的交点为止。因为交点个数是有限的,这一过程是一定可以结束的。第十页，共五十页，2022年，8月28日射线交点计数的方法： 从多边形外一点，引水平射线（即扫描线）穿过多边形，记录扫描线与多边形边的交点个数情况，当交点数为奇数时，扫描线处在多边形内部，当交点数为偶数时，扫描线处在多边形外部。多边形与同一扫描线的交点按x方向大小顺序排列，并两两配对，则可得扫描线在多边形内的直线段，从而可实现多边形填充。第十一页，共五十页，2022年，8月28日奇点问题

奇点：当扫描线与多边形的交点是顶点。如果奇点存在,上述判别过程就不能正确地进行多边形顶点的潜在问题这个问题与交点的求解方法有关. 所有交点通过扫描线所在直线依次与多边形各边所在直线段求解出。如果某个交点恰恰是其中一个边的端点：重复计算。水平边问题

水平边重合于某一条扫描线：无数多交点，不予处理第十二页，共五十页，2022年，8月28日可能情况图示： 第十三页，共五十页，2022年，8月28日奇点的处理多边形的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)≥0，则称顶点Pi为极值点；否则称Pi为非极值点。规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。第十四页，共五十页，2022年，8月28日奇点的计数问题543210P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数

计数0次计数1次计数2次第十五页，共五十页，2022年，8月28日3/31/202315总结：简单地数交点不能解决所有的问题，需要补充规则完善此射线交点计数法： （1）忽略多边形的水平边； （2）与多边形的极值点端点相交时，该点算做两个； （3）其余的非极值点端点，仅计算一次。实际操作任务：（1）判断水平边；（2）判断奇点；在求交点过程中，因为是依次计算扫描线与各条边的交点，因此奇点也自然被计算两次。但造成另一个问题是非极值点的顶点也被计算了两次。第十六页，共五十页，2022年，8月28日

对此问题的一种处理办法是，计算前，先将每条斜边的低端点在y方向上缩小一个屏幕坐标单位，这将忽略极小值

第十七页，共五十页，2022年，8月28日另一种预处理办法是，通过判断每条斜边的端点y值是否单调来找出奇点，对极值端点不作处理，而对非极值端点则缩短其中一条斜边的端点。此法的缺点是，填充的图形可能会出现残缺第十八页，共五十页，2022年，8月28日这样处理后，极值点仍计算两次，而非极值点的斜边交点只计算一次。经上述约定及处理后，可保证同一扫描线与多边形的交点成对出现，因此只要算出交点，填充就可以利用画直线算法快速完成。第十九页，共五十页，2022年，8月28日扫描线算法步骤如下：（1）确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。（2）从y=ymin到y=ymax，每次用一条扫描线进行填充。（3）对一条扫描线填充的过程可分为四个步骤：

a、求交：计算扫描线与多边形各边的交点；

b、排序：把所有交点按递增顺序进行排序；

c、交点配对：第一个与第二个，第三个与第四个等等，每对交点就代表扫描线与多边形的一个相交区间；

d、区间填色：把这些相交区间内的像素置成不同于背景色的填充色。

第二十页，共五十页，2022年，8月28日如何计算下一条扫描线与边的交点。直线方程：ax+by+c=0

当前交点坐标：(xi,yi)

下一交点坐标：(xi+1,yi+1)xi+1=

((-byi+1)-c)/a=((-byi+1)-c)/a=xi-b/a=xi+1/mi第二十一页，共五十页，2022年，8月28日扫描线算法特点特点：算法效率较高。缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。第二十二页，共五十页，2022年，8月28日填充图元生成原理多边形扫描转换区域填充第二十三页，共五十页，2022年，8月28日区域填充区域指已经表示成点阵形式的填充图形，它是象素的集合。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。第二十四页，共五十页，2022年，8月28日区域填充表示方法：内点表示、边界表示内点表示枚举出区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色

第二十五页，共五十页，2022年，8月28日区域填充—区域的连通性连通性

4连通、8连通、16连通4连通像素（P(xp,yp)）

N4(p)={r|d4(p,r)=1}d4(p,r)=|xp-xr|+|yp-yr|8连通N8(p)={r|d8(p,r)=1}d8(p,r)=max(|xp-xr|,|yp-yr|)prrrrrrrrprrrr第二十六页，共五十页，2022年，8月28日区域填充—区域的连通性16连通

N16(p)=N8(p)∪Nk(p)Nk(p)={dk(p,r)=1}:马步邻域马步距离rrrrprrrrrrrrrrrr第二十七页，共五十页，2022年，8月28日区域填充—区域的连通性4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求第二十八页，共五十页，2022年，8月28日区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果第二十九页，共五十页，2022年，8月28日区域填充—区域内外测试填充过程：确定种子点—种子着色—区域扩展问题：如何判断种子合适？方法：奇偶规则：射线法。判断射线与多边形边的交点数奇数：内部点偶数：外部点要求：射线不过顶点

第三十页，共五十页，2022年，8月28日区域填充—区域内外测试用于鉴别物体内外点（内部种子点）非零环绕规则环绕数：多边形以逆时针方向环绕某一特定点的次数.

多边形内部点环绕数非零判断方法差乘法：v

A

uu*e>0环绕数+1u*e<0环绕数-1点乘法Bve>0环绕数+1ve<0环绕数-1e=VB-VA第三十一页，共五十页，2022年，8月28日区域填充—边界填充算法边界表示法中，由于边界以特殊颜色指定，填充算法可逐个像素地向外处理，直到遇到边界颜色为止。这种方法称为边界填充算法。填充算法可以让艺术家或设计师首先勾画图的轮廓，选择填充颜色和填充模式，然后拾取内部点，系统就可以自动给图的内部涂上所需的颜色和图案填充算法的输入是种子点坐标（x，y），填充色和边界颜色。算法从（x，y）开始检测相邻位置是否是边界颜色，若不是，就用填充色着色，并检测其相邻位置。该过程延续到已经检测完区域边界颜色范围内的所有像素为止。下面使用栈结构来实现4-连通边界填充算法。可以很容易地将它扩充成8-连通边界填充算法，只要把检查4-邻接点改为检查8-邻接点即可。步骤如下：第三十二页，共五十页，2022年，8月28日设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。区域填充—边界填充算法第三十三页，共五十页，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);}}/*endofFloodFill4() */

第三十四页，共五十页，2022年，8月28日该算法也可以填充有孔区域。

缺点：

(1)有些象素会入栈多次，降低算法效率；栈结构占空间。

(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。

(3)区域内若已有具有填充色的点，递归停止。改进算法，减少递归次数，提高效率。 解决方法是用扫描线填充算法区域填充—边界填充算法第三十五页，共五十页，2022年，8月28日区域填充—扫描线算法扫描线算法目标：减少递归层次适用于边界表示的4连通区域算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的各区段都填充完毕。第三十六页，共五十页，2022年，8月28日区域填充—扫描线算法(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。第三十七页，共五十页，2022年，8月28日区域填充—扫描线算法（举例分析）该算法也可以填充有孔区域。

像素中的序号标指它所在区段位于堆栈中的位置第三十八页，共五十页，2022年，8月28日区域填充—扫描线算法（举例分析）第三十九页，共五十页，2022年，8月28日区域填充—扫描线算法（举例分析）第四十页，共五十页，2022年，8月28日区域填充—扫描线算法（举例分析）第四十一页，共五十页，2022年，8月28日区域填充—泛滥填充问题：边界有多种颜色 区域内部有多种颜色解决：替换颜色统一像素颜色，种子填充第四十二页，共五十页，2022年，8月28日区域填充—图像填充用一种图案来填充平面区域。均匀着色填充方式位图不透明位图透明像素图填充确定区域内像素点查询图案位图的对应位置写像素透明填充1：前景色

0：不改变不透明填充

1：前景色

0：背景色关键：确定区域与图像间的位置关系

第四十三页，共五十页，2022年，8月28日填充方法:

图案为M*N位图，由数组存放确定需要填充的区域与当前扫描线的相交区间确定相交区间内像素点(x,y),图案位图pattern(x%M,y%N)

不透明填充或透明填充

用透明方式写不透明方式写第四十四页，共五十页，2022年，8月28日多边形扫描转换与区域填充方法比较联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。

第四十五页，共五十页，2022年，8月28日多边形扫描转换与区域填充方法比较不同点：1.基本思想不同；前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。2.对边界的要求不同前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。3.基本的条件不同前者：从边界顶点信息出发。后者：区域内种子点。第四十六页，共五十页，2022年，8月28日字符生成字符：计算机在文本方式下能够在屏幕上显示的数字、字母、音标、标点符号、数学符号、汉字等符号。编码标准

ASCII码：美国信息交换用标准代码集

7位二进制编码

GB2312－80(GB18030-2000)：信息交换用汉字编码字符集基本集

94个区，94个位采用字节的最高位来标识：0:ASCII码；1:汉