本文实例为大家分享了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;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/OOFFrankDura/article/details/79581437
