有效边表填充算法.doc

河南理工大学万方科技学院电气与自动化工程系课程设计报告2010 2011学年第二学期课程名称 计算机图形学 设计题目 计算机图形学基本算法 多边形有效边表填充算法学生姓名 宗彦涛(0828030033) 李建飞(0828030019) 文欣伟(0828030002) 专业班级 计算机081 指导教师 侯守明 2011年 6 月 12日25目 录目 录目 录I第1章设计内容与要求11.1总体目标和要求11.2内容与要求1第2章 总体设计42.1多边形定义42.2多边形有效边表填充算法描述42.3多边形有效边表填充算法基本原理5第3章 详细设计7第4章 功能实现9第5章 不足与改进 22第6章 总结23参考文献23第1章 基础知识第1章 设计内容与要求1.1 总体目标和要求目标：以图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：1)巩固和实践计算机图形学课程中的理论和算法；2)学习表现计算机图形学算法的技巧；3)培养认真学习、积极探索的精神。总体要求：策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。开发环境：Viusal C+ 6.0，VC2005或其他你认为比较熟悉的环境。1.2内容与要求1.2.1实验分为两项内容。（1）设计边表与活性链表数据结构；1）边表的定义有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。2）边表的构造：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|ymin ymax 1/k NEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymin 相等，则按照1/m由小到大排序。(2）根据多边形有效边表填充算法原理，设计相应算法；算法步骤：(1)初始化：构造边表，AET表置空；(2)将第一个不空的ET表中的边与AET表合并；(3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边；(4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；(5)AET表不为空则转(3)，否则结束。结果如下图所示1.2.2功能要求：（1）要求根据鼠标输入点来生成多边形；（2）通过右键菜单显示填充效果，右键菜单有两个选项：未填充与填充；第2章 总体设计第2章 总体设计2.1多边形定义多边形是由折线段组成的封闭图形。它由有序顶点的点集 Pi（i1n ）及有向边的线集 Ei（i1n）定义，n 为多边形的顶点数或边数，且 EiPiPi+1，i1n。这里 Pn+1P1，用以保证了多边形的封闭性。多边形可以分为凸、凹多边形以及环，（1）凸多多边形凸多多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于 180，只具有凸点的多边形称为凸多边形。（2）凹多边形多边形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于 180，有一个凹点的多边形称为凹多边形。（3）环多边形内包含有另外的多边形。如果规定：每条有向边的左侧为其内部实面积区域。则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环行方向为逆时针，内轮廓线的环行方向为顺时针。这种定义了环行方向的多边形称为环。2.2多边形有效边表填充算法描述(1)多边形的填充以顶点法表示的多边形为例。多边形的填充是指从多边形的顶点信息出发，求出其覆盖的每个像素点，取为填充色，而将多边形外部的像素点保留为背景色。多边形填充的主要工作是确定穿越多边形内部的扫描线的覆盖区间。首先确定多边形覆盖的扫描线条数（yyminymax），对每一条扫描线，计算扫描线与多边形边界的交点区间（xminxmax），然后再将该区间内的像素赋予指定的颜色。在扫描线从多边形顶点的最小值ymin 到多边形顶点的最大值 ymax 的移动过程中，重复上述工作，就可以完成多边形的填充。(2)区域填充区域是指一组相邻而又具有相同属性的像素，可以理解为多边形的内部。区域的边界色和填充色不一致，填充算法只对区域内部进行填充。种子填充算法是从给定的种子位置开始，按填充颜色点亮种子的相邻像素直到颜色不同的边界像素为止。种子填充算法主要有 4 邻接点算法和 8 邻接点算法。2.3多边形有效边表填充算法基本原理多边形的有效边表填充算法的基本原理：按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按 x 值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间内的所有像素，即完成填充工作。有效边表填充算法是按扫描顺序计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。有效边表填充算法采用了较灵活的数据结构，通过边的分类表和活性链表访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。第3章 详细设计第3章 详细设计首先建立ET表，如图所示。边表一般是由一系列存储桶构成的，存储桶的数目和扫描线的数目一样多，按扫描线递减的顺序存放。建立ET表后，扫描多边形填充算法可按如下步骤进行。1）初始化AET，使之为空，取扫描线纵坐标y的初始值为ET中非空元素的最小序号。2）按从上到下的顺序对每条扫描线重复以下各步骤，知道AEL和ET为空。（1）将ET中与当前y有关的结点加入至AEL，同时保存AEL中按x值从小到大实现的顺序序列。（2）对于AEL中的扫描线y，在一对交点之间填充所需的像素值。（3）从AEL中删掉y=ymax结点。（4）对于留在AEL中的每个结点，执行xi+1=xi+deltax。（5）对于AEL中的各结点按x值从小到大排序。（6）使y=y+1成为下一条扫描线的坐第4章 功能实现第4章 功能实现 案例效果如下：具体实现：（1） 新建OPENGL工程：（2）在classview中输入:#include#include#include#include#includeint xx0,xx1,yy0,yy1;struct Edge /边的数据结构int ymax;float x;float delx;Edge*next;struct SortEdge /分类表Edge*out;struct Point /点int x;int y;SortEdge sortEdge500;Edge*head;void display(void);void reshape(int width,int height);void keyboard(unsigned char key ,int x,int y);void fillPolygon(Point *pt,int n);void insertSortEdge(int n,Edge*edge);/void sortLife(Edge*lifehead);/对活性边表排序void drawLife(Edge*lifehead,int y);/绘图void deleLife(Edge*lifehead,int y);/在活性边表删除边void addLife(Edge*lifehead,int y);/在活性边表中添加边int initSort(Point*pt,int n);/初始化分类表void init(void)glClearColor(0,0,0,0);glShadeModel(GL_SMOOTH);int main(int argc,char*argv)glutInit(&argc,argv);glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);glutInitWindowSize(640,480);glutInitWindowPosition(500,200);glutCreateWindow(Basic);init();glutDisplayFunc(display);glutReshapeFunc(reshape);glutKeyboardFunc(keyboard);glutMainLoop();return 0;void display(void)glClear(GL_COLOR_BUFFER_BIT);Point pt5;pt0.x=50;pt0.y=50;pt1.x=200;pt1.y=100;pt2.x=450;pt2.y=50;pt3.x=450;pt3.y=200;pt4.x=250;pt4.y=250;fillPolygon(pt,5);glFlush();void reshape(int width,int height)glViewport(0,0,width,height);glMatrixMode(GL_PROJECTION);glLoadIdentity();gluOrtho2D(0.0,width,0.0,height);void keyboard(unsigned char key,int x,int y)if(key=27)exit(0);void fillPolygon(Point *pt,int n)int max=0;int i=0,sweepY;Edge*lifeHead=new Edge;/初始化分类表max=initSort(pt,n);/初始化活性表while(sortEdgei.out=NULL)i+;sweepY=i;lifeHead=sortEdgei.out;glClear(GL_COLOR_BUFFER_BIT);glBegin(GL_LINES);glColor3f(1.0f,1.0f,1.0f);for (;imax;i+)/排序sortLife(lifeHead);/绘图drawLife(lifeHead,sweepY);sweepY+;/添加if(sortEdgesweepY.out!=NULL)addLife(lifeHead,sweepY);/删除deleLife(lifeHead,sweepY);glEnd();int initSort(Point*pt,int n)Edge*edge=new Edgen;int i,j;int max=0;for(i=0;inext=NULL;for(i=0;iymax)max=(pt+i)-y;if(i=n-1)(edge+i)-ymax=(pt+i)-ypt-y?(pt+i)-y:(pt+0)-y;(edge+i)-x=(pt+i)-y)(pt+0)-y)?(pt+0)-x):(pt+i)-x);(edge+i)-delx=(double)(pt+i)-x-(pt+0)-x)/(pt+i)-y-(pt+0)-y);if(pt+i)-ypt-y)insertSortEdge(pt-y,edge+i);elseinsertSortEdge(pt+i)-y,edge+i);else(edge+i)-ymax=(pt+i)-y(pt+i+1)-y?(pt+i)-y:(pt+i+1)-y;(edge+i)-x=(pt+i)-y)(pt+i+1)-y)?(pt+i+1)-x):(pt+i)-x);(edge+i)-delx=(double)(pt+i+1)-x-(pt+i)-x)/(pt+i+1)-y-(pt+i)-y);if(pt+i)-y(pt+i+1)-y)insertSortEdge(pt+i+1)-y,edge+i);elseinsertSortEdge(pt+i)-y,edge+i);return max;void deleLife(Edge*lifehead,int y)if(lifehead=NULL)return;else if(lifehead-ymax=y)lifehead=lifehead-next;deleLife(lifehead,y);elseEdge*curr,*pre;curr=lifehead;while(curr!=NULL)if(curr-ymax=y)pre-next=curr-next;curr=pre-next;elsepre=curr;curr=curr-next;void addLife(Edge*lifehead,int y)Edge*curr;curr=lifehead;while(curr-next!=NULL)curr=curr-next;curr-next=sortEdgey.out;void drawLife(Edge*lifehead,int y)Edge*curr,*pre;curr=pre=lifehead;while(curr!=NULL)pre=curr-next;glVertex2i(curr-x,y);glVertex2i(pre-x,y);curr-x+=curr-delx;pre-x+=pre-delx;curr=pre-next;void sortLife(Edge*lifehead)Edge*curr,*pre;curr=pre=lifehead;int num=0;float min=0;while(curr!=NULL)pre=curr;min=500;while(pre!=NULL)if(pre-xx;pre=pre-next;pre=curr;while(pre-x!=min)pre=pre-next;if(pre!=curr)int temp=pre-ymax;pre-ymax=curr-ymax;curr-ymax=temp;temp=pre-x;pre-x=curr-x;curr-x=temp;double delx=pre-delx;pre-delx=curr-delx;curr-delx=delx;curr=curr-next;void insertSortEdge(int n,Edge*edge)Edge*pre;if(sortEdgen.out=NULL)sortEdgen.out=edge;elsepre=sortEdgen.out;while(pre-next!=NULL)pre=pre-next;pre-next=edge; 第6章 总结 第5章 不足与改进第5章 不足与改进1）边表构造的算法:(1) 首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(2) 将每条边的信息链入与该边最小y坐标相对的桶处。也就是说，若某条边的较低点为ymin，则该边就放在相应的扫描线中。(3) 每条边的数据形成一个结点，内容包括:该扫描线与该的初始交点x(即较低端点的x值),1/k，以及该边的最大y值ymax如下：x|yminymax1/knext(4) 同一桶中若干条边按x|ymin由小到在大排序，若x|ymin相等，则按照1/k由小到大排序。2）改进的有效边表填充算法步骤如下:(1) 初始化： 构造边表， AET表置空.(2) 将第一个不空的ET表中的边与AET表合并。(3) 删除AET表中y = ymax的边后再填充，按“下闭上升”的原则进行填充，此时就无需缩短任何边。然后进行填充，填充时设置一个布尔量b(初值为假)，令指针从有效边表中第 一个