第四章 多边形填充.

Presentation on theme: "第四章 多边形填充."— Presentation transcript:

1 第四章 多边形填充

2 本章内容 4.1 实面积图形的概念 4.2 x-扫描线算法 4.3 有效边表填充算法 4.4 边缘填充算法 4.5 区域填充算法
4.1　实面积图形的概念 x-扫描线算法 有效边表填充算法 边缘填充算法 区域填充算法 本章小结 习题

3 4.1实面积图形的概念 填充后的多边形称为实面积图形
实面积图形既能描述物体的几何轮廓，又能表现物体的表面色彩，与人们观察物体表面的习惯相一致 实面积图形是描述三维物体、绘制三维真实感图形的基础

4 4.1.1 多边形的定义 多边形是由折线段组成的封闭图形 多边形分为凸多边形、凹多边形、含内环的多边形

5 4.1.2 多边形的表示 在计算机图形学中，多边形有两种示方法：顶点表示法和点阵表示法。 图 4-4 多边形的点阵表示法
图 4-3 多边形的顶点表示法 P0 P1 P2 P3 P4 P5 图 4-4 多边形的点阵表示法

6 ⑴顶点表示法 多边形的顶点表示法是用多边形的顶点序列来描述。 特点是直观、占内存少，易于进行几何变换
但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换 图 4-3 多边形的顶点表示法 P0 P1 P2 P3 P4 P5

7 ⑵点阵表示法 多边形的点阵表示法是用多边形覆盖的像素点集来描述。 特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式
但是缺少了多边形顶点的几何信息 图 4-4 多边形的点阵表示法

8 ⑶多边形的扫描转换 多边形的扫描转换：将多边形的描述从顶点表示法变换到点阵表示法的过程
从多边形的顶点信息出发，求出多边形内部的各个像素点信息 图 4-3 多边形的顶点表示法 P0 P1 P2 P3 P4 P5 图 4-4 多边形的点阵表示法

9 4.1.3 填充区域图元 多边形扫描转换填充：通过确定横越区域的扫描线的覆盖间隔来填充
x-扫描线算法 有效边表算法 边缘填充算法（栅栏填充算法） 区域填充（种子填充）：从给定的位置开始涂描直到指定的边界条件为止 边界填充算法 泛填充算法

10 4.2 x-扫描线算法 基本思想 按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作

