第五章基本图形生成算法 5.4区域填充 16 5.42边填充算法 1、正负相消算法: 基本思想:对于每一条扫描线和每条多边形的交点,将该扫描 线上交点右方所有的象素取补。对多边形的每一条边作此 处理,多边形各边的处理顺序随意。 优点:算法简单 缺点:1)每个象素可能被访问多次; 2)输入/输出量大
16 第五章 基本图形生成算法 5.4 区域填充 5.4.2 边填充算法 1、正负相消算法： 基本思想：对于每一条扫描线和每条多边形的交点，将该扫描 线上交点右方所有的象素取补。对多边形的每一条边作此 处理，多边形各边的处理顺序随意。 优点：算法简单 缺点：1）每个象素可能被访问多次； 2）输入/输出量大
第五章基本图形生成算法 5.4区域填充 17 5.42边填充算法 再例:
17 第五章 基本图形生成算法 5.4 区域填充 5.4.2 边填充算法 再例：
第五章基本图形生成算法 5.4区域填充 18 5.42边填充算法 2.栅栏填充算法 栅栏:与扫描线垂直的直线,通常过多边形顶点,且将多边形分成两半 方法:对每个扫描线与多边形的交点,将交点与栅栏间的像素取“补” 特点: 方法简单 减少了被重复访问的像素,特别是有多个填充对象时,效果显著
18 第五章 基本图形生成算法 5.4 区域填充 5.4.2 边填充算法 2. 栅栏填充算法 栅栏：与扫描线垂直的直线，通常过多边形顶点，且将多边形分成两半 方法：对每个扫描线与多边形的交点，将交点与栅栏间的像素取“补” 特点： ⚫ 方法简单 ⚫ 减少了被重复访问的像素，特别是有多个填充对象时，效果显著
第五章基本图形生成算法 5.4区域填充 19 5.42边填充算法 3.边标志算法 步骤: 1.对多边形的每一条边进行扫描转换,即对多边形边界所经过 的象素作一个边界标志。 2填充。对每条与多边形相交的扫描线,按从左到右的顺序, 逐个访问该扫描线上的象素。 取一个布尔变量 inside来指示当前点的状态,若点在多边形内, 则 inside为真。若点在多边形外,则 inside为假。 Inside的初始值为假,每当当前访问象素为被打上标志的点, 就把 Iinside取反。对未打标志的点, inside不变
19 第五章 基本图形生成算法 5.4 区域填充 5.4.2 边填充算法 3. 边标志算法 步骤： 1. 对多边形的每一条边进行扫描转换，即对多边形边界所经过 的象素作一个边界标志。 2.填充。对每条与多边形相交的扫描线，按从左到右的顺序， 逐个访问该扫描线上的象素。 取一个布尔变量inside来指示当前点的状态，若点在多边形内， 则inside为真。若点在多边形外，则inside为假。 Inside 的初始值为假，每当当前访问象素为被打上标志的点， 就把inside取反。对未打标志的点，inside不变
第五章基本图形生成算法 5.4区域填充 20 5.42边填充算法 分为两个步骤: (1)打标记 43210 (2)填充 Inside 初值:假 遇到标记点:取反 98765432 真:填充; 假:不填充 012345678910111213141516 当用软件实现本算法时,速度与改进的有效边表算法相当,但本算法用 硬件实现后速度会有很大提高。注:算法见P184
20 第五章 基本图形生成算法 5.4 区域填充 5.4.2 边填充算法 分为两个步骤： (1)打标记 (2)填充 Inside 初值：假 遇到标记点：取反 真：填充； 假：不填充 当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用 硬件实现后速度会有很大提高。注：算法见P184