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

1、Interactive Computer Graphics-交互式计算机图形学本章内容v直线的扫描转换v圆与椭圆的扫描转换v区域填充v二维裁剪v字符生成v反走样第三节 区域填充区域填充是指：在一个封锁的二维图形内部象素上着色(纹理、图案。也称为：多边形的扫描转换。本节内容：矩形的扫描转换多边形区域填充图案填充Interactive Computer Graphics-交互式计算机图形学矩形的扫描转换v可利用矩形的简单性提高扫描转换的效率。minxmaxxminymaxyminxmaxxminymaxy问题：边境共享边境像素的绘制？处理：象素中心定位于矩形的左、下边境时绘制象素点。该规那么适用于

2、线画矩形及多边形以及共享顶点的情形。Interactive Computer Graphics-交互式计算机图形学多边形填充直线的扫描转换算法填充区间：区间端点由扫描线与多边形边境限段的交点确定Interactive Computer Graphics-交互式计算机图形学注：多边形上的区间 (a) 原始端点由中点算法确定(b) 限制端点在多边形内 Interactive Computer Graphics-交互式计算机图形学实现区间填充的三个步骤v计算扫描线与多边形边境限段的交点v按照x升序陈列交点v填充多边形内交点对之间的一切像素)9 , 2()7 , 7()11,13()5 ,13() 1

3、 , 7()3 , 2(654321PPPPPP?：程度线段如何处置 P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 Interactive Computer Graphics-交互式计算机图形学区间填充战略y=8为例：排序后的交点x坐标列表为: (2, 4.5, 8.5, 13) P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 如何填充?)9 , 2()7 , 7()11,13()5 ,13() 1 , 7()3 , 2(654321PPPPPPInteractive Computer Graphics-交互式计算机图形学4舍？还是5入?当

4、交点的当交点的 x 坐标值是分数时需进展舍入运算。坐标值是分数时需进展舍入运算。(b)左端点:向上取整v右端点:向下取整Interactive Computer Graphics-交互式计算机图形学内？或者外?v当交点的x 坐标值是整数时，需确定该点是内点拟或是外点。(b) 在右边境:外点v在左边境:内点Interactive Computer Graphics-交互式计算机图形学交点为尖点v交点Pl为尖点时，可计数为：1，2或者0。如以下图P0P0P0P0P1P1P1P1P2P2P2P2(a)(b)(c)(d)(a) (b) 计数为1个交点 (c) 计数为2个交点 (d) 计为0个交点规那么

5、：端点纵坐标是ymin 时计数加1； 端点纵坐标是ymax 时不计数 Interactive Computer Graphics-交互式计算机图形学续：v在详细实现时，对交点的后处置过程可以转化为对边境限段进展的预处置。Interactive Computer Graphics-交互式计算机图形学扫描线与多边形边境限段交点的计算(1)v交点特点：(,),(,)minmaxxyxy12maxminyyy(,)minxy1Y方向坐标值满足:交点界于线段两端点间:第一个交点是其端点之一，无妨设为？：后续交点的计算 取整？！bayx (,)minxy1),(max2yxInteractive Comp

6、uter Graphics-交互式计算机图形学扫描线与多边形边境限段交点的计算(2)v记前一扫描线与边境限段交点为则：),(11iiyxbayxyxiiii ),(满足bayxyyiiii1111byai) 1(axi的斜率是该边界线段所在直线其中kka,1当前扫描线与该边境限段有否交点可经过其纵坐标值确定。记当前扫描线与边境限段交点为 xx的取整需针对边境限段在多边形的左右两侧做不同的处置：左侧边：向右取整，且当交点落在边境上时视做内部点右侧边：向左取整，且当交点落在边境上时视做外部点 xInteractive Computer Graphics-交互式计算机图形学v思索到 ，为消除浮点数运

7、算，v以交点在左侧边为例，可增设计数器Counter，并改写交点公式为：扫描线与多边形边境限段交点的计算(3)xCounterakxxyyxy121maxminyCounterxyCounterxxiiiv下一个交点对应计算器的值为：vCounter的初始值可以是：yxyCounterxyxxxxiiii11（随初始点而定）或者 x0Interactive Computer Graphics-交互式计算机图形学yyCounterxyCounterxii1yCounter 仍以交点在左侧边为例。1判别Counter的值能否大于02假设不是，那么直接取为xi；假设是，那么进展如下运算：此时，计数器

8、刷新为： 问题：交点在右侧边时的处置扫描线与多边形边境限段交点的计算(4):向右取整可运算如下yCounterxi3上述步骤反复执行k次，直至Counter的值小于0，此时xi+k的值即为交点向右取整的结果。其截断部分仍是 。 yCounterInteractive Computer Graphics-交互式计算机图形学活性边表 AET (active-edge table)y m a x x a N e x t - p o i n t e r 引入如下的数据构造记录交点9 2 0 9 2 -5/211 10 3/2 1 1 1 3 0 P6P1P5P6P4P5P3P4Line 9 AETpo

9、inter11 11.5 3/2 11 13 0 P4P5P3P4Line 10 AETpointer引入Counter？9 2 0 9 4.5 -5/211 8.5 3/2 1 1 1 3 0 P6P1P5P6P4P5P3P4Line 8 AETpointer P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 Interactive Computer Graphics-交互式计算机图形学012345678910113 7 -5/25 7 3/2 9 2 0 11 13 0 9 7 -5/211 7 3/2 )9 , 2()7 , 7()11,13()5 ,13() 1

