opengl画线（opengl中点画线算法）

本文实例为大家分享了OpenGL扫描线填充算法，供大家参考，具体内容如下

说明

把最近一系列的图形学经典算法实现了一下。课业繁忙，关于该系列的推导随后再写。但是在注释里已经有较为充分的分析。

分情况讨论

注意对于横线需要特别讨论，但是对于垂直线却不必特别讨论。想一想为什么？

代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 #include <iostream> #include <GLUT/GLUT.h> #include <map> #include <vector> #include <list> #include <algorithm> using namespace std; int hmin,hmax; //记录扫描线开始和结束的位置 struct Line { //定义线段的结构体 float dx,x,y,ym; //不用记录K直接记录dx和x即可 Line(float x1,float y1,float x2,float y2) { if(y1==y2){ //单独讨论横直线的情况 this->y = y1; this->ym = y1; if(x1 < x2){ dx = x1; x = x2; }else{ dx =x2;x = x1;} }else if(y2<y1){ //选择靠上者的x值 this -> x = x2; //记录上方的x值一方便处理关键时刻（用于插入AET排序） this ->y = y2; //记录上方的y值，用于排序 this -> ym = y1; //靠下者ym }else{ this -> x = x1; this ->y = y1; this -> ym = y2; } dx = (x2-x1)/(y2-y1); } }; typedef list<Line> TESTLIST; vector<vector<Line>> con; //记录重要事件表（有序），当然这个也可以使用优先队列 list<Line> AET; //滚动记录活动边表,这里将 //该边表完整存储的意义不大所以采用滚动存储的方式 map<int, int> mapper; //用于数据（y值）离散化处理 int x1,y1,x2,y2; //描述构成直线的两个端点 int x0,y0; //记录图形开始位置 float h_min,h_max; //画线开始和结束的位置 int flag = 1; //用于记录用户点击的次数，单次画点，双次画线。 int if_drawable = 1; //当用户再次点击鼠标时不在更改信息 int window_size=600; //这是我们显示界面的大小 vector<vector<Line>> con2; int level = 1; /* 操作说明：算法没有严格的图形绘制检查。仅为了图形学算法的演示。 您使用鼠标【左键】进行绘制点，请您保证没有线是交叉的。 当您点击鼠标【右键】绘制最后一个点。系统会自动将其与起始点相连。 整体思路描述：使用map将y的值离散化，用有序表记录“关键事件”主要 是加入边（一条或者两条）删除边操作。在用一个滚动的活动边表进行遍历画线。 */ void show_v(Line a){ /* 函数说明：显示点的信息 */ cout << "(" <<a.x << "," << a.y <<")"; cout << " (" <<a.dx<<")" << "下限："<<a.ym; cout << " -- "<<endl; } bool higher(const vector<Line> & l1, const vector<Line>& l2) { //将关键事件表中的line按照y值进行排序； //注意我们的画布是从上到下不断递增从左到右不断递增 return l1[0].y < l2[0].y;//可以保证一定至少有一个不然map不会映射到 } bool AET_lefter(const Line & l1, const Line & l2) { //将AET表中的line按照x值进行排序； return l1.x < l2.x;//可以保证一定至少有一个不然map不会映射到 } bool lefter(const Line & l1, const Line & l2) { /* 函数说明：将关键事件表中的line按照x值以及dx进行排序； */ if(l1.x < l2.x){ return 1; }else if (l1.x == l2.x){ if(l1.dx<0&&l2.dx>0) return 1; else return 0; }else return 0; } void sort_con(){ /* 函数说明：对关键事件表进行排序处理 其中y从小到大递增，x方向按照斜率和x大小由左到右排序 */ for (int i = 0 ; i < con.size(); i++) if (con[i].size()>=2) sort(con[i].begin(),con[i].end(),lefter); for (int i = 0;i < con.size(); i++) { vector<Line> a; for (int j =0; j < con[i].size(); j++) a.push_back(con[i][j]); con2.push_back(a); //这里将事件表进行拷贝，另一种方式是将map的映射对应改变 } sort(con.begin(), con.end(), higher); } void draw_lines(float x1,float y1,float x2,float y2){ glBegin(GL_LINES); glColor3f(1.0,1.0,0.0); glVertex2f(x1,window_size-y1); glVertex2f(x2,window_size-y2); glEnd(); glFlush(); } void show_con(){ //输出排序后的关键事件表 for (int i = 0; i < con.size(); i++) { cout <<"number : "<<i <<endl; for (int j = 0; j < con[i].size(); j++) { vector<Line> a = con[i]; show_v (a[j]); }cout <<"================"<<endl; } } void lines_filling(){ //真正的扫描线填充过程 if (con.empty()) //为了展示过程细节，部分功能没有使用函数ti return; int h_leveler = 0; //高度遍历器 map<int,int>::iterator iter; //定义一个迭代指针iter for(h_leveler = h_min;h_leveler <= h_max;h_leveler++){//开始扫描 int id = mapper[h_leveler]; if (!id) { //说明没有到达关键节点，我们只需要进行绘制和更新即可； float xx = 0.0; flag = 1; //flag用于控制每两组画一次线 for(list<Line> ::iterator it=AET.begin();it!=AET.end();) { if (flag%2==0) { //该画线了！ draw_lines(xx, h_leveler,it->x,h_leveler); for (TESTLIST::iterator pl = AET.begin(); pl != AET.end();) if (pl->ym == h_leveler) AET.erase(pl++); else pl++; //这个负责删除的for循环在画线后执行可以避免留白情况 it->x = it->x +it->dx; }else{ if (it->y == it->ym) { xx = x1; }else{ xx =it->x; it->x = it->x +it->dx; } }flag++;it++;} }else{ //如果到了关键事件，那么加线、去线 list<Line> ::iterator it; float xx = 0.0;int counter = 1; for(it=AET.begin();it!=AET.end();it++) { Line temp= *it; if (counter%2==0) //该画线了！ draw_lines(xx, h_leveler,temp.x,h_leveler); else xx =temp.x; //删除边前先画好线避免留白 counter++; } for (TESTLIST::iterator it = AET.begin(); it != AET.end();) if (it->ym == h_leveler) AET.erase(it++); else it++; //关键时间删除边 for (int i =0 ; i < con2[id-1].size(); i++) if (con2[id-1][i].y == con2[id-1][i].ym) continue; //如果是横线直接不用添加该横线 else AET.push_back(con2[id-1][i]); AET.sort(AET_lefter); //维持滚动活动边表的有序性 }}} void InitEnvironment() //对环境进行初始化操作 { glClearColor(0.0,0.0,0.0,0); glClear(GL_COLOR_BUFFER_BIT); glPointSize(7); glMatrixMode(GL_MODELVIEW); glLoadIdentity(); gluOrtho2D(0,window_size,0,window_size); } void myDisplay(void) { glClear(GL_COLOR_BUFFER_BIT); glFlush(); } void OnMouse(int button,int state,int x,int y) /* 函数说明：进行用户交互的操作 每两个点一组进行操作。设置左键、右键手势动作 */ {if(button==GLUT_LEFT_BUTTON&&state==GLUT_DOWN&&if_drawable) {if (flag ==1 &&if_drawable) { glColor3f(1,0,0); glBegin(GL_POINTS); glVertex2f(x,window_size-y); x0 = x;y0 =y; x1 = x;y1 = y; h_min = y0; h_max = y0; glEnd(); glFlush(); flag++; }else{ glColor3f(1,0,0); glBegin(GL_POINTS); glVertex2f(x,window_size-y); glEnd(); x2 = x;y2 = y; glBegin(GL_LINES); glColor3f(1.0,0.0,0.0); glVertex2f(x1,window_size-y1); glVertex2f(x2,window_size-y2); if (y1 !=y2) { Line a(x1,y1,x2,y2); int r_y = min (y1,y2); if (y1 < h_min) h_min = y1; if (y2 < h_min) h_min = y2; if (y1 > h_max) h_max = y1; if (y2 >h_max) h_max = y2; int pos = mapper[r_y]; if (pos==0) { //说明该变量还没有离散化 mapper[r_y] = level++; vector<Line> lines; lines.push_back(a); con.push_back(lines);} else con[pos-1].push_back(a); } x1 = x2; y1 = y2; glEnd(); glFlush(); } } if(button==GLUT_RIGHT_BUTTON&&state==GLUT_DOWN&&if_drawable) { //点击右键 glColor3f(1,0,0); glBegin(GL_POINTS); glVertex2f(x,window_size-y); glEnd(); x2 = x;y2 = y; glBegin(GL_LINES); glColor3f(1.0,0.0,0.0); glVertex2f(x1,window_size-y1); glVertex2f(x2,window_size-y2); Line a(x1,y1,x2,y2); int r_y = min (y1,y2); int pos = mapper[r_y]; if (pos==0) { //说明该变量还没有离散化 mapper[r_y] = level++; vector<Line> lines; lines.push_back(a); con.push_back(lines);} else con[pos-1].push_back(a); glEnd(); glFlush(); glBegin(GL_LINES); glColor3f(1.0,0.0,0.0); glVertex2f(x0,window_size-y0); glVertex2f(x2,window_size-y2); glEnd(); glFlush(); Line aa(x0,y0,x2,y2); r_y = min (y0,y2); pos = mapper[r_y]; if (pos==0) { //说明该变量还没有离散化 mapper[r_y] = level++; vector<Line> lines; lines.push_back(aa); con.push_back(lines);} else con[pos-1].push_back(aa); sort_con(); lines_filling(); if_drawable = 0; } } int main(int argc, char *argv[]) { glutInit(&argc, argv); //初始化GLUT glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE); glutInitWindowPosition(300, 100); glutInitWindowSize(window_size, window_size); glutCreateWindow("hw2_filling_line"); InitEnvironment(); //初始化 glutMouseFunc(&OnMouse); //注册鼠标事件 glutDisplayFunc(&myDisplay); //回调函数 glutMainLoop(); //持续显示，当窗口改变会重新绘制图形 return 0; }