计算机图形学有效边表算法源代码.docx
《计算机图形学有效边表算法源代码.docx》由会员分享，可在线阅读，更多相关《计算机图形学有效边表算法源代码.docx（13页珍藏版）》请在冰点文库上搜索。
计算机图形学有效边表算法源代码
#include
#include
#include
#include
#defineEPSILON0.000001//最小浮点数
//点结构体
structPoint
{
intx;//x坐标
inty;//y坐标
};
//线结构体
structLine
{
Pointhigh_point;//高端点
Pointlow_point;//低端点
intis_active;//是否为有效边，水平边（0），非水平边
（1）
doubleinverse_k;//斜率k的倒数
};
//边结点
structEdgeNode
{
doublex;//扫描线与边交点的x坐标（边的低端点的x坐标）
inty_max;//边的高端点的y坐标ymax
doubleinverse_k;//斜率k的倒数
EdgeNode*next;//下一个边结点的指针
};
//有效边表
structActiveEdgeTable
{
inty;//扫描线y
EdgeNode*head;//边链表的头指针
};
//桶结点
typedefstructBucket
{
inty;//扫描线y
EdgeNode*head;//边链表的头指针
Bucket*next;//下一个桶的指针
}EdgeTable;
intcompare（Pointp1,Pointp2）;
Line*create_lines（Pointpoints[],intn）;
Pointget_lowest_point（Linelines[],intn）;
Pointget_highest_point（Linelines[],intn）;
voidswap（Line&l1,Line&l2）;
voidsort（Linelines[],intn）;
EdgeTable*create_edge_table（Linelines[],intn）;
ActiveEdgeTable*init_active_table（EdgeTable*edge_table）;
voiddelete_edge（ActiveEdgeTable*active_table,inty_max）;
voidadd_edge（ActiveEdgeTable*active_table,EdgeNodeedge）;
ActiveEdgeTable*update_active_table（ActiveEdgeTable*active_table,EdgeTable*edge_table）;
voidDrawPolygon（Pointpoints,intn）;
voidDrawGrid（intx,inty）;
voidFill（Pointpoints[],intn）;
voidInitial（）;
voidDisplay（）;
intmain（intargc,char*argv[]）
{
glutInit（&argc,argv）;
glutInitDisplayMode（GLUT_SINGLE|GLUT_RGB）;
glutInitWindowSize（400,300）;
glutInitWindowPosition（100,120）;
glutCreateWindow（"PolygonFilling"）;
glutDisplayFunc（Display）;
Initial（）;
glutMainLoop（）;
return0;
}
//比较2个点的高度
intcompare（Pointp1,Pointp2）
{
if（p1.y>p2.y）
return1;
elseif（p1.y==p2.y）
return0;
return-1;
}
//由点数组生成线段数组
Line*create_lines（Pointpoints[],intn）
{
Line*lines=（Line*）malloc（n*sizeof（Line））;
for（inti=0;i{
Pointp1=points[i];
Pointp2=points[（i+1）%n];
intresult=compare（p1,p2）;
if（result==0）
lines[i].is_active=0;
else
lines[i].is_active=1;
lines[i].high_point=result>0?
p1:
p2;
lines[i].low_point=result<0?
p1:
p2;
lines[i].inverse_k=（double）（p2.x-p1.x）/（double）（p2.y-p1.y）;
}
returnlines;
}
//获取线数组中最低的端点
Pointget_lowest_point（Linelines[],intn）
{
Pointlowest_point=lines[0].low_point;
for（inti=1;i{
Pointlow_point=lines[i].low_point;
if（compare（lowest_point,low_point）>0）
lowest_point=low_point;
}
returnlowest_point;
}
//获取线数组中最高的端点
Pointget_highest_point（Linelines[],intn）
{
Pointhighest_point=lines[0].high_point;
for（inti=1;i{
Pointhigh_point=lines[i].high_point;
if（compare（highest_point,high_point）<0）
highest_point=high_point;
}
returnhighest_point;
}
//交换2个Line对象
voidswap（Line&l1,Line&l2）
{
Linetemp=l1;
l1=l2;
l2=temp;
}
//对线数组进行排序
voidsort（Linelines[],intn）
{
//先按低端点的y坐标进行升序排序
for（inti=0;i{
intmin_index=i;
for（intj=i+1;j{
if（lines[j].low_point.ymin_index=j;
}
swap（lines[i],lines[min_index]）;
}
//再将有序数组按低端点的x坐标升序排列，若x坐标相等，按inverse_k升序
for（i=0;i{
intmin_index=i;
for（intj=i+1;lines[j].low_point.y==lines[i].low_point.y;++j）
{
if（lines[j].low_point.xmin_index=j;
}
swap（lines[i],lines[min_index]）;
if（i>0&&lines[i].low_point.x==lines[i-1].low_point.x）
{
if（lines[i].is_active==1&&lines[i-1].is_active==1）
{
if（lines[i].inverse_kswap（lines[i],lines[i-1]）;
}
}
}
}
//创建一个边表
EdgeTable*create_edge_table（Linelines[],intn）
{
EdgeTable*edge_table=（EdgeTable*）malloc（sizeof（EdgeTable））;
edge_table->head=NULL;
edge_table->next=NULL;
sort（lines,n）;
Pointlowest_point=get_lowest_point（lines,n）;
Pointhighest_point=get_highest_point（lines,n）;
EdgeTable*s=edge_table;
for（inti=lowest_point.y;i<=highest_point.y;++i）
{
Bucket*bucket=（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（intj=0;j{
if（lines[j].is_active==0）
continue;
if（lines[j].low_point.y==i）
{
EdgeNode*q=（EdgeNode*）malloc（sizeof（EdgeNode））;
q->x=lines[j].low_point.x;
q->y_max=lines[j].high_point.y;
q->inverse_k=lines[j].inverse_k;
q->next=NULL;
p->next=q;
p=q;
}
}
s->next=bucket;
s=bucket;
}
returnedge_table;
}
//从边表中取出第一个不为空的桶初始化有效边表
ActiveEdgeTable*init_active_table（EdgeTable*edge_table）
{
ActiveEdgeTable*active_table=（ActiveEdgeTable*）malloc（sizeof（ActiveEdgeTable））;
active_table->y=edge_table->next->y;
active_table->head=（EdgeNode*）malloc（sizeof（EdgeNode））;
active_table->head->next=NULL;
EdgeNode*p=edge_table->next->head;
EdgeNode*q=active_table->head;
while（p->next!
=NULL）
{
EdgeNode*s=（EdgeNode*）malloc（sizeof（EdgeNode））;
s->x=p->next->x;
s->y_max=p->next->y_max;
s->inverse_k=p->next->inverse_k;
s->next=NULL;
q->next=s;
q=s;
p=p->next;
}
returnactive_table;
}
//从有效边表中删除指定y_max的边结点
voiddelete_edge（ActiveEdgeTable*active_table,inty_max）
{
EdgeNode*p=active_table->head;
while（p->next!
=NULL）
{
EdgeNode*q=p->next;
if（q->y_max==y_max）
{
p->next=q->next;
free（q）;
}
else
p=p->next;
}
}
//将一个边结点按次序添加到有效边表中
voidadd_edge（ActiveEdgeTable*active_table,EdgeNodeedge）
{
EdgeNode*t=（EdgeNode*）malloc（sizeof（EdgeNode））;
t->x=edge.x;
t->y_max=edge.y_max;
t->inverse_k=edge.inverse_k;
t->next=NULL;
EdgeNode*p=active_table->head;
while（p->next!
=NULL）
{
EdgeNode*q=p->next;
if（（edge.xx）||（edge.x==q->x&&edge.inverse_kinverse_k））
{
p->next=t;
t->next=q;
return;
}
p=p->next;
}
p->next=t;
}
//更新有效边表，并与边表中对应的桶合并
ActiveEdgeTable*update_active_table（ActiveEdgeTable*active_table,EdgeTable*edge_table）
{
//更新扫描线y
++active_table->y;
//删除y=ymax的边
delete_edge（active_table,active_table->y）;
//更新边结点的数据
EdgeNode*p=active_table->head->next;
while（p!
=NULL）
{
p->x+=p->inverse_k;
p=p->next;
}
//找到边表中对应的桶
EdgeTable*q=edge_table;
while（（q=q->next）!
=NULL&&q->y!
=active_table->y）;
//如果找到，则进行合并
if（q!
=NULL）
{
EdgeNode*s=q->head;
while（（s=s->next）!
=NULL）
{
add_edge（active_table,*s）;
}
}
returnactive_table;
}
//画出多边形的边框
voidDrawPolygon（Pointpoints[],intn）
{
glBegin（GL_LINE_LOOP）;
for（inti=0;iglVertex2i（points[i].x,points[i].y）;
glEnd（）;
}
//画出x*y的网格
voidDrawGrid（intx,inty）
{
glBegin（GL_LINES）;
//横线
for（inti=0;i<=y;++i）
{
glVertex2d（0,i）;
glVertex2d（x,i）;
}
//竖线
for（i=0;i<=x;++i）
{
glVertex2d（i,0）;
glVertex2d（i,y）;
}
glEnd（）;
}
//用指定的像素大小填充多边形
voidFill（Pointpoints[],intn）
{
Line*lines=create_lines（points,n）;
EdgeTable*edge_table=create_edge_table（lines,n）;
ActiveEdgeTable*active_table=init_active_table（edge_table）;
while（active_table->head->next!
=NULL）
{
EdgeNode*p=active_table->head;
intb=-1;
while（p->next!
=NULL）
{
if（b>0）
{
intleft=p->x;
intright=p->next->x;
//如果不是局部最低点，则进行边界处理
if（!
（p->x-p->next->x>=-EPSILON&&p->x-p->next->x<=EPSILON））
{
//处理左边界
if（!
（p->x-left>=-EPSILON&&p->x-left<=EPSILON））
left+=1;
//处理右边界
if（p->next->x-right>=-EPSILON&&p->next->x-right<=EPSILON）
right-=1;
}
for（inti=left;i<=right;++i）
{
glBegin（GL_POINTS）;
glVertex2d（i,active_table->y）;
glEnd（）;
glFlush（）;
Sleep（50）;
}
}
p=p->next;
b=-b;
}
active_table=update_active_table（active_table,edge_table）;
}
}
//初始化窗口，x和y指定窗口的坐标大小
voidInitial（）
{
glClearColor（1.0f,1.0f,1.0f,1.0f）;
glMatrixMode（GL_PROJECTION）;
gluOrtho2D（0.0,20.0,0.0,15.0）;
}
//窗口的显示回调函数
voidDisplay（）
{
//使用当前背景色填充窗口
glClear（GL_COLOR_BUFFER_BIT）;
//使用灰色画出网格线
glColor3f（0.75f,0.75f,0.75f）;
DrawGrid（20,14）;
glFlush（）;
//多边形的顶点坐标
Pointpoints[]={{3,1},{6,5},{8,1},{12,9},{7,8},{3,12},{1,7}};
//计算顶点个数
intn=sizeof（points）/sizeof（Point）;
//使用黑色画出多边形的边框
glColor3f（0.0f,0.0f,0.0f）;
DrawPolygon（points,n）;
glFlush（）;
//指定点大小
glPointSize（6.0f）;
//使用红色填充多边形
glColor3f（1.0f,0.0f,1.0f）;
Fill（points,n）;
glFlush（）;
}
升级会员 