《计算机图形学教学资料》第6讲-多边形填充.ppt

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