第3章填充多边形 光栅扫描显示器的特点是它具有表示实区域(solidarea)的能力。根据顶点的描述生 成实区域的过程称为实区域光栅化,相应的算法称为区域填充算法。常用的区域填充算法 分为两大类:光栅化算法与种子填充算法。 3.多边形的光栅化 1 计算机中早期表示物体的方法是线框模型。线框模型用定义物体轮廓线的直线或曲线 绘制。线框模型并不存在面的信息,每一段轮廓线都是单独构造出来的。图3-1(a)所示为 球体线框模型。为了提升真实感效果,从20 世纪70 年代开始,计算机中物体的表示方法开始 向表面模型转换。与线框模型相比,表面模型显得更加生动、直观,真实感更强。对线框模型 添加材质属性后,根据场景中视点、光源的位置及朝向,先计算出多边形网格顶点的颜色,然后 使用光滑着色模式填充每个多边形内部,便得到表面模型。球体表面模型如图3-1(b)所示。 图3-1 球体的计算机表示法 3.1 多边形的定义 1. 多边形是由折线段组成的平面封闭图形。它 由有序顶点的点集Pi (0,…,及有向边 的线集Ei(i=n- i= 定义, n-1) 0,…,1) n 为多边形的顶点 数或边数,且Ei =PiPi+1(0,…,1)。这里 i=n- Pn =P0,保证了多边形的闭合。多边形可以分为 凸、凹多边形以及环,如图3-2所示。多边形具有 顶点、边、面和法线等基本几何属性。 1. 凸多边形 含有凸点的多边形称为凸多边形。凸点对应 的内角小于180°。多边形上任意两顶点间的连线 都在多边形之内。 图3-2 多边形的定义 ·34· 2. 凹多边形 至少有一个凹点的多边形称为凹多边形。凹点对应的内角大于180°。多边形上任意 两顶点间的连线有不在多边形内部的部分。 3. 环 多边形内部含有另外的多边形称为环。如果规定每条有向边的左侧为其内部区域,则 当观察者沿着边界行走时,内部区域总在其左侧。这就是说,多边形外轮廓线的环形方向为 逆时针,内轮廓线的环形方向为顺时针。 1.多边形的表示 3.2 在计算机图形学中,多边形有两种表示方法:点元表示法与面元表示法。 1. 点元表示法 点元表示法是一种用多边形的顶点序列来描述多边形的方法,其特点是直观、占内存 少、易于进行几何变换,但由于没有明确指出哪些像素位于多边形之内,所以不能直接进行 填充。点元表示法是多边形线框模型描述的形式,如图3-3(a)所示。 图3-3 多边形的表示法 2. 面元表示法 面元表示法是一种用位于多边形内部的像素点集来描述多边形的方法。这种表示方法 虽然失去了顶点、边界等许多重要的几何信息,但便于直接读取像素来填充多边形。面元表 示法是多边形表面模型描述的形式,如图3-3(b)所示。 3. 多边形的光栅化 将多边形的描述从点元表示法变换到面元表示法的过程,称为多边形的光栅化。即从 多边形的顶点信息出发,计算位于多边形轮廓线内部的各个像素点的信息,并按照扫描线顺 序,将像素点颜色写入多边形中。 1.多边形着色模式 3.3 多边形可以使用平面着色模式(e)或光滑着色模式( flatshadingmodsmoothshadingmode)进行填充。无论采用哪种着色模式,都意味着要根据多边形的顶点颜色计算多边形 内部各个像素点的颜色。回顾一下,直线的平面着色模式是使用一个顶点的颜色绘制直线, ·35· 例如使用起点颜色作为直线的颜色,可以绘制出单一颜色的直线。直线的光滑着色模式是 使用两个顶点颜色来绘制直线,例如使用起点颜色和终点颜色的线性插值作为直线的颜色, 可以绘制出颜色渐变的直线。 1. 平面着色模式 多边形的平面着色模式是指使用多边形任意一个顶点的颜色填充多边形,多边形具有 单一颜色。图3-4(a)为三角形的平面着色。三角形3个顶点的颜色分别为红色、绿色、蓝 色。三角形的填充色取自第1个顶点颜色。 图3-4 三角形着色模式 2. 光滑着色模式 多边形的光滑着色模式假定多边形顶点的颜色不同,多边形任意一点的颜色由各顶点 的颜色进行双线性插值(bilinearinterpolation)得 到。基于顶点颜色的光滑着色模式也称为Gouraud 光滑着色模式。Gouraud是一名法国计算机科学 家,以提出Gouraud着色模式而闻名。图3-4(b)为 三角形的Gouraud着色。三角形填充色为3个顶 点颜色的双线性插值结果。 以图3-5所示三角形为例,说明Gouraud光滑 着色算法原理。假定三角形ABC 的3个顶点坐标 xA ,xB ,xC ,yC 为A(yA ),B(yB ),C()。 A 点的颜 色为cA , B 点的颜色为cB , C 点的颜色为cC 。在自 定义坐标系中, y 轴向上为正。当前扫描线为yi, 图3-5 光滑着色模式 扫描线最小值为ymin,最大值为ymax,扫描线从ymin向ymax移动,执行yi+1=yi+1 操作。 当前扫描线上, D 点的颜色可以通过 A 点颜色与 C 点颜色的线性插值得到 cD =(t)cC , t ∈[1] 31) 1-cA +t0,( 当前扫描线上, E 点的颜色可以通过 A 点颜色与 B 点颜色的线性插值得到 cE =(t)cB , t ∈[1] 32) 1-cA +t0,( 当前扫描线上,DE 跨度内任意一点 F 的颜色通过 D 点颜色与 E 点颜色插值得到 cF =(t)cE , t ∈[1] ( 1-cD +t0,33) 随着扫描线从ymin向ymax移动, F 点会遍历三角形内部,其颜色为三角形的3个顶点颜 色的双线性插值。 3. 马赫带 图3-6所示图形是一组亮度递增变化的平面着色矩形块。由于矩形块的亮度发生轻微 ·36· 的跳变,边界处的亮度对比度增强,使得矩形轮廓表现得非常明显。1868年奥地利物理学 家Mach发现了这种明暗对比的视觉效应,称为马赫带效应。在亮度变化的一侧感知到正 向尖峰效果,看到一条更亮的线;在另一侧感知到负向尖峰效果,看到一条更暗的线。马赫 带效应不是一种物理现象,而是一种心理现象,是由人类视觉系统造成的。马赫带效应夸大 了平面着色的渲染效果,使得人眼感知到的亮度变化比实际的亮度变化要大,如图3-7所 示。一个具有复杂光滑表面的物体是由一系列多边形(主要是三角形和四边形)网格表示 的。如果采用平面着色模式填充多边形,就会出现马赫带效应,边界特别明显。物体看上去 就像是一片一片拼接起来的,显得很不真实。改善的方法是用光滑着色模式代替平面着色 模式来填充多边形。 图3-6 马赫带图3-7 边界位置的实际亮度与感知亮度 3.边界像素处理规则 2 首先自定义二维坐标系, x 轴向右, y 轴向上,扫描线自下向上移动。由于CDC类的 Rectangle()成员函数使用画笔绘制矩形的边界,使用画刷填充矩形内部。CDC类的 FilSolidRect()成员函数不使用画笔绘制边界,仅使用当前画刷填充整个矩形,包括左边界 和下边界,但不包括右边界和上边界。本节以矩形的光栅化为例,说明多边形边界像素的处 理规则。首先讨论以平面着色模式填充矩形,然后讨论以光滑着色模式填充矩形。 3.1 平面着色模式填充矩形 2. 矩形由左下角点P0(xmin,ymin)与右上角点P1(xmax,ymax)唯一定义,如图3-8所示。 在每条扫描线上,将矩形跨度内的所有像素都置成相同的颜色。填充单一的矩形时,从数学 上讲可以填充矩形所覆盖的内部像素及全部边界像素。但当多个矩形连接存在共享边界 图3-8 矩形填充效果图 ·37· 时,就不能填充矩形的全部边界像素。所有的光栅化算法对运算符<、>和=的使用都十分 敏感。 3.2 处理边界像素 2. 图3-9所示矩形P0P1P2P3 被等分为4个小矩形。假定左下方的小矩形P0P5P8P4 填充为绿色,右下方的小矩形P5P1P6P8 填充为黄色,右上方的小矩形P8P6P2P7 填充为 绿色,左上方的小矩形P4P8P7P3 填充为黄色。4个小矩形的公共边为P5P8、P8P7、 P4P8 和P8P6。考虑到公共边P5P8 既是小矩形P0P5P8P4 的右边界,又是小矩形 P5P1P6P8 的左边界;考虑到公共边P4P8 既是小矩形P0P5P8P4 的上边界,又是小矩形 P4P8P7P3 的下边界,那么P5P8 和P4P8 作为相邻小矩形的共享边界,应该着色为哪个小 矩形的颜色? 同理,P8P7 和P8P6 也作为相邻小矩形的共享边界,应该着色为哪个小矩形 的颜色? 如果对公共边不做处理,则可能将公共边先设置为一种颜色,然后又设置为另一种 颜色。一条边界两次不同的着色会导致混乱的视觉效果。图3-9的正确处理结果如 图3-10 所示,每个小矩形的右边界像素和上边界像素都不填充,等待与其相连接的后续小 矩形进行填充。最终,边界P5P8 和P4P8 填充为黄色,P8P7 和P8P6 填充为绿色,而边界 P3P7、P7P2、P1P6 和P6P2 并未进行填充。 图3-9 边界像素的问题图3-10 共享边界像素的处理 在实际填充过程中,也需要考虑到像素面积大小的影响:填充左下角为(1,1)、右上角 为(4,3)的矩形时,若将边界上的所有像素全部着色,就得到图3-11(a)所示的效果。矩形光 栅化后的像素覆盖面积为4×3 个单位,而实际矩形的面积只有3×2 个单位,如图3-11(b) 所示。如果不填充矩形的上边界和右边界,则可以保证其面积为3×2 个单位。 图3-11 根据像素计算矩形面积 边界像素处理规则为,由一条边界确定的包含图元的半平面,如果位于该边界的左方或 下方,那么这条边界上的像素就不属于该图元。可以将其简单表述为“左闭右开,下闭上 ·38· 开”,即绘制矩形左边界和下边界上的像素,不绘制矩形右边界和上边界上的像素。共享的 水平边将“属于”有共享边的两个矩形中靠上的那个;共享的垂直边将“属于”有共享边的两 个矩形中靠右的那个。本规则适用于任意形状的多边形,而不是只局限于矩形。本规则会 导致多边形遗失最上一行像素和最右一列像素,图形出现瑕疵。为了避免共享边界上的像 素发生两次重绘,没有比这更好的解决方法。 2.光滑着色模式填充矩形 3.3 光滑着色模式不再以单一颜色去填充矩形,矩形内部填充颜色是4个顶点的颜色的双 线性插值。这样越靠近顶点,顶点颜色就越突出。Gouraud着色模式为矩形填充了光滑的 渐变颜色。 图3-12(a)中,假定P0 点的颜色为红色、P1 点的颜色为绿色、P2 点的颜色为黄色、P3 点的颜色为蓝色。沿着 x 方向和 y 方向对顶点颜色进行双线性插值得到内点颜色,就可以 绘制出颜色渐变的图像。下面以一条扫描线为例进行讲解,首先由P0 点的颜色与P3 点的 颜色进行线性插值计算出扫描线上 A 点的颜色。由P1 点的颜色和P2 点的颜色进行线性 插值计算出在同一条水平扫描线上 B 点的颜色。在该扫描线上,由 A 点的颜色和 B 点的 颜色可以进行线性插值计算出 C 点的颜色。当扫描线从P0P1 边界向上移动到P3P2 边界 时,在每条扫描线上, C 点从 A 点移动到 B 点,那么 C 点将遍历矩形覆盖的所有像素。根据 “左闭右开”,矩形中每个跨度是在左边封闭而右边开放的区间内,不绘制每条扫描线的最右 像素点。根据“下闭上开”规则,不绘制最上一条扫描线。矩形的光滑着色效果如图3-12 (b)所示。 图3-12 矩形的光滑着色 3.边标志算法 3 3.1 基本思想 3. 由Agkland和Weste于1981 年提出的边标志算法,不仅可以处理凸多边形,而且可以 处理凹多边形。边标志算法分两步实现:第1步勾勒轮廓线。对多边形的每条边进行光栅 化,亦即对多边形边界所经过的像素打上标志,在每条扫描线上建立各跨度的边界像素点 对。第2步填充多边形。沿着扫描线由小往大的顺序,按照从左到右的顺序,填充像素点对 所构成的跨度之间的全部像素。 ·39· 3.2 光栅化边 3. 扫描线是 y 方向连续的,根据扫描线的连续性,所有边均可使用第2个八分圆域的 DDA 算法进行光栅化。扫描线由边的低端(y=ymin)向高端(y=ymax)运动,交点的 y 坐标 每次加1,交点的 x 坐标加1/k。 k 是边的斜率。 边的低端坐标为(y0), 边与下一条扫描线的交点为(xi+1,yi+1 )。其中,xi+1=xi + x0,1/k=xi+Δx/Δy=xi+m,yi+1 。交点相关性如图3-13 所示。这说明,随着扫描 yi+1= 线的移动,扫描线与有效边交点的 x 坐标,从起点开始可以按增量m=1/ k 计算出来。 图3-13 计算扫描线与边的交点 3.3 判断点与边的位置关系 3. 使用向量叉积运算,可以判断点与边的位置关系。图3-14(a)中,使用向量叉积,可以 判断点P1 与边P0P2 的位置关系。写为从P0 点发出的向量 →{-x0,0},→ ={-x0,0} P0P2=x2y2-y0,P0P1 x1y1-y0, 计算两向量的叉积N=P0P→2×P0P→1,有 N ={0,0,(x2-x0)(y1-y0)-(y2-y0)(x1-x0)} 假设Δz 代表三角形法向量的 z 分量,有 Δz=(x2y1-y0)-(x1-x0) 34) -x0)(-y0)(( y2 如果Δz>0,则P1 点位于边P0P2 的左侧,如图3-14(b)所示;否则,P1 点位于边P0P2 的 右侧,如图3-14(c)所示。 图3-14 判断点与边的位置关系 ·40· 说明:由于用到了向量的叉积,这里使用的是三维向量来表示平面二维向量,只是 P0P→2和P0P→1向量的 z 分量为0,而垂直于平面的法向量 N 的 x 分量和 y 分量为0。 3.4 平面着色模式填充三角形 3. 无论多么复杂的物体,最终都可以使用三角形小面逼近。解决了填充三角形的问题,就 解决了物体的表面着色问题。三角形是一个凸多边形,扫描线与三角形相交只有一对交点, 形成一个相交区间,称为跨度。本节以三角形的光栅化为例讲解边标志算法。 在三角形P0P1P2 中,对顶点进行排序,使P0 点为 y 坐标最小的点,P2 点为 y 坐标最 大的点,P1 点的 y 坐标位于二者之间。P0P2 称为三角形的主边。若P1 点位于主边左侧, 称为左三角形;若P1 点位于主边右侧,称为右三角形。为了区分跨度的起点与终点,约定 位于三角形跨度左侧的边的特征为真,位于跨度右侧的边的特征为假,如图3-15 所示。三 角形覆盖的扫描线的最小值为ymin=P0y,最大值为ymax=P2y。三角形所覆盖的扫描线 条数n=ymax-ymin+1 。使用DDA算法,将三条边离散到标志数组SpanLeft[n]和 Spaghn]中。Spnet数组存放边特征为真的离散点标志,SpnRight数组存放边特 nRit[aLf15(中,net数组存放的是P0aP1 边与P1P2 边的标 征为假的离散点标志。在图3-a) SpaLf 志点,Spaght数组存放的是P0P2 边的标志点;在图315(中,Spnet数组存放的是 nRi-b) aLfP0P2 边的标志点,SpanRight数组存放的是P0P1 边与P1P2 边的标志点。当扫描线从 ym向yma移动时,基于标志数组内标志点的颜色,使用颜色线性插值算法计算跨度内每个像素(i) 点的颜(x) 色。填充时,(n) 根据“左闭右开”的规则,不填充每条扫描线上的最右一个像素;根 据下闭上开的规则,不填充最后一条扫描线ymax。 图3-15 三角形的分类 算法9:平面着色的三角形填充算法 例3- 1 使用边标志算法填充图3-16(a)所示的三角形,写出SpanLeft数组与 SpanRight数组存储的标志。 从图中可知,三角形顶点为P0(1,1)、P1(5,3)和P2(4,7)。根据三角形主边顶点坐标 P0 和P2,可以计算出扫描线个数n=y2-y0+1=7。定义左边标志数组为SpanLeft[7]和 右边标志数组为SpanRight[7]。由于三角形为右三角形,所以SpanLeft[7]数组存放P0P2 边的标志,SpanRight[7]数组存放P0P1 边和P1P2 边的标志。这样,由于数组的下标索引 从0开始,所以SpanLeft[0]和SpanRight[0]数组对存放三角形所覆盖的第一条扫描线上 ·41· 图3-16 三角形离散为像素点 跨度两端的边标志;SpanLeft[6]和SpanRight[6]数组对存放三角形所覆盖的最后一条扫 描线上跨度两端的边标志。 第1条扫描线:SpanLeft[0]=(1,1),SpanRight[0]=(1,1); 第2条扫描线:SpanLeft[1]=(2,2),SpanRight[1]=(3,2); 第3条扫描线:SpanLeft[2]=(2,3),SpanRight[2]=(5,3); 第4条扫描线:SpanLeft[3]=(3,4),SpanRight[3]=(5,4); 第5条扫描线:SpanLeft[4]=(3,5),SpanRight[4]=(5,5); 第6条扫描线:SpanLeft[5]=(4,6),SpanRight[5]=(4,6)。 图3-16(b)中,边标志用黑色实心小圆表示,跨度内部的像素点用空心小圆表示。 3.5 光滑着色模式填充三角形 3. 在平面着色模式填充三角形的基础上,设定三个顶点的颜色后,可以对三角形进行光滑 着色。光滑着色是真实感图形的生成基础,可以使画面明暗自如、色彩丰富。假定,三角形 顶点P0 的颜色为红色、P1 的颜色为绿色、P2 的颜色为蓝色,沿着边和扫描线方向对颜色 进行双线性插值,绘制的三角形光滑着色效果如图3-17 所示。 图3-17 三角形光滑着色效果图 假定四边形的4个顶点颜色分别为红、绿、黄、蓝。四边形细分为左上和右下两个三角 形,或左下和右上两个三角形,如图3-18 所示。将其与图3-12(b)进行对比后可以看出,虽 然通过填充两个三角形可以完成填充四边形的任务,但二者的效果有一定差异,两个三角形 填充的四边形有明显的分界线。尽管如此,OpenGL 或者DirextX 中仍将四边形细分为两 个三角形后,才分别进行填充。 ·42· 图3-18 四边形细分为左上和右下两个三角形,或左下和右上两个三角形 算法10:光滑着色的三角形填充算法 3.有效边表算法 4 3节介绍的边标志算法用于填充三角形。如果需要填充复杂的多边形,则可以使用 x 扫描线算法。该算法可以一次性完成复杂多边形的填充,而不用将多边形细分为三角形。 3. 3.1 x 扫描线法 4. 多边形分为凸多边形与凹多边形。扫描线与凸多边形相交只有一个跨度。扫描线与凹 多边形边界可能会出现多个跨度。 x 扫描线算法填充多边形的基本思想是按扫描线顺序, 计算扫描线与多边形的相交区间,再用指定的颜色显示这些区间的像素。 x 扫描线算法的 核心是须按 x 递增顺序排列交点的 x 坐标序列。由此可以得到 x 扫描线算法步骤如下。 (1)确定多边形覆盖的扫描线条数,得到多边形顶点的最小 y 值ymin和最大 y 值ymax。 (2)从y=ym到y=ymax,每次用一条扫描线进行填充。对每条扫描线的填充过程可分为以下4个步骤。(n) (i) ①求交:计算扫描线与多边形各边的交点。 ②排序:把所有交点按 x 坐标递增顺序进行排序。 ③配对:将相邻交点配对,每对交点代表扫描线与多边形相交的一个跨度。 ④着色:把这些跨度内的像素置为填充色。 x 扫描线算法在处理每条扫描线时,需要与多边形的所有边求交,处理效率很低。这是 ·43· 因为一条扫描线往往只与多边形的少数几条边相交,甚至与整个多边形都不相交。若在处 理每条扫描线时,把所有边都拿出来与扫描线求交,则其中绝大多数运算都是徒劳的。因此 将 x 扫描线算法加以改进,形成有效边表算法,也称为 y 连贯性算法。 有效边表算法的基本思想是按照扫描线从小到大的移动顺序,计算当前扫描线与多边 形有效边的交点,然后把这些交点按 x 值递增的顺序进行排序、配对,以确定填充区间。有 效边表算法通过维护边表(edgetable,ET)与有效边表(activeedgetable,AET), 避开了扫 描线与多边形所有边求交的复杂运算,已成为最常用的多边形光栅化算法之一。有效边表 算法可以填充凸多边形、凹多边形和环。 3.2 示例多边形 4. 以图3-19 所示的凹多边形为示例多边形,讲解有效边表算法。示例多边形的点元表示 法为P0(7,8)、P1(3,12 )、P2(1,7)、P3(3,1)、P4(6,5)、P5(8,1)、P6(12,9)。多边形覆盖 的扫描线最小值为ymin=1,最大值为ymax=12 。假定多边形各个顶点的颜色都相同,填充 模式为平面着色。 -2.4. 图320 中,扫描线y=3与示例多边形有4个交点(3,3)、(5,3)、(7,3)和(9,3)。 边界交点的整数坐标为(2,3)、(5,3)、(7,3)和(9,3)。每个跨度的最后一个整数像素分别为 (5,3)和(9,3), 根据“左闭右开”规则不予填充。按 x 值递增的顺序对交点进行排序、配对 后的填充区间为[2,4]和[7,8], 共有5个像素。为了避免填充[5,6]区间,填充时设置一个 逻辑变量(初始值为假)进行区间内部外部测试(t)。按 x 值递增的顺序, inside-outsidetes 每访问一个交点,逻辑变量就取反一次。如果进入区间内部,逻辑变量为真;如果离开区间 内部,逻辑变量则为假。填充逻辑变量为真的所有区间内的像素,这样可以对有多个跨度的 扫描线进行正确处理。例如,进入区间[2,4]之内,逻辑变量为真;离开区间[2,4]后,逻辑变 量为假。再次进入[7,8]之内,逻辑变量为真;离开区间[7,8]后,逻辑变量为假。 图3-19 示例多边形图3-20 用一条扫描线填充示例多边形 3.3 顶点处理规则 4. 示例多边形的顶点可以分为3类。局部最高点P1、P6 和P4,共享顶点的两条边均落 在顶点所在扫描线的下方;普通连接点P2,共享顶点的两条边分别落在顶点所在扫描线的 ·44· 两侧;局部最低点P0、P3 和P5,共享顶点的两条边均落在顶点所在扫描线的上方。处理 时,常根据共享顶点的两条边的另一端的 y 值大于顶点 y 值的个数来将顶点个数分别置为 0、1和2。事实上,根据“下闭上开”的处理规则,有效边表算法能自动处理这3类顶点。 1. 普通连接点的处理规则 图3-21 中,普通连接点P2 是边P3P2 的终点,同时也是边P2P1 的起点,顶点个数计 为1。按照“下闭上开”的规则,P2 点作为P3P2 边 的终点不予填充,但作为P2P1 边的起点予以填充。 2. 局部最低点的处理规则 P0 点、P3 点和P5 点是局部最低点。如果处理 不当,扫描线y=1会填充区间[3,8], 结果填充了 P3 到P5 点之间的像素,如图3-21 中y=1扫描线 所示。将局部最低点的顶点个数计数为2。y=1的 扫描线填充时,共享顶点P3 的P3P2 边与P3P4 边 加入有效边表,所以P3 点被填充两次;同理,共享 顶点P5 的P5P4 边与P5P6 边加入有效边表,P5 点也被填充两次;共享顶点P0 的P0P1 边与P0P6 边加入有效边表,P0 点也被填充两次。图3-21 顶点的处理规则 3. 局部最高点的处理规则 局部最高点的顶点个数计数为0。根据“下闭上开”规则,扫描线会自动放弃P1 点、P4 点和P6 点。P1 点与P6 点将不予填充,而P4 点被经过P3P2 和P5P6 边的扫描线y=5 予以填充,如图3-21 所示。 4.有效边与有效边表 3.4 1. 有效边 多边形与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行求交 运算,可以避免与多边形的所有边求交,提高了算法效率。 2. 有效边表 将有效边按照与扫描线交点 x 坐标递增的顺序存放在一个链表中,称为有效边表。有 效边表利用了边的连贯性。 (1)与扫描线yi 相交的边,多数与扫描线yi+1 相交。 所示 ( 。 2)从一条扫描线到下一条扫描线,交点的 x 值增量相等。有效边表的结点如图3-22 图3-22 有效边表的结点 图3-22 中,ymax为有效边所在扫描线的最大值, x 为当前扫描线与有效边的交点;用于 判断该边何时扫描完毕后被抛弃而成为无效边;1/ k 为 x 坐标的增量,其值为斜率的倒数。 对于图3-19 给出的示例多边形,扫描线y=1至y=3的有效边表如图3-23 所示。 ·45· 图3-23 扫描线y=1至y=3的有效边表 y=4的扫描线处理完毕后,因为下一条扫描线y=5与ymax相等,根据“下闭上开”的原 则,把P3P4 和P4P5 两条边删除,如图3-24 所示。 y=6的扫描线处理完毕后,因为下一条扫描线y=7与ymax相等,根据“下闭上开”的规 则,把P2P3 边删除。 当y=7时,添加新边P1P2,如图3-25 所示。 图3-24 扫描线y=4至y=5的有效边表 图3-25 扫描线y=6至y=7的有效边表 当y=8时,添加上新边P0P1 和P0P6,如图3-26 所示。这条扫描线处理完毕后,因 为下一条扫描线y=9与ymax相等,根据“下闭上开”的规则,将P5P6 边和P0P6 边删除,如 图3-27 所示。 y=11 的扫描线处理完毕后,因为下一条扫描线y=12 与ymax相等,根据“下闭上开”的 ·46· 图3-26 扫描线y=8的有效边表 图3-27 扫描线y=9至y=11 的有效边表 规则,将P1P2 边和P0P1 边删除。 至此,给出了示例多边形的全部有效边表。 4.桶表与边表 3.5 从有效边表的建立过程可以看出,有效边表给出了扫描线与有效边交点坐标的计算方 法,但是并没有给出新边出现的位置。为了确定在哪条扫描线上插入新边,就需要构造一个 边表,用以存放扫描线上多边形各边出现的信息。因为水平边的1/ k 为∞,并且水平边本 身就是扫描线,在建立边表时可以不予考虑。 1. 桶表与边表的表示法 (1)桶表(buckettable)是按照扫描线顺序管理边出现情况的一个数据结构。首先,构 造一个纵向扫描线链表,链表的长度为多边形所覆盖的最大扫描线数,链表的每个结点称为 桶,对应多边形覆盖的每条扫描线。 (2)将每条边的信息链入与该边最小 y 坐标(ymin)相对应的桶处。也就是说,若某边 的低端点为ymn,则该边就存放在相应的扫描线桶中。边的低端点与高端点的定义如图3-28 所示。低端点 y 坐标(扫描线)小,高端点的 y 坐标(扫描线)大。的(i) 图3-28 按照扫描线大小定义边的端点 ·47· (3)对于每条扫描线,如果新增多条边,则按x|ymin坐标递增的顺序存放在一个链表 中,若x|ymin相等,则按照1/ k 由小到大排序,这样就形成边表,如图3-29 所示。 图3-29 边表结点 图3-29 中,表示为x|ymn, x 为新增边低端点的 x 值, 用于判断边表在桶中的排序; ymax是该边高端点的最大扫描线值,用于判断该边何时成为(i) 无效边。1/ k 是 x 坐标的增量, 即Δx/Δy。对比图3-22 与图3-29,可以看出边表是有效边表的特例,即在该边低端点处 的一个有效边表。有效边表与边表可以使用同一个CAET 类来表示。 2. 桶表与边表示例 为了高效地将边加入到有效边表中,需要在初始化时建立一个包含多边形所有边的边 表。边表是按照桶排序的方式建立的,有多少条扫描线就有多少个桶。在每个桶中,根据边 的低端的 x 坐标,按照增序的方式排列每条边。对于图3-19 给出的示例多边形,桶表与边 表结构如图3-30 所示。 图3-30 示例多边形的桶表与边表 算法11:有效边表填充算法 例3- 2 使用有效边表算法填充图3-31 所示的三角形,写 出边表与各条扫描线的有效边表。 边表如图3-32 所示,在第一条扫描线上出现两条边,在第 3条扫描线上出现一条边。有效边表如图3-33 所示,在第3条 扫描线上抛弃P0P1 边,在第7条扫描线上抛弃P0P2 边和 P1P2 边。图3-31 三角形 ·48· 图3-32 边表 图3-33 有效边表 3.边填充算法 5 3.1 填充原理 5. 有效边表算法填充多边形的优点是多边形内的每个像素仅被访问一次。由于扫描线上 每个跨度的两端点像素在填充前就已经确定,因此可以对跨度内的像素进行光滑着色;有效 边表算法的缺点是维护和排序各种表的开销太大。 Agkland和Weste提出的另一种填充算法是边填充算法。边填充算法是先求出多边形 的每条边与扫描线的交点,然后将交点右侧的所有像素颜色全部取为补色。边填充算法中, 边的顺序无关紧要。按某个顺序处理完多边形的所有边后,就完成了多边形的填充任务。 边填充算法利用了图像处理中的“取补”的概念,对于黑白图像,取补就是将白色的像素 取为黑色,反之亦然;对于彩色图像,取补就是将背景色取为填充色,反之亦然。取补的一条 基本性质是一个像素经过两次取补就恢复为原色。如果多边形的内部像素取补奇数次,则 显示为填充色;如果取补偶数次,则保持为背景色。 ·49· 3.2 填充过程 5. 假定边的顺序为E0、E1、E2、E3、E4、E5 和E6,如图3-34 所示。这里,边的顺序并不影 响填充结果,只是方便编写算法的循环结构而已。边填充算法处理过程如图3-35 所示。 图3-34 标注了边顺序的示例多边形 图3-35 边填充算法执行过程 y0), 对于E0 边,边的低端点为P0(x0,高端点为P1(x1,)。该边扫描线的最小值为 y1 最大值为yma斜率为k=y1-y0,边上当前扫描线的坐标为xi,边上下一条 ymin=y0, x=y1, x1-x0 扫描线的坐标为xi+1=xi +1/k。在扫描线沿着该边从y0 向y1 移动的过程中,将该边右 侧像素的颜色全部取补,即将E0 边右侧的像素全部置为填充色,如图3-35(a)所示。对于 E1 边,边的低端点为P2(y2), 高端点为P1(y1)。该边扫描线的最小值为ymn= x2,x1,iy2, 最大值为ymax=y1,斜率为k=y2-y1。在扫描线沿着该边从y2 移动到y1 的过程中,将x2-x1 该边右侧像素的颜色全部取补,即将E1 边与E0 边之间的像素置为填充色,而E0 边右侧的 像素经过两次取补恢复为背景色,如图3-35(b)所示。按照某个顺序处理完多边形的每条 ·50· 边后,填充过程就结束了。 边填充算法特别适合于具有帧缓冲的显示器,可以按任意的顺序处理多边形的每条边。 当所有的边处理完毕后,按扫描线顺序读出帧缓冲的内容并送显示设备。边填充算法的优 点是不需要任何数据存储,缺点是复杂图形的许多边经过同一条扫描线,导致一些像素可能 被访问多次。算法的效率受到边右侧像素数量的影响,右侧像素越多,需要取补的像素也就 越多。为了减少边右侧像素的访问次数,可以在多边形的包围盒内进行像素取补,如图3-36 所示。包围盒就是包含该多边形的最小矩形,即用多边形在x、 y 方向的最大值和最小值作 为顶点绘制的矩形。为了提高效率,有时也可以在多边形内添加一条边界,称为栅栏,如图 3-37 所示。这便是Dunlavey于1983 年提出的栅栏填充算法。为了计算方便,栅栏通常取 过多边形某一顶点的垂线。栅栏填充算法在处理每条边与扫描线的交点时,只将交点与栅 栏之间的像素取补。若交点位于栅栏左侧,将交点之右,栅栏左侧的所有像素取补;若交点 位于栅栏右侧,将交点左侧、栅栏右侧的所有像素取补。图3-38 给出了使用栅栏填充算法 填充示例多边形的执行过程。 图3-36 带包围盒的多边形图3-37 带栅栏的多边形 图3-38 栅栏填充算法执行过程 算法12:边填充算法 例3-3在窗口客户区内,使用边填充算法填充图3-39 所示的三角形。 ·15· 图3-39 边填充算法的原理 3.区域填充算法 6 前面讨论的填充算法都是按照扫描线顺序对多边形进行着色,而区域填充算法则采用 了完全不同的策略。区域填充算法假设,区域内部至少有一个像素是已知的,将该像素(称 为种子像素)的颜色扩展至整个区域。区域是指相互连通的一组像素的集合,因为只有在连 通域内,才可能将种子像素的颜色扩展到其他像素点。区域可以 采用内点表示与边界表示两种形式。如果区域是用内点表示的, 那么区域内的所有像素具有同一种颜色,区域外的像素具有另一 种颜色,如图3-40所示;如果区域是用边界表示,区域内部像素与 边界像素具有不同的颜色,区域外部的像素可以与内部像素同色 或不同色,如图3-41所示。基于内点表示的填充算法称为泛填充 算法(hm )。基于边界表示的填充算法称为边界填 floodfilalgorit 充算法(boundaryfilalgorithm )。泛填充算法与边界填充算法都图3-40 区域的内点表示 是从区域内的一个种子像素开始填充,所以统称为种子填充算法(sedfilalgorithm )。无 论是采用内点表示还是边界表示,区域均可以划分为四连通域与八连通域。要定义四连通 域与八连通域,首先要定义一个像素的四邻接点与八邻接点。 ·52· 图3-41 区域的边界表示 3.1 四邻接点与八邻接点 6. 1. 四邻接点定义 对于区域内部任意一个像素,其左、上、右、下4个相邻像素称为四邻接点,如图3-42(a) 所示。 图3-42 邻接点定义 2. 八邻接点定义 对于区域内部任意一个像素,其左、左上、上、右上、右、右下、下和左下8个相邻像素称 为八邻接点,如图3-42(b)所示。 3.2 四连通域与八连通域 6. 1. 四连通域定义 如果从区域内部任意一个种子像素出发,通过访问其水平方向、垂直方向的四个邻接点 就可以遍历整个区域,则称为四连通(4-connected)区域,如图3-43 所示。 图3-43 边界表示的四连通域 ·53·