P4/P3 图2.3.5扫描线与多边形相交,特殊情况的处理 2.3.1.2边界标志算法 边界标志算法的基本思想是:在帧缓冲器中对多边形的每条边进行直线扫描转换,亦即对多边形边界所 经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对 每条与多边形相交的扫描线依从左到右的顺序,逐个访问该扫描线上的象素。使用一个布尔量 inside来指 示当前点是否在多边形内的状态。 Inside的初值为假,每当当前访问的象素为被打上边标志的点,就把 inside取反。对未打标志的象素, inside不变。若访问当前象素时, inside为真,说明该象素在多边形内 则把该象素置为填充颜色 边界标志算法 void edgemark fill(pol ydef, color 多边形定义 polytef: int cold 对多边形 polytef每条边进行直线扫描转换 inside False for(每条与多边形 polytef相交的扫描线y) for(扫描线上每个象素x) if(象素x被打上边标志) inside=!( inside) if(inside!= FALSE) drawpixel (x, y, color) else drawpixel (x, y, background) 图2.3.6正方形内切n个圆的边界标志算法 用软件实现时,扫描线算法与边界标志算法的执行速度几乎相同,但由于边界标志算法不必建立维护边 表以及对它进行排序,所以边界标志算法更适合硬件实现,这时它的执行速度比有序边表算法快一至两个 数量级 2.3.2区域填充算法 这里讨论的区域指已经表示成点阵形式的填充图形,它是象素的集合。区域可采用内点表示和边界表示 两种表示形式。在内点表示中,区域内的所有象素着同一颜色。在边界表示中,区域的边界点着同一颜色 区域填充指先将区域的一点赋予指定的颜色,然后将该颜色扩展到整个区域的过程 区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点的颜色扩展到区域内的其它 点。区域可分为4向连通区域和8向连通区域。4向连通区域指的是从区域上一点出发,可通过四个方向, 即上、下、左、右移动的组合,在不越出区域的前提下,到达区域内的任意象素:8向连通区域指的是从区 域内每一象素出发,可通过八个方向,即上、下、左、右、左上、右上、左下、右下这八个方向的移动的 ●●● 组合来到达 四个方向运动八个方向运动 四连通区域 八连通区域 ●●●● 图2.3.7四连通区域和八连通区域 ●●● 计算机图形学第二章第24页共27页计算机图形学 第二章 第 24 页 共 27 页 图 2.3.5 扫描线与多边形相交，特殊情况的处理 2.3.1.2 边界标志算法 边界标志算法的基本思想是：在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所 经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对 每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的象素。使用一个布尔量 inside 来指 示当前点是否在多边形内的状态。Inside 的初值为假，每当当前访问的象素为被打上边标志的点，就把 inside 取反。对未打标志的象素，inside 不变。若访问当前象素时，inside 为真，说明该象素在多边形内， 则把该象素置为填充颜色。 边界标志算法： void edgemark_fill(polydef, color) 多边形定义 polydef； int color; { 对多边形 polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形 polydef 相交的扫描线 y ) for (扫描线上每个象素 x ) { if(象素 x 被打上边标志)inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); } } 图 2.3.6 正方形内切 n 个圆的边界标志算法 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边 表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个 数量级。 2.3.2 区域填充算法 这里讨论的区域指已经表示成点阵形式的填充图形，它是象素的集合。区域可采用内点表示和边界表示 两种表示形式。在内点表示中，区域内的所有象素着同一颜色。在边界表示中，区域的边界点着同一颜色。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它 点。区域可分为 4 向连通区域和 8 向连通区域。4 向连通区域指的是从区域上一点出发，可通过四个方向， 即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素；8 向连通区域指的是从区 域内每一象素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的 组合来到达。 四个方向运动 八个方向运动 四连通区域 八连通区域 图 2.3.7 四连通区域和八连通区域