第四章 多边形填充VIP免费

第四章第四章有效边表填充算法有效边表填充算法边缘填充算法边缘填充算法四邻接点种子填充算法四邻接点种子填充算法八邻接点种子填充算法八邻接点种子填充算法扫描线种子填充算法扫描线种子填充算法本章学习目标本章学习目标4.1多边形的扫描转换4.2有效边表填充算法4.3边缘填充算法4.4区域填充算法4.5本章小结习题4本章内容本章内容4.14.1多边形的扫描转换多边形的扫描转换本章将以直线段连接而成的示例多边形为例讲解多边形的填充算法，同时给出图形边界像素的处理原则。多边形内部可以使用平面着色模式或光滑着色模式填充。无论使用哪种着色模式，都意味着要使用指定颜色为多边形边界内的每一个像素着色。多边形是由折线段组成的封闭图形。它由有序顶点的点集Pi（i＝0，…，n-1）及有向边的线集Ei（i＝0，…，n-1）定义，n为多边形的顶点数或边数，且Ei＝PiPi+1，i＝0，…，n-1。这里Pn＝P0，保证了多边形的闭合。多边形可以分为凸、凹多边形以及环。4.1.14.1.1多边形的定义多边形的定义P0P1P2P3P4P5E0E1E2E3E4E5顺时针逆时针图4-4多边形的定义用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换后才能逐条扫描线填充。⑴顶点表示法⑵点阵表示法多边形的点阵表示法是用位于多边形内的像素点集来描述，这种表示方法虽然失去了许多重要的集合信息，如顶点、边界等，但便于运用帧缓冲来表示图形，方便直接读取像素来更改多边形的填充色。4.1.24.1.2多边形的表示多边形的表示⑶多边形的扫描转换将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出位于多边形内部的各个像素点信息，并将其颜色值写入帧缓冲的相应单元中。多边形的顶点表示法多边形的点阵表示法P0P1P2P3P4P5P64.1.34.1.3多边形着色模式多边形着色模式多边形可以使用平面着色模式（flatshadingmode）或光滑着色模式（smoothshadingmode）填充。平面着色是指多边形所有顶点的颜色都相同，多边形内部具有同顶点一样的颜色。光滑着色是指多边形各个顶点的颜色不同，多边形边的颜色是由这条边的两个顶点的颜色插值得到，多边形内部的颜色是由扫描线上共享同一顶点的相邻两条边上的颜色插值得到。光滑着色平面着色实际光强感知光强马赫带边界位置的实际光强与感知光强马赫带（MachBand）是由灰度接近的矩形块组成。在观察明暗变化的边界时，边界处亮度对比度加强，常常在光强阶梯变化的一侧感知到亮度的正向尖峰效果，而在另一侧感知到亮度的负向尖峰效果，使得边界表现得非常明显，这种现象称为马赫带效应。马赫带效应不是一种物理现象，而使一种心理现象，夸大了平面着色的渲染效果，使得人眼感觉到的亮度变化比实际的亮度变化要大。绘制真实感图形的过程中应尽量避免出现马赫带效应。球面的马赫带4.1.44.1.4填充多边形填充多边形多边形填充的主要算法是扫描线算法。先确定多边形覆盖的扫描线条数，对每一条扫描线，计算扫描线与多边形边界的交点区间，如果能判断该区间在多边形内部，则将其内的像素绘制为指定的颜色。扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，处理效率很低。改进的算法是有效边表算法。对一条扫描线的填充一般分为以下4个步骤•求交：计算扫描线与多边形各边的交点；•排序：把扫描线上所有交点按递增顺序进行排序；•配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。•着色：把区间内的像素置为填充色。4.1.54.1.5填充区域填充区域区域是指相互连通的一组像素的集合。区域通常由一个封闭的边界来定义，处于一个封闭边界线内的所有像素构成一个区域。区域内的所有像素着同一填充色，区域的边界色和填充色一般不一致。种子填充算法是从区域内的一个种子位置开始，由内向外用填充颜色绘制种子及其相邻像素直到颜色不同的边界像素为止。种子填充算法主要分为4邻接点算法和8邻接点算法。4.24.2有效边表填充算法有效边表填充算法4.2....