基础图形绘制-多边形

种子填充

给定一个多边形的顶点，圈出一个多边形，我们可以先用 Bresenham 直线算法 画上边界。

此时，若已知多边形内一个像素，我们可以轻易地从该像素出发，利用搜索（BFS、DFS等），将多边形完整填充，这就是 种子填充 算法。

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
static bool pixelMatrix[SCR_WIDTH][SCR_HEIGHT];
static int dx[] = { 0, 1, 0, -1 };
static int dy[] = { 1, 0, -1, 0 };

static void Bresenham(int x1, int y1, int x2, int y2)
{
	bool steep = abs(y2 - y1) > abs(x2 - x1);
	if (steep) Swap(x1, y1), Swap(x2, y2);
	if (x1 > x2) Swap(x1, x2), Swap(y1, y2);
	int dx = x2 - x1, dy = y2 - y1;

	int d = -dx;
	for (int i = 0, x = x1, y = y1; i <= dx; i++, count++)
	{
		vertices[count * 3] = !steep ? x : y;
		vertices[count * 3 + 1] = !steep ? y : x;

		x++;
		d += 2 * abs(dy);
		if (d > 0) y += (dy > 0 ? 1 : -1), d -= 2 * dx;
	}
}

static void SeedFilling()
{
	printf("Coordinates of seed:\n");
	static point seed;
	std::cin >> seed.x >> seed.y;
	std::queue <point> q;
	q.push(seed);

	memset(pixelMatrix, false, sizeof(pixelMatrix));

	for (int i = 0; i < inputCount; i++)
		Bresenham(inputVertex[i].x, inputVertex[i].y,
			inputVertex[(i + 1) % inputCount].x, inputVertex[(i + 1) % inputCount].y);

	for (int i = 0; i < count; i++)
	{
		point u = point((int)vertices[i * 3], (int)vertices[i * 3 + 1]);
		pixelMatrix[u.x][u.y] = true;
		Normalize(vertices[i * 3], vertices[i * 3 + 1]);
	}

	while (!q.empty())
	{
		point u = q.front();
		q.pop();

		vertices[count * 3] = (float)u.x, vertices[count * 3 + 1] = (float)u.y;
		Normalize(vertices[count * 3], vertices[count * 3 + 1]), count++;

		for (int i = 0; i < 4; i++)
		{
			point v = point(u.x + dx[i], u.y + dy[i]);
			if (0 <= v.x && v.x < SCR_WIDTH && 0 <= v.y && v.y < SCR_HEIGHT && !pixelMatrix[v.x][v.y])
			{
				pixelMatrix[v.x][v.y] = true;
				q.push(v);
			}
		}
	}
}

扫描线

顾名思义，我们用一条条线来扫描，一边扫描一边填充图形。

我们用 水平于 x 轴 的直线来扫描，从 y=0 开始，每次绘制在多边形内的线段，然后 y=y+1 。

image-20211018205445633

我们从下往上走，假设当前处理到 y=7 这条边，与这条边相交的有：P1P6P_1P_6、P5P6P_5P_6、P4P5P_4P_5、P3P4P_3P_4 这四条边。

按照交点 A、B、C、D 的 x 排序后，容易发现可以将其两两配对，画出线段 AB、CD。

于是，我们需要知道：1. X（与扫描线的交点的 x 值）；2. 有哪些边于扫描线相交。

  1. 考虑 X 如何计算：我们每次 y = y + 1，对于一条直线 y = kx + b，若 y += 1 则 x += 1/k 。于是我们需要记录 delX = 1/k（斜率的倒数），扫描线移动时 x += delX 即可；
  2. 怎么获得与扫描线相交的边：我们每次 y=y+1，显然当 y = 该边最小的 y 值 时加入，y = 该边最大的 y 值 时删除。那么我们可以开一个 SCR_HEIGHT 级别的 vectorE[SCR_HEIGHT] ，然后 E[该边最小的 y 值].push(该边)，每次 y=y+1 时，E[y] 中存储的边，就是需要新加入的边；同时当 maxY = y 时，将这条边删去。（当然，用链表处理也是可以的，任意选择一种可以处理的数据结构即可）

我们确定流程：1. 将边加入需要处理的集合；2. 按照 x 排序并两两匹配绘制线段；3. 删去该删的边。

现在我们来处理遇到多边形顶点时的问题。

  1. 如上图遇到 y=1，加入 P1P2P_1P_2、P2P3P_2P_3。绘制线段时：有P2、P2，发现并没有问题；
  2. 如上图遇到 y=2，加入 P1P6P_1P_6。绘制线段时：有P1、P1、E ，发现无法匹配
  3. 如上图遇到 y=3，加入 P3P4P_3P_4。绘制线段时：有(2,3)、P3、P3，发现无法匹配；
  4. 如上图遇到 y=5，加入 P5P6P_5P_6、P4P5P_4P_5。绘制线段时：有 (2,5)、P5、P5、(11,5)，发现并没有问题；
  5. 如上图遇到 y=7，不加入。绘制线段时：有 P6、P6、F、G，发现并没有问题。

