计算机圆形学 余敦辉 湖北大学数计学院
1 余 敦 辉 湖北大学 数计学院 计算机图形学
第五章基本图形生成算法 5.4区域填充 填充共有如下三种: 1、有序边表法 优点:对每个元素值访问一次,输入输出要求降为最少,适于 软件实现; 2、边填充算法(正负相消算法):适于硬件实现; 边填充 分类:了栅栏填充; 边标志法; 3、种子填充:为一个递归算法。 可分为漫水法 简单种子填充 种子填充法 扫描线填充
2 第五章 基本图形生成算法 5.4 区域填充 填充共有如下三种： 1、有序边表法： 优点：对每个元素值访问一次，输入输出要求降为最少，适于 软件实现； 2、边填充算法（正负相消算法）：适于硬件实现； 边填充 分类： 栅栏填充； 边标志法； 3、种子填充：为一个递归算法。 可分为 漫水法 简单种子填充 种子填充法 扫描线填充
第五章基本图形生成算法 5.4区域填充 区域:指相互连通的一组象素的集合。区域通常由 个封闭的轮廓线来定义,处于一个封闭轮廓线内的 所有象素点构成一个区域。 区域填充:将区域内的象素置成新的颜色,新的颜色 可以是常数,表示填以某种颜色;也可以是变量, 表示填充的是图案。 区域填充需解决的问题: )确定需要填充哪些象素; 2)确定用什么颜色;
3 第五章 基本图形生成算法 5.4 区域填充 区域：指相互连通的一组象素的集合。区域通常由一 个封闭的轮廓线来定义，处于一个封闭轮廓线内的 所有象素点构成一个区域。 区域填充：将区域内的象素置成新的颜色，新的颜色 可以是常数，表示填以某种颜色；也可以是变量， 表示填充的是图案。 区域填充需解决的问题： 1）确定需要填充哪些象素； 2）确定用什么颜色；
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 顶点表示:用多边形的顶点序列来点阵表示:用位于多边形内的象 刻划多边形 素的集合来刻划多边形 12 ……;… 多边形的扫 描转换或多 09876543 边形的填充 123456789101112x (a)多边形PoPP2PP4P5PePo
4 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 顶点表示：用多边形的顶点序列来 刻划多边形 点阵表示：用位于多边形内的象 素的集合来刻划多边形 多边形的扫 描转换或多 边形的填充 x y 1 2 3 4 5 6 7 8 9 11 1 2 3 4 5 6 7 8 9 10 11 12 10 12 p1 p3 p4 p5 (a) 多边形P0P1P2P3P4P5P6P0 p2 p0 p6
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 (1)凸多边形和凹多边形 凸多边形:对于多边形内任意两点,连接他们的直线上的所有 点均在该多边形内部,该多边形即为凸多边形; 凹多边形:不满足上述条件的多边形即为凹多边形; (2)多边形的内点和外点: 内点:填充成固定颜色或图案; 外点:不填充; 边界点:作为内点还是外点视要求而定
5 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （1）凸多边形和凹多边形 凸多边形：对于多边形内任意两点，连接他们的直线上的所有 点均在该多边形内部，该多边形即为凸多边形； 凹多边形：不满足上述条件的多边形即为凹多边形； （2）多边形的内点和外点： 内点：填充成固定颜色或图案； 外点：不填充； 边界点：作为内点还是外点视要求而定
第五章基本图形生成算法 5.4区域填充 54.1多边形填充 (3)内外点判定—奇偶性原理 从无穷远处向该点引一条射线,如果这条射线与多边形的交点 为奇数时,此点为内点,否则为外点 推导:当射线与多边形相交奇数次后,线上点都是内点,偶数 次相交后线上点都是外点。 特例:顶点是交点。 若射线与多边形顶点相交 a)共享顶点的两条边分别位于扫描线的两边,交点算一个 b)共享顶点的两条边都位于扫描线的下边,交点算零个。 c)共享顶点的两条边都位于扫描线的上边,交点算二个
6 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （3）内外点判定——奇偶性原理 从无穷远处向该点引一条射线，如果这条射线与多边形的交点 为奇数时，此点为内点，否则为外点。 推导：当射线与多边形相交奇数次后，线上点都是内点，偶数 次相交后线上点都是外点。 特例：顶点是交点。 若射线与多边形顶点相交 a）共享顶点的两条边分别位于扫描线的两边，交点算一个。 b）共享顶点的两条边都位于扫描线的下边，交点算零个。 c）共享顶点的两条边都位于扫描线的上边，交点算二个
第五章基本图形生成算法 5.4区域填充 54.1多边形填充 y 请分别回答A~H点中哪 12 些点需要填充?为什 么? 987654321 G 123456789101112g 图5-23x-扫描线算法填充多边形
7 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 请分别回答A～H点中哪 些点需要填充？为什 么？
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 (4)边界处理 边界上象素的取舍原则: 432 左闭右开 下上开一 012345 屏幕坐标顶点在 (0,0),(40)(4,3),(0,3)的矩 型 01234
8 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （4）边界处理 屏幕坐标顶点在 (0,0),(4,0),(4,3),(0,3)的矩 型 0 1 2 3 4 1 2 3 0 1 2 3 4 5 1 2 3 4 边界上象素的取舍原则： 左闭右开 下闭上开
第五章基本图形生成算法 5.4区域填充 5.4.1多边形填充 (5)确定扫描线y=scan 12 inax ymin≤scan≤ymax 10 98z 原因:所有的边和扫描线求交, 效率很低。因为一条扫描 线往往只和少数几条边相 654321 交 y-Jnin 456789101122 如何判断多边形的一条边与扫 图5-23x-扫描线算法填充多边形 描线是否相交? (ymin, ymax)
9 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （5）确定扫描线y=scan ymin ≤ scan ≤ ymax 原因：所有的边和扫描线求交， 效率很低。因为一条扫描 线往往只和少数几条边相 交。 如何判断多边形的一条边与扫 描线是否相交？ (ymin,ymax)
第五章基本图形生成算法 5.4区域填充 10 5.4.1多边形填充 (6)扫描线的连贯性 当前扫描线与各边的交点顺序,与下一条扫描线与各边 的交点顺序很可能相同或类似。 只需对当前扫描线的活动边表作更新,即可得到下一条 扫描线的活动边表。 (7)边的连贯性 当某条边与当前扫描线相交时,它很可能也与下一条扫 描线相交。 与当前扫描线相交的边称为活动边( active edge),把它 们按与扫描线交点x坐标递增的顺序存入一个链表中,称为 活动边表(AET, Active edge table)
10 第五章 基本图形生成算法 5.4 区域填充 5.4.1 多边形填充 （6）扫描线的连贯性 当前扫描线与各边的交点顺序，与下一条扫描线与各边 的交点顺序很可能相同或类似。 只需对当前扫描线的活动边表作更新，即可得到下一条 扫描线的活动边表。 （7）边的连贯性 当某条边与当前扫描线相交时，它很可能也与下一条扫 描线相交。 与当前扫描线相交的边称为活动边（active edge)，把它 们按与扫描线交点x坐标递增的顺序存入一个链表中，称为 活动边表（AET, Active edge table)