【图形学】探秘图形学奥秘：区域填充的解密与实战

SarPro

发布于 2024-02-20 18:34:21

1440

发布于 2024-02-20 18:34:21

文章被收录于专栏：【计网】Cisco

🌌1. 初识模式识别

图形学技术是一门涉及计算机图形和图像处理的学科，其目标是通过算法和数学模型来创建、处理和呈现图形和图像。这项技术的应用范围非常广泛，涵盖了许多领域，包括计算机游戏、虚拟现实、计算机辅助设计（CAD）、医学图像处理、动画制作等。以下是图形学技术的一些关键方面：

图形生成和渲染： 图形学技术用于生成和呈现视觉图像。这包括三维图形的创建、光照、阴影、颜色和纹理等方面的处理，以产生逼真的图形。
计算机辅助设计（CAD）： 在工程学和设计领域，图形学技术被广泛用于创建和编辑数字化的设计图纸，促进设计过程的可视化和交互。
计算机游戏和虚拟现实： 图形学技术是游戏开发和虚拟现实领域的核心。它用于创建游戏中的角色、场景、特效以及虚拟现实环境，提供沉浸式的视觉体验。
医学图像处理： 在医学领域，图形学技术被用于处理和呈现医学图像，如CT扫描、MRI等，以协助医生进行诊断和手术规划。
动画制作： 图形学技术是制作动画的关键。通过在计算机上生成图形帧并进行渲染，动画制作得以实现。
图像处理： 图形学技术也包括对静态图像的处理，如图像编辑、滤镜应用、图像合成等。

在图形学技术的发展中，硬件加速、实时渲染、虚拟现实和增强现实等方面的创新不断推动着图形学的前沿。这门技术为数字世界的可视化和交互提供了强大的工具和方法。

🌌2. 区域填充

🌍2.1 开发环境及实现

语言: C++
平台: Microsoft Visual Studio 2022

🌍2.2 实验目的

掌握图形填充的基本技能；
理解区域填充算法，重点掌握扫描线填色算法。

🌍2.3 实验要求

使学生用Microsoft Visual Studio 2022编程；
掌握扫描线填色算法（要求yaoqiu 要求构造几何图形并填充）。

🌍2.4 实验原理

区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色，本节中我们就以此为例讨论区域填充算法。

填色算法分为两大类：

扫描线填色（Scan-Line Filling）算法。这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。
种子填色（Seed Filling）算法。这类算法建立在多边形边边界的图象形式数据之上，并还需提供多边形界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。

扫描线填色算法的基本思想是：用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。

🌍2.5 实验步骤

新建工程，绘制几何图形，同时进行扫描线添色。

🌕2.5.1 扫描线填色算法

#define NDEBUG
#ifndef GLUT_DISABLE_ATEXIT_HACK
#define GLUT_DISABLE_ATEXIT_HACK
#endif
#include <windows.h>
#include <gl/glut.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <list>

using namespace std;

void setPixel(int xCoord, int yCoord) {
	glBegin(GL_POINTS); {
		glVertex2i(xCoord, yCoord);
	}
	glEnd();
}

//点类
struct Point {
	int x, y;
	Point() :x(0), y(0) {}
	Point(int nx, int ny) :x(nx), y(ny) {}
};

//边类
struct Edge {
	float x;
	float dx;
	int yMax;
	Edge() :x(0), dx(0), yMax(0) {}
	Edge(float nx, float ndx, int nyMax) :x(nx), dx(ndx), yMax(nyMax) {}

};

bool cmp_x(Point p1, Point p2) {
	return p1.x < p2.x;
}
bool cmp_y(Point p1, Point p2) {
	return p1.y < p2.y;
}

