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

第三节区域填充区域填充是指：在一个封闭的二维图形内部象素上着色(纹理、图案）。也称为：多边形的扫描转换。本节内容：矩形的扫描转换多边形区域填充图案填充矩形的扫描转换可利用矩形的简单性提高扫描转换的效率。问题：边界（共享边界）像素的绘制？解决：象素中心定位于矩形的左、下边界时绘制象素点。该规则适用于线画矩形及多边形以及共享顶点的情形。2023/7/222多边形填充—直线的扫描转换算法填充区间：区间端点由扫描线与多边形边界线段的交点确定2023/7/223注：多边形上的区间

(a)原始端点由中点算法确定(b)限制端点在多边形内

2023/7/224实现区间填充的三个步骤计算扫描线与多边形边界线段的交点按照x升序排列交点填充多边形内交点对之间的所有像素?：水平线段如何处理2023/7/225区间填充策略y=8为例：排序后的交点x坐标列表为:(2,4.5,8.5,13)如何填充?2023/7/2264舍？还是5入?当交点的x

坐标值是分数时需进行舍入运算。(b)左端点:向上取整右端点:向下取整2023/7/227内？或者外?当交点的x

坐标值是整数时，需确定该点是内点拟或是外点。(b)在右边界:外点在左边界:内点2023/7/228交点为尖点交点Pl为尖点时，可计数为：1，2或者0。如下图P0P0P0P0P1P1P1P1P2P2P2P2(a)(b)(c)(d)a)(b)计数为1个交点(c)计数为2个交点(d)计为0个交点规则：端点纵坐标是ymin

时计数加1；

端点纵坐标是ymax

时不计数

2023/7/229续：在具体实现时，对交点的后处理过程可以转化为对边界线段进行的预处理。2023/7/2210扫描线与多边形边界线段交点的计算(1)交点特点：Y方向坐标值满足:交点界于线段两端点间:第一个交点是其端点之一，不妨设为？：后续交点的计算取整？！2023/7/2211扫描线与多边形边界线段交点的计算(2)记前一扫描线与边界线段交点为当前扫描线与该边界线段有否交点可通过其纵坐标值确定。记当前扫描线与边界线段交点为

x的取整需针对边界线段在多边形的左右两侧做不同的处理：左侧边：向右取整，且当交点落在边界上时视做内部点右侧边：向左取整，且当交点落在边界上时视做外部点2023/7/2212考虑到，为消除浮点数运算，以交点在左侧边为例，可增设计数器Counter，并改写交点公式为：扫描线与多边形边界线段交点的计算(3)下一个交点对应计算器的值为：Counter的初始值可以是：2023/7/2213仍以交点在左侧边为例。（1）判断Counter的值是否大于0（2）若不是，则直接取为xi；若是，则进行如下运算：此时，计数器刷新为：问题：交点在右侧边时的处理扫描线与多边形边界线段交点的计算(4)（3）上述步骤反复执行k次，直至Counter的值小于0，此时xi+k的值即为交点向右取整的结果。其截断部分仍是。

2023/7/2214活性边表AET

(active-edge

table)引入如下的数据结构记录交点92092-5/211103/211130

P6P1P5P6P4P5P3P4Line9AETpointer1111.53/211130

P4P5P3P4Line10AETpointer引入Counter？92094.5-5/2118.53/211130

P6P1P5P6P4P5P3P4Line8AETpointer2023/7/22150123456789101137-5/2573/29201113097-5/21173/2边表(ET)的初始化2023/7/2216直线的扫描转换填充算法生成初始边表ET;把扫描线的y值设为ET的最小y坐标;AET初始化为空;循环直至满足终止条件:AET和ET为空从ET取值(满足ymin=y的线段)放到AET;从AET中删除满足y=ymax的线段,然后按照x坐标排序;填充既定区间;y

增加1;针对新的y值刷新AET中各项的x

