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

1、设计题目改进的有效边表算法对多边形的填充毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教 师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加 以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体， 均已在文中作了明确的说明并表示了谢意。作者签名：円期：指导教师签名：曰期：使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电 子版本；学校有权保存毕

2、业设计（论文）的印刷本和电子版，并提供 目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制 手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分 或全部内容。作者签名： 曰 期：学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，木论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。作者签名：日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，

3、 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月曰导师签名：u期：年nu注意事项1. 设计（论文）的内容拈：1）封面（按教务处制定的标准封面格式制作）2）原创性声明3）中文摘要（300字左右）、关键词4）外文摘要、关键同5）目次页（附件不统一编入）6）论文主体部分：引言（或绪论）、正文、结论7）参考文献8）致谢9）附录（对论文支持必要时）2. 论文字数要求：理工类设计（论文）正文字数不少于1万

4、字（不铋拈图纸、 程序清半等），文科类论文正文字数不少于1. 2万字。3. 附件包括：任务书、开题报告、外文译文、译文原文（复印件）。4. 文字、图表要求：1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错 別字，不准请他人代写2）工程设计类题的图纸，要求部分用尺规绘制，部分用计算机绘制，所 有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程 字书写，不准用徒手画3）毕业论文须用a4单而打印，论文50页以上的双而打印4）图表应绘制于无格子的页面上5）软件工程类课题应有程序清单，并提供电子文档5. 装订顺序1）设计（论文）2）附件：按照任务书、幵题报告、外文译

5、文、译文原文（复印件）次序装指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神优中及格口不及格2、学生掌握专业知识、技能的扎实程度优良 中及格口不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力优良中及格口不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性优良中及格口不及格5、完成毕业论文（设计）期问的岀勤情况优良屮及格口不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？优良中及格口不及格2、是否完成指定的论文（设计）任务（ti拈装订及附件）？ 优 良 屮 及格 口不及格三、论文（设计）水平1、论文（设计）

6、的理论意义或对解决实际问题的指导意义 优 良 中 及格 口不及格2、论文的观念是否有新意？设计是否有创意？优良屮及格口不及格3、论文（设计说明书）所体现的整体水平优 r 中 及格 口不及格建议成绩：优良中及格不及格（在所选等级前的内画“ v”）指导教师：（签名）单位：年 月 日（盖章）评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？优 r中及格口不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 口不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 r 中 及格 口不及格2、论文的观念是否有

7、新意？设计是否有创意？优 良 中 及格 口不及格3、论文（设计说明书）所体现的整体水平优口良中及格不及格建议成绩：优良中（在所选等级前的内画及格“ v ”）不及格评阅教师:（签名）年 月 日单位：（盖章）教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 口不及格2、对答辩w题的反应、理解、表达情况优良中及格口不及格3、学生答辩过程中的精神状态优良中及格口不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？优良中及格口不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及

8、格 口不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 口不及格2、论文的观念是否有新意？设计是否有创意？优 良 中 及格 口不及格3、论文（设计说明书）所体现的整体水平优口良中及格不及格评定成绩：优良中及格不及格教研室主任（或答辩小组组长）參（签名）年月 曰教学系意见：系主任：（签名）年月 曰目录一、设计内容与要求91.1 设计题目91.2设计内容91.3设计目标9二、总体设计92.1多边形的表示92.2 x-扫描线算法102.3改进的有效边表算法102.3. 1改进的有效边表算法102.3.2有效边表112.3.3 边表12> !羊会田

9、 t十 143.1改进的有效边表算法的实现143.2有效边表算法程序流程图15四、测试结果1535.,21六、源代码21詩城32一、设计内容与要求1.1设计题目用改进的有效边农算法实现多边形的填充1.2设计内容使用opengl实现用改进的有效边表算法填充多边形1.3设计目标参照课本上改进的有效边表算法的思想，实现该算法的c语言代码，并用该算法 搭配opengl以像素点的方式绘制出给定顶点坐标的多边形。二、总体设计2.1多边形的表示在计算机图形学屮，多边形有2种重要的表示方法：顶点表示和点阵表示。顶点表示用多边形的顶点序列來刻画多边形，这种方法直观、几何意义强，占用闪存少，应用普遍，但它没有明确

