鉴于本周忙于各种党课的时期，以及团队项目我负责的部分不是很忙，所以就写写关于刚结束的图形学实验一的收获。
实验一是关于基本二维图元生成算法，其中又分为三个小实验，分别是生成直线、圆以及多边形填充算法。由于实验室三人一组分工，所以我负责了多边形填充算法的实现。
简单介绍一下算法，算法用到了两个数据结构：Edge Table和Active Edge List。Edge Table是个list<Edge>型的链表数组，数组下标为y轴坐标，当顺着y轴坐标从下往上扫描过程中扫描到某个边的最低端点时，就把该边的信息存入(同一下标的边以链表形式存储)，边包括x_low(两端点中y较小的点对应的x值)，y_top(两端点中y较大的值)，1/m(斜率的倒数)。而Active Edge List是list<Edge>型的，大循环需要遍历Edge Tabl数组，每次先把同一下标中链表存储的边按左右位置排序加入到Active Edge Lis (具体实现不细说了，因为涉及到斜率问题)，然后按照两条边的x_low坐标填充之间的所有点，再把x_low+=1/m，然后数组下标+1(当有变得y_top==当前下标时，把该边从Active Edge List中移除)。
不得不说我感觉我完全没有说清楚。。。
void Scan(){ Edge edge; list<Edge> ET[21]; int i = 0; int temp; list<Edge> ALE; list<Edge>::iterator k; float xtemp, x1temp, ytemp; for (i = 1; i < j - 1; i++){ if (points[i][1]>points[i + 1][1]){ edge.x_low = points[i + 1][0]; edge.y_top = points[i][1]; edge.m = (points[i][0] - points[i + 1][0]) / (points[i][1] - points[i + 1][1]); temp = points[i + 1][1] * 10 + 10; if (i == j - 2){ if (((points[i][1] - points[i + 1][1])*(points[0][1] - points[i + 1][1])) < 0){ edge.x_low = edge.x_low + edge.m / 10; temp++; } } else{ if (((points[i][1] - points[i + 1][1])*(points[i + 2][1] - points[i + 1][1])) < 0){ edge.x_low = edge.x_low + edge.m / 10; temp++; } } ET[temp].push_back(edge); } else if (points[i][1]<points[i + 1][1]){ edge.x_low = points[i][0]; edge.y_top = points[i + 1][1]; edge.m = (points[i][0] - points[i + 1][0]) / (points[i][1] - points[i + 1][1]); temp = points[i][1] * 10 + 10; if (((points[i - 1][1] - points[i][1])*(points[i + 1][1] - points[i][1]))<0){ edge.x_low = edge.x_low + edge.m / 10; temp++; } ET[temp].push_back(edge); } } if (points[0][1] > points[j - 1][1]){ edge.x_low = points[j - 1][0]; edge.y_top = points[0][1]; edge.m = (points[0][0] - points[j - 1][0]) / (points[0][1] - points[j - 1][1]); temp = points[j-1][1] * 10 + 10; if (((points[j - 2][1] - points[j - 1][1])*(points[j][1] - points[j - 1][1])) < 0){ edge.x_low = edge.x_low + edge.m / 10; temp++; } ET[temp].push_back(edge); } else if (points[0][1] < points[j - 1][1]){ edge.x_low = points[0][0]; edge.y_top = points[j - 1][1]; edge.m = (points[0][0] - points[j - 1][0]) / (points[0][1] - points[j - 1][1]); temp = points[0][1] * 10 + 10; if (((points[j - 1][1] - points[0][1])*(points[1][1] - points[0][1]))<0){ edge.x_low = edge.x_low + edge.m / 10; temp++; } ET[temp].push_back(edge); } if (points[0][1] > points[1][1]){ edge.x_low = points[1][0]; edge.y_top = points[0][1]; edge.m = (points[0][0] - points[1][0]) / (points[0][1] - points[1][1]); temp = points[1][1] * 10 + 10; if (((points[0][1] - points[1][1])*(points[2][1] - points[1][1])) < 0){ edge.x_low = edge.x_low + edge.m / 10; temp++; } ET[temp].push_back(edge); } else if (points[0][1] < points[1][1]){ edge.x_low = points[0][0]; edge.y_top = points[1][1]; edge.m = (points[0][0] - points[1][0]) / (points[0][1] - points[1][1]); temp = points[0][1] * 10 + 10; if (((points[j - 1][1] - points[0][1])*(points[1][1] - points[0][1])) < 0){ edge.x_low = edge.x_low + edge.m / 10; temp++; } ET[temp].push_back(edge); } for (i = 0; ET[i].size() != 0; i++){ temp = i; } for (i = temp; i < 21; i++){ while(ET[i].size()!=0){ edge = ET[i].front(); ET[i].pop_front(); for (k = ALE.begin(); k != ALE.end(); k++){ if (edge.x_low < k->x_low) break; if (edge.x_low == k->x_low){ if (edge.m*k->m>0){ if (edge.m>k->m) break; else{ k++; break; } } else{ if (edge.m<k->m) break; else{ k++; break; } } } } ALE.insert(k, edge); } glBegin(GL_POINTS); for (k = ALE.begin(); k != ALE.end(); k++){ xtemp = k->x_low; k++; x1temp = k->x_low; ytemp = (i - 10) / 10.0; for (float j = xtemp; j < x1temp; j = j + 0.1) glVertex2f(Round(j), ytemp); } glEnd(); glFlush(); for (k = ALE.begin(); k != ALE.end(); ){ ytemp = (i - 10) / 10.0; if (k->y_top == ytemp) k = ALE.erase(k); else{ k->x_low = k->x_low +k->m/10.0; k++; } } } }
程序主界面如下
点击鼠标左键可在屏幕中输入多边形顶点(点击顺序对多边形生成有影响)
点击鼠标右键可唤出菜单
Line(连线)：将输入的点按点击顺序连线，调用了glBegin(GL_LINE_LOOP)函数
Fill(填充)：对生成的多边形进行填充(可以不连线)，使用了上述的算法
Color(变色)：只改变多边形颜色而不影响坐标系
ClearScreen(清屏)：重置主界面
Exit(退出)：就是退出
这次的实验让我感叹于openGL画图的便捷(虽然eaxyX也挺好的)，学习到了openGL相关的画图、菜单、鼠标等函数的使用以及c++ list链表的使用，感觉能图形化的东西确实比干巴巴的算法有意思，不过算法还是重点难点，有点愁。