值.2023/7/2217算法伪代码Polygongfill(polydef,color)Pointpolydef[];intcolor;{for(各条扫描线i)

建立初始化活性边表EdgeTable[i];i=0;ActiveEdgeList=0；//当前扫描线对应的活性边表初始化

for(各条扫描线i){

把EdgeTable[i]插入ActiveEdgeList中，并排序；遍历ActiveEdgeList，把配对交点构成半开半闭区间；填充各区间；从ActiveEdgeList中删除假交点；刷新ActiveEdgeList中交点的X坐标值；

}//for}2023/7/2218曲线边界区域填充应用举例可用类似方法（扫描转换确定出交点）实现曲线边界区域的填充，但所需运算量显然比多边形更大。例：圆域的活性边表填充算法。仍假设圆心在坐标原点；每条扫描线与圆周有两个交点，填充两个交点构成的区间即可；扫描线与圆周的交点的计算，可利用圆的扫描转换结果。2023/7/2219算法特点利用了多边形边界的连贯性加速与扫描线交点的计算：算法及数据结构复杂计算效率高对每个象素只访问一次，对硬件的访问量最小，且与设备无关。引入活性边表结构，增加了维持边表及进行交点排序的开销，不适合硬件实现。2023/7/2220练习题-作业4用多边形的扫描线算法对如下多边形进行扫描转换。（其中多边形各顶点的坐标为p1(5,7)，p2(5,11)，p3(8,13)，p4(12,12)，p5(12,7)，p6(9,9)）求该多边形的ET表用AEL表表示出多边形扫描转换的过程2023/7/2221其它填充算法边缘填充算法种子填充算法：从区域内部一点开始填充直至边界。递归种子填充算法扫描线种子填充算法2023/7/2222边缘填充算法条件：已通过扫描线与线段求交或对线段进行扫描转换得到边界点。思路：利用求余运算代替交点排序、配对、构造填充区间。原理：象素点颜色值经过偶数次求余运算后保持不变，经过奇数次求余运算后变为其余数算法：以扫描线为中心的边缘填充算法以边为中心的边缘填充算法像素求余运算2023/7/2223以扫描线为中心的边缘填充算法将当前扫描线上的所有象素着上指定颜色的补色2023/7/2224以扫描线为中心的边缘填充算法逐个“边界点”向右取余2023/7/2225以扫描线为中心的边缘填充算法逐个“边界点”向右取余2023/7/2226以扫描线为中心的边缘填充算法逐个“边界点”向右取余2023/7/2227以扫描线为中心的边缘填充算法逐个“边界点”向右取余2023/7/2228以扫描线为中心的边缘填充算法逐个“边界点”向右取余2023/7/2229以扫描线为中心的边缘填充算法逐个“边界点”向右取余2023/7/2230以扫描线为中心的边缘填充算法逐个“边界点”向右取余2023/7/2231以扫描线为中心的边缘填充算法对各条扫描线循环上述处理过程。2023/7/2232以边为中心的边缘填充算法原始多边形2023/7/2233以边为中心的边缘填充算法初始化：将绘图窗口的背景色置为多边形颜色的补色2023/7/2234以边为中心的边缘填充算法对非水平边上的每个象素点向右求余边1求余的结果图示2023/7/2235以边为中心的边缘填充算法边2求余的结果图示2023/7/2236以边为中心的边缘填充算法边3求余的结果图示2023/7/2237以边为中心的边缘填充算法边4求余的结果图示2023/7/2238种子填充算法原理在多边形内部找到一个已知的象素点作为种子点，由此开始，利用区域的连通性找到多边形内部的其它所有象素点进行填充。区域连通性2023/7/2239区域连通性（1）四向连通区域从区域上任一点出发，在不超出区域边界的前提下，可通过4个方向：上、下、左、右的移动组合到达区域中的任意象素点。允许从4个方向搜索下一个象素的填充算法称为是四向填充算法2023/7/2240区域连通性（2）八向连通区域从区域上任一点出发，在不超出区域边界的前提下，可通过8个方向：上、下、左、右、左上、左下、右上、右下的移动组合，到达区域中的任意象素。允许从8个方向搜索下一个象素的填充算法称为是8向填充算法2023/7/2241区域连通性（3）理论上认为，8向填充算法可以填充4向、8向连通区域，但实际上对于4向连通区域来说，使用8向填充算法会扩大填充范围、甚至会导致所定义区域不闭合的问题。2023/7/2242填充问题描述设填充区域为四向连通区域。区域表示采用边界表示方法：即区域边界上所有象素点的值与区域内部象素点的值不同。对于有内环的区域仍可进行处理。2023/7/2243种子填充算法分类递归填充算法扫描线算法改进的扫描线种子填充算法2023/7/2244递归填充算法初始化：种子象素入栈第一步：栈顶象素出栈，作为种子点；第二步：种子点被置为填充色；第三步：按照左、上、右、下顺序检查与种子点相邻的象素：若非边界且未被填充，则入栈（8向连通区域需考虑更多相邻象素）。若栈不空，则重复第一步。2023/7/2245s125697834象素填充顺序示意图问题：效率低下。2023/7/2246扫描线算法原理：在每条扫描线上只取一个种子，每次填充该种子所在扫描线上区域内部象素点区间。（减少水平方向连通性测试次数）在其相邻的上、下扫描线上确定出一个新的种子，进行如上处理。（减少在垂直方向上连通性测试次数）2023/7/2247扫描线种子填充算法流程（1）初始化：由指定的种子象素点(x,y)生成种子(y,xl,xr)填充区间并入栈。(xl,xr分别为种子点所在扫描线上多边形内部区间的左、右端点)第一步：若种子栈空则算法终止，否则栈顶种子出栈第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈，第三步：上述过程循环执行。2023/7/2248扫描线种子填充算法流程（2）考虑到区域可以是凹的或有内环的，所以可能在该扫描线上出现多个填充区间，亦即需定义多个种子。yy+1同样考虑到凹或有孔的区域，需对扫描线y-1进行同样的处理，获得新的种子。2023/7/2249扫描线种子填充算法的改进思路算法中的回溯过程并非总是必要的。无需进行填充回溯需要进行填充回溯2023/7/2250Referto:任继成，刘慎权，区域填充扫描线算法的改进，计算机辅助设计与图形学学报，Vol.10No.62019.改进的扫描线种子填充算法对栈结构进行改造记录种子点所在区间的左右端点，及扫描顺序标志+y：表示沿纵坐标增加的方向进行逐行扫描；-y：表示沿纵坐标减小的方向进行逐行扫描。实际的记录数据分别可以表示为：2023/7/2251相关问题对于8向连通区域的填充需考虑：当象素点（x，y）为内部点时，需考察象素点（x+1，y+1）是否是边界。图案填充2023/7/2252图案填充图案定义：可以使用一个二维数组：MXN来记录color[i][j]:表示局部坐标系(i,j)处的象素值涉及问题：图案与区域的定位问题:相对定位，绝对定位像素着色模式的问题：透明(Transparent)还是不透明(Opaque)2023/7/2253图案定位(1)图案在区域所在的绘图空间坐标系中定位

此时若区域的位置不同，则区域中填充的图案也不同。此时的视觉效果是：若区域移动，则区域中的填充图案发生变化。(x,y)value[x][y]=color[x%M][y%n]MN个像素定义的图案2023/7/2254图案定位(2)图案在区域