10、 , 7()3 , 2(654321PPPPPP边表 (ET)的初始化 P 1 P 2 P 4 P 5 P 6 0 2 4 6 8 10 P 3 Interactive Computer Graphics-交互式计算机图形学直线的扫描转换填充算法v生成初始边表 ET;v把扫描线的y值设为ET的最小y坐标;vAET 初始化为空;v循环直至满足终止条件: AET 和 ET 为空v从ET 取值(满足ymin=y的线段)放到AET;v从AET中删除满足 y=ymax的线段,然后按照x坐标排序;v填充既定区间;vy 添加 1;v针对新的y值刷新AET中各项的 x 值. Interactive Compu

11、ter Graphics-交互式计算机图形学算法伪代码Polygongfill(polydef,color)Point polydef;int color; for(各条扫描线i) 建立初始化活性边表EdgeTablei; i=0; ActiveEdgeList=0；/当前扫描线对应的活性边表初始化 for(各条扫描线i) 把EdgeTablei插入ActiveEdgeList中，并排序； 遍历ActiveEdgeList，把配对交点构成半开半闭区间； 填充各区间； 从ActiveEdgeList中删除假交点； 刷新ActiveEdgeList中交点的X坐标值； /forInteractive

12、 Computer Graphics-交互式计算机图形学曲线边境区域填充运用举例v可用类似方法扫描转换确定出交点实现曲线边境区域的填充，但所需运算量显然比多边形更大。v例：圆域的活性边表填充算法。v仍假设圆心在坐标原点；v每条扫描线与圆周有两个交点，填充两个交点构成的区间即可；v扫描线与圆周的交点的计算，可利用圆的扫描转换结果。Interactive Computer Graphics-交互式计算机图形学算法特点v利用了多边形边境的衔接性加速与扫描线交点的计算：v算法及数据构造复杂v计算效率高v对每个象素只访问一次，对硬件的访问量最小，且与设备无关。v引入活性边表构造，添加了维持边表及进展交点

13、排序的开销，不适宜硬件实现。Interactive Computer Graphics-交互式计算机图形学练习题-作业4用多边形的扫描线算法对如下多边形进展扫描转换。其中多边形各顶点的坐标为p1(5,7)，p2(5,11)，p3(8,13)，p4(12,12) ，p5(12,7)， p6(9,9)求该多边形的ET表用AEL表表示出多边 形扫描转换的过程 Interactive Computer Graphics-交互式计算机图形学其它填充算法v边缘填充算法v种子填充算法：从区域内部一点开场填充直至边境。v递归种子填充算法v扫描线种子填充算法Interactive Computer Graphi

14、cs-交互式计算机图形学边缘填充算法v条件：已经过扫描线与线段求交或对线段进展扫描转换得到边境点。v思绪：利用求余运算替代交点排序、配对、构造填充区间。v原理：象素点颜色值经过偶数次求余运算后坚持不变，经过奇数次求余运算后变为其他数v算法：v以扫描线为中心的边缘填充算法v以边为中心的边缘填充算法像素求余运算Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法0 x1x2x3x将当前扫描线上的一切象素着上指定颜色的补色Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法0 x1x2x3x向

15、右求余从0)(xa逐个“边境点向右取余Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法0 x1x2x3x向右求余从1)(xb逐个“边境点向右取余Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法0 x1x2x3x向右求余从1)(xb逐个“边境点向右取余Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法0 x1x2x3x向右求余从2)(xc逐个“边境点向右取余Interactive Computer Graphics-交互式计算

16、机图形学以扫描线为中心的边缘填充算法0 x1x2x3x向右求余从2)(xc逐个“边境点向右取余Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法0 x1x2x3x向右求余从3)(xd逐个“边境点向右取余Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法0 x1x2x3x向右求余从3)(xd逐个“边境点向右取余Interactive Computer Graphics-交互式计算机图形学以扫描线为中心的边缘填充算法对各条扫描线循环上述处置过程。Interactive Computer

17、Graphics-交互式计算机图形学以边为中心的边缘填充算法原始多边形Interactive Computer Graphics-交互式计算机图形学以边为中心的边缘填充算法初始化：将绘图窗口的背风光置为多边形颜色的补色Interactive Computer Graphics-交互式计算机图形学以边为中心的边缘填充算法对非程度边上的每个象素点向右求余边1求余的结果图示Interactive Computer Graphics-交互式计算机图形学以边为中心的边缘填充算法边2求余的结果图示Interactive Computer Graphics-交互式计算机图形学以边为中心的边缘填充算法边3求余

18、的结果图示Interactive Computer Graphics-交互式计算机图形学以边为中心的边缘填充算法边4求余的结果图示Interactive Computer Graphics-交互式计算机图形学种子填充算法v原理v 在多边形内部找到一个知的象素点作为种子点，由此开场，利用区域的连通性找到多边形内部的其它一切象素点进展填充。v区域连通性Interactive Computer Graphics-交互式计算机图形学区域连通性区域连通性1v四向连通区域v 从区域上任一点出发，在不超出区域边境的前提下，可经过4个方向：上、下、左、右的挪动组合到达区域中的恣意象素点。允许从4个方向搜索下一

19、个象素的填充算法称为是四向填充算法Interactive Computer Graphics-交互式计算机图形学区域连通性2v八向连通区域v 从区域上任一点出发，在不超出区域边境的前提下，可经过8个方向：上、下、左、右、左上、左下、右上、右下的挪动组合，到达区域中的恣意象素。允许从8个方向搜索下一个象素的填充算法称为是8向填充算法Interactive Computer Graphics-交互式计算机图形学区域连通性3 实际上以为，8向填充算法可以填充4向、8向连通区域，但实践上对于4向连通区域来说，运用8向填充算法会扩展填充范围、甚至会导致所定义区域不闭合的问题。Interactive Co

20、mputer Graphics-交互式计算机图形学填充问题描画v设填充区域为四向连通区域。v区域表示采用边境表示方法：v 即区域边境上一切象素点的值与区域内部象素点的值不同。v 对于有内环的区域仍可进展处置。Interactive Computer Graphics-交互式计算机图形学种子填充算法分类v递归填充算法v扫描线算法v改良的扫描线种子填充算法Interactive Computer Graphics-交互式计算机图形学递归填充算法v初始化：种子象素入栈v第一步：栈顶象素出栈，作为种子点；v第二步：种子点被置为填充色；v第三步：按照左、上、右、下顺序检查与种子点相邻的象素：假设非边境且

21、未被填充，那么入栈8向连通区域需思索更多相邻象素。v假设栈不空，那么反复第一步。Interactive Computer Graphics-交互式计算机图形学s125697834象素填充顺序表示图问题：效率低下。Interactive Computer Graphics-交互式计算机图形学扫描线算法扫描线算法v原理：v在每条扫描线上只取一个种子，每次填充该种子所在扫描线上区域内部象素点区间。v减少程度方向连通性测试次数v在其相邻的上、下扫描线上确定出一个新的种子，进展如上处置。v减少在垂直方向上连通性测试次数Interactive Computer Graphics-交互式计算机图形学扫描线种

22、子填充算法流程1v初始化：由指定的种子象素点(x,y)生成种子(y,xl,xr)填充区间并入栈。v (xl,xr分别为种子点所在扫描线上多边形内部区间的左、右端点)v第一步：假设种子栈空那么算法终止，否那么栈顶种子出栈v第二步：确定新种子：分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间；填充新区间并将新种子压入堆栈，v第三步：上述过程循环执行。Interactive Computer Graphics-交互式计算机图形学扫描线种子填充算法流程2思索到区域可以是凹的或有内环的，所以能够在该扫描线上出现多个填充区间，亦即需定义多个种子。yy+1同样思索到凹或有孔的区域，需对扫描线y-

23、1进展同样的处置，获得新的种子。Interactive Computer Graphics-交互式计算机图形学扫描线种子填充算法的改良思绪v算法中的回溯过程并非总是必要的。无需进展填充回溯需求进展填充回溯Interactive Computer Graphics-交互式计算机图形学Refer to:任继成，刘慎权，区域填充扫描线算法的改良，计算机辅助设计与图形学学报，Vol.10 No.6 1998.改良的扫描线种子填充算法v对栈构造进展改造记录种子点所在区间的左右端点，及扫描顺序标志v+y：表示沿纵坐标添加的方向进展逐行扫描；v-y：表示沿纵坐标减小的方向进展逐行扫描。v实践的记录数据分别可

24、以表示为：)1( ,()1(,(yxxyxxrlrl及Interactive Computer Graphics-交互式计算机图形学相关问题v对于8向连通区域的填充需思索：当象素点x，y为内部点时，需调查象素点x+1，y+1能否是边境。v图案填充Interactive Computer Graphics-交互式计算机图形学图案填充v图案定义：v可以运用一个二维数组：M X N来记录vcolorij:表示部分坐标系(i,j)处的象素值v涉及问题：v图案与区域的定位问题:相对定位，绝对定位v像素着色方式的问题：透明(Transparent)还是不透明(Opaque)Interactive Computer Graphics-交互式计算机图形学图案定位(1)v图案在区域所在的绘图空间坐标系中定位v 此时假设区域的位置不