10、指出哪些像素在多边形故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来刻画多边形。这种表示法里然失去y许多重要的儿何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。 大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转换或多边形的填充。即从多边形的顶点信息出发，求出位于其内部的各个像素，并将 其颜色值写入帧缓存的相应单元屮。2.2 x-扫描线算法x-扫描线算法的基本思想是，按照扫描线的顺序，计算扫描线与多边形的相交区间， 再用要求的颜色显示这些区间的像素，即完成填充工作。区i&

11、#39;hj的端点可以通过计算扫 描线与多边形边界线的交点获得。根据此原理，x-扫描线算法讨以填充凸的、m的或 带有孔的多边形区域。x-扫描线的算法步骤如下：(1) 确定多边形顶点的最小和最大y值ymax)，得到多边形所占有的最大扫描 线数。(2) 从y=ymin到y=ymax，每次用一条扫描线填充。每一条扫描线填充的过程分力4 个步骤： 求交。计算扫描线与多边形所有边的交点。 排序。把所有交点按x坐标递增的顺序进行排序。 交点配对。配对第一与第二、第三与第四个交点等，每对交点代表一个填充 区问。 区间填色。把这些相交区间内的像素置成不同于背景色的填充色。x-扫描线算法在处理每条扫描线时，需要

12、与多边形的所有边求交，这样处理效率非 常低。因为一条扫描线往往只与少数儿条边相交，甚至与整个多边形都不相交。因此, 有必要对算法进行改进。2.3改进的有效边表算法2.3.1改进的有效边表算法将x-扫描线算法加以改进可以得到改进的有效边表算法，也称y连贯算法。改进可以从三个方而进行：首先，在处理一条扫描线吋，仅对与它相交的多边形的边(有效边)求交；其次，利用扫描线的连贯性，考虑到当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似，因此在当前扫描线处理完毕之10后，不必为下一条扫描线从头幵始构造交点信息；最后，利用多边形的连贯性，认为 若某条边与当前扫描线相交，则它很可能

13、也与下一条扫描线相交且其交点与上一次的 交点相关。如下图所示，设直线的斜率为k，若y=yi时，x=xi;则当y=yi+1时，有xi+1=xi+l/k。2.3.2有效边表有效边(active edge)是指与当前扫描线相交的多边形的边，也称活性边。把有 效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表 (active edge table, aet)。有效边表的每个结点存放对应边的如下信息：y 眶1/knext其中，x为当前扫描线与有效边交点的x坐标；ymax是有效边所在的最大扫描线值， 通过它可以知道何吋才能“抛弃”该边；1/k是边斜率的倒数；next是下一个结点的指 针

14、，如下图所示的多边形pop,p2p3p4p5p6,其顶点表示为：p0(7, 8), p,(3, 12), p2(l, 7), p3(3, 1), p4(6, 5), p5(8, 1)，p6(12，9)。y=sp.p：pop.11.4122/5712-1ip5p6当y=8时的有效边表如下图所示:pnp62.3.3边表有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的 位置坐标。为了方便有效边表的建立与更新，就需耍构造一个边表(edge table, et), 用以存放扫描线上多边形各条边的信息。由于水平边的1/k为，并且水平边木身就 是扫描线，所以在建立边表时不予考虑。边表的

15、构造分为4个步骤: 首先构造一个纵向链表，链表的长度为多边形占有的最大扫描线数，链表的每 个结点，称为一个桶，对应多边形覆盖的每一条扫描线。 将每条边的信息装入与该边最小y坐标(yin)相对应的桶中。也就是说，若某 边的较低端点为ymin,则该边就放在相应的7=。的扫描线桶中。 每条边的数据形成一个结点，内容包括该扫描线与该边的初始交点x(即较低 端点的x坐标值)，该边最大y坐标值ymax，以及斜率的倒数1/k和下一个边结 点的指针next:niaxl/knext同一桶中若干条边按xlymin由小到大排歹lj，若xlymin相等，则按l/k由小到大排 序。从上面可以看出，边表是有效边表的特例，