于是发现，当我们 加入奇数条边 的时候，顶点匹配会出现问题。为了处理这种情况，我们将所有边的最大的 y 值 - 1，提早删除这条边。

虽然这样处理图形最上面的一条线会失去一行像素，但是看起来问题不是很大，我们可以单独判断一下。

最后，对于 水平于 x 轴 的边，我们直接绘制，然后跳过处理。

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
static struct edge
{
	float x, delX;
	int maxY;
	edge(float _x, float _delX, int _maxY) : x(_x), delX(_delX), maxY(_maxY) {}
	bool operator <(const edge& other) { return x < other.x; }
};

std::vector <edge> E[SCR_HEIGHT];
std::vector <edge> Set;

static void DrawLine(int x0, int x1, int y)
{
	for (int i = x0; i <= x1; i++)
	{
		vertices[count * 3] = i, vertices[count * 3 + 1] = y;
		Normalize(vertices[count * 3], vertices[count * 3 + 1]), count++;
	}
}

static void Sweep()
{
	int MinY = SCR_HEIGHT, MaxY = 0;
	for (int i = 0; i < inputCount; i++)
	{
		point u = point(inputVertex[i].x, inputVertex[i].y);
		point v = point(inputVertex[(i + 1) % inputCount].x, inputVertex[(i + 1) % inputCount].y);
		if (u.x > v.x) Swap(u, v);
		if (u.y > v.y) Swap(u, v);

		if (u.y == v.y)
		{
			DrawLine(u.x, v.x, u.y);
			continue;
		}
		E[u.y].push_back( edge(u.x, (float)(v.x - u.x) / (v.y - u.y), v.y - 1) );
		MinY = u.y < MinY ? u.y : MinY;
		MaxY = v.y > MaxY ? v.y : MaxY;
	}

	for (int y = MinY; y <= MaxY; y++)
	{
		for (auto edge : E[y]) Set.push_back(edge);
		E[y].clear();

		std::sort(Set.begin(), Set.end());

		for (int i = 0, size = Set.size(); i < size; i += 2)
			if (i + 1 < size)
				DrawLine(Set[i].x, Set[i + 1].x, y);

		for (int i = Set.size() - 1; i >= 0; i--)
			if (Set[i].maxY == y)
				Set.erase(Set.begin() + i);

		for (int i = 0, size = Set.size(); i < size; i++)
			Set[i].x += Set[i].delX;
	}
}

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
#define GLEW_STATIC
#include <GL/glew.h>
#include <GL/GL.h>
#include <GLFW/glfw3.h>

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#pragma region Setting

static GLFWwindow* window;
const unsigned int SCR_WIDTH = 800;
const unsigned int SCR_HEIGHT = 600;
const unsigned int MAX_COUNT = 800 * 600;

static void InitializeWindow()
{
	glfwInit();
	glfwWindowHint(GLFW_CONTEXT_VERSION_MAJOR, 3);
	glfwWindowHint(GLFW_CONTEXT_VERSION_MINOR, 3);
	glfwWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE);

	window = glfwCreateWindow(SCR_WIDTH, SCR_HEIGHT, "Test", NULL, NULL);
	glfwMakeContextCurrent(window);
	glfwSetFramebufferSizeCallback(window, [](GLFWwindow* window, int width, int height) { glViewport(0, 0, width, height); });


	glewExperimental = GL_TRUE;
	glewInit();

}

static void ProcessInput(GLFWwindow* window)
{
	if (glfwGetKey(window, GLFW_KEY_ESCAPE) == GLFW_PRESS)
		glfwSetWindowShouldClose(window, true);
}
#pragma endregion


#pragma region InitializeVertex

static struct point
{
	int x, y;
	point() : x(0), y(0) {}
	point(int _x, int _y) : x(_x), y(_y) {}
};
point inputVertex[MAX_COUNT];

static int inputCount;

static float vertices[MAX_COUNT * 3 * 2];
static unsigned int VAO, VBO;
static unsigned int count = 0;

static void Normalize(float& x, float& y)
{
	x = (x - (SCR_WIDTH / 2)) / (SCR_WIDTH / 2);
	y = (y - (SCR_HEIGHT / 2)) / (SCR_HEIGHT / 2);
}

template <typename T>
static void Swap(T& a, T& b) { T temp(a); a = b; b = temp; }

static void InputVertex()
{
	printf("Count of vertices: ");
	std::cin >> inputCount;
	printf("Coordinates of vertices:\n");

	for (int i = 0; i < inputCount; i++)
	{
		printf("ID[%d]: ", i);
		std::cin >> inputVertex[i].x >> inputVertex[i].y;
	}
}

/////////////////////////////////////////////////////////
// SeedFilling
static bool pixelMatrix[SCR_WIDTH][SCR_HEIGHT];
static int dx[] = { 0, 1, 0, -1 };
static int dy[] = { 1, 0, -1, 0 };