void boundaryFill(vector <Point> pointList) {
	int pointNum = pointList.size();

	vector<Point> pointListCopy(pointList);
	sort(pointListCopy.begin(), pointListCopy.end(), cmp_y);
	int yMin = pointListCopy.at(0).y;
	int yMax = pointListCopy.at(pointNum - 1).y;

	//初始化边表ET & 活动边表AET
	list<Edge> ET[500];
	list<Edge> AET;
	AET.push_back(Edge());

	//建立边表ET
	for (int i = 0; i < pointNum; ++i) {
		int x0 = pointList.at(i).x;
		int y0 = pointList.at(i).y;
		int x1 = pointList.at((i + 1) % pointNum).x;
		int y1 = pointList.at((i + 1) % pointNum).y;

		if (y0 == y1) {
			continue;
		}
		int yMinNow = min(y0, y1);
		int yMaxNow = max(y0, y1);
		float x = y0 < y1 ? x0 : x1;
		float dx = (x0 - x1) * 1.0 / (y0 - y1);

		ET[yMinNow].push_back(Edge(x, dx, yMaxNow));
	}

	for (int i = yMin; i < yMax; ++i) {
		for (auto j = ET[i].begin(); j != ET[i].end();) {
			auto pAET = AET.begin();
			auto end = AET.end();
			for (; pAET != end; ++pAET) {
				if (pAET->x > j->x) {
					break;
				}
				if (j->x == pAET->x && j->dx < pAET->dx) {
					break;
				}
			}
			AET.insert(pAET, *j);
			j = ET[i].erase(j);
		}

		for (auto temp = AET.begin(); temp != AET.end();) {
			if (temp->yMax == i) {
				temp = AET.erase(temp);
			}
			else {
				temp++;
			}
		}
		auto pAET = AET.begin();
		pAET++;	
		auto pAET_next = pAET;
		pAET_next++;
		int count = AET.size() - 1;
		while (count >= 2) {
			for (int x = pAET->x; x < pAET_next->x; ++x) {
				setPixel(x, i);
			}
			pAET++;
			pAET++;
			pAET_next = pAET;
			count -= 2;
		}
		for (auto& temp : AET) {
			temp.x += temp.dx;
		}
	}
	return;
}
//绘制程序
void display() {
	vector <Point> pointList1;
	pointList1.push_back(Point(100, 100));
	pointList1.push_back(Point(300, 100));
	pointList1.push_back(Point(100, 500));
	pointList1.push_back(Point(300, 500));
	pointList1.push_back(Point(50, 350));
	pointList1.push_back(Point(350, 350));
	vector <Point> pointList2;
	pointList2.push_back(Point(100, 300));
	pointList2.push_back(Point(280, 285));
	pointList2.push_back(Point(280, 170));
	pointList2.push_back(Point(340, 100));
	pointList2.push_back(Point(340, 340));
	pointList2.push_back(Point(100, 340));
	glClear(GL_COLOR_BUFFER_BIT);
	glColor3f(0.0, 1.0, 1.0);
	boundaryFill(pointList1);
	boundaryFill(pointList2);
	glutSwapBuffers();
	return;
}
void init() {
	glClearColor(1.0, 0.8, 1.0, 1.0);
	glColor3f(0.0, 0.5, 0.5);
	glPointSize(1.0);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluOrtho2D(0.0, 1000.0, 0.0, 1000.0);
}
int main(int argc, char** argv) {
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
	glutInitWindowPosition(250, 250);
	glutInitWindowSize(600, 500);
	glutCreateWindow("GLUT_Project_1");
	init();
	glutDisplayFunc(display);
	glutMainLoop();

	return 0;
}

运行结果：

🌕2.5.2 动态烟花算法

#include <easyx.h>
#include <cmath>
#include <ctime>
#include <list>


long ret_useless = 0;				
const int GW = 640;				
const int GH = 480;				
const double g = 9.8;				
const double PI = 3.1415926;
const int len_max = 80;			
const int h_max = GH - len_max;		
const double v_max = sqrt(2 * g * h_max / 10);
//除以10的缘故是公式是用m做单位,1m代表10个像素点
const int n_max = 5;				// Maximum number of fireworks on the screen烟花在屏幕上同时存在最多的数量


/* *************** LightLine *************** */
class LightLine
{
public:
	LightLine(int, double);
	void Draw() const;
	void Move();
	bool Stopped() const { return v == 0; }
	bool OverLine() const { return py < h_max* n_max / (n_max + 1); }	
	int GetX() const { return px; }
	int GetY() const { return py; }

private:
	int px;				// Position_x
	int py;				// Position_y
	int len;			// Length
	double v;			// Velocity (The -y axis is positiva)速度(Y轴是正的)
	clock_t ct = 0;		
};
LightLine::LightLine(int x = rand() % (GW - 80) + 40, double vv = (rand() % 20 + 80.0) / 100 * v_max) :px(x), py(h_max)
{
	v = vv;								//初始速度决定了可以达到的高度
	len = int(v / v_max * len_max);		// v : v_max = len : len_max速度快的，尾影会拖得长一些
}
void LightLine::Draw() const
{
	srand((unsigned)(time)(NULL));
	int Light_color = rand() % 360;
	//绘制上升曲线，是一列圆的绘制，第一个圆形亮度最高，后面的亮度逐渐减少，达到渐变的效果
	for (int j = py; j < py + len; ++j)
	{
		float hsv_v = 0.8f * (len - (j - py)) / len + 0.2f;		// Gradient color这是亮度
		setfillcolor(HSVtoRGB(float(Light_color), 1.0f, hsv_v));
		solidcircle(px, j, 1);
	}
}
void LightLine::Move()
{
	if (v == 0)
		return;
	if (ct == 0)
	{
		ct = clock();
		Draw();
		return;
	}
	clock_t t = clock() - ct;
	ct = clock();
	double v_cur = v - g * t / 1000.0;
	//除以1000的原因是，公式是以s做单位，程序里是ms作为单位，1s=1000ms
	if (v_cur > 0)
	{
		py += int(10 * (v_cur * v_cur - v * v) / 2 / g);//上升运动高度  vt^2-v0=2gh
		v = v_cur;
	}
	else
	{
		//如果v_cur<0，则表示可以到顶点了。
		py -= int(10 * v * v / 2 / g);//自由落体的高度 0-vt^2=2gh
		v = 0;//因为顶点烟花爆炸
	}
	len = int(v / v_max * len_max);
	Draw();
}


