有效边表填充算法

《有效边表填充算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、河南理工大学万方科技学院电气与自动化工程系课程设计报告2010—2011学年第二学期课程名称计算机图形学设计题目计算机图形学基本算法多边形有效边表填充算法学生姓名宗彦涛(0828030033)李建飞(0828030019)文欣伟(0828030002)专业班级计算机08—1指导教师侯守明2011年6月12日26目录目录目录I第1章设计内容与要求11.1总体目标和要求11.2内容与要求1第2章总体设计42.1多边形定义42.2多边形有效边表填充算法描述42.3多边形有效边表填充算法基本原理5第3章详细设计7第4章功能实现9第5章不足与改进22

2、第6章总结23参考文献2326第1章基础知识第1章设计内容与要求1.1总体目标和要求目标：以图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：1)巩固和实践计算机图形学课程中的理论和算法；2)学习表现计算机图形学算法的技巧；3)培养认真学习、积极探索的精神。总体要求：策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。开发环境：

3、ViusalC++6.0，VC2005或其他你认为比较熟悉的环境。1.2内容与要求1.2.1实验分为两项内容。（1）设计边表与活性链表数据结构；1）边表的定义有效边（ActiveEdge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（ActiveEdgeTable,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。26第1章基础知识2）边表的构造：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(2)将每条边的信息

4、链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x

5、yminymax1/kNEXT(4)同一桶中若干条边按X

6、ymin由小到大排序，若X

7、ymin相等，则按照1/m由小到大排序。(2）根据多边形有效边表填充算法原理，设计相应算法；算法步骤：(1)初始化：构造边表，AET表置空；(2)将第一个不空的ET表中的边与AET表合并；(3)由AET表中取出交点对

8、进行填充。填充之后删除y=ymax的边；(4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；(5)AET表不为空则转(3)，否则结束。结果如下图所示26第1章基础知识1.2.2功能要求：（1）要求根据鼠标输入点来生成多边形；（2）通过右键菜单显示填充效果，右键菜单有两个选项：未填充与填充；26第2章总体设计第2章总体设计2.1多边形定义多边形是由折线段组成的封闭图形。它由有序顶点的点集Pi（i＝1～n）及有向边的线集Ei（i＝1～n）定义，n

9、为多边形的顶点数或边数，且Ei＝PiPi+1，i＝1～n。这里Pn+1＝P1，用以保证了多边形的封闭性。多边形可以分为凸、凹多边形以及环，（1）凸多多边形凸多多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于180°，只具有凸点的多边形称为凸多边形。（2）凹多边形多边形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于180°，有一个凹点的多边形称为凹多边形。（3）环多边形内包含有另外的多边形。如果规定：每条有向边的左侧为其内部实面积区域。则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环行方向为

10、逆时针，内轮廓线的环行方向为顺时针。这种定义了环行方向的多边形称为环。2.2多边形有效边表填充算法描述(1)多边形的填充26第2章总体设计以顶点法表示的多边形为例。多边形的填充是指从多边形的顶点信息出发，求出其覆盖的每个像素点，取为填充色，而将多边形外部的像素点保留为背景色。多边形填充的主要工作是确定穿越多边形内部的扫描线的覆盖区间。首先确定多边形覆盖的扫描线条数（y＝ymin～ymax），对每一条扫描线，计算扫描线与多边形边界的交点区间（xmin～xmax），然后再将该区间内的像素赋予指定的颜色。在扫描线从多边形顶点的最小值ymin到多边

11、形顶点的最大值ymax的移动过程中，重复上述工作，就可以完成多边形的填充。(2)区域填充区域是指一组相邻而又具有相同属性的像素，可以理解为多边形的内部。区域的边界色和填充色不一致