1. Toy模板网首页
  2. > Toy博客

【计算机图形学 】扫描线多边形填充算法 | OpenGL+鼠标交互

10月前 作者：Timer95 分类：Toy博客 阅读(77) 违法举报

这篇具有很好参考价值的文章主要介绍了【计算机图形学 】扫描线多边形填充算法 | OpenGL+鼠标交互。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

其他计算机图形学实验

传送门

前言

实现多边形扫描线填充算法，并和鼠标进行交互。
具体原理略过，会贴上完整代码，可直接运行。

环境：
vs2019,OpenGL的库（可以搜索如何用vs使用OpenGL的库，可以使用vs自带的插件或者其他方法，很方便）

要点：
1.NET和AET的创建，改动
2.改变鼠标点击和鼠标拖拽的响应事件。

最终效果：
用鼠标随意画顶点，然后展示填充过程
对应控制台会输出顶点坐标和个数
【计算机图形学 】扫描线多边形填充算法 | OpenGL+鼠标交互

思路借鉴

文章1
文章2

步骤

1.点的结构体

struct point
{
	float x, y;
	point(){}
	point(int xx, int yy):
		x(xx), y(yy) {}
};
vector<point> vertice; //顶点

2. AET 活性边表、NET新边表 的结构体

typedef struct XET
{
	float x;
	float dx;  // 从当前扫描线到下一条扫描线间x的增量，即斜率的倒数
	float ymax; //该边所交的最高扫描线的坐标值ymax
	XET* next;
}AET, NET; //AET 活性边表； NET新边表

3. 扫描线算法实现

