网站建设项目确认书,建设路街道办事处门户网站,在线玩网页游戏,我的世界做视频封面的网站作者#xff1a;非妃是公主 专栏#xff1a;《计算机图形学》 博客地址#xff1a;https://blog.csdn.net/myf_666 个性签#xff1a;顺境不惰#xff0c;逆境不馁#xff0c;以心制境#xff0c;万事可成。——曾国藩 文章目录专栏推荐专栏系列文章序一、算法原理二、… 作者非妃是公主 专栏《计算机图形学》 博客地址https://blog.csdn.net/myf_666 个性签顺境不惰逆境不馁以心制境万事可成。——曾国藩 文章目录专栏推荐专栏系列文章序一、算法原理二、OpenGL代码实现三、效果展示the end…… 专栏推荐
专栏名称专栏地址软件工程专栏——软件工程计算机图形学 专栏——计算机图形学 操作系统专栏——操作系统软件测试专栏——软件测试机器学习专栏——机器学习数据库专栏——数据库算法专栏——算法
专栏系列文章
文章名称文章地址直线生成算法(DDA算法)计算机图形学01——DDA算法中点BH算法绘制直线计算机图形学02——中点BH算法改进的中点BH算法计算机图形学03——改进的中点BH算法中点Bresenham画椭圆计算机图形学04——中点BH绘制椭圆中点BH算法绘制任意斜率直线计算机图形学05——中点BH算法绘制任意斜率的直线中点Bresenham画圆计算机图形学06——中点BH算法画圆有效边表法的多边形扫描转换计算机图形学07——有效边表法绘制填充多边形中点BH算法绘制抛物线 100xy2100x y^2100xy2计算机图形学08——中点BH绘制抛物线二维观察之点的裁剪计算机图形学09——二维观察之点裁剪二维观察之线的裁剪计算机图形学10——二维观察之线裁剪二维观察之多边形的裁剪计算机图形学11——二维观察之多边形裁剪二维图形的几何变换计算机图形学12——二维图形几何变换三维图形的几何变换计算机图形学13——三维图形几何变换三维图形的投影变换计算机图形学14——三维图形投影变换
序
计算机图形学英语computer graphics缩写为CG是研究计算机在硬件和软件的帮助下创建计算机图形的科学学科是计算机科学的一个分支领域主要关注数字合成与操作视觉的图形内容。虽然这个词通常被认为是指三维图形事实上同时包括了二维图形以及影像处理。 一、算法原理
有效边表法是X射线扫描转换的一种改进实现方式相比于X射线方法有效边表法由于不需要判断虚实交点整体效率更高。
通过构造边表然后随着X射线的移动不断地维护有效边表通过两两配对边表中的有效边点亮像素实现多边形的绘制。
具体原理如下 排序方式按照x_ymin(y取到最小值的时候x值的大小)排x_ymin相等时按照1k\frac{1}{k}k1大小排稍加思考会发现正常情况下不会出现相等情况。 由于配对原则在顶点相交处会影响到配对采用的做法是在影响配对的情况下进行ymaxymax−1ymaxymax-1ymaxymax−1处理通过此来保证在进行有效边交替的时候不会出现错误(即保证有效边表中的有效边数量为偶数)。 算法流程(本人在实现的时候为编码符合自己的逻辑方式先增加节点、再填充像素、填充后即检查是否需要删除如需要删除、最后进行各个有效边x_ymin属性的1k\frac{1}{k}k1) 二、OpenGL代码实现
OpenGL代码实现如下
// 有效边表法(AET)绘制填充多边形
void AETPolygon(vectorPoint pnts) {vectorPoint::iterator min_iter min_element(pnts.begin(), pnts.end());vectorPoint::iterator max_iter max_element(pnts.begin(), pnts.end());int min_y min_iter-y;int max_y max_iter-y;int dist max_y - min_y 1;vectorETNode* ET; // 边表for (int i 0; i dist; i) {ET.push_back(new ETNode(0, 0, 0));}for (int i 0; i pnts.size(); i) { // 建立边表// 建立边表节点的属性值double x_ymin, y_max, rev_k;if (pnts[i].y pnts[(i 1) % pnts.size()].y) { // 找出y最小值对应的x值x_ymin pnts[(i 1) % pnts.size()].x;y_max pnts[i].y;// 如果为一个顶点的情况y_max--if ((pnts[(i - 1 pnts.size()) % pnts.size()].y - pnts[i].y) * (pnts[(i 1 pnts.size()) % pnts.size()].y - pnts[i].y) 0) {y_max--;}}else {x_ymin pnts[i].x;y_max pnts[(i 1) % pnts.size()].y;// 如果为一个顶点的情况y_max--if ((pnts[(i pnts.size()) % pnts.size()].y - pnts[i 1].y) * (pnts[(i 2 pnts.size()) % pnts.size()].y - pnts[i 1].y) 0) {y_max--;}}// 计算 1/krev_k (double)(pnts[(i 1) % pnts.size()].x - pnts[i].x) / (pnts[(i 1) % pnts.size()].y - pnts[i].y);// 计算 (1/斜率)ETNode* tmp new ETNode(x_ymin, y_max, rev_k);ETNode* tmpFirstNode ET[x_ymin - min_y];// 寻找合适的插入位置while (tmpFirstNode-next ! nullptr *(tmpFirstNode-next) *tmp){tmpFirstNode tmpFirstNode-next;}// 插入tmp-next tmpFirstNode-next;tmpFirstNode-next tmp;}// 建立活动边表ETNode* AET new ETNode(0, 0, 0); // AET为头节点不储存边表节点后续节点才储存// 从下到上进行 x 射线扫描for (int i min_y; i max_y; i) {ETNode* tmp_ETNode ET[i - min_y];ETNode* tmp_AETNode AET;while (tmp_ETNode-next ! nullptr) {tmp_AETNode AET;// 寻找AET中的插入位置while (tmp_AETNode-next ! nullptr *(tmp_AETNode-next) *(tmp_ETNode-next)) {tmp_AETNode tmp_AETNode-next;}//ET[i - min_y]-next tmp_ETNode-next-next; 将tmp-next加入到 AET中//tmp_ETNode-next-next tmp_AETNode-next;//tmp_AETNode-next tmp_ETNode-next;//tmp_ETNode ET[i - min_y];// 将tmp加入到 AET 中ETNode* tmp new ETNode(tmp_ETNode-next-x_ymin, tmp_ETNode-next-y_max, tmp_ETNode-next-rev_k);tmp-next tmp_AETNode-next;tmp_AETNode-next tmp;tmp_ETNode tmp_ETNode-next;}// 添加完以后进行画点tmp_AETNode AET;while (tmp_AETNode-next ! nullptr tmp_AETNode-next-next ! nullptr) {int fillBegin (int)(tmp_AETNode-next-x_ymin 0.5);int fillEnd (int)(tmp_AETNode-next-next-x_ymin 0.5);glColor3f(0.0f, 1.0f, 0.0f); // 设置颜色为绿色进行填充glBegin(GL_POINTS);for (int j fillBegin; j fillEnd; j) {glVertex2i(j, i);} glEnd();// 填充之后删除yy_max的边if (i tmp_AETNode-next-y_max || i tmp_AETNode-next-next-y_max) {if (i tmp_AETNode-next-y_max i tmp_AETNode-next-next-y_max) { // 删两个ETNode* del tmp_AETNode-next;tmp_AETNode-next tmp_AETNode-next-next;delete del;del tmp_AETNode-next;tmp_AETNode-next tmp_AETNode-next-next;delete del;}else if(i tmp_AETNode-next-y_max) { // 删第一个ETNode* del tmp_AETNode-next;tmp_AETNode-next tmp_AETNode-next-next;delete del;tmp_AETNode tmp_AETNode-next;}else { // 删第二个ETNode* del tmp_AETNode-next-next;tmp_AETNode-next-next tmp_AETNode-next-next-next;delete del;tmp_AETNode tmp_AETNode-next;}continue;}tmp_AETNode tmp_AETNode-next-next;}// 更新AET表中的x值tmp_AETNode AET;while (tmp_AETNode-next ! nullptr){tmp_AETNode-next-x_ymin tmp_AETNode-next-rev_k;tmp_AETNode tmp_AETNode-next;}}// 进行析构// 析构AETETNode* AEThead AET;while (AEThead ! nullptr) {ETNode* del AEThead;AEThead AEThead-next;delete del;}// 析构ETfor (int i 0; i ET.size(); i) {ETNode* EThead ET[i];while (EThead ! nullptr) {ETNode* del EThead;EThead EThead-next;delete del;}}
}三、效果展示
有效边表法的多边形扫描转换效果如下 the end……
有效边表法的多边形扫描转换算法到这里就要结束啦~~到此既是缘分欢迎您的点赞、评论、收藏关注我不迷路我们下期再见 我是Cherries一位计算机科班在校大学生写博客用来记录自己平时的所思所想 内容繁杂又才疏学浅难免存在错误欢迎各位大佬的批评指正 我们相互交流共同进步 注本文由非妃是公主发布于https://blog.csdn.net/myf_666转载请务必标明原文链接https://blog.csdn.net/myf_666/article/details/128226399
