南京大学：《计算机图形学》课程教学资源（PPT课件讲稿）第7讲 图元填充与裁剪算法

第7讲图元填充与裁剪算法 1扫描转换填充算法 2区域填充算法 3图元裁剪算法

第7讲 图元填充与裁剪算法 1 扫描转换填充算法 2 区域填充算法 3 图元裁剪算法

1.图元填充算法 2-3

2-3 1. 图元填充算法

学习要点 填充图元生成的基本原理 多边形的类型与表示方式 填充图元生成的方式 扫描转换方法 扫描线与多边形边相交的处理 扫描转换的连贯性和增量计算 区域填充方法 区域的表示及连通类型 区域内点、外点测试 奇偶规则 非零环绕规则 2-4

2-4 学习要点 ◼ 填充图元生成的基本原理 ◼ 多边形的类型与表示方式 ◼ 填充图元生成的方式 ◼ 扫描转换方法 ◼ 扫描线与多边形边相交的处理 ◼ 扫描转换的连贯性和增量计算 ◼ 区域填充方法 ◼ 区域的表示及连通类型 ◼ 区域内点、外点测试 ▪ 奇偶规则 ▪ 非零环绕规则

学习要点 区域的边界填充算法:边界表示的区域的填充 递归边界填充 扫描线边界填充 区域泛滥填充算法:内点表示的区域的填充 图像填充 ■两种方法的比较 填充图元属性 2-5

2-5 学习要点 ◼ 区域的边界填充算法：边界表示的区域的填充 ▪ 递归边界填充 ▪ 扫描线边界填充 ◼ 区域泛滥填充算法：内点表示的区域的填充 ◼ 图像填充 ◼ 两种方法的比较 ◼ 填充图元属性

填充图元生成的基本概念 ■填充图元:用实心(某种颜色)或图案填充边界闭合的图元。 涉及两个方面问题: ■图元内哪些像素要被填充 用什么值填充 ■通常的图元填充是指多边形填充 多边形:一系列首尾相连的直线段构成的图形 多边形图元有线性边界 多边形填充更加容易处理 二维多边形填充是三维面着色的基础 2-6

2-6 填充图元生成的基本概念 ◼ 填充图元：用实心（某种颜色）或图案填充边界闭合的图元。 涉及两个方面问题： ◼ 图元内哪些像素要被填充 ◼ 用什么值填充 ◼ 通常的图元填充是指多边形填充 ◼ 多边形：一系列首尾相连的直线段构成的图形 ◼ 多边形图元有线性边界 ◼ 多边形填充更加容易处理 ◼ 二维多边形填充是三维面着色的基础

多边形的类型与表示方法 多边形有多种类型,如凸多边形、凹多边形、含环的多 边形等 凸/多边形:如果在多边形内任意选取不相同的两点 ,其连线上的所有点均在该多边形内,则称为凸多边 形;否则称为凹多边形 含环的多边形:多边形内部有洞 2-7

2-7 多边形的类型与表示方法 ◼ 多边形有多种类型，如凸多边形、凹多边形、含环的多 边形等 ◼ 凸/凹多边形：如果在多边形内任意选取不相同的两点 ，其连线上的所有点均在该多边形内，则称为凸多边 形；否则称为凹多边形 ◼ 含环的多边形：多边形内部有洞

多边形的类型与表示方法 多边形有两种表示方法: √顶点表示:用多边形的顶点序列(逆时针或顺时针)来 刻画多边形。这种表示直观,几何意义强,占空间少,易 于进行几何变换,被广泛应用于各种几何造型系统中 √点阵表示:用多边形上的像素的集合来刻画多边形。 这种表示虽然失去了很多重要几何信息(如边界、顶点 等),但它却是光栅显示系统显示时所需的表示形式。 占用空间大 2-8

2-8 多边形的类型与表示方法 ◼ 多边形有两种表示方法： ✓顶点表示：用多边形的顶点序列（逆时针或顺时针）来 刻画多边形。这种表示直观，几何意义强，占空间少，易 于进行几何变换，被广泛应用于各种几何造型系统中 ✓点阵表示：用多边形上的像素的集合来刻画多边形。 这种表示虽然失去了很多重要几何信息（如边界、顶点 等），但它却是光栅显示系统显示时所需的表示形式。 占用空间大

填充图元生成基本方法 ■由于多边形表示的不同,光栅系统中分为两种多边形填 充(填充图元生成)方法: 扫描转换填充(多边形扫描填充) 针对顶点表示的多边形区域 通过确定横越区域的扫描线的覆盖间隔来填充多边 形 可用来填充多边形、圆、椭圆和其它简单曲线 围成的区域(给定边界的区域 2-9

2-9 填充图元生成基本方法 ◼ 由于多边形表示的不同，光栅系统中分为两种多边形填 充(填充图元生成)方法： ◼ 扫描转换填充(多边形扫描填充) ◼ 针对顶点表示的多边形区域 ◼ 通过确定横越区域的扫描线的覆盖间隔来填充多边 形 ▪ 可用来填充多边形、圆、椭圆和其它简单曲线 围成的区域(给定边界的区域)

填充图元生成基本方法 ■区域填充: 针对点阵表示的多边形区域 从给定的位置出发,涂描着色直到满足指定的 边界条件为止 具有复杂形状边界的图元填充 交互式涂描填充 2-10

2-10 填充图元生成基本方法 ◼ 区域填充： ✓ 针对点阵表示的多边形区域 ✓ 从给定的位置出发，涂描/着色直到满足指定的 边界条件为止 ◼ 具有复杂形状边界的图元填充 ◼ 交互式涂描填充

多边形扫描转换填充 ■基本思路:从多边形的顶点描述出发,求出位于 其内部的各个像素,再将其颜色值填入帧缓冲器 的相应单元 大多数多边形用顶点表示法描述 顶点表示的多边形无法直接显示 顶点表示的多边形无法直接描述其内部点阵信 息;因此必须根据顶点信息求出其内部像素后 才能填充显示 2-11

2-11 多边形扫描转换填充 ◼ 基本思路：从多边形的顶点描述出发，求出位于 其内部的各个像素，再将其颜色值填入帧缓冲器 的相应单元 ◼ 大多数多边形用顶点表示法描述 ◼ 顶点表示的多边形无法直接显示 ◼ 顶点表示的多边形无法直接描述其内部点阵信 息；因此必须根据顶点信息求出其内部像素后 才能填充显示