计算机图形学区域填充-多边形扫描转换算法实现

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
#include<GL/glut.h>
#include<vector>
#include<algorithm>
int mi_y;
struct ETnode {
float x_min;//最小x
int y_max;//最大y
float $1_k;//斜率的倒数
};
struct AETnode {//和ETnode没啥区别, 区别就是x是当前的x
float x;//当前x
int y_max;//最大y
float $1_k;//斜率的倒数
};
std::vector <ETnode> ET[1005];
std::vector <AETnode> AET;
//比较函数
bool cmp(AETnode a, AETnode b) {
//y_max越小排在越前面
return a.x < b.x;
}
//ET表的初始化:将待处理多边形的各条边按照该边上最小的y值加入对应该y值的存储桶中
void ETlist_init(int x1,int y1,int x2,int y2 )//尽管这里是一个list,但我们是用vector去实现的
{
//输入两个顶点,初始化ET表
//值得注意的是,两个y不能相等, 也就是不能出现斜率为0 的情况 , 否则无法给出斜率的倒数
ETnode tmp;
if (y1 < y2)
{
std::swap(x1, x2);
std::swap(y1, y2);
}
//现在我们的y1 就是 大于 y2的
if (y1 == y2) //被我们舍弃了
{
return;
}
//已经剔除了分母为0的情况
tmp.$1_k = float(x1-x2)/(y1-y2);//斜率倒数
tmp.x_min = float(x2);//当前x是x2
tmp.y_max = y1;//当前y_max是y1
//再把它push到一桶里面
ET[y2].push_back(tmp);
//求最小值
mi_y = std::min(mi_y, y2);
}
void AETlist()
{

}
void myDisplay()
{
//背景色设置
glClearColor(1.0f, 1.0f, 0.0f, 0.0f);//黄色的RGB 是 (1, 1, 0)
glClear(GL_COLOR_BUFFER_BIT);
glEnd();
glBegin(GL_POINTS);
glColor3f(1.0f, 1.0f, 0.0f);
glVertex2f(float(0) / 300.0f, float(0) / 200.f);//黄色背景上面放一个黄点
glEnd();


for (int i = 0; i <= 1000; i++)
ET[i].clear();

//圈1,初始化ET,将多边形各条边按照该边的y_min 存进ET表
ETlist_init(50, 50, 300, 60);
ETlist_init(50, 50, 200, 200);
ETlist_init(300, 60, 200, 200);
//圈2,初始化AET为空表
AET.clear();
//圈3,将now_y设置成ET中的最小y值。第一个非空ET表对应的y值
int now_y = mi_y;//now_y就是扫描线的y
do {
//步骤一,将ET[now_y]中所有节点都加入AET,之后清空ET[now_y],这里AET中要按x的大小排序
for (int i = 0, sz = ET[now_y].size(); i < sz; i++)//将ET[y]中所有节点都加入AET
{
AETnode tmp;
tmp.$1_k = ET[now_y][i].$1_k;
tmp.y_max = ET[now_y][i].y_max;
tmp.x = ET[now_y][i].x_min;//注意这里
AET.push_back(tmp);
}
ET[now_y].clear();//清空ET[now_y]
//按照x排序,从小到大
std::sort(AET.begin(), AET.end(), cmp);
//步骤二,对于一对交点,填充所需要的像素值
for (int i = 0, sz = AET.size(); i < sz; i += 2)//注意是+2
{
AETnode le, ri;
le = AET[i];
ri = AET[i + 1];
// le.x<=ri.x
for (float j = le.x; j < ri.x; j += 1)
{
//涂一个颜色为红色的点
glPointSize(1);
glBegin(GL_POINTS);
glColor3f(1.0f, 0.0f, 0.0f);
glVertex2f(float(j) / 300.0f, float(now_y) / 200.f);
glEnd();
}
}
//步骤三,now_y++,删除所有now_y>=y_max的点
now_y++;
for (auto it = AET.begin(); it != AET.end(); ) {
if (now_y>=(*it).y_max ) {
it = AET.erase(it);
if (it == AET.end()) break;
}
else {
it++;
}
}
//步骤四,更新AET中所有剩余节点的x值,用x + (&1_k)来代替 x .
for (int i = 0, sz = AET.size(); i < sz; i ++)
{
AET[i].x += AET[i].$1_k;
}
//步骤五,重新排序
std::sort(AET.begin(), AET.end(), cmp);


} while (!(AET.empty()&&ET[now_y].empty()));
glFlush();
}
int main(int argc, char* argv[])
{
mi_y = 10000000;//mi_y的初始化
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
glutInitWindowPosition(50, 50);// 窗口位置
glutInitWindowSize(600, 400); // 窗口大小
glutCreateWindow("多边形区域填充");// 设置标题

glutDisplayFunc(&myDisplay);

glutMainLoop();

return 0;
}