计算机图形学07：有效边表法的多边形扫描转换 |
您所在的位置：网站首页 › 多边形的边缘怎么画图 › 计算机图形学07：有效边表法的多边形扫描转换 |
计算机图形学07：有效边表法的多边形扫描转换
|
作者：非妃是公主 专栏：《计算机图形学》 博客地址：https://blog.csdn.net/myf_666 个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩 计算机图形学（英语：computer graphics，缩写为CG）是研究计算机在硬件和软件的帮助下创建计算机图形的科学学科，是计算机科学的一个分支领域，主要关注数字合成与操作视觉的图形内容。虽然这个词通常被认为是指三维图形，事实上同时包括了二维图形以及影像处理。 一、算法原理有效边表法是X射线扫描转换的一种改进实现方式，相比于X射线方法，有效边表法由于不需要判断虚实交点，整体效率更高。 通过构造边表，然后随着X射线的移动不断地维护有效边表，通过两两配对边表中的有效边点亮像素，实现多边形的绘制。 具体原理如下：
排序方式按照x_ymin(y取到最小值的时候，x值的大小)排，x_ymin相等时按照 1 k \frac{1}{k} k1大小排，稍加思考会发现，正常情况下，不会出现相等情况。
由于配对原则，在顶点相交处，会影响到配对，采用的做法是，在影响配对的情况下进行 y m a x = y m a x − 1 ymax=ymax-1 ymax=ymax−1处理，通过此来保证在进行有效边交替的时候不会出现错误(即保证有效边表中的有效边数量为偶数)。
算法流程(本人在实现的时候，为编码符合自己的逻辑方式，先增加节点、再填充像素、填充后即检查是否需要删除如需要删除、最后进行各个有效边x_ymin属性的 + 1 k +\frac{1}{k} +k1)：
OpenGL代码实现如下： // 有效边表法(AET)绘制填充多边形 void AETPolygon(vector pnts) { vector::iterator min_iter = min_element(pnts.begin(), pnts.end()); vector::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; vector ET; // 边表 for (int i = 0; i next = tmpFirstNode->next; tmpFirstNode->next = tmp; } // 建立活动边表 ETNode* AET = new ETNode(0, 0, 0); // AET为头节点，不储存边表节点，后续节点才储存 // 从下到上进行 x 射线扫描 for (int i = min_y; i next != nullptr) { tmp_AETNode = AET; // 寻找AET中的插入位置 while (tmp_AETNode->next != nullptr && *(tmp_AETNode->next) 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 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; } } // 进行析构 // 析构AET ETNode* AEThead = AET; while (AEThead != nullptr) { ETNode* del = AEThead; AEThead = AEThead->next; delete del; } // 析构ET for (int i = 0; i next; delete del; } } } 三、效果展示有效边表法的多边形扫描转换效果如下：
有效边表法的多边形扫描转换算法到这里就要结束啦~~到此既是缘分，欢迎您的点赞、评论、收藏！关注我，不迷路，我们下期再见！！ 😘😘😘 我是Cherries，一位计算机科班在校大学生，写博客用来记录自己平时的所思所想！ 💞💞💞 内容繁杂，又才疏学浅，难免存在错误，欢迎各位大佬的批评指正！ 👋👋👋 我们相互交流，共同进步！ 注：本文由非妃是公主发布于https://blog.csdn.net/myf_666，转载请务必标明原文链接：https://blog.csdn.net/myf_666/article/details/128226399 |
【本文地址】