1、1 设 计设 计 题 目题 目 改 进 的 有 效 边 表 算 法 对 多 边 形 的 填 充改 进 的 有 效 边 表 算 法 对 多 边 形 的 填 充 2 目录 一、设计内容与要求 .3 1.1 设计题目 .3 1.2 设计内容.3 1.3 设计目标.3 二、总体设计3 2.1 多边形的表示3 2.2 x-扫描线算法4 2.3 改进的有效边表算法 .4 2.3.1 改进的有效边表算法.4 2.3.2 有效边表 5 2.3.3 边表 .6 三、详细设计8 3.1 改进的有效边表算法的实现.8 3.2 有效边表算法程序流程图 9 四、测试结果9 五、总结. 15 六、源代码 . 15 参考文
2、献. 26 3 一、设计内容与要求一、设计内容与要求 1.11.1 设计题目设计题目 用改进的有效边表算法实现多边形的填充 1 1.2 .2 设计内容设计内容 使用 OpenGL 实现用改进的有效边表算法填充多边形 1.3 1.3 设计目标设计目标 参照课本上改进的有效边表算法的思想，实现该算法的 C 语言代码，并用该算法 搭配 OpenGL 以像素点的方式绘制出给定顶点坐标的多边形。 二、总体二、总体设计设计 2 2. .1 1 多边形的表示多边形的表示 在计算机图形学中，多边形有 2 种重要的表示方法：顶点表示和点阵表示。 顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，
3、占用 内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来刻画多边形。 这种表示法虽然失去了许 多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。 大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示， 那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转 4 换或多边形的填充。即从多边形的顶点信息出发，求出位于其内部的各个像素，并将 其颜色值写入帧缓存的相应单元中。 2 2. .2 2 x x- -扫描线算法扫描线算法 x-扫描线算法的基本思想是， 按照扫描线的顺序，
4、 计算扫描线与多边形的相交区间， 再用要求的颜色显示这些区间的像素，即完成填充工作。区间的端点可以通过计算扫 描线与多边形边界线的交点获得。根据此原理，x-扫描线算法可以填充凸的、凹的或 带有孔的多边形区域。 x-扫描线的算法步骤如下： (1) 确定多边形顶点的最小和最大 y值(ymin和 ymax)， 得到多边形所占有的最大扫描 线数。 (2) 从 y=ymin到 y=ymax，每次用一条扫描线填充。每一条扫描线填充的过程分为 4 个步骤： 求交。计算扫描线与多边形所有边的交点。 排序。把所有交点按 x坐标递增的顺序进行排序。 交点配对。配对第一与第二、第三与第四个交点等，每对交点代表一个填充 区间。 区间填色。把这些相交区间内的像素置成不同于背景色的填充色。 x-扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，这样处理效率非 常低。因为一条扫描线往往只与少数几条边相交，甚至与整
