计算机图形学课程设计-有效边表填充算法的实现

《计算机图形学课程设计-有效边表填充算法的实现》由会员分享，可在线阅读，更多相关《计算机图形学课程设计-有效边表填充算法的实现（27页珍藏版）》请在金锄头文库上搜索。

1、 计算机图形学计算机图形学 课程设计课程设计 设设计计 题题目目 改改进进的的有有效效边边表表算算法法对对多多边边形形的的填填充充 学学院院名名称称 信信息息科科学学与与技技术术学学院院 专专业业名名称称 计计算算机机科科学学与与技技术术 学学生生姓姓名名 刘刘 柯柯 学学生生学学号号 2 20 01 12 21 13 30 03 30 01 11 12 2 任任课课 教教师师 梅梅 占占 勇勇 设设计计 （论论文文） 成成绩绩 教务处教务处 制制 2015 年 9 月 28 日 目录 一、设计内容与要求 .3 1.1设计题目 .3 1.2 设计内容 .3 1.3 设计目标 .3 二、总体设计

2、 .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 参考文献 .26 一、设计内容与要求一、设计内容与要求 1.11.1设计题目设计题目 用改进的有效边表算法实现多边形的填充 1.21.2 设计内容设计内容 使用 OpenGL 实现用改进的有效边表算法填充多边形 1.31.3 设计目标设计目标 参照课本上

3、改进的有效边表算法的思想，实现该算法的 C 语言代码，并用该算法 搭配 OpenGL 以像素点的方式绘制出给定顶点坐标的多边形。 二、总体设计二、总体设计 2.12.1 多边形的表示多边形的表示 在计算机图形学中，多边形有 2 种重要的表示方法：顶点表示和点阵表示。 顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用 内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来刻画多边形。 这种表示法虽然失去了 许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。 大多数图形应用系统采用顶点序列表

4、示多边形，而顶点表示又不能直接用于显示， 那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转 换或多边形的填充。即从多边形的顶点信息出发，求出位于其内部的各个像素，并将 其颜色值写入帧缓存的相应单元中。 2.22.2 x-x-扫描线算法扫描线算法 x-扫描线算法的基本思想是，按照扫描线的顺序，计算扫描线与多边形的相交区 间，再用要求的颜色显示这些区间的像素，即完成填充工作。区间的端点可以通过计 算扫描线与多边形边界线的交点获得。根据此原理，x-扫描线算法可以填充凸的、凹 的或带有孔的多边形区域。 x-扫描线的算法步骤如下： (1) 确定多边形顶点的最小和最大 y 值(y

5、min和 ymax)，得到多边形所占有的最大扫 描线数。 (2) 从 y=ymin到 y=ymax，每次用一条扫描线填充。每一条扫描线填充的过程分为 4 个步骤： 求交。计算扫描线与多边形所有边的交点。 排序。把所有交点按 x 坐标递增的顺序进行排序。 交点配对。配对第一与第二、第三与第四个交点等，每对交点代表一个填 充区间。 区间填色。把这些相交区间内的像素置成不同于背景色的填充色。 x-扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，这样处理效率 非常低。因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。因 此，有必要对算法进行改进。 2.32.3 改进的有效边表算法

6、改进的有效边表算法 2.3.12.3.1 改进的有效边表算法改进的有效边表算法 将 x-扫描线算法加以改进可以得到改进的有效边表算法，也称 y 连贯算法。改进 可以从三个方面进行：首先，在处理一条扫描线时，仅对与它相交的多边形的边（有 效边）求交；其次，利用扫描线的连贯性，考虑到当前扫描线与各边的交点顺序与下 一条扫描线与各边的交点顺序很可能相同或非常相似，因此在当前扫描线处理完毕之 后，不必为下一条扫描线从头开始构造交点信息；最后，利用多边形的连贯性，认为 若某条边与当前扫描线相交，则它很可能也与下一条扫描线相交且其交点与上一次的 交点相关。如下图所示，设直线的斜率为 k，若 y=yi时，x

7、=xi；则当 y=yi+1时，有 xi+1=xi+1/k。 2.3.22.3.2 有效边表有效边表 有效边（Active Edge）是指与当前扫描线相交的多边形的边，也称活性边。把有 效边按与扫描线交点 x 坐标递增的顺序存放在一个链表中，此链表称为有效边表 （Active Edge Table， AET） 。有效边表的每个结点存放对应边的如下信息： 其中，x 为当前扫描线与有效边交点的 x 坐标；ymax是有效边所在的最大扫描线 值，通过它可以知道何时才能“抛弃”该边；1/k 是边斜率的倒数；next 是下一个结 点的指针。 如下图所示的多边形 P0P1P2P3P4P5P6，其顶点表示为：

8、P0(7，8)，P1(3，12)，P2(1，7)，P3(3，1)，P4(6，5)，P5(8，1)，P6(12，9)。 当 y=8 时的有效边表如下图所示： 2.3.32.3.3 边表边表 有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的 位置坐标。为了方便有效边表的建立与更新，就需要构造一个边表（Edge Table， ET） ，用以存放扫描线上多边形各条边的信息。由于水平边的 1/k 为，并且水平边 本身就是扫描线，所以在建立边表时不予考虑。 边表的构造分为 4 个步骤： 首先构造一个纵向链表，链表的长度为多边形占有的最大扫描线数，链表的 每个结点，称为一个桶，对应多边

