《《计算机图形学教学资料》第6讲-多边形填充.ppt》由会员分享，可在线阅读，更多相关《《计算机图形学教学资料》第6讲-多边形填充.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Interactive Computer Graphics-交互式计算机图形学2023/2/121本章内容v直线的扫描转换v圆与椭圆的扫描转换v区域填充v二维裁剪v字符生成v反走样第三节 区域填充区域填充是指：在一个封闭的二维图形内部象素上着色(纹理、图案）。也称为：多边形的扫描转换。本节内容：v矩形的扫描转换v多边形区域填充v图案填充Interactive Computer Graphics-交互式计算机图形学2023/2/123矩形的扫描转换v可利用矩形的简单性提高扫描转换的效率。问题：边界（共享边界）像素的绘制？解决：象素中心定位于矩形的左、下边界时绘制象素点。该规则适用于线画矩形及多边
2、形以及共享顶点的情形。Interactive Computer Graphics-交互式计算机图形学2023/2/124多边形填充直线的扫描转换算法填充区间：区间端点由扫描线与多边形边界线段的交点确定Interactive Computer Graphics-交互式计算机图形学2023/2/125注：多边形上的区间(a)原始端点由中点算法确定(b)限制端点在多边形内 Interactive Computer Graphics-交互式计算机图形学2023/2/126实现区间填充的三个步骤v计算扫描线与多边形边界线段的交点v按照x升序排列交点v填充多边形内交点对之间的所有像素?：水平线段如何处理I
3、nteractive Computer Graphics-交互式计算机图形学2023/2/127区间填充策略y=8为例：排序后的交点x坐标列表为:(2,4.5,8.5,13)如何填充?Interactive Computer Graphics-交互式计算机图形学2023/2/1284舍？还是5入?当交点的当交点的 x 坐标值是分数时需进行舍入运算。(b)左端点:向上取整(a)右端点:向下取整Interactive Computer Graphics-交互式计算机图形学2023/2/129内？或者外?v当交点的x 坐标值是整数时，需确定该点是内点拟或是外点。(b)在右边界:外点(a)在左边界:内
4、点Interactive Computer Graphics-交互式计算机图形学2023/2/1210交点为尖点v交点Pl为尖点时，可计数为：1，2或者0。如下图P0P0P0P0P1P1P1P1P2P2P2P2(a)(b)(c)(d)(a)(b)计数为1个交点 (c)计数为2个交点 (d)计为0个交点规则：端点纵坐标是ymin 时计数加1；端点纵坐标是ymax 时不计数 Interactive Computer Graphics-交互式计算机图形学2023/2/1211续：v在具体实现时，对交点的后处理过程可以转化为对边界线段进行的预处理。Interactive Computer Graphi
5、cs-交互式计算机图形学2023/2/1212扫描线与多边形边界线段交点的计算(1)v交点特点：Y方向坐标值满足:交点界于线段两端点间:第一个交点是其端点之一，不妨设为？：后续交点的计算 取整？！Interactive Computer Graphics-交互式计算机图形学2023/2/1213扫描线与多边形边界线段交点的计算(2)v记前一扫描线与边界线段交点为当前扫描线与该边界线段有否交点可通过其纵坐标值确定。记当前扫描线与边界线段交点为 x的取整需针对边界线段在多边形的左右两侧做不同的处理：左侧边：向右取整，且当交点落在边界上时视做内部点右侧边：向左取整，且当交点落在边界上时视做外部点In
6、teractive Computer Graphics-交互式计算机图形学2023/2/1214v考虑到 ，为消除浮点数运算，v以交点在左侧边为例，可增设计数器Counter，并改写交点公式为：扫描线与多边形边界线段交点的计算(3)v下一个交点对应计算器的值为：vCounter的初始值可以是：Interactive Computer Graphics-交互式计算机图形学2023/2/1215 仍以交点在左侧边为例。（1）判断Counter的值是否大于0（2）若不是，则直接取为xi；若是，则进行如下运算：此时，计数器刷新为：问题：交点在右侧边时的处理扫描线与多边形边界线段交点的计算(4)（3）上
7、述步骤反复执行k次，直至Counter的值小于0，此时xi+k的值即为交点向右取整的结果。其截断部分仍是 。Interactive Computer Graphics-交互式计算机图形学2023/2/1216活性边表 AET(active-edge table)引入如下的数据结构记录交点9 2 0 9 2 -5/211 10 3/2 11 13 0 P6P1P5P6P4P5P3P4Line 9 AETpointer11 11.5 3/2 11 13 0 P4P5P3P4Line 10 AETpointer引入Counter？9 2 0 9 4.5 -5/211 8.5 3/2 11 13 0
8、P6P1P5P6P4P5P3P4Line 8 AETpointerInteractive Computer Graphics-交互式计算机图形学2023/2/1217012345678910113 7 -5/25 7 3/2 9 2 0 11 13 0 9 7 -5/211 7 3/2 边表(ET)的初始化Interactive Computer Graphics-交互式计算机图形学2023/2/1218直线的扫描转换填充算法1.生成初始边表 ET;2.把扫描线的y值设为ET的最小y坐标;3.AET 初始化为空;4.循环直至满足终止条件:AET 和 ET 为空v从ET 取值(满足ymin=y的
9、线段)放到AET;v从AET中删除满足 y=ymax的线段,然后按照x坐标排序;v填充既定区间;vy 增加 1;v针对新的y值刷新AET中各项的 x 值.Interactive Computer Graphics-交互式计算机图形学2023/2/1219算法伪代码Polygongfill(polydef,color)Point polydef;int color;for(各条扫描线i)建立初始化活性边表EdgeTablei;i=0;ActiveEdgeList=0；/当前扫描线对应的活性边表初始化 for(各条扫描线i)把EdgeTablei插入ActiveEdgeList中，并排序；遍历Ac
10、tiveEdgeList，把配对交点构成半开半闭区间；填充各区间；从ActiveEdgeList中删除假交点；刷新ActiveEdgeList中交点的X坐标值；/forInteractive Computer Graphics-交互式计算机图形学2023/2/1220曲线边界区域填充应用举例v可用类似方法（扫描转换确定出交点）实现曲线边界区域的填充，但所需运算量显然比多边形更大。v例：圆域的活性边表填充算法。v仍假设圆心在坐标原点；v每条扫描线与圆周有两个交点，填充两个交点构成的区间即可；v扫描线与圆周的交点的计算，可利用圆的扫描转换结果。Interactive Computer Graphi
11、cs-交互式计算机图形学2023/2/1221算法特点v利用了多边形边界的连贯性加速与扫描线交点的计算：v算法及数据结构复杂v计算效率高v对每个象素只访问一次，对硬件的访问量最小，且与设备无关。v引入活性边表结构，增加了维持边表及进行交点排序的开销，不适合硬件实现。Interactive Computer Graphics-交互式计算机图形学2023/2/1222练习题-作业4用多边形的扫描线算法对如下多边形进行扫描转换。（其中多边形各顶点的坐标为p1(5,7)，p2(5,11)，p3(8,13)，p4(12,12)，p5(12,7)，p6(9,9)）v求该多边形的ET表v用AEL表表示出多边
12、 形扫描转换的过程 Interactive Computer Graphics-交互式计算机图形学2023/2/1223其它填充算法v边缘填充算法v种子填充算法：从区域内部一点开始填充直至边界。v递归种子填充算法v扫描线种子填充算法Interactive Computer Graphics-交互式计算机图形学2023/2/1224边缘填充算法v条件：已通过扫描线与线段求交或对线段进行扫描转换得到边界点。v思路：利用求余运算代替交点排序、配对、构造填充区间。v原理：象素点颜色值经过偶数次求余运算后保持不变，经过奇数次求余运算后变为其余数v算法：1.以扫描线为中心的边缘填充算法2.以边为中心的边缘
13、填充算法像素求余运算Interactive Computer Graphics-交互式计算机图形学2023/2/1225以扫描线为中心的边缘填充算法将当前扫描线上的所有象素着上指定颜色的补色Interactive Computer Graphics-交互式计算机图形学2023/2/1226以扫描线为中心的边缘填充算法逐个“边界点”向右取余Interactive Computer Graphics-交互式计算机图形学2023/2/1227以扫描线为中心的边缘填充算法逐个“边界点”向右取余Interactive Computer Graphics-交互式计算机图形学2023/2/1228以扫描线为
14、中心的边缘填充算法逐个“边界点”向右取余Interactive Computer Graphics-交互式计算机图形学2023/2/1229以扫描线为中心的边缘填充算法逐个“边界点”向右取余Interactive Computer Graphics-交互式计算机图形学2023/2/1230以扫描线为中心的边缘填充算法逐个“边界点”向右取余Interactive Computer Graphics-交互式计算机图形学2023/2/1231以扫描线为中心的边缘填充算法逐个“边界点”向右取余Interactive Computer Graphics-交互式计算机图形学2023/2/1232以扫描线为
15、中心的边缘填充算法逐个“边界点”向右取余Interactive Computer Graphics-交互式计算机图形学2023/2/1233以扫描线为中心的边缘填充算法对各条扫描线循环上述处理过程。Interactive Computer Graphics-交互式计算机图形学2023/2/1234以边为中心的边缘填充算法原始多边形Interactive Computer Graphics-交互式计算机图形学2023/2/1235以边为中心的边缘填充算法初始化：将绘图窗口的背景色置为多边形颜色的补色Interactive Computer Graphics-交互式计算机图形学2023/2/123
16、6以边为中心的边缘填充算法对非水平边上的每个象素点向右求余边1求余的结果图示Interactive Computer Graphics-交互式计算机图形学2023/2/1237以边为中心的边缘填充算法边2求余的结果图示Interactive Computer Graphics-交互式计算机图形学2023/2/1238以边为中心的边缘填充算法边3求余的结果图示Interactive Computer Graphics-交互式计算机图形学2023/2/1239以边为中心的边缘填充算法边4求余的结果图示Interactive Computer Graphics-交互式计算机图形学2023/2/124
17、0种子填充算法v原理 在多边形内部找到一个已知的象素点作为种子点，由此开始，利用区域的连通性找到多边形内部的其它所有象素点进行填充。v区域连通性Interactive Computer Graphics-交互式计算机图形学2023/2/1241区域连通性（区域连通性（1）v四向连通区域 从区域上任一点出发，在不超出区域边界的前提下，可通过4个方向：上、下、左、右的移动组合到达区域中的任意象素点。允许从4个方向搜索下一个象素的填充算法称为是四向填充算法Interactive Computer Graphics-交互式计算机图形学2023/2/1242区域连通性（2）v八向连通区域 从区域上任一点
18、出发，在不超出区域边界的前提下，可通过8个方向：上、下、左、右、左上、左下、右上、右下的移动组合，到达区域中的任意象素。允许从8个方向搜索下一个象素的填充算法称为是8向填充算法Interactive Computer Graphics-交互式计算机图形学2023/2/1243区域连通性（3）理论上认为，8向填充算法可以填充4向、8向连通区域，但实际上对于4向连通区域来说，使用8向填充算法会扩大填充范围、甚至会导致所定义区域不闭合的问题。Interactive Computer Graphics-交互式计算机图形学2023/2/1244填充问题描述v设填充区域为四向连通区域。v区域表示采用边界表
19、示方法：即区域边界上所有象素点的值与区域内部象素点的值不同。v 对于有内环的区域仍可进行处理。Interactive Computer Graphics-交互式计算机图形学2023/2/1245种子填充算法分类v递归填充算法v扫描线算法v改进的扫描线种子填充算法Interactive Computer Graphics-交互式计算机图形学2023/2/1246递归填充算法v初始化：种子象素入栈v第一步：栈顶象素出栈，作为种子点；v第二步：种子点被置为填充色；v第三步：按照左、上、右、下顺序检查与种子点相邻的象素：若非边界且未被填充，则入栈（8向连通区域需考虑更多相邻象素）。v若栈不空，则重复第
20、一步。Interactive Computer Graphics-交互式计算机图形学2023/2/1247s125697834象素填充顺序示意图问题：效率低下。Interactive Computer Graphics-交互式计算机图形学2023/2/1248扫描线算法扫描线算法v原理：v在每条扫描线上只取一个种子，每次填充该种子所在扫描线上区域内部象素点区间。（减少水平方向连通性测试次数）v在其相邻的上、下扫描线上确定出一个新的种子，进行如上处理。（减少在垂直方向上连通性测试次数）Interactive Computer Graphics-交互式计算机图形学2023/2/1249扫描线种子填
21、充算法流程（1）v初始化：由指定的种子象素点(x,y)生成种子(y,xl,xr)填充区间并入栈。(xl,xr分别为种子点所在扫描线上多边形内部区间的左、右端点)v第一步：若种子栈空则算法终止，否则栈顶种子出栈v第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈，v第三步：上述过程循环执行。Interactive Computer Graphics-交互式计算机图形学2023/2/1250扫描线种子填充算法流程（2）考虑到区域可以是凹的或有内环的，所以可能在该扫描线上出现多个填充区间，亦即需定义多个种子。yy+1同样考虑到凹或有孔的区域
22、，需对扫描线y-1进行同样的处理，获得新的种子。Interactive Computer Graphics-交互式计算机图形学2023/2/1251扫描线种子填充算法的改进思路v算法中的回溯过程并非总是必要的。无需进行填充回溯需要进行填充回溯Interactive Computer Graphics-交互式计算机图形学2023/2/1252Refer to:任继成，刘慎权，区域填充扫描线算法的改进，计算机辅助设计与图形学学报，Vol.10 No.6 1998.改进的扫描线种子填充算法v对栈结构进行改造记录种子点所在区间的左右端点，及扫描顺序标志v+y：表示沿纵坐标增加的方向进行逐行扫描；v-y
23、：表示沿纵坐标减小的方向进行逐行扫描。实际的记录数据分别可以表示为：Interactive Computer Graphics-交互式计算机图形学2023/2/1253相关问题v对于8向连通区域的填充需考虑：当象素点（x，y）为内部点时，需考察象素点（x+1，y+1）是否是边界。v图案填充Interactive Computer Graphics-交互式计算机图形学2023/2/1254图案填充v图案定义：v可以使用一个二维数组：M X N来记录vcolorij:表示局部坐标系(i,j)处的象素值v涉及问题：v图案与区域的定位问题:相对定位，绝对定位v像素着色模式的问题：透明(Transpar
24、ent)还是不透明(Opaque)Interactive Computer Graphics-交互式计算机图形学2023/2/1255图案定位(1)v图案在区域所在的绘图空间坐标系中定位 此时若区域的位置不同，则区域中填充的图案也不同。此时的视觉效果是：若区域移动，则区域中的填充图案发生变化。(x,y)valuexy=colorx%My%nMN个像素定义的图案Interactive Computer Graphics-交互式计算机图形学2023/2/1256图案定位(2)v图案在区域的局部坐标系中定义记局部坐标系原点为:(x0,y0)valuexy=color(x-x0)%M(y-y0)%n(
25、x0,y0)MN个像素定义的图案Interactive Computer Graphics-交互式计算机图形学2023/2/1257前景色与背景色的合成问题v像素着色模式问题v透明或不透明v本质：规定前景色与背景色的组合规则，如前景色优先、背景色优先、前景色与背景色的加权组合、或各种规则的组合。Interactive Computer Graphics-交互式计算机图形学2023/2/1258像素着色模式v图案填充 在扫描转换算法中对像素着色操作需增加额外控制v像素着色模式v与图案中1标记位置对应的像素写为前景色v在透明模式下：与图案中0标记位置对应的像素不进行写操作v在不透明模式下：与图案中
26、0标记位置对应的像素写为背景色Interactive Computer Graphics-交互式计算机图形学2023/2/1259(a)山峦景色(b)待填充区域轮廓线(d)(e)(g)(c)图案模式(f)(d)待填充区域的像素位图(e)擦除(a)中(d)区域，将像素写为背景色(f)对待填充区域进行图案填充(g)以透明模式把(f)绘在屏幕上例:以不透明模式实现图案填充 Interactive Computer Graphics-交互式计算机图形学2023/2/1260本节小结v多边形有序边表填充算法v交点的计算v区间的构成v边表的更新v边缘填充算法v以扫描线为中心的边缘填充算法v以边界线段为中心的边缘填充算法v种子填充算法v递归种子填充算法v扫描线种子填充算法、改进的扫描线种子填充算法