隐藏面消除✧实验目的通过实现隐藏面算法，深入理解消隐算法的原理。
进一步熟悉OpenGL编程。
✧算法所采用的数据结构本程序采用活化边表的扫描线Z缓冲器算法，并实现了交互界面的测试。
采用C/C++ 、OpenGL编写程序✧主要的函数功能说明void insertEdge(Edge *list,Edge *edge)//在已经建立的边表中按照x坐标递增的顺序插入一条新边void getEdgeList(int count,point *pts,Edge *edges[],int a)//根据已给出的顶点得到边表void sort(Edge *list,Edge *edge)//对活化边表中的边进行排序void getActiveList(int scan,Edge *active,Edge *edges[])//构造活化边表void scanfill()//扫描填充算法的实现✧测试用例本程序实现一个交互输入的界面，下面是用于算法检验的数据：2990 300 110330 380 -210390 200 -90180 120 20090 300 110120 280 100350 220 -70200 130 170120 280 1001.0 1.0 1.0 -5004230 250 -80480 480 -560430 150 -180300 80 201.0 1.0 1.0 -400得到的运行界面如下图所示：代码附录#include <windows.h>#include <gl/gl.h>#include <gl/glaux.h>#include <gl/glu.h>#include <iostream.h>#define SCAN_NUM 500typedef struct Edge //边Y桶中的边结构{int yUpper; //边的最大y值float xInt,dx; //边的最低点的x值，之所以是最低点，是因为本程序是从下往上扫描的int E_mark;float z,dzx,dzy;struct Edge *next; //指向下一条边节点的指针}Edge;typedef struct point //定义一个点的结构体{int x;int y;float z;}point;extern point **points=NULL; //存放多个多边形的顶点信息extern float **as=NULL; //存放多边形所在平面的方程的四个系数extern int *counts=NULL; //存放各个多边形的顶点个数extern int num=0; //记录多边形个数void DrawPoint(int x, int y)//画点函数{::glBegin(GL_POINTS);::glVertex2d(x, y);::glEnd();}int nexty(int k,int count,point *pts)//当前测试点的下一个点的纵坐标，其方向为顺时针{int j;if((k+1)>(count-1))j=0;else j=k+1;while(pts[k].y==pts[j].y){if((j+1)>(count-1))j=0;elsej++;}return pts[j].y;}void insertEdge(Edge *list,Edge *edge)//往已知边表中插入一条边，当然得按顺序插入{Edge *p,*q=list;p=q->next;//p指向y=lower.y的第一条边while(p!=NULL){if(edge->xInt<p->xInt)//测试活化边表按x增加排序，从而保证了扫描时从左往右的准确性p=NULL;else{q=p; //p、q后移p=p->next;}}edge->next=q->next;//插入edge边q->next=edge;}void makeEdges(point lower,point upper,int yComp,Edge *edges[],int &a){Edge *edge=new Edge;edge->dx=(float)(upper.x-lower.x)/(upper.y-lower.y);//存储当前边(lower、upper)信息edge->xInt=(float)lower.x;//边的x坐标if(upper.y<yComp)edge->yUpper=upper.y-1;//如果upper点非极值点else //如果为极值点edge->yUpper=upper.y;edge->E_mark=a;edge->z=lower.z;edge->dzx=-as[a][0]/as[a][2];edge->dzy=-as[a][1]/as[a][2];insertEdge(edges[lower.y],edge);//将此边添加至有序边表}void getEdgeList(int count,point *pts,Edge *edges[],int a){point v1,v2; //定义两个中间变量int i,yPrev=pts[count-2].y;//定义yPrev为当前点的前一点纵坐标坐标v1.x=pts[count-1].x;v1.y=pts[count-1].y;v1.z=pts[count-1].z;for(i=0;i<count;i++){v2=pts[i];//v2记录当前测试点if(v1.y!=v2.y)//如果直线非水平的{if(v1.y<v2.y)//如果此直线是沿v1、v2方向是上升的makeEdges(v1,v2,nexty(i,count,pts),edges,a);else //如果此直线是沿v1、v2方向是下降的makeEdges(v2,v1,yPrev,edges,a);}yPrev=v1.y;v1=v2;}}void deleteEdge(Edge *q)//删除扫描过的边{Edge *p=q->next;q->next=p->next;free(p);}void sort(Edge *list,Edge *edge)//对活化边表中的边进行排序{Edge *p,*q=list;p=q->next;//p指向y=lower.y的第一条边while(p!=NULL){if(edge->E_mark<p->E_mark)//首先按多边形类型进行排序，第一个排在最前面{p=NULL;}else if(edge->E_mark==p->E_mark) //接着按具体某一个多边形的边的x值进行排序{if(edge->xInt<p->xInt)//测试活化边表按x增加排序，从而保证了扫描时从左往右的准确性p=NULL;else{q=p; //p、q后移p=p->next;}}else{q=p; //p、q后移p=p->next;}}edge->next=q->next;//插入edge边q->next=edge;}void getActiveList(int scan,Edge *active,Edge *edges[])//构造活化边表{Edge *p,*q;p=edges[scan]->next;//p指向edges[scan]的第一条边while(p){q=p->next;//q指向下一条边sort(active,p);p=q;}}void scanfill(){Edge **edges=new Edge* [SCAN_NUM]; //边Y桶Edge *active; //边活化边表int i,yscan,j;for(i=0;i<SCAN_NUM;i++){edges[i]=new Edge;//初始化有序边表edges[i]->next=NULL;}for(i=0;i<num;i++)getEdgeList(counts[i],points[i],edges,i);//修改边Y桶active=new Edge;active->next=NULL;int FraBuffer[SCAN_NUM][SCAN_NUM]; //创建桢缓冲器和Z缓冲器int ZBuffer[SCAN_NUM];for(i=0;i<SCAN_NUM;i++){ZBuffer[i]=-10000;for(j=0;j<SCAN_NUM;j++)FraBuffer[i][j]=-1;}for(yscan=0;yscan<SCAN_NUM;yscan++){getActiveList(yscan,active,edges);//构造好活化边表if(active->next){Edge *q=active,*p=active->next;while(p) //遍历一趟活化边表，一次两条边，即找到一个顶点对{q=p->next;for(int xx=p->xInt;xx<=q->xInt;xx++)//比较当前顶点对之间{int zz; //点的Z值和Z缓冲器中的值zz=p->z+(xx-p->xInt)*p->dzx; //然后确定桢缓冲器中的颜色值if(zz>ZBuffer[xx]) //如果大，则颜色值设置为当前多边形的颜色值{FraBuffer[yscan][xx]=p->E_mark;ZBuffer[xx]=zz;}}p=q->next;}for(i=0;i<SCAN_NUM;i++) //当前扫描线对应的桢缓冲器中的颜色值{if(FraBuffer[yscan][i]==0) //显示输出，假设本程序最多有8个多边形{::glColor3f(1.0, 0.0, 0.0);DrawPoint(i,yscan);}else if(FraBuffer[yscan][i]==1){::glColor3f(1.0, 1.0, 0.0);DrawPoint(i,yscan);}else if(FraBuffer[yscan][i]==2){::glColor3f(1.0, 0.0, 1.0);DrawPoint(i,yscan);}else if(FraBuffer[yscan][i]==3){::glColor3f(0.0, 0.1, 0.2);DrawPoint(i,yscan);}else if(FraBuffer[yscan][i]==4){::glColor3f(0.2, 0.1, 0.0);DrawPoint(i,yscan);}else if(FraBuffer[yscan][i]==5){::glColor3f(0.1, 0.2, 0.0);DrawPoint(i,yscan);}else if(FraBuffer[yscan][i]==6){::glColor3f(0.1, 0.2, 0.2);DrawPoint(i,yscan);}else if(FraBuffer[yscan][i]==7){::glColor3f(0.4, 0.6, 0.3);DrawPoint(i,yscan);}ZBuffer[i]=-1000; //恢复Z缓冲器中的值，以备下次扫描时使用}//更新活化边表中具体的边中的元素值q=active;p=active->next;//更新具体每条边的值或者删除某些边while(p){if(yscan>=p->yUpper)//当扫描线即将于某一条边分离时，删除此边{p=p->next;//p后移deleteEdge(q);}else{p->xInt=p->xInt+p->dx;//扫描线仍与此边相交，更新下一次扫描时的x坐标的值p->z+=(p->dzx*p->dx+p->dzy);q=p; //p、q后移p=p->next;}}//更新活化边表，对更新后的边进行重新排序p=active->next;//更新活化边表active->next=NULL;while(p){q=p->next;sort(active,p); //调用排序函数，此函数乃是本算法的关键所在p=q;}}}}void CALLBACK Reshape(GLsizei w, GLsizei h){::glViewport(0, 0, w, h);::glMatrixMode(GL_PROJECTION);glLoadIdentity();if (w <= h)gluOrtho2D (0.0, SCREEN_WIDTH, 0.0, SCREEN_WIDTH*(GLfloat)h/(GLfloat)w);elsegluOrtho2D (0.0, (GLfloat)SCREEN_WIDTH*(GLfloat)w/(GLfloat)h, 0.0, SCREEN_WIDTH);glMatrixMode(GL_MODELVIEW);return;}void CALLBACK Display1(){scanfill();return;}void Init(){::auxInitDisplayMode(AUX_RGBA|AUX_SINGLE);::auxInitPosition(0, 0, 500, 500);::auxInitWindow("Scan algithmic");::glShadeModel(GL_FLAT);::glClearColor(0.0, 0.0, 0.0, 0.0);}void main(int argc, char **argv){int x,y,z;float a,b,c,d;int n;cout<<"下面将一个复杂的空间图形按照其具有的平面进行输入"<<endl<<endl;cout<<"请输入多边形个数："<<endl;cin>>num;points=new point*[num];as=new float*[num];counts=new int[num];for(int i=0;i<num;i++){cout<<"请输入第"<<i<<"个多边形的顶点个数"<<endl;cin>>n;counts[i]=n;points[i]=new point[n];for(int j=0;j<n;j++){cin>>x>>y>>z;points[i][j].x=x;points[i][j].y=y;points[i][j].z=z;}as[i]=new float[4];cout<<endl<<"请输入第"<<i<<"个多边形的四个系数："<<endl;cin>>a>>b>>c>>d;as[i][0]=a;as[i][1]=b;as[i][2]=c;as[i][3]=d;}::auxReshapeFunc(Reshape);::auxMainLoop(Display1);return;}。
