《计算机图形学》有序边表填充算法Word格式文档下载.docx
- 文档编号:3646473
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:12
- 大小:223.18KB
《计算机图形学》有序边表填充算法Word格式文档下载.docx
《《计算机图形学》有序边表填充算法Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《《计算机图形学》有序边表填充算法Word格式文档下载.docx(12页珍藏版)》请在冰点文库上搜索。
p2,p6为非极值点,则不用如上处理。
为了提高效率,在处理一条扫描线时,仅对与它相交的多边形的边进行求交运算。
把与当前扫描线相交的边称为活性边,并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,称此链表为活性边表(AET)。
对每一条扫描线都建立一个与它相交的多边形的活性边表(AET。
每个AET的一
个节点代表一条活性边,它包含三项内容
1.x-当前扫描线与这条边交点的x坐标;
2.△x-该边与当前扫描线交点到下一条扫描线交点的x增量;
3.ymax-该边最高顶点相交的扫描线号。
每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序
连接在一起。
当扫描线y移动到下一条扫描线y=y+1时,活性边表需要更新,即删去不与新扫描线相交的多边形边,同时增加与新扫描线相交的多边形边,并根据增量法重新计算扫描线与各边的交点x。
当多边形新边表ET构成后,按下列步骤进行:
1对每一条扫描线i,初始化ET表的表头指针ET[i];
2将ymax=i的边放入ET[i]中;
3使y=多边形最低的扫描线号;
4初始化活性边表AET为空;
5循环,直到AET和ET为空。
将新边表ET中对应y值的新边节点插入到AET表。
遍历AET表,将两两配对的交点之间填充给定颜色值。
遍历AET表,将ymax=y的边节点从AET表中删除,并将ymax>
y的各边节点的x值递增△x;
并重新排序。
y增加1。
三、程序源代码
#inelude"
graphics.h"
#defineWINDOW_HEIGHT480
#defineNULL0
#include"
alloc.h"
stdio.h"
dos.h"
conio.h"
typedefstructtEdge/*typedef是将结构定义成数据类型*/
{intymax;
/*边所交的最高扫描线号*/
floatx;
/*当前扫描线与边的交点的x值*/
floatdx;
/*从当前扫描线到下一条扫描线之间的x增量*/
structtEdge*next;
}Edge;
intyNext(intk,intcnt,POINT*pts)
/*对于多边形中的某个顶点序号k(0,1...6),返回下一顶点的纵坐标,如果这2个顶点所在边是水平的,则顺延,即返回第(k+2)个顶点的纵坐标),cnt是顶点个数+1,pts指向多边形顶点结构体的指针*/
{
intj;
if((k+1)>
(cnt-1))/*当前顶点为最后一个顶点,则下一个顶点为第0个顶点*/
j=0;
else
j=k+1;
/*当前顶点不是最后一个顶点,下一个顶点为数组下标加一*/
while(pts[k].y==pts[j].y)
/*扫描线扫过平行顶点,需分情况找到当前顶点下下个顶点*/
/*创建边表的主体函数*/
voidBuildEdgeList(intcnt,POINT*pts,Edge*edges[])
/*建立新边表,cnt:
多边形顶点个数+1,edges[]:
指向活性边结点的指针数组*/
Edge*edge;
POINTv1,v2;
inti,yPrev=pts[cnt-2].y;
/*当前顶点的前一个顶点的y值,在当前顶点不是奇点时使用该参数*/
v1.x=pts[cnt-1].x;
v1.y=pts[cnt-1].y;
for(i=0;
i<
cnt;
i++)
{v2=pts[i];
if(v1.y!
=v2.y)/*非水平线*/
edge=(Edge*)malloc(sizeof(Edge));
yPrev=v1.y;
v1=v2;
填充一对交点的主体函数
voidFillScan(intscan,Edge*active,intcolor)
/*填充扫描线:
填充扫描线上,且在下一结点到再下一结点之间的点*/
Edge*p1,*p2;
inti;
p仁active->
next;
while(p1)
p2=p1->
画出图形内部的点*/活性表的下一条边表*/
for(i=p1->
x;
p2->
putpixel((int)i,scan,color);
/*
p仁p2->
next;
}
voidDeleteAfter(Edge*q)
/*删除链表中结点,删除边结点q的后续结点p*/
/*删除结点*/
Edge*p=q->
q->
next=p->
free(p);
/*删除y=ymax的边*/
/*填充完后,更新活动边表的主体函数*/
voidUpdateActiveList(intscan,Edge*active)
/*删除扫描线scan完成交点计算的活性边,同时更新交点x域*/
Edge*q=active,*p=active->
while(p)
if(scan>
=p->
ymax)/*扫描线超过边的最大y值,此条边的节点应该删掉*/
p=p->
deleteAfter(q);
else/*扫描线未超过边的最大y值,相应的x值增加*/
p->
x=p->
x+p->
dx;
q=p;
/*对活性边表结点重新排序的主体函数*/
voidResortActiveList(Edge*active)
/*活性边表active中的结点按x域从小到大重新排序*/
Edge*q,*p=active->
active->
next=NULL;
while(p)
{q=p->
InsertEdge(active,p);
p=q;
把更新后的边表重新插入边表中保存*/
/*多边形填充的主体程序*/
voidScanFill(intcnt,POINT*pts,intcolor)
/*填充函数,输入:
多边形顶点个数+仁ent,指向多边形顶点的指针数组pts*/
Edge*edges[WINDOW_HEIGHT],*active;
inti,scan,scanmax=0,scanmin=WINDOW_HEIGHT;
for(i=0;
cnt-1;
/*
求扫描线的最大值最小值
*/
{if(scanmax<
pts[i].y)scanmax=pts[i].y;
if(scanmin>
pts[i].y)scanmin=pts[i].y;
for(scan=scanmin;
scan<
=scanmax;
scan++)/*{edges[scan]=(Edge*)malloc(sizeof(Edge));
edges[scan]->
初始化每条扫面线的边链表
建“桶”
BuildEdgeList(cnt,pts,edges);
active=(Edge*)malloc(sizeof(Edge));
scan++){
BuildActiveList(scan,active,edges);
if(active->
next)
{FillScan(scan,active,color);
UpdateActiveList(scan,active);
ResortActiveList(active);
建立有序边表
扫描每条扫描线,求活性表*/
建立活性边表*/活性边表不为空*/填充当前扫描线
更新活化边表
重排活化边表
/*开始菜单*/
voidmain()
POINTpts[7];
intgdrive=DETECT,gmode;
pts[0].x=100;
pts[0].y=40;
pts[1].x=220;
pts[1].y=140;
pts[2].x=280;
pts[2].y=80;
pts[3].x=350;
pts[3].y=300;
pts[4].x=200;
pts[4].y=380;
pts[5].x=50;
pts[5].y=280;
pts[6].x=100;
pts[6].y=40;
设置graphic模式*/
/*保存数组*/
/*多边形顶点x、y坐标*/
合并桶中的新边,按次序插入到AET中*/
initgraph(&
gdrive,&
gmode,"
C:
\\TC3.0\\BGI"
);
SeanFill(7,pts,2);
getch();
四、
实验结果
图1用有序边表算法生成的多边形总结与体会
实验步骤
五、
1)分析多边形区域扫描线填充算法的原理,确定算法流程
1初始化:
构造边表,AET表置空
2将第一个不空的ET表中的边插入AET表
3由AET表取出交点进行配对(奇偶)获得填充区间,依次对这些填充区间着色
4y=yi+1时,根据x=xi+1/k修改AET表所有结点中交点的x坐标。
同时如果相应的ET表不空,则将其中的结点插入AET表,形成新的AET表
5AET表不空,则转(3),否则结束。
2)编程实现
1首先确定多边形顶点和ET/AET表中结点的结构
2编写链表相关操作(如链表结点插入、删除和排序等)
3根据1)中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的
主体功能
4编写主函数,测试该算法
通过运用C语言环境下的图像显示设置,本次实验我学会了多边形区域扫描线填充的有序边表算法,设计相关的数据结构(如链表结构、结点结构等),并将实现的算法应用于任意多边形的填充,为深一步的学习做好了铺垫。
六、参考文献
[1]张家广等编著.计算机图形学(第3版)•北京:
清华大学出版社,1998年9月.
[2]陈传波,陆枫主编,《计算机图形学基础》,电子工业出版社,2002年3月.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机图形学 计算机 图形学 有序 填充 算法