11 举例 在图中，多边形覆盖了12条扫描线。扫描线y＝3与多边形有4个交点（2.3，3），(4.5，3），（7，3）和（9，3）。对交点进行圆整处理后的结果为（2，3），(5，3），（7，3）和（9，3）。按x值递增的顺序对交点进行排序、配对后的填充区间为（2，5）和（7，9），共有7个像素点需要填充为指定颜色 P0 P1 P2 P3 P4 P5 P6 用一条扫描线填充多边形

12 x-扫描线算法 算法步骤： (1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。
(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。 (3)对一条扫描线填充的过程可分为四个步骤： a.求交 ：计算扫描线与多边形各边的交点 b.排序：把所有交点按x递增顺序进行排序 c.交点配对：第一个与第二个，第三个与第四个，…，第2i-1与第2i个交点配对，其中，i取1~n。每对交点就代表扫描线与多边形的一个相交区间。 d.区间填色：把这些相交区间内的像素置成多边形填充色，把区间外的像素置成背景色

13 x-扫描线算法 存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。

14 x-扫描线算法 解决办法：当扫描线与多边形的顶点相交时， 若共享顶点的两条边分别落在扫描线的两边，交点只算一个；
若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个 这取决于该顶点是多边形的局部最高点（0个）还是局部最低点（2个）。如图 (b)和图 (c)

15 A B C (a) 取一个 (b) 取零个 (c) 取二个 扫描线与多边形顶点相交时交点的取舍

16 1 2 算法程序 见计算机图形学演示系统

17 图 4-8 面积3×3 图 4-9 面积2×2 也称作“下闭上开”和“左闭右开”的原则。每个小正方形的右边界像素和上边界像素都没有填充。图4-8的处理结果如图4-9所示，上面一行像素和右面一列像素没有填充。

18 按照此原则对图4-5中的一些特殊点进行处理 1.P2点的处理原则
图4-5中P2是边P3P2的终点，同时也是边P2P1的起点。按照“下闭上开”的原则，可以自动处理。 图4-10 局部点的处理 P0 P1 P2 P3 P4 P5 P6

19 2. P0、P3、P5点和P4点的处理原则 P0点、P3和P5是局部最低点，P4点是局部最高点。如果处理不当，扫描线y＝1会填充区间（3，8），结果填充了P3和P5点之间的像素，如图4-10所示。（1）对局部最低点P0、P3和P5的处理方法为：填充时设置一个逻辑变量（初始值为假），每访问一个结点，逻辑变量值取反一次，若逻辑变量值为真，则填充该区间，这样可以保证局部最低点处理正确。（2）对局部最高点P4，根据“下闭上开”的原则，P4点不予填充，y＝5扫描线会自动填充P4点，如图4-10所示。 图4-10 局部点的处理 P0 P1 P2 P3 P4 P5 P6

20 讨论 x-扫描线算法计算每条扫描线与多边形各边的交点
把多边形的所有边放在一个表中。在处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线求交 这样处理效率很低，这是因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。 如何改进？

21 4.3 有效边表填充算法 4.3.1 填充原理 4.3.2 有效边和有效边表 4.3.3 边表

22 4.3.1 填充原理 在x-扫描线算法上改进： 处理一条扫描线时，仅对有效边求交 利用扫描线的连贯性： 利用多边形边的连贯性：
即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常类似 利用多边形边的连贯性： 即当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交

23 4.3.2 有效边和有效边表 1.有效边（Active Edge，AE）
多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高了算法效率。

24 2.有效边表（Active Edge Table，AET）
把有效边按照与扫描线交点x坐标递增的顺序存放在一个 链表中，称为有效边表。在AET中，只保留与当前扫描线相交的所有的边，而且这些边按其与扫描线交点x坐标递增的顺序存放，以便于在一对交点之间填充。有效边表的结点如图4-12所示。 图 4-12 有效边表结点 x : 当前扫描线与边的交点； ymax : 边所交的最高扫描线号。 1/k : 从当前扫描线到下一条扫描线之间的x增量；

25 有效边表的数据结构 class AET { public: AET(); virtual ~AET(); double x;
int yMax; double k;//代替1/k AET *next; };

26 2.有效边表 由于边的连贯性以及扫描线的连贯性，在当前扫描线处理完毕之后，不必为下一条扫描线从头开始构造有效边表，而只要对当前扫描线的有效边表稍作修改和更新，就可以得到下一条扫描线的有效边表。 有效边上的扫描线由起点到终点每次加1，即像素点的y坐标为：y＝y+1，x坐标的变化可以按如下方法推导。

27 4.3.2 有效边和有效边表 设有效边的斜率为k。假定有效边与当前扫描线yi的交点为（xi，yi），则有效边与下一条扫描线yi+1的交点为（xi+1，yi+1）。其中 如图4-11所示。这说明随着扫描线的移动，扫描线与有效边交点的x坐标从起点开始可以按增量1/k计算出来。 使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性表中删除，避免下一步无谓的计算

28 （xi+1，yi+1） （xi，yi） 1/k 图4-11 有效边交点相关性 1

29 举例 P0 P1 P2 P3 P4 P5 P6 图 4-13 示例多边形 对于图4-13所示的多边形，顶点表示法为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。扫描线的最大值为Smax＝12，最小值为Smin＝1，共有12条扫描线，每条扫描线之间间隔1个像素单位。每条扫描线的有效边表为如下图所示。

30 P0（7，8） P1（3，12） P2（1，7） P3（3，1） P4（6，5） P5（8，1） P6（12，9） 图 4-13 示例多边形

31 P0（7，8） P1（3，12） P2（1，7） P3（3，1） P4（6，5） P5（8，1） P6（12，9） 图 4-13 示例多边形

32 P0（7，8） P1（3，12） P2（1，7） P3（3，1） P4（6，5） P5（8，1） P6（12，9） 图 4-13 示例多边形

33 P0（7，8） P1（3，12） P2（1，7） P3（3，1） P4（6，5） P5（8，1） P6（12，9） 图 4-13 示例多边形

34 S=4扫描线处理完毕后 对于P3P4和P4P5两条边，因为下一条扫描线S=5和ymax相等，根据“下闭上开”的原则予以删除。
图 4-13 示例多边形 S=4扫描线处理完毕后 对于P3P4和P4P5两条边，因为下一条扫描线S=5和ymax相等，根据“下闭上开”的原则予以删除。

35 P0（7，8） P1（3，12） P2（1，7） P3（3，1） P4（6，5） P5（8，1） P6（12，9） 图 4-13 示例多边形 S=6扫描线处理完毕后 对于P2P3边，因为下一条扫描线S=7和ymax相等，根据“下闭上开”的原则予以删除。当S＝7时，添加上新边P1P2。

36 当S＝8时，添加上新边P0P1和P0P6。 图 4-13 示例多边形 P1（3，12） P6（12，9） P0（7，8） P2（1，7）

37 S=8这条扫描线处理完毕后 对于P5P6边和P0P6边，因为下一条扫描线S=9和ymax相等，根据“下闭上开”的原则予以删除。
图 4-13 示例多边形 S=8这条扫描线处理完毕后 对于P5P6边和P0P6边，因为下一条扫描线S=9和ymax相等，根据“下闭上开”的原则予以删除。

38 S=11的扫描线处理完毕后 对于P1P2边和P0P1边，因为下一条扫描线S=12和ymax相等，根据“下闭上开”的原则予以删除。至此，全部有效边表已经给出。

39 4.3.3 边表 从有效边表的建立过程可以看出，有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的位置坐标。为了确定在哪条扫描线上插入了新边，就需要构造一个边表（Edge Table，ET），用以存放扫描线上多边形各条边出现的信息。因为水平边的1/k为∞，并且水平边本身就是扫描线，在建立边表时可以不予考虑。 1.边表的表示法 (1)边表是按照扫描线顺序管理边的出现情况的一个数据结构。首先，构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶，对应多边形覆盖的每一条扫描线。

40 桶的数据结构定义 class Bucket { public: Bucket(); virtual ~Bucket();
int ScanLine;//扫描线 AET *p;//桶上的边表指针 Bucket *next; };

41 将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就存放在相应的扫描线桶中。
对于每一条扫描线，如果新增多条边，则按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin 相等，则按照1/k由小到大排序，这样就形成边表，如图4-14所示。

42 图 4-14 边表结点 其中，x为新增边低端的x|ymin值，用于判断边表在桶中的排序；ymax是该边所在的最大扫描线值，用于判断该边何时成为无效边。1/k是边在x方向的变化量和在y方向的变化量的比值，即△x/△y。从图4-14可以看出边表是有效边表的特例，即该边的最低点处的有效边表，有效边表和边表可以使用同一个数据结构来表示。

43 对于图 4-13示例多边形。边表结构如图4-15所示。
2.边表示例 对于图 4-13示例多边形。边表结构如图4-15所示。 P0（7，8） P1（3，12） P2（1，7） P3（3，1） P4（6，5） P5（8，1） P6（12，9） 图 4-13 示例多边形

44 2.边表示例 对于图 4-13示例多边形。边表结构如图4-15所示。 图 4-15 边表

45 算法步骤 (1)初始化：构造边表，AET表置空； (2)将第一个不空的ET表中的边与AET表合并；
(3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边； (4)yi+1=yi+1,根据xi+1=xi+1/k计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表； (5)AET表不为空则转(3)，否则结束。 算法flash演示

46 算法程序 见有效边填充算法程序

47 总结 该算法对显示的每个像素只访问一次，这样，输入/输出的要求可降低为最少。有由于该算法与输入/输出的细节无关，因而它也是与设备无关的。
有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法 该算法的主要缺点是对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。

48 4.4 边缘填充算法 4.4.1 填充原理 4.4.2 填充过程

49 4.4.1 填充原理 边缘填充算法是求出多边形的每条边与扫描线的交点，然后将交点右侧的所有像素颜色全部取为反色。按任意顺序处理完多边形的所有边后，就完成了多边形的填充任务。

50 4.4.2 填充过程 假定边的顺序为E0、E1、E2、E3、E4、E5、E6，如图4-16所示。填充过程如图4-17所示。
图 4-16 边缘填充算法示例多边形 P0（x0，y0） P1（x1，y1） E0 E1 E2 E3 E4 E5 E6

51 图 4-17 边缘填充算法原理

52 边缘填充算法 边缘填充算法最适用于具有帧缓冲器的图形系统，按任意顺序处理多边形的边。
在处理每条边时，仅访问与该边有交的扫描线上交点右方的像素。当所有的边都被处理之后，按扫描线顺序读出帧缓冲器的内容，送入显示设备。 该算法的优点是简单，缺点是对于复杂图形，每一像素可能被访问多次，输入输出的量也比较大。

53 改进：栅栏填充算法 为了减少边填充算法访问像素的次数，可引入栅栏。所谓栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。

54 栅栏填充算法的基本思想 对于每条扫描线与多边形边的交点，就将交点与栅栏之间的像素取补。
若交点位于栅栏左边，则将交点之右，栅栏之左的所有像素取补；若交点位于栅栏右边，则将栅栏之右，交点之左的像素取补。 下图是采用栅栏填充算法的示意图。栅栏填充算法只是减少了被重复访问像素的次数，但仍有一些像素会被重复访问。

55 栅栏线 P5 P3 P4 P1 P2 P2P3 P3P4 P5P1 P4P5 栅栏填充算法示意图

56 区域填充 区域是指已经表示成点阵形式的填充图形，它是像素集合。
区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的

57 4-邻接点和8-邻接点

58 4-连通区域和8-连通区域 表示方法：内点表示、边界表示 把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法。
边界填充算法（Boundary-fill Algorithm）。 枚举出给定区域内所有象素的表示方法称为内点表示法。 泛填充算法（Flood-fill Algorithm）

59 4-连通区域和8-连通区域

60 4-连通边界填充算法 算法的输入：种子点坐标(x,y)，填充色和边界颜色。 栈结构实现4-连通边界填充算法的算法步骤为：
种子象素入栈；当栈非空时重复执行如下三步操作： (1)栈顶象素出栈； (2)将出栈象素置成填充色； (3)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。

61 8-连通边界填充算法 栈结构实现8-连通边界填充算法的算法步骤为： 种子象素入栈；当栈非空时重复执行如下三步操作： (1)栈顶象素出栈；
(2)将出栈象素置成填充色； (3)检查出栈象素的8-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。

62 算法讨论 算法特点： 算法改进 可以用于填充带有内孔的平面区域。 把太多的象素压入堆栈
通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。

63 改进的扫描线种子填充算法步骤 种子象素入栈；当栈非空时作如下三步操作： (1)栈顶象素出栈；
(2)填充出栈象素所在扫描行的连续象素段，直到遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描线区间进行填充； (3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、未填充边界的象素，则把每一区间的最右象素取作种子象素入栈。 算法演示flash

64 泛填充算法 泛填充算法：对一个不是用单一颜色边界定义的区域填充（或重新上色），可通过替换指定的内部颜色来对这个区域涂色而不是搜索边界颜色值
算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。 算法原理： 算法从指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。

65 8-连通泛填充算法步骤 种子象素入栈；当栈非空时重复执行如下三步操作： (1)栈顶象素出栈； (2)将出栈象素置成填充色；
(3)检查出栈象素的8-邻接点，若其中某个象素点不是给定内部点的颜色且未置成新的填充色，则把该象素入栈。

66 注意 当以边界表示时，4-连通边界填充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。
当以内点表示时，8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域。 见示例

67 4.6 本章小结 本章主要讲解了多边形的填充原理。有效边表算法可以访问多边形内的每一个像素，是光照模型的基础，请读者深刻体会AET表和ET表的内涵。AET表表示的是扫描线在一条边上的连贯性，ET表表示的是新边在扫描线上的插入位置，ET表是AET表的特例。种子填充算法主要包括四邻接点算法和八邻接点算法，特别要注意区分四连通域和八连通域。

68 4.7 习题 1.试写出图4-28所示多边形的边表和扫描线y＝4的有效边表。
图4-28 多边形 图4-29多边形 2.写出图4-29所示多边形的边表，并按x|ymin由小到大排序，若x|ymin相等，则按照1/k由小到大排序。

69 3.给定四个点绘制图4-30所示的不同转角的两个正方形，使用有效边表算法编程对其进行填充，填充效果如图4-31所示，注意采用“上闭下开”和“左闭右开”原则实现，使得每个正方形的右边界和下边界没有填充。
图4-30填充正方形 图4-31 正方形填充效果 4.图4-37和4-38所示正方形分别由两个三角形面片组成，可以通过填充三角形面片完成正方形的填充任务。使用有效边表算法编程实现，填充效果分别如图4-38和4-40所示。请观察在每个正方形的三角形连接处是否有没有填充到的线段。

70 图4-34 三角形面片填充正方形 图4-33 正方形填充效果 5.图4-41所示正方形分别由四个三角形面片组成，可以通过填充三角形面片完成正方形的填充任务。使用有效边表算法编程实现，填充效果如图4-37所示。请观察在每个正方形的三角形连接处是否有没有填充到的线段。 图4-36 三角形面片填充正方形 图4-37 正方形填充效果

71 6.绘制一个正方形，把正方形四等分，如图4-38所示，使用有效边表算法用蓝、黑、黄、红四种颜色分别填充每个小四边形面片，观察大正方形的填充效果，如图4-39所示。
图4-38 四边形面片填充正方形 图4-39 正方形填充效果 7.边缘填充算法中，像素的取补范围为每条边到屏幕整个客户区的右边界。请设置如图4-40所示的外接矩形，并使用边缘填充算法编程实现多边形的填充。填充效果如图4-41所示。

72 4-41带外接矩形的多边形填充效果图 图 4-40 带外接矩形的多边形图 8.边缘填充算法的重要缺点是每一个像素可能被多次访问。为此，在多边形外接矩形的中心设置栅栏，把多边形分成两部分，如图4-42所示。在处理每条扫描线时，只将交点与栅栏间的像素取补。请读者编程实现。填充效果如图4-43所示。 图 4-47 带栅栏的的多边形图 4-48带栅栏的多边形填充效果图

73 9.编写八邻接点算法填充图4-44所示的八连通区域，请注意在两个正方体的连接处有一个像素的连通，如图4-45所示。
图 4-44八连通域 图 4-50八连通域交点放大图 10.扫描线种子填充算法是通过扫描线来填充水平像素段，仅将每条扫描线的最右端像素点入栈，可以有效提高算法效率，请编程实现。

74 11.使用鼠标在屏幕上绘制任意顶点数的封闭多边形并填充，填充效果如下图所示。编程要求：⑴多边形的顶点数不受限制；⑵按下鼠标左键，拖动鼠标绘制多边形，同时按下Shift键可以绘制水平边或垂直边；⑶单击鼠标右键闭合多边形；⑷使用边缘填充算法填充多边形。请读者编程实现。