16、有效边表和边表可以使用同一个数据 结构来表示。对于多边形p0p1p2p3p4p5p6，它的边表结构如k图所示：三、详细设计3.1改进的有效边表算法的实现改进的冇效边表算法具体实现过程如下： 初始化边表et。为了方便边表的建立，可以定义sort ()函数对多边形的边进行排序，保证边 表屮每个桶屮的边是有序的。同吋定义一个creat_edge_table()函数，该函数需 要多边形的顶点信息作为参数传入，并返冋一个边表指针。 初始化有效边表aet。从et表中取出第一个不为空的桶与aet表合并。为了初始化aet表，可以定义一个init_active_table()函数，该函数传入边 表指针作为形参，

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

18、描线为y=y+l,然后删除aet表屮所 有yy的边结点；再根据xi+i=xi+l/k计算并修改aet表中各边结点的x坐.fe，同 时合并et表对应丁扫描线y的桶屮的边，按次序插入到aet表屮，形成新aet表。 此步骤满足多边形的“下闭上开”原则。此过程用到自定义的函数delete_edge()、 add_edge()、 update_active_table ()o 判断aet表是否为空。若为空，则结束；否则转到3.2有效边表算法程序流程测试结果为了便于观察多边形的填充，本程序将像索点进行放大处理，400 x 300的分辨率 投影到20x15,并绘制出网格，使用opengl画出多边形的边框。使

19、用了 sleep()函数 来延时生成像素点，并且每填充一个像素点刷新一次，给人动态直观的感受。在不处理边界的情况下，如下阁所示，多边形的区域可能会扩大化。对边界进行处理后，结果如下:/1 1/1 117/1 11 1/1 1:/ 1 11 1癱 1 11/7z-为了验证改进的有效边表填充算法，现将本程序的像素大小恢复为1: 1，按 比例扩大多边形的顶点坐标，测试结果如下：3 polygon filling x从上图可以看出填充过后的多边形与原多边形p0p1p2p3p4p5p6的形状一致,该算法验证通过。 测试其他多边形 长方形：m3 polygon filling x13 polygon fi

20、lling三角形:五角星:j) polygon fillingx从以上结果来看，该算法基木得到完美实现。而程序的执行时间来看，生成边表 的时间（包拈分配内存、对桶屮的结点进行排序等）远比填充像素点的时间要长。因 此，该算法的效率虽然很高，但对于表的维护和排序开销太大，它适合软件实现而不 适合硬件实现。五、总结通过本次课程设计，我掌握了多边形的填充算法，了解了 opengl的运行结构， 熟悉了很多opengl的函数，对opengl编程也产生的浓厚的兴趣。m时也巩固了对 计算机图形学知识的掌握，锻炼丫我对手实验的能力，看清了0己的水平，认识到了 自己的不足。在本次课程设计屮，存在一些不足之处。比如

21、对边界的处理，课本上的说法模糊 不清，在网上也没有找到相应的解答，我只能根据自匕的理解來试着解决；这方血也 存在没有及时和老师沟通的原因。从这一点上，我认识到理论和实践的差别，我们应 该多实践才能真止掌握理论。还有就是完全填充后的多边形，边缘有“鋸齿”现象，不知道是我程序的原因还 是算法的问题。或许对于多边形的填充算法还应该处理“锯齿”。六、源代码/源代码仅包含文件polygonfi 11 ing. cppinclude <stdio.h>#includemalloc. hinclude <gl/glut. h>#includewindows. h>ttdcfin

22、c epsilon 0.000001/最小浮点数 /点结构体struct pointint x;/x巫标int y;/y坐标；/线结构体struct linepoint high_point:/高端点point low point; int is_activc; double inverse k;/低端点/是否为有效边，水平边（0），非水平边（1） /斜率k的倒数/边结点struct edgcnodc double x; int y_max; double inverse k; edgcnodc *ncxt:;/扫描线与边交点的x少标（边的低端点的x少标） /边的高端点的y坐标ymax /斜率