9、形覆盖的每一条扫描线。 将每条边的信息装入与该边最小 y 坐标(ymin)相对应的桶中。也就是说，若某 边的较低端点为 ymin，则该边就放在相应的 y=ymin的扫描线桶中。 每条边的数据形成一个结点，内容包括该扫描线与该边的初始交点 x(即较低 端点的 x 坐标值)，该边最大 y 坐标值 ymax，以及斜率的倒数 1/k 和下一个边 结点的指针 next: 同一桶中若干条边按 x|ymin由小到大排列，若 x|ymin相等，则按 1/k 由小到大 排序。 从上面可以看出，边表是有效边表的特例，有效边表和边表可以使用同一个数据 结构来表示。 对于多边形 P0P1P2P3P4P5P6，它的边表

10、结构如下图所示： 三、详细设计三、详细设计 3.13.1 改进的有效边表算法的实现改进的有效边表算法的实现 改进的有效边表算法具体实现过程如下： 初始化边表 ET。 为了方便边表的建立，可以定义 sort()函数对多边形的边进行排序，保证边 表中每个桶中的边是有序的。同时定义一个 creat_edge_table()函数，该函数需 要多边形的顶点信息作为参数传入，并返回一个边表指针。 初始化有效边表 AET。从 ET 表中取出第一个不为空的桶与 AET 表合并。 为了初始化 AET 表，可以定义一个 init_active_table()函数，该函数传入 边表指针作为形参，返回一个有效边表指针

11、。 从 AET 表中取出交点进行填充。 填充时设置一个布尔值 b（初值为假） ，令指针从有效边表的第一个结点（也 就是扫描线与有效边的交点）开始遍历。每访问一个结点，把 b 取反一次。若 b 为真，则把从当前结点的 x 值开始（设为 x1）到下一结点的 x 值结束(设为 x2)的 区间x1, x2用多边形色填充。填充时为了避免多边形区域扩大化，需要对区间 边界进行如下处理： 若 x 是整数，则按“左闭右开”的原则处理，即左边界上的 x（x1）不变，右 边界上的 x（x2）减 1；若 x 不是整数，左边界上的 x（x1）向右取整，右边界上 的 x（x2）向左取整。 更新 AET 表。 设当前 A

12、ET 表中扫描线为 y，首先更新扫描线为 y=y+1，然后删除 AET 表中所 有 ymax=y 的边结点；再根据 xi+1=xi+1/k 计算并修改 AET 表中各边结点的 x 坐标， 同时合并 ET 表对应于扫描线 y 的桶中的边，按次序插入到 AET 表中，形成新 AET 表。此步骤满足多边形的“下闭上开”原则。 此过程用到自定义的函数 delete_edge()、add_edge()、 update_active_table()。 判断 AET 表是否为空。若为空，则结束；否则转到 3.23.2 有效边表算法程序流程图有效边表算法程序流程图 开始 构造边表 初始化有效边表 更新AET表

13、 取出交点进行填充 ET AET 输入多边形顶点信息 AET是否为空是结束 否 四、测试结果四、测试结果 为了便于观察多边形的填充，本程序将像素点进行放大处理，400 x 300 的分辨率 投影到 20 x 15，并绘制出网格，使用 OpenGL 画出多边形的边框。使用了 Sleep()函数 来延时生成像素点，并且每填充一个像素点刷新一次，给人动态直观的感受。 在不处理边界的情况下，如下图所示，多边形的区域可能会扩大化。 对边界进行处理后，结果如下： 为了验证改进的有效边表填充算法，现将本程序的像素大小恢复为 1：1，按 比例扩大多边形的顶点坐标，测试结果如下： 从上图可以看出填充过后的多边形

14、与原多边形 P0P1P2P3P4P5P6的形状一致， 该算法验证通过。 测试其他多边形 长方形： 三角形： 五角星： 从以上结果来看，该算法基本得到完美实现。而程序的执行时间来看，生成边表 的时间（包括分配内存、对桶中的结点进行排序等）远比填充像素点的时间要长。因 此，该算法的效率虽然很高，但对于表的维护和排序开销太大，它适合软件实现而不 适合硬件实现。 五、总结五、总结 通过本次课程设计，我掌握了多边形的填充算法，了解了 OpenGL 的运行结构， 熟悉了很多 OpenGL 的函数，对 OpenGL 编程也产生的浓厚的兴趣。同时也巩固了对 计算机图形学知识的掌握，锻炼了我对手实验的能力，看清

15、了自己的水平，认识到了 自己的不足。 在本次课程设计中，存在一些不足之处。比如对边界的处理，课本上的说法模糊 不清，在网上也没有找到相应的解答，我只能根据自己的理解来试着解决；这方面也 存在没有及时和老师沟通的原因。从这一点上，我认识到理论和实践的差别，我们应 该多实践才能真正掌握理论。 还有就是完全填充后的多边形，边缘有“锯齿”现象，不知道是我程序的原因还 是算法的问题。或许对于多边形的填充算法还应该处理“锯齿” 。 六、源代码六、源代码 /源代码仅包含文件PolygonFilling.cpp #include #include #include #include #define EPSILON 0.000001 /最小浮点数 /点结构体 struct Point int x; /x坐标 int y; /y坐标 ; /线结构体 struct Line Point high_point; /高端点 Point low_point; /低端点