void PolyScan()
{
	/*得到最高点的y坐标*/
	int Max_Y = 0;
	for (int i = 0; i < vertice.size(); i++) 
		/*Max_Y = max(Max_Y, vertice[i].y);*/
		if (vertice[i].y > Max_Y)
			Max_Y = vertice[i].y;


	//初始化AET表
	AET* pAET = new AET;
	pAET->next = NULL;

	//初始化NET表
	NET* pNET[800]; //吊桶
	for (int i = 0; i <= Max_Y; i++)
	{
		pNET[i] = new NET;
		pNET[i]->next = NULL;;
	}

	//扫描并且建立NET表
	int len = vertice.size(); //顶点个数
	for (int i = 0; i <= Max_Y; i++)
	{
		for (int j = 0; j < len; j++) //扫描每个点
		{
			if (i == vertice[j].y)
			{
				//如果一个点和前一个点有一条边相连，则该点和后面一个点也相连
				//！这个式子 便于最后一个顶点和第一个点相连 和 防止出现负数
				
				//判断当前点的高低，使ymax、DX、DY的计算有变化
				if (vertice[(j - 1 + len) % len].y > vertice[j].y)
				{
					//前一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j - 1 + len) % len].y;//与当前扫描线相交的活性边 的 最高点即为相邻顶点的y
					float DX = vertice[(j - 1 + len) % len].x - vertice[j].x;
					float DY = vertice[(j - 1 + len) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
				if (vertice[(j + 1) % len].y > vertice[j].y)
				{
					//后一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j + 1) % len].y;
					float DX = vertice[(j + 1) % len].x - vertice[j].x;
					float DY = vertice[(j + 1) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
			}
		}
	}

	//建立并且更新活性边表AET
	//各条扫描线i
	for (int i = 0; i <= Max_Y; i++)
	{
		/*把新边表NET[i] 中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列*/
		
		//计算每条扫描线上不同线产生的新的交点x，更新AET
		NET* p = pAET->next;
		while (p)
		{
			p->x = p->x + p->dx; //更新x坐标
			p = p->next;
		}

		//断表排序,不再开辟空间 
		AET* tq = pAET;
		p = pAET->next;
		tq->next = NULL;
		while (p)//顺着链表往下走
		{
			//找到第一个比它大的数字tq->next->next->x，则从p->next到tq->next都是比p->x小的
			while (tq->next != NULL && tq->next->x <= p->x)
				tq = tq->next;
			//插入p到tq和tq->next之间
			NET* t = p->next;
			p->next = tq->next;
			tq->next = p;
			p = t;

			tq = pAET;//回到头
		}

		/*(改进算法) 取消求交，减少计算量*/
		//先从AET表中删除ymax==i的结点****************************************/
		//像素的取舍问题，保证多边形的“下闭上开”，避免填充扩大化（交点的个数应保证为偶数个）
		AET* q = pAET;
		p = q->next;
		while (p)
		{
			if (p->ymax == i)
			{
				q->next = p->next;
				delete p;
				p = q->next;
			}
			else
			{
				q = q->next;
				p = q->next;
			}
		}

		//若NET中有新点，将其用插入法插入AET，按x递增的顺序排列
		p = pNET[i]->next;
		q = pAET;
		while (p)
		{
			while (q->next && p->x >= q->next->x)
				q = q->next;
			//插入p
			NET* t = p->next;
			p->next = q->next;
			q->next = p;
			p = t;

			q = pAET;//回到头
		}

		//配对后填充颜色
		p = pAET->next;
		while (p && p->next != NULL)
		{
			for (float j = p->x; j <= p->next->x; j++)
			{
				//扫描线画点
				draw_a_point(j, i);
				//cout << "(" << j << ", " << i << ")" << endl;
			}
			p = p->next->next;//考虑端点情况
		}
	}
	glFlush();
}

4. 改变鼠标响应函数

void mymouse(int button, int state, int x, int y)
{
	//左键
	if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
	{
		draw_a_point(x, window_height - y);

		point p(x, window_height - y);
		vertice.push_back(p);
		cout << "顶点" << vertice.size() << ": (" << x << ", " << window_height - y << ")" << endl;
	}
	//右键
	if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
	{
		glClearColor(1, 1, 1, 1);//设置绘制窗口颜色为白色
		glColor3f(0, 1, 1);

		//绘制多边形
		glBegin(GL_LINES);	
		for (int i = 0; i < vertice.size(); i++)
		{
			if (i == vertice.size() - 1)//画完最后一个点，使其闭合
			{
				glVertex2f(vertice[0].x, vertice[0].y);
				glVertex2f(vertice[i].x, vertice[i].y);
			}
			else
			{
				glVertex2f(vertice[i].x, vertice[i].y);
				glVertex2f(vertice[i + 1].x, vertice[i + 1].y);
			}
		}
		glEnd();
		glFlush();
	}

	//鼠标中间
	if (button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN)
	{
		//cout << "center: (" << x << ", " << y << ")" << endl;
		//BoundaryFill4(x, window_height - y);
		//BoundaryFill4_Stack(x, window_height - y);

		cout << "多边形顶点个数为" << vertice.size() << "。 " << "开始扫描线填充。" << endl;
		PolyScan();
	}
}

完整代码

//扫描线算法
#include<iostream>
#include<gl/glut.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int window_width = 800, window_height = 600;
const int maxn = 99999;

struct point
{
	float x, y;
	point(){}
	point(int xx, int yy):
		x(xx), y(yy) {}
};
vector<point> vertice; //顶点

typedef struct XET
{
	float x;
	float dx;  // 从当前扫描线到下一条扫描线间x的增量，即斜率的倒数
	float ymax; //该边所交的最高扫描线的坐标值ymax
	XET* next;
}AET, NET; //AET 活性边表； NET新边表

void draw_a_point(int x, int y);
void PolyScan();
void mymouse(int button, int state, int x, int y);
void display();


int main(int argc, char* argv[])
{
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
	glutInitWindowPosition(100, 50);
	glutInitWindowSize(window_width, window_height);
	glutCreateWindow("扫描线填充");

	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluOrtho2D(0, window_width, 0, window_height);

	glClearColor(1, 1, 1, 1);
	glClear(GL_COLOR_BUFFER_BIT);

	glutMouseFunc(&mymouse);
	glutDisplayFunc(&display);

	glutMainLoop();
	return 0;
}

//画点函数
void draw_a_point(int x, int y)
{
	glBegin(GL_POINTS);
	glColor3f(0, 1, 1);
	glVertex2f(x, y);
	glEnd();
	glFlush();
}

void PolyScan()
{
	/*得到最高点的y坐标*/
	int Max_Y = 0;
	for (int i = 0; i < vertice.size(); i++) 
		/*Max_Y = max(Max_Y, vertice[i].y);*/
		if (vertice[i].y > Max_Y)
			Max_Y = vertice[i].y;


	//初始化AET表
	AET* pAET = new AET;
	pAET->next = NULL;

	//初始化NET表
	NET* pNET[800]; //吊桶
	for (int i = 0; i <= Max_Y; i++)
	{
		pNET[i] = new NET;
		pNET[i]->next = NULL;;
	}

	//扫描并且建立NET表
	int len = vertice.size(); //顶点个数
	for (int i = 0; i <= Max_Y; i++)
	{
		for (int j = 0; j < len; j++) //扫描每个点
		{
			if (i == vertice[j].y)
			{
				//如果一个点和前一个点有一条边相连，则该点和后面一个点也相连
				//！这个式子 便于最后一个顶点和第一个点相连 和 防止出现负数
				
				//判断当前点的高低，使ymax、DX、DY的计算有变化
				if (vertice[(j - 1 + len) % len].y > vertice[j].y)
				{
					//前一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j - 1 + len) % len].y;//与当前扫描线相交的活性边 的 最高点即为相邻顶点的y
					float DX = vertice[(j - 1 + len) % len].x - vertice[j].x;
					float DY = vertice[(j - 1 + len) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
				if (vertice[(j + 1) % len].y > vertice[j].y)
				{
					//后一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j + 1) % len].y;
					float DX = vertice[(j + 1) % len].x - vertice[j].x;
					float DY = vertice[(j + 1) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
			}
		}
	}

	//建立并且更新活性边表AET
	//各条扫描线i
	for (int i = 0; i <= Max_Y; i++)
	{
		/*把新边表NET[i] 中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列*/
		
		//计算每条扫描线上不同线产生的新的交点x，更新AET
		NET* p = pAET->next;
		while (p)
		{
			p->x = p->x + p->dx; //更新x坐标
			p = p->next;
		}

		//断表排序,不再开辟空间 
		AET* tq = pAET;
		p = pAET->next;
		tq->next = NULL;
		while (p)//顺着链表往下走
		{
			//找到第一个比它大的数字tq->next->next->x，则从p->next到tq->next都是比p->x小的
			while (tq->next != NULL && tq->next->x <= p->x)
				tq = tq->next;
			//插入p到tq和tq->next之间
			NET* t = p->next;
			p->next = tq->next;
			tq->next = p;
			p = t;

			tq = pAET;//回到头
		}

		/*(改进算法) 取消求交，减少计算量*/
		//先从AET表中删除ymax==i的结点****************************************/
		//像素的取舍问题，保证多边形的“下闭上开”，避免填充扩大化（交点的个数应保证为偶数个）
		AET* q = pAET;
		p = q->next;
		while (p)
		{
			if (p->ymax == i)
			{
				q->next = p->next;
				delete p;
				p = q->next;
			}
			else
			{
				q = q->next;
				p = q->next;
			}
		}

		//若NET中有新点，将其用插入法插入AET，按x递增的顺序排列
		p = pNET[i]->next;
		q = pAET;
		while (p)
		{
			while (q->next && p->x >= q->next->x)
				q = q->next;
			//插入p
			NET* t = p->next;
			p->next = q->next;
			q->next = p;
			p = t;

			q = pAET;//回到头
		}

		//配对后填充颜色
		p = pAET->next;
		while (p && p->next != NULL)
		{
			for (float j = p->x; j <= p->next->x; j++)
			{
				//扫描线画点
				draw_a_point(j, i);
				//cout << "(" << j << ", " << i << ")" << endl;
			}
			p = p->next->next;//考虑端点情况
		}
	}
	glFlush();
}
void mymouse(int button, int state, int x, int y)
{
	//左键
	if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
	{
		draw_a_point(x, window_height - y);

		point p(x, window_height - y);
		vertice.push_back(p);
		cout << "顶点" << vertice.size() << ": (" << x << ", " << window_height - y << ")" << endl;
	}
	//右键
	if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
	{
		glClearColor(1, 1, 1, 1);//设置绘制窗口颜色为白色
		glColor3f(0, 1, 1);

		//绘制多边形
		glBegin(GL_LINES);	
		for (int i = 0; i < vertice.size(); i++)
		{
			if (i == vertice.size() - 1)//画完最后一个点，使其闭合
			{
				glVertex2f(vertice[0].x, vertice[0].y);
				glVertex2f(vertice[i].x, vertice[i].y);
			}
			else
			{
				glVertex2f(vertice[i].x, vertice[i].y);
				glVertex2f(vertice[i + 1].x, vertice[i + 1].y);
			}
		}
		glEnd();
		glFlush();
	}

	//鼠标中间
	if (button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN)
	{
		//cout << "center: (" << x << ", " << y << ")" << endl;
		//BoundaryFill4(x, window_height - y);
		//BoundaryFill4_Stack(x, window_height - y);

		cout << "多边形顶点个数为" << vertice.size() << "。 " << "开始扫描线填充。" << endl;
		PolyScan();
	}
}
void display()
{
	glClear(GL_COLOR_BUFFER_BIT);
	glColor3f(0.0, 0.4, 0.2);
	glPointSize(1);
	glBegin(GL_POINTS);
	PolyScan();
	glEnd();
	glFlush();
}

总结

扫描线算法部分，建立NET 和 建立并且更新活性边表AET 这两个地方比较复杂，可以带入图中多想文章来源地址https://www.toymoban.com/news/detail-400768.html

到了这里，关于【计算机图形学 】扫描线多边形填充算法 | OpenGL+鼠标交互的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【学习笔记】扫描线

    扫描线可以用来求解周长并和面积并。 给定 (n) 个长方形，求它们的面积并。下面以两个长方形为例： 对于这个问题，可以有容斥等做法，但是还有个更简单的方法——扫描线。 扫描线，顾名思义，就是，拿一条“线”取扫（这里是从下往上扫，其实其它的扫的方式也是可

    2024年02月15日
    浏览(40)
  • 计算机图形学 第4章 多边形填充

    计算机图形学 第4章 多边形填充

    了解扫描转换的基本概念。 熟练掌握多边形有效边表填充算法。 掌握多边形边缘填充算法。 熟练掌握区域四邻接点和八邻接点区域填充算法。 掌握区域扫描线种子填充算法。 无论使用哪种着色模式，都意味着要使用指定颜色为多边形 边界内 的每一个像素着色。 多边形的

    2024年02月02日
    浏览(54)
  • 【单调队列】 单调队列的“扫描线”理解

    【单调队列】 单调队列的“扫描线”理解

       “如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理 比你强，而且比你影响时间更长。 某种意义上，数学思维是生活中的思考的延伸。   算法学习笔记(66): 单调队列。引用 Pecco 的算法笔记。   在这里给出一种扫描线的理解。   我们以滑动

    2024年02月12日
    浏览(45)
  • 【Weiler-Atherton算法】 计算机图形学多边形裁剪算法

    【Weiler-Atherton算法】 计算机图形学多边形裁剪算法

    源代码： https://github.com/ricar0/Weiler-Atherton-Alogrithm/tree/master 通常来说就是利用多边形来裁剪多边形的一种方法，一般情况下是利用矩形来裁剪凹凸多边形 凸多边形 凹多边形 上面红色划线部分就是裁剪出的部分 OPENGL基础语法 基本上就是一些画线和画多边形的操作，难度较低

    2023年04月09日
    浏览(68)
  • 计算机图形硬件（二） 5 - 2 光栅扫描系统

    计算机图形硬件（二） 5 - 2 光栅扫描系统

    2.1视频控制器 图2.17给出了常用的光栅系统组织。缓存使用系统存储器的固定区域且由视频控制器直接访问。          帧缓存的位置及相应的屏幕位置均使用笛卡儿(Cartesian)坐标。应用程序使用图形软件包的命令来设定显示对象相对于笛卡儿坐标系原点的坐标位置。尽管

    2024年02月11日
    浏览(42)
  • 计算机图形学05：中点BH算法对任意斜率的直线扫描转换方法

    计算机图形学05：中点BH算法对任意斜率的直线扫描转换方法

    作者 ：非妃是公主 专栏 ：《计算机图形学》 博客地址 ：https://blog.csdn.net/myf_666 个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩 专栏名称 专栏地址 软件工程 专栏——软件工程 计算机图形学 专栏——计算机图形学 操作系统 专栏——操作系统 软件测试 专

    2024年02月02日
    浏览(57)
  • 【计算机图形学】二维图形裁剪算法

    【计算机图形学】二维图形裁剪算法

    Cohen-Sutherland算法 Cohen-Sutherland是最早最流行的算法。 核心思想：通过 编码测试 来减少计算交点的次数。（编码算法） 1. 区域码： 线段端点以区域赋值以四位二进制码。 编码顺序：四位从右到左分别为：左边界、右边界、下边界、上边界。 编码值：落在相应位置为1，否则

    2024年02月02日
    浏览(59)
  • 初识计算机图形学

    初识计算机图形学

    笔记来源：【老奇】阴差阳错 撼动世界的游戏引擎 详见本人博客： 1.Transformation 2.梳理从MVP变换到光栅化的过程 MVP变换将空间中3D物体投影到2D屏幕 详见本人博客： 1.Rasterization（光栅化） 2.梳理从MVP变换到光栅化的过程 场景是一个个由三角面组成的模型 将模型投射到像素就

    2024年01月21日
    浏览(51)
  • 计算机图形与图像技术

    计算机图形与图像技术

    可以使用Python、Java等语言。 下图中，图中各事物比例失调 如何使用代码去掉某个人（不允许使用抠图工具）？         像素（Pixel）是“图像元素”的缩写， 指的是图像的最小单位 。 它是构成数码图像或屏幕显示图像的基本单元，代表了图像中的一个小点或一个小方块

    2024年02月07日
    浏览(56)
  • 计算机图形学——大作业

    计算机图形学——大作业

    绘制一个简单的三维场景，可以是室内：卧室，办公室，教室，也可以是室外：运动场，公园等，加上光照效果，简单的纹理映射，透视投影；不能过于简单；可以加动画、鼠标和键盘交互。     上交材料： project和word文档（具体内容展示，思路和心得） 首先初始化窗口，

    2024年02月11日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包