计算机图形学 (6)(精品·公开课件).ppt

余 敦 辉 湖北大学 数计学院 第五章 基本图形生成算法5.4 区域填充 填充共有如下三种： 1、有序边表法： 优点：对每个元素值访问一次，输入输出要求降为最少，适于软件实现； 2、边填充算法（正负相消算法）：适于硬件实现； 边填充 分类： 栅栏填充； 边标志法； 3、种子填充：为一个递归算法。 可分为 漫水法 简单种子填充 种子填充法 扫描线填充 第五章 基本图形生成算法5.4 区域填充 区域：指相互连通的一组象素的集合。区域通常由一个封闭的轮廓线来定义，处于一个封闭轮廓线内的所有象素点构成一个区域。 区域填充：将区域内的象素置成新的颜色，新的颜色可以是常数，表示填以某种颜色；也可以是变量，表示填充的是图案。 区域填充需解决的问题： 1）确定需要填充哪些象素； 2）确定用什么颜色； 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 顶点表示：用多边形的顶点序列来 刻划多边形 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 （1）凸多边形和凹多边形 凸多边形：对于多边形内任意两点，连接他们的直线上的所有点均在该多边形内部，该多边形即为凸多边形； 凹多边形：不满足上述条件的多边形即为凹多边形； （2）多边形的内点和外点： 内点：填充成固定颜色或图案； 外点：不填充； 边界点：作为内点还是外点视要求而定。 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 （3）内外点判定——奇偶性原理 从无穷远处向该点引一条射线，如果这条射线与多边形的交点为奇数时，此点为内点，否则为外点。 推导：当射线与多边形相交奇数次后，线上点都是内点，偶数次相交后线上点都是外点。 特例：顶点是交点。 若射线与多边形顶点相交 a）共享顶点的两条边分别位于扫描线的两边，交点算一个。 b）共享顶点的两条边都位于扫描线的下边，交点算零个。 c）共享顶点的两条边都位于扫描线的上边，交点算二个。 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 请分别回答A～H点中哪些点需要填充？为什么？ 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 （4）边界处理 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 （5）确定扫描线 y=scan ymin ≤ scan ≤ ymax 原因：所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。 如何判断多边形的一条边与扫描线是否相交？(ymin,ymax) 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 （6）扫描线的连贯性 当前扫描线与各边的交点顺序，与下一条扫描线与各边的交点顺序很可能相同或类似。 只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。 （7）边的连贯性 当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交。 与当前扫描线相交的边称为活动边（active edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活动边表（AET, Active edge table) 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 （8）数据结构 ① “新边表” (有序边表) 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 第五章 基本图形生成算法5.4 区域填充5.4.1 多边形填充 算法步骤： (1)初始化：构造边表ET，将AET表置空； (2)将第一个不空的ET表中的边与AET表合并； (3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边； (4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表； (5)AET表不为空则转(3)，否则结束。 注：算法见P182 第五章 基本图形生成算法5.4 区域填充5.4.2 边填充算法