《计算机图形学教学资料》第6讲-多边形填充.ppt
2023/9/1,1,本章内容,直线的扫描转换圆与椭圆的扫描转换区域填充二维裁剪字符生成反走样,第三节 区域填充,区域填充是指：在一个封闭的二维图形内部象素上着色(纹理、图案）。也称为：多边形的扫描转换。本节内容：矩形的扫描转换多边形区域填充图案填充,2023/9/1,3,矩形的扫描转换,可利用矩形的简单性提高扫描转换的效率。,问题：边界（共享边界）像素的绘制？解决：象素中心定位于矩形的左、下边界时绘制象素点。该规则适用于线画矩形及多边形以及共享顶点的情形。,2023/9/1,4,多边形填充直线的扫描转换算法,填充区间：区间端点由扫描线与多边形边界线段的交点确定,2023/9/1,5,注：多边形上的区间,(a)原始端点由中点算法确定,(b)限制端点在多边形内,2023/9/1,6,实现区间填充的三个步骤,计算扫描线与多边形边界线段的交点按照x升序排列交点填充多边形内交点对之间的所有像素,?：水平线段如何处理,2023/9/1,7,区间填充策略,y=8为例：排序后的交点x坐标列表为:(2,4.5,8.5,13),如何填充?,2023/9/1,8,4舍？还是5入?,当交点的 x 坐标值是分数时需进行舍入运算。,2023/9/1,9,内？或者外?,当交点的x 坐标值是整数时，需确定该点是内点拟或是外点。,2023/9/1,10,交点为尖点,交点Pl为尖点时，可计数为：1，2或者0。如下图,规则：端点纵坐标是ymin 时计数加1；端点纵坐标是ymax 时不计数,2023/9/1,11,续：,在具体实现时，对交点的后处理过程可以转化为对边界线段进行的预处理。,2023/9/1,12,扫描线与多边形边界线段交点的计算(1),交点特点：,Y方向坐标值满足:,交点界于线段两端点间:,第一个交点是其端点之一，不妨设为,？：后续交点的计算 取整？！,2023/9/1,13,扫描线与多边形边界线段交点的计算(2),记前一扫描线与边界线段交点为,当前扫描线与该边界线段有否交点可通过其纵坐标值确定。,记当前扫描线与边界线段交点为,x的取整需针对边界线段在多边形的左右两侧做不同的处理：左侧边：向右取整，且当交点落在边界上时视做内部点右侧边：向左取整，且当交点落在边界上时视做外部点,2023/9/1,14,考虑到，为消除浮点数运算，以交点在左侧边为例，可增设计数器Counter，并改写交点公式为：,扫描线与多边形边界线段交点的计算(3),下一个交点对应计算器的值为：,Counter的初始值可以是：,2023/9/1,15,仍以交点在左侧边为例。（1）判断Counter的值是否大于0,（2）若不是，则直接取为xi；若是，则进行如下运算：,此时，计数器刷新为：,问题：交点在右侧边时的处理,扫描线与多边形边界线段交点的计算(4),（3）上述步骤反复执行k次，直至Counter的值小于0，此时xi+k的值即为交点向右取整的结果。其截断部分仍是。,2023/9/1,16,活性边表 AET(active-edge table),引入如下的数据结构记录交点,引入Counter？,2023/9/1,17,边表(ET)的初始化,2023/9/1,18,直线的扫描转换填充算法,生成初始边表 ET;把扫描线的y值设为ET的最小y坐标;AET 初始化为空;循环直至满足终止条件:AET 和 ET 为空从ET 取值(满足ymin=y的线段)放到AET;从AET中删除满足 y=ymax的线段,然后按照x坐标排序;填充既定区间;y 增加 1;针对新的y值刷新AET中各项的 x 值.,2023/9/1,19,算法伪代码,Polygongfill(polydef,color)Point polydef;int color;for(各条扫描线i)建立初始化活性边表EdgeTablei;i=0;ActiveEdgeList=0；/当前扫描线对应的活性边表初始化 for(各条扫描线i)把EdgeTablei插入ActiveEdgeList中，并排序；遍历ActiveEdgeList，把配对交点构成半开半闭区间；填充各区间；从ActiveEdgeList中删除假交点；刷新ActiveEdgeList中交点的X坐标值；/for,2023/9/1,20,曲线边界区域填充应用举例,可用类似方法（扫描转换确定出交点）实现曲线边界区域的填充，但所需运算量显然比多边形更大。例：圆域的活性边表填充算法。仍假设圆心在坐标原点；每条扫描线与圆周有两个交点，填充两个交点构成的区间即可；扫描线与圆周的交点的计算，可利用圆的扫描转换结果。,2023/9/1,21,算法特点,利用了多边形边界的连贯性加速与扫描线交点的计算：算法及数据结构复杂计算效率高对每个象素只访问一次，对硬件的访问量最小，且与设备无关。引入活性边表结构，增加了维持边表及进行交点排序的开销，不适合硬件实现。,2023/9/1,22,练习题-作业4,用多边形的扫描线算法对如下多边形进行扫描转换。（其中多边形各顶点的坐标为p1(5,7)，p2(5,11)，p3(8,13)，p4(12,12)，p5(12,7)，p6(9,9)）求该多边形的ET表用AEL表表示出多边 形扫描转换的过程,2023/9/1,23,其它填充算法,边缘填充算法种子填充算法：从区域内部一点开始填充直至边界。递归种子填充算法扫描线种子填充算法,2023/9/1,24,边缘填充算法,条件：已通过扫描线与线段求交或对线段进行扫描转换得到边界点。思路：利用求余运算代替交点排序、配对、构造填充区间。原理：象素点颜色值经过偶数次求余运算后保持不变，经过奇数次求余运算后变为其余数算法：以扫描线为中心的边缘填充算法以边为中心的边缘填充算法,像素求余运算,2023/9/1,25,以扫描线为中心的边缘填充算法,将当前扫描线上的所有象素着上指定颜色的补色,2023/9/1,26,以扫描线为中心的边缘填充算法,逐个“边界点”向右取余,2023/9/1,27,以扫描线为中心的边缘填充算法,逐个“边界点”向右取余,2023/9/1,28,以扫描线为中心的边缘填充算法,逐个“边界点”向右取余,2023/9/1,29,以扫描线为中心的边缘填充算法,逐个“边界点”向右取余,2023/9/1,30,以扫描线为中心的边缘填充算法,逐个“边界点”向右取余,2023/9/1,31,以扫描线为中心的边缘填充算法,逐个“边界点”向右取余,2023/9/1,32,以扫描线为中心的边缘填充算法,逐个“边界点”向右取余,2023/9/1,33,以扫描线为中心的边缘填充算法,对各条扫描线循环上述处理过程。,2023/9/1,34,以边为中心的边缘填充算法,原始多边形,2023/9/1,35,以边为中心的边缘填充算法,初始化：将绘图窗口的背景色置为多边形颜色的补色,2023/9/1,36,以边为中心的边缘填充算法,对非水平边上的每个象素点向右求余,边1求余的结果图示,2023/9/1,37,以边为中心的边缘填充算法,边2求余的结果图示,2023/9/1,38,以边为中心的边缘填充算法,边3求余的结果图示,2023/9/1,39,以边为中心的边缘填充算法,边4求余的结果图示,2023/9/1,40,种子填充算法,原理 在多边形内部找到一个已知的象素点作为种子点，由此开始，利用区域的连通性找到多边形内部的其它所有象素点进行填充。区域连通性,2023/9/1,41,区域连通性（1）,四向连通区域 从区域上任一点出发，在不超出区域边界的前提下，可通过4个方向：上、下、左、右的移动组合到达区域中的任意象素点。,允许从4个方向搜索下一个象素的填充算法称为是四向填充算法,2023/9/1,42,区域连通性（2）,八向连通区域 从区域上任一点出发，在不超出区域边界的前提下，可通过8个方向：上、下、左、右、左上、左下、右上、右下的移动组合，到达区域中的任意象素。,允许从8个方向搜索下一个象素的填充算法称为是8向填充算法,2023/9/1,43,区域连通性（3）,理论上认为，8向填充算法可以填充4向、8向连通区域，但实际上对于4向连通区域来说，使用8向填充算法会扩大填充范围、甚至会导致所定义区域不闭合的问题。,2023/9/1,44,填充问题描述,设填充区域为四向连通区域。区域表示采用边界表示方法：即区域边界上所有象素点的值与区域内部象素点的值不同。对于有内环的区域仍可进行处理。,2023/9/1,45,种子填充算法分类,递归填充算法扫描线算法改进的扫描线种子填充算法,2023/9/1,46,递归填充算法,初始化：种子象素入栈第一步：栈顶象素出栈，作为种子点；第二步：种子点被置为填充色；第三步：按照左、上、右、下顺序检查与种子点相邻的象素：若非边界且未被填充，则入栈（8向连通区域需考虑更多相邻象素）。若栈不空，则重复第一步。,2023/9/1,47,象素填充顺序示意图,问题：效率低下。,2023/9/1,48,扫描线算法,原理：在每条扫描线上只取一个种子，每次填充该种子所在扫描线上区域内部象素点区间。（减少水平方向连通性测试次数）在其相邻的上、下扫描线上确定出一个新的种子，进行如上处理。（减少在垂直方向上连通性测试次数）,2023/9/1,49,扫描线种子填充算法流程（1）,初始化：由指定的种子象素点(x,y)生成种子(y,xl,xr)填充区间并入栈。(xl,xr分别为种子点所在扫描线上多边形内部区间的左、右端点)第一步：若种子栈空则算法终止，否则栈顶种子出栈第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈，第三步：上述过程循环执行。,2023/9/1,50,扫描线种子填充算法流程（2）,考虑到区域可以是凹的或有内环的，所以可能在该扫描线上出现多个填充区间，亦即需定义多个种子。,同样考虑到凹或有孔的区域，需对扫描线y-1进行同样的处理，获得新的种子。,2023/9/1,51,扫描线种子填充算法的改进思路,算法中的回溯过程并非总是必要的。,2023/9/1,52,Refer to:任继成，刘慎权，区域填充扫描线算法的改进，计算机辅助设计与图形学学报，Vol.10 No.6 1998.,改进的扫描线种子填充算法,对栈结构进行改造记录种子点所在区间的左右端点，及扫描顺序标志+y：表示沿纵坐标增加的方向进行逐行扫描；-y：表示沿纵坐标减小的方向进行逐行扫描。实际的记录数据分别可以表示为：,2023/9/1,53,相关问题,对于8向连通区域的填充需考虑：当象素点（x，y）为内部点时，需考察象素点（x+1，y+1）是否是边界。图案填充,2023/9/1,54,图案填充,图案定义：可以使用一个二维数组：M X N来记录colorij:表示局部坐标系(i,j)处的象素值涉及问题：图案与区域的定位问题:相对定位，绝对定位像素着色模式的问题：透明(Transparent)还是不透明(Opaque),2023/9/1,55,图案定位(1),图案在区域所在的绘图空间坐标系中定位 此时若区域的位置不同，则区域中填充的图案也不同。此时的视觉效果是：若区域移动，则区域中的填充图案发生变化。,valuexy=colorx%My%n,2023/9/1,56,图案定位(2),图案在区域的局部坐标系中定义,记局部坐标系原点为:(x0,y0)valuexy=color(x-x0)%M(y-y0)%n,2023/9/1,57,前景色与背景色的合成问题,像素着色模式问题透明或不透明本质：规定前景色与背景色的组合规则，如前景色优先、背景色优先、前景色与背景色的加权组合、或各种规则的组合。,2023/9/1,58,像素着色模式,图案填充 在扫描转换算法中对像素着色操作需增加额外控制像素着色模式与图案中1标记位置对应的像素写为前景色在透明模式下：与图案中0标记位置对应的像素不进行写操作在不透明模式下：与图案中0标记位置对应的像素写为背景色,2023/9/1,59,(d)待填充区域的像素位图(e)擦除(a)中(d)区域，将像素写为背景色(f)对待填充区域进行图案填充(g)以透明模式把(f)绘在屏幕上,例:以不透明模式实现图案填充,2023/9/1,60,本节小结,多边形有序边表填充算法交点的计算区间的构成边表的更新边缘填充算法以扫描线为中心的边缘填充算法以边界线段为中心的边缘填充算法种子填充算法递归种子填充算法扫描线种子填充算法、改进的扫描线种子填充算法,