static void Bresenham(int x1, int y1, int x2, int y2)
{
	bool steep = abs(y2 - y1) > abs(x2 - x1);
	if (steep) Swap(x1, y1), Swap(x2, y2);
	if (x1 > x2) Swap(x1, x2), Swap(y1, y2);
	int dx = x2 - x1, dy = y2 - y1;

	int d = -dx;
	for (int i = 0, x = x1, y = y1; i <= dx; i++, count++)
	{
		vertices[count * 3] = !steep ? x : y;
		vertices[count * 3 + 1] = !steep ? y : x;

		x++;
		d += 2 * abs(dy);
		if (d > 0) y += (dy > 0 ? 1 : -1), d -= 2 * dx;
	}
}

static void SeedFilling()
{
	printf("Coordinates of seed:\n");
	static point seed;
	std::cin >> seed.x >> seed.y;
	std::queue <point> q;
	q.push(seed);

	memset(pixelMatrix, false, sizeof(pixelMatrix));

	for (int i = 0; i < inputCount; i++)
		Bresenham(inputVertex[i].x, inputVertex[i].y,
			inputVertex[(i + 1) % inputCount].x, inputVertex[(i + 1) % inputCount].y);

	for (int i = 0; i < count; i++)
	{
		point u = point((int)vertices[i * 3], (int)vertices[i * 3 + 1]);
		pixelMatrix[u.x][u.y] = true;
		Normalize(vertices[i * 3], vertices[i * 3 + 1]);
	}

	while (!q.empty())
	{
		point u = q.front();
		q.pop();

		vertices[count * 3] = (float)u.x, vertices[count * 3 + 1] = (float)u.y;
		Normalize(vertices[count * 3], vertices[count * 3 + 1]), count++;

		for (int i = 0; i < 4; i++)
		{
			point v = point(u.x + dx[i], u.y + dy[i]);
			if (0 <= v.x && v.x < SCR_WIDTH && 0 <= v.y && v.y < SCR_HEIGHT && !pixelMatrix[v.x][v.y])
			{
				pixelMatrix[v.x][v.y] = true;
				q.push(v);
			}
		}
	}
}

/////////////////////////////////////////////////////////
// Sweep

static struct edge
{
	float x, delX;
	int maxY;
	edge(float _x, float _delX, int _maxY) : x(_x), delX(_delX), maxY(_maxY) {}
	bool operator <(const edge& other) { return x < other.x; }
};

std::vector <edge> E[SCR_HEIGHT];
std::vector <edge> Set;

static void DrawLine(int x0, int x1, int y)
{
	for (int i = x0; i <= x1; i++)
	{
		vertices[count * 3] = i, vertices[count * 3 + 1] = y;
		Normalize(vertices[count * 3], vertices[count * 3 + 1]), count++;
	}
}

static void Sweep()
{
	int MinY = SCR_HEIGHT, MaxY = 0;
	for (int i = 0; i < inputCount; i++)
	{
		point u = point(inputVertex[i].x, inputVertex[i].y);
		point v = point(inputVertex[(i + 1) % inputCount].x, inputVertex[(i + 1) % inputCount].y);
		if (u.x > v.x) Swap(u, v);
		if (u.y > v.y) Swap(u, v);

		if (u.y == v.y)
		{
			DrawLine(u.x, v.x, u.y);
			continue;
		}
		E[u.y].push_back( edge(u.x, (float)(v.x - u.x) / (v.y - u.y), v.y - 1) );
		MinY = u.y < MinY ? u.y : MinY;
		MaxY = v.y > MaxY ? v.y : MaxY;
	}

	for (int y = MinY; y <= MaxY; y++)
	{
		for (auto edge : E[y]) Set.push_back(edge);
		E[y].clear();

		std::sort(Set.begin(), Set.end());

		for (int i = 0, size = Set.size(); i < size; i += 2)
			if (i + 1 < size)
				DrawLine(Set[i].x, Set[i + 1].x, y);

		for (int i = Set.size() - 1; i >= 0; i--)
			if (Set[i].maxY == y)
				Set.erase(Set.begin() + i);

		for (int i = 0, size = Set.size(); i < size; i++)
			Set[i].x += Set[i].delX;
	}
}


static void InitializeVertex()
{
	// Generate
	glGenVertexArrays(1, &VAO);
	glGenBuffers(1, &VBO);

	// Bind
	glBindVertexArray(VAO);
	glBindBuffer(GL_ARRAY_BUFFER, VBO);

	glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

	glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float), (void*)0);
	glEnableVertexAttribArray(0);
}

#pragma endregion


void Render()
{
	glClearColor(0.5, 0.5, 0.5, 1);
	glClear(GL_COLOR_BUFFER_BIT);

	glBindVertexArray(VAO);
	glDrawArrays(GL_POINTS, 0, count);
}

int main()
{
	InputVertex();
	InitializeWindow();

	//SeedFilling();
	Sweep();

	InitializeVertex();

	while (!glfwWindowShouldClose(window))
	{
		ProcessInput(window);

		Render();

		glfwSwapBuffers(window);
		glfwPollEvents();
	}

	glfwTerminate();
	return 0;
}