/* *************** ParticleSwarm *************** */
class ParticleSwarm
{
	struct Particle
	{
		int x;			//表示粒子的运动过程的x坐标
		int y;			//表示粒子的运动过程的y坐标
		int z = 0;		// Z axis vertical screen inword Z轴垂直屏幕输入
		double vy;		//  The y axis is positiva for the velocity结构体里面的vy是每个粒子的y方向速度
		Particle(int xx, int yy, double vv) :x(xx), y(yy), vy(vv) {}
	};
public:
	ParticleSwarm(int, int, float);
	void Draw() const;
	void Move();
	bool Finish() const { return vec.size() <= 1; }

private:
	double vx;
	double vz = 0;
	float hsv_h;					// Color parameter
	clock_t ct = 0;
	std::list<Particle> vec;		// For saving particles
};
ParticleSwarm::ParticleSwarm(int x, int y, float colorh = float(rand() % 256))
{
	hsv_h = colorh + rand() % 20;
	hsv_h = hsv_h > 255 ? hsv_h - 256 : hsv_h;

	//Z轴的负向对着人，即人对着屏幕的方向为Z轴的正向
	double vm = v_max / 2 * (rand() % 5 + 15.0) / 25.0;
	double radian_xz = (rand() % 360) * PI / 180;//X轴偏向Z轴的角度0--2*PI
	double radian_xy = (rand() % 90) * PI / 180 + PI / 2;//X轴偏向Y轴的角度PI/2--PI
	vx = vm * cos(radian_xy) * cos(radian_xz);//向量在X轴的投影
	vz = vm * cos(radian_xy) * sin(radian_xz);//向量在Z轴的投影
	double vy = vm * sin(radian_xy); //向量在Y轴的投影

	//len表示粒子运动轨迹的长度，也可以认为是装填粒子的数量
	int len = rand() % 30 + 50;//rand() % 30 + 50这个是源代码的数值，数值越大，烟花爆炸的范围，散开的范围就越大。
	//这一段刻画的是爆炸花束粒子中的其中一条线
	while (len)
	{
		// Use len as time parameter
		//目标像素位置＝初始像素位置+偏移米×10
		int xx = x + int(10 * vx * len / 200.0);
		//int zz = int(10 * vz * len / 200.0);
		double cvy = vy - g * len / 200.0;
		int yy = y + int(10 * (cvy * cvy - vy * vy) / 2 / g);
		vec.push_back(Particle(xx, yy, cvy));
		--len;
	}
}
void ParticleSwarm::Draw() const
{
	int n = 0;
	auto size = vec.size();
	for (auto& x : vec)
	{
		if (x.x >= 0 && x.x < GW && x.y >= 0 && x.y < GH)
		{
			//烟花线条的尾端亮度最低，反之首端是比较亮的
			float cv = 0.2f + 0.8f * (size - n) / size - x.z; //原来的float cv = 0.2f + 0.8f * (size - n) / size - x.z / 40 * 0.1f
			auto color = HSVtoRGB(hsv_h, 1.0f, cv > 0 ? cv : 0);
			if (x.z < 0)		// Z axis vertical screen inword如果烟花是往屏幕外扩散的话，就把像素点变大
			{
				setfillcolor(color);
				solidcircle(x.x, x.y, abs(x.z) / 80 > 1 ? 2 : 1);
			}
			else
				putpixel(x.x, x.y, color);
		}
		++n;
	}
}
void ParticleSwarm::Move()
{
	if (ct == 0)
	{
		ct = clock();
		Draw();
		return;
	}
	for (int i = 0; i < 3 && vec.size() > 1; i++)//
		vec.pop_back();		// Delete particles for shortening length画面每次刷新删除3个末尾粒子
	clock_t t = clock() - ct;
	ct = clock();
	for (auto& x : vec)//爆炸花束之中一条光纤的粒子持续运动
	{
		double vy_cur = x.vy - g * t / 1000.0;
		x.x += int(10 * vx * t / 1000.0);
		x.y += int(10 * (vy_cur * vy_cur - x.vy * x.vy) / 2 / g);
		x.z += int(10 * vz * t / 1000.0);
		x.vy = vy_cur;
	}
	Draw();
}


