图形学课件 第四章 多边形填充.ppt

《图形学课件 第四章 多边形填充.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章多边形填充有效边表填充算法本章学习目标4.1多边形的扫描转换4.2有效边表填充算法4.3本章小结本章内容4.1多边形的扫描转换本章将以直线段连接而成的示例多边形为例讲解多边形的填充算法，同时给出图形边界像素的处理原则。多边形内部可以使用平面着色模式或光滑着色模式填充。无论使用哪种着色模式，都意味着要使用指定颜色为多边形边界内的每一个像素着色。多边形是由折线段组成的封闭图形。它由有序顶点的点集Pi（i＝0，…，n-1）及有向边的线集Ei（i＝0，…，n-1）定义，n为多边形的顶点数或边数，且Ei＝PiPi+1，i＝0

2、，…，n-1。这里Pn＝P0，保证了多边形的闭合。多边形可以分为凸、凹多边形以及环。4.1.1多边形的定义P0P1P2P3P4P5E0E1E2E3E4E5顺时针逆时针图4-4多边形的定义用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换后才能逐条扫描线填充。⑴顶点表示法⑵点阵表示法多边形的点阵表示法是用位于多边形内的像素点集来描述，这种表示方法虽然失去了许多重要的集合信息，如顶点、边界等，但便于运用帧缓冲来表示图形，方便直

3、接读取像素来更改多边形的填充色。4.1.2多边形的表示⑶多边形的扫描转换将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出位于多边形内部的各个像素点信息，并将其颜色值写入帧缓冲的相应单元中。多边形的顶点表示法多边形的点阵表示法4.1.3多边形着色模式多边形可以使用平面着色模式（flatshadingmode）或光滑着色模式（smoothshadingmode）填充。平面着色是指多边形所有顶点的颜色都相同，多边形内部具有同顶点一样的颜色。光滑着色是指多边形各个顶点的颜色不

4、同，多边形边的颜色是由这条边的两个顶点的颜色插值得到，多边形内部的颜色是由扫描线上共享同一顶点的相邻两条边上的颜色插值得到。光滑着色平面着色实际光强感知光强马赫带边界位置的实际光强与感知光强马赫带（MachBand）是由灰度接近的矩形块组成。在观察明暗变化的边界时，边界处亮度对比度加强，常常在光强阶梯变化的一侧感知到亮度的正向尖峰效果，而在另一侧感知到亮度的负向尖峰效果，使得边界表现得非常明显，这种现象称为马赫带效应。马赫带效应不是一种物理现象，而使一种心理现象，夸大了平面着色的渲染效果，使得人眼感觉到的亮度变化比实际的

5、亮度变化要大。绘制真实感图形的过程中应尽量避免出现马赫带效应。球面的马赫带4.1.4填充多边形多边形填充的主要算法是扫描线算法。先确定多边形覆盖的扫描线条数，对每一条扫描线，计算扫描线与多边形边界的交点区间，如果能判断该区间在多边形内部，则将其内的像素绘制为指定的颜色。扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，处理效率很低。改进的算法是有效边表算法。对一条扫描线的填充一般分为以下4个步骤求交：计算扫描线与多边形各边的交点；排序：把扫描线上所有交点按递增顺序进行排序；配对：将第一个顶点与第二个顶点，第三个顶点

6、与第四个顶点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。着色：把区间内的像素置为填充色。4.1.5填充区域区域是指相互连通的一组像素的集合。区域通常由一个封闭的边界来定义，处于一个封闭边界线内的所有像素构成一个区域。区域内的所有像素着同一填充色，区域的边界色和填充色一般不一致。种子填充算法是从区域内的一个种子位置开始，由内向外用填充颜色绘制种子及其相邻像素直到颜色不同的边界像素为止。种子填充算法主要分为4邻接点算法和8邻接点算法。4.2有效边表填充算法4.2.1填充原理有效边表填充算法通过维护边表和有效边表，

7、避开了扫描线与多边形所有边求交的复杂运算。填充原理是按照扫描线从小到大的移动顺序，计算当前扫描线与有效边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，最后用指定颜色填充区间内的所有像素，即完成填充工作。有效边表填充算法已成为目前最为有效的多边形填充算法之一。4.2.2边界像素处理原则填充左下角为（1，1），右上角为（3，3）的正方形时，若将边界上的所有像素全部填充，就得到图示的结果。面积3×3面积2×2在多边形填充过程中，常采用“左闭右开”和“下闭上开”的原则对边界像素进行处理。参CDC::Fil

8、lRect的处理原则：Whenfillingthespecifiedrectangle,FillRectdoesnotincludetherectangle’srightandbottomsides.其中CDC使用的设备坐标系与本书自定义的坐标系不同。P6P7P0P5P8P1P4P2边界像素的处理局部最高点P1、P6