《计算机图形学》有序边表填充算法.doc

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

1、实验报告一、实验目的1、掌握有序边表算法填充多边形区域；2、理解多边形填充算法的意义；3、增强C语言编程能力。二、算法原理介绍根据多边形部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。判断扫描线上的点是否在多边形之，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤：（1）求交：计算扫描线与多边形各边的交点；（2）排序：把所有交点按x值递增顺序排序；（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;（4）着色：把相交区间的象素置成多边形颜色，把相

2、交区间外的象素置成背景色。p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项容1.x-当前扫描线与这条边交

3、点的x坐标；2.Δx-该边与当前扫描线交点到下一条扫描线交点的x增量；3.ymax-该边最高顶点相交的扫描线号。每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。当扫描线y移动到下一条扫描线y=y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。当多边形新边表ET构成后，按下列步骤进行：①　对每一条扫描线i，初始化ET表的表头指针ET[i]；②　将ymax=i的边放入ET[i]中；③　使y=多边形最低的扫描线号；④　初始化活性边表AET为空；⑤　循环，直到AET和

4、ET为空。l将新边表ET中对应y值的新边节点插入到AET表。l遍历AET表，将两两配对的交点之间填充给定颜色值。l遍历AET表，将ymax=y的边节点从AET表中删除，并将ymax>y的各边节点的x值递增Δx；并重新排序。ly增加1。一、程序源代码#include"graphics.h"#defineWINDOW_HEIGHT480#defineNULL0#include"alloc.h"#include"stdio.h"#include"dos.h"#include"conio.h"typedefstructtEdge/*typedef是将结构定义成数据类型*/{intymax;

5、/*边所交的最高扫描线号*/floatx;/*当前扫描线与边的交点的x值*/floatdx;/*从当前扫描线到下一条扫描线之间的x增量*/structtEdge*next;}Edge;typedefstructpoint{intx,y;}POINT;/*将结点插入边表的主体函数*/voidInsertEdge(Edge*list,Edge*edge)/*活性边edge插入活性边表list中*/{Edge*p,*q=list;p=q->next;/*记住q原来所指之结点*/while(p!=NULL)/*按x值非递减顺序增加边表*/{if(edge->xx)/*要插入的边的x

6、较大不应该在当前插入*/p=NULL;else/*要插入的边的x较小应该在当前插入*/{q=p;p=p->next;}}edge->next=q->next;/*使欲插入之结点edge指向q原来所指之结点*/q->next=edge;/*使q指向插入之结点*/}intyNext(intk,intcnt,POINT*pts)/*对于多边形中的某个顶点序号k(0,1...6)，返回下一顶点的纵坐标,如果这2个顶点所在边是水平的，则顺延，即返回第(k+2)个顶点的纵坐标),cnt是顶点个数+1,pts指向多边形顶点结构体的指针*/{intj;if((k+1)>(cnt-1))/*当前顶点

7、为最后一个顶点，则下一个顶点为第0个顶点*/j=0;elsej=k+1;/*当前顶点不是最后一个顶点，下一个顶点为数组下标加一*/while(pts[k].y==pts[j].y)/*扫描线扫过平行顶点，需分情况找到当前顶点下下个顶点*/if((j+1)>(cnt-1))j=0;elsej++;return(pts[j].y);/*返回下一个顶点的y值*/}/*计算增量，修改AET*//*生成边表结点，并插入到边表中的主体函数*/voidMakeEdgeRec(POI