/* *************** Fireworks *************** */
class Fireworks
{
public:
	Fireworks(int, int);
	void Move();
	bool Empty() const { return vec.empty(); }

private:
	std::list<ParticleSwarm> vec;
};
Fireworks::Fireworks(int x, int y)
{
	bool colorful = rand() % 100 < 20 ? true : false;//1/5的几率判断
	float h = float(rand() % 256);
	int n = rand() % 5 + 45;//烟花升到顶点后，爆炸出来的光线量
	for (int i = 0; i < n; i++)
	{
		if (colorful)//决定烟花的爆炸光线，每一条是否是同一颜色的。1/5的几率判断
			vec.push_back(ParticleSwarm(x, y));
		else
			vec.push_back(ParticleSwarm(x, y, h));
	}
}
void Fireworks::Move()
{
	std::list<decltype(vec.begin())> toDel;
	for (auto it = vec.begin(); it != vec.end(); ++it)
	{
		if (it->Finish())//如果该粒子群里的粒子数只剩下一个，则跳过
		{
			toDel.push_back(it);
			continue;
		}
		it->Move();//如果粒子群里的粒子数不只是剩下一个，则继续描画它的轨迹
	}
	for (auto& x : toDel)
		vec.erase(x);
}


/* *************** main *************** */
int main()
{
	initgraph(GW, GH);
	setrop2(R2_MERGEPEN);
	srand((unsigned)time(nullptr));

	// Refresh once in 50ms
	clock_t ct = clock();
	// LightLine list
	std::list<LightLine> vec;
	vec.push_back(LightLine());
	// Fireworks list
	std::list<Fireworks> vec2;

	BeginBatchDraw();
	while (!(GetAsyncKeyState(VK_ESCAPE) & 0x8000))
	{
		if (clock() - ct > 50)
		{
			cleardevice();
			ct = clock();

			std::list<decltype(vec.begin())> toDel;
			if (vec.size() == 0)
				vec.push_back(LightLine());
			else if (vec.size() < n_max && rand() % 100 < 20 && (--vec.end())->OverLine())
				vec.push_back(LightLine());
			for (auto it = vec.begin(); it != vec.end(); ++it)
			{
				if (it->Stopped())
				{
					vec2.push_back(Fireworks(it->GetX(), it->GetY()));
					toDel.push_back(it);
					continue;
				}
				it->Move();
			}
			for (auto& it : toDel)
				vec.erase(it);
			std::list<decltype(vec2.begin())> toDel2;
			for (auto it = vec2.begin(); it != vec2.end(); ++it)
			{
				if (it->Empty())
				{
					toDel2.push_back(it);
					continue;
				}
				it->Move();
			}
			for (auto& it : toDel2)
				vec2.erase(it);

			FlushBatchDraw();
		}
		Sleep(1);
	}
	EndBatchDraw();

	closegraph();
	return 0;
}

运行结果：

🌍2.6 研究体会

图形填充技能的掌握：通过本次实验，我成功掌握了图形填充的基本技能，了解了区域填充算法，并重点掌握了扫描线填色算法。在使用Visual Studio 2022开发平台编程的过程中，我能够在自己构造的几何区域进行填充操作。这为我在图形学领域的实际应用提供了坚实的基础。
烟花程序的实现：这次实验不仅帮助我完成了图形填充技能的学习，还让我圆了大一时候的烟花程序的愿望。之前由于使用dev-c++平台，无法成功搭建环境，但这次在Visual Studio 2022中成功搭建了相应的环境，并尝试实现了烟花爆炸的程序。这使我对C++的制图能力更加自信，也为我在图形学领域的兴趣提供了更多的可能性。
学习过程中的挑战和成长：在实验过程中，我花费了较多的时间在控制图像生成方面，包括输出面板的底色、图像初始位置的控制以及输出框的大小控制。由于之前使用的是dev-c++平台，初次使用Visual Studio 2022并不是很顺手，因此我不得不花费一些时间在网络上自学。最终，通过付出的努力，我成功解决了这些挑战，看到最终的运行结果，我感到付出的努力得到了回报。这次学习也让我更加注重虚心学习，静心思考，相信这样的态度将在以后的学习和工作中带来更多的成长。