23、k的倒数 /下一个边结点的指针/扫描线y/边链表的头指针/扫描线y/边链表的尖指针/下一个桶的指针/杏效边表struct activekdgetable int y;edgenode *head;/桶结点typedef struct bucket int y;edgcnodc 氺head; bucket 氺next; edgetable;int compare(point pi, point p2);line* create_lincs(point points口，int n):point gct_lowcst_point(line lines口， int n);point get_highe

24、st_point(line lines, int n);void swap(line &11， line &12);void sort (line 1 ines, int n);kdgetable* create_edge_table (line linesf, int n);activcedgctable* init_activc_tablc(edgctablc *cdge_tablc);void delete_edge(activeedgetable *active_table, int yjnax);void addedge(activeedgetab1e *active

25、_table, edgenode edge);activeedgetable* update_active_table(act i veedgetable 氺active_table, edgetable *edge_table);void drawpolygon (point points, int n); void drawgrickint x, int y);void kill (point pointsu，int n);void initial 0;void display();int main(int argc, char* argv)glutlnit(&argc, argv

26、);glutlnitdisplaymode(glut single | glut rgb); glut initwindowsize(400, 300); gluttni twindowposi t ion(100, 120); glutcreatewindow(polygon filling)； glutdisplayfunc(display);initial ();glutmainloopo ;return 0;/比较2个点的髙度int compare(point pi, point p2) if (pi. y > p2. y)return 1;else if (pi. y = p2

27、. y) return 0;return -1;/山点数绀生成线段数组line* createines(point. points, int n)line *lincs = (linc*)malloc(n * sizcof(line): for (int i=0; i < n; +i)point pi = pointsi;point p2 = points(i + 1) % n;int result = compare (pi, p2); if (result = 0)1inesi. is_active = 0;elselincsi. is_activc = 1;linesi. high

28、 point = result > 0 ? pi : p2;linesil low_point = result < 0 ? pi : p2;linesfi. inverse k = (double) (p2.x - pi.x) / (double) (p2.y - pi.y)return lines;/获取线数组中最低的端点point get_lowest_point(line 1ines, int n)point lowcst_point = lines0. low_point;for (int i = 1; i n; +i)point lowpoint = lincsi>

29、; lowpoint; if (compare(lowcst_point, lowpoint) > 0)lowest point = low point;return lowest_point:/获取线数组中最高的端点point get_highest_point(line 1ines, int n)point highcst_point = lines0. high_point;for (int i = 1; i n; +i)point high point = 1incsi. high point; if (compare(highcst_point, high_point) <

30、; 0)highest_point = high_point;return highest point;/交换2个line对象vo id swap (line &1 1, line &12)line temp = 11;11 = 12;/对线数组进行排序void sort(line 1ines, int n)/先按低端点的y坐标进行升序排序 for (int i = 0; i < n; +i)int min_index = i;for (int j = i + 1; j < n; +j)if (linesj. low point, y < linesmin i

31、ndex, low point, y) min_index = j;swap(lincsi, linesmin_indcx):/再将科序数组按低端点的x叱标升序排列，若x少标相等，按inversej升序 for (int i = 0; i n: +i)int min_index = i;for (int j = i + 1; 1inesj. low_point. y linesi. low_point. y; +j) if (1incsj. low point, x < 1incsmin index. low_point. x) min_indcx = j;swap (1inesfi,

32、1inesmin_index);if (i > 0 && lincsi. low point. x = lincsi - 1. low point. x)if (linesi. is_active = 1 && linesi - 1. is_active = 1)if (hnesi. inverse。k < 1 incsi - 1. inverse, k) swap(lincsi, lincsi - 1);/创建-个边表edgctable* create cdge_table (line lines口，int n)edgetable *edge_ta

33、ble = (edgetable*)malloc(sizeof(edgetable): edge_table-head = null; edge_table-next = null;sort(lines, n);point lowest point = get lowest point (lines, n);point highest_point = get_highest_point(1ines, n);edgetable *s = edge_table;for (int i = lowcst_point. y; i <= highcst_point. y; +i)bucket buc

34、ket = (bucket*)malloc(sizeof(bucket); bucket-y = i; bucket->next = null;bucket->head = (edgenode*)malloc(sizeof(edgenode); bucket->head->next = null;edgenode *p = bucket->head; for (int j = 0; j < n; +j)if (linesj. is_active = 0) continue;if (lincsj. low一point, y = i)edgenode = (ed

35、genode*)malloc(sizeof(edgenode);q->x = 1inesj. low_point. x;q->y max = 1incsj.highpoint.y;q->invcrse_k = lincsj. inversek;q->next = null;p->next = q; p = q；s->next = bucket; s = bucket;return edge tabic;/从边表屮取出第一个不为空的桶初始化有效边表activeedgetable* init_active_table(edgetable *edge_table)

36、activcedgctablc *activc_tablc = (activcedgctablc*)malloc(sizeof(activcedgctablc); active table->y = edge table->next->y;active_table->head = (edgenode*)malloc(sizeof(edgenode); active_table-head-next = null;edgenode *p = cdgc_tablc->ncxt->hcad;edgenode *q = active table->head; w

37、hile (p->next != null)edgenode *s = (l;dgcnode*)malloc (si zeof (kdgenodc):s-x = p-next->x;s-y max = p->next->y max;s->inverse_k = p->next->inverse_k;s->next = null;q->ncxt = s; q = s;p = p->next;return active_table;/从有效边表中删除指定y ma x的边结点void dclctc_cdgc(activcedgctablc

38、*activc_tablc, int y_max) edgenode *p = active_table->head;while (p->next != null)edgenode *q = p->ncxt; if (q->y_max = y_max)p-next = q->next; free(q):else/将一个边结点按次序添加到科效边表中void add edge (ac t i vekdgetab1e *activc tabic, kdgcnodc edge)edgenode *t = (edgenode*)malloc(sizeof(edgenode)

39、;t->x = edge, x;t->y_max = edge. y_max;t->inverse k = edge, inverse k;t->ncxt = null;edgenode *p = active_table->head;while (p->next != null)edgenode *q = p->ncxt;if (edge.x < q->x)| (edge, x = q->x && edge, inverse k < q->inverse k)p->next = t; t>ne

40、xt = q; return;p = p->next;p-next = t;/史新科效边表，并与边表中对应的桶合并activcedgetable* updatc_ activetable(activcedgctablc 氺active tabic, edgctablc 氺edge table) /史新扫描线y +active_table->y;/删除y=ymax的边dclcte_edgc(activc_tablc, activc_tablc-y);/更新边结点的数据edgenode *p = active_table->head->next; while (p != n

41、ull)p->x += p->inverse_k;p = p->ncxt:/找到边表屮对应的桶edgetable *q = edge_tabe;while (q = q->next) != null && q->y != active tablc>y):/如果找到，则进行合并if (q != null)edgcnode *s = q->head; while (s = s-ncxt) != null)add_edge(active_table, *s);return active table;/両山多边形的边框void drawpoly

42、gon(point points口， int n)glbegin(gl_line_loop); for (int i = 0; i < n; +i)glvertex2i(pointsi. x, pointsi.y); glendo;/画出x * y的网格void drawgrid(int x, int y)g1begin(gl_ltnes);"横线for (int i = 0; i = y: +i)g1vertex2d(0, i); glvertex2d(x, i);/竖线for (int i = 0; i <= x; +i)glvcrtcx2d(i, 0); glver

43、tex2d(i, y);glendo ;/用指定的像索人小填充多边形void fill(point points, int n)line 氺lines = crcatc_lincs(points, n);edgetable 氺edge table = create edge table (lines, n);activeedgetable *active_table = init_active_table(edge_table);while (active table->heacl->ncxt != null)edgenode *p = active table->head; int b = -1;while (p->next != null)if (b > 0)int left = p-&g