2.1 扫描线填充算法（活动边表 AET 法）#

1. 任务描述#

根据下面要求，在右侧修改代码空间，绘制出预期输出的图片。平台会对你编写的代码进行测试。

本关任务#

1. 理解扫描线填充算法的原理。
2. 利用 VC + OpenGL 实现基本的多边形填充算法。
3. 调试、编译、修改程序。

运行前#

输出#

具体要求#

利用扫描线填充算法（活动边表 AET 法）对 PolyScan() 函数进行补全，最终实现多边形填充后的图片。

相关知识#

为了完成本关任务，你需要掌握：扫描线填充算法。

1. 扫描线填充算法原理#

扫描线算法是确定水平扫描线与多边形的相交区间，把该区间内的所有像素一次性赋予新的颜色值。该算法充分利用了多边形边界与上下两条相邻扫描线的交点之间的连续性以及同一扫描线上像素之间的连续性。

对每条扫描线，分以下 3 个步骤：

1. 求交点：计算当前扫描线与多边形所有边的交点。
2. 排序与配对：把所有交点按 X 值递增顺序排序，排序后的交点两两配成区间。例如，第 1 个和第 2 个交点之间为一个区间，第 3 个和第 4 个交点之间为一个区间，以此类推。
3. 填色：将各个区间内的像素值设置为目标颜色值。

具体算法步骤如下：

1. 初始化 NET (新边表)：将多边形各条边按照该边的 MinY 值存放至 MinY 所对应的 NET 存储桶中。
2. 初始化 AET (活动边表) 为空表。
3. 将 y 值设置成 NET 中所列的最小 y 值，即第一个非空存储桶的 y 值。
4. 重复执行以下各步，直至 AET 和 NET 都为空：
   • 当扫描线的 y 值开始大于或等于 NET 中某个 y 桶的值时，将该桶的所有结点接入 AET 中（同时要从 NET 中删去），并将 AET 中的记录按 x 值排序。
   • 对于扫描线 y，在一对交点之间填充所需要的像素值。
   • 删去 AET 中 y > MaxY 的项。
   • 更新 AET 中所有剩余结点的 x 值。当一个结点是在本循环中才进入 AET 时，它记录的 x 值为 MinX。
   • 对 AET 中的各结点按 x 值重新排序。
   • y 增 1 后进入下一轮循环。

---

开始你的任务吧，祝你成功！

2. 我的回答#

文件 step1/test1.cpp:

// 评测代码所用头文件-开始
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
// 评测代码所用头文件-结束

#include <GL/freeglut.h>
#include <math.h>
#include <string>
#include <iostream>
using namespace std;
const int POINTNUM = 5;

typedef struct XET {
    int x;
    int dx, ymax;
    struct XET* next;
} AET, NET;

struct Point {
    int x;
    int y;
    Point() {}
    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }
} polypoint[POINTNUM];

int MaxY, MinY;//多边形顶点沿Y轴的最小值和最大值

void Init(){
    polypoint[0] = Point(100,100);
    polypoint[1] = Point(100,300);
    polypoint[2] = Point(200,200);
    polypoint[3] = Point(300,300);
    polypoint[4] = Point(300,100);

    MaxY = polypoint[0].y;
    MinY = polypoint[0].y;
    for (int i = 0; i < POINTNUM; i++) {
        if (polypoint[i].y > MaxY) {
            MaxY = polypoint[i].y;
        }
        if (polypoint[i].y < MinY) {
            MinY = polypoint[i].y;
        }
    }
}

void PolyScan() {
    glBegin(GL_POINTS);
    glColor3f(0.0, 1.0, 0.0);//设置颜色的函数
    // 请在此添加你的代码
    /********** Begin ********/
     AET* pAET = new AET;
    pAET->next = NULL;
    NET* pNET[1024];
    for (int i = MinY; i <= MaxY; i++) {
        pNET[i] = new NET;
        pNET[i]->next = NULL;
    }
    //填NET表
    for (int i = MinY; i <= MaxY; i++)
    {
        for (int j = 0; j < POINTNUM; j++)
        {
            if (polypoint[j].y == i)
            {
                if (polypoint[(j - 1 + POINTNUM) % POINTNUM].y > polypoint[j].y) //左边的点
                {
                    NET* p = new NET;
                    p->x = polypoint[j].x;
                    p->ymax = polypoint[(j - 1 + POINTNUM) % POINTNUM].y;
                    p->dx = (polypoint[(j - 1 + POINTNUM) % POINTNUM].x - polypoint[j].x) / (polypoint[(j - 1 + POINTNUM) % POINTNUM].y - polypoint[j].y);
                    p->next = pNET[i]->next;
                    pNET[i]->next = p;
                }
                if (polypoint[(j + 1 + POINTNUM) % POINTNUM].y > polypoint[j].y)  //右边的点
                {
                    NET* p = new NET;
                    p->x = polypoint[j].x;
                    p->ymax = polypoint[(j + 1 + POINTNUM) % POINTNUM].y;
                    p->dx = (polypoint[(j + 1 + POINTNUM) % POINTNUM].x - polypoint[j].x) / (polypoint[(j + 1 + POINTNUM) % POINTNUM].y - polypoint[j].y);
                    p->next = pNET[i]->next;
                    pNET[i]->next = p;
                }
            }
        }
    }
    //建立更新AET
    for (int i = MinY; i <= MaxY; i++) {
        //计算新的交点x，更新AET
        NET* p = pAET->next;
        while (p != NULL)
        {
            p->x = p->x + p->dx;
            p = p->next;
        }
        //更新后新AET先排序
        //断表排序,不再开辟空间
        AET* tq = pAET;
        p = pAET->next;
        tq->next = NULL;
        while (p != NULL)  //按x排序
        {
            while (tq->next != NULL && p->x >= tq->next->x)
            {
                tq = tq->next;
            }
            NET* s = p->next;
            p->next = tq->next;
            tq->next = p;
            p = s;
            tq = pAET;
        }
        AET* q = pAET;
        p = q->next;
        while (p != NULL)
        {
            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 != NULL)
        {
            while (q->next != NULL && p->x >= q->next->x)
            {
                q = q->next;
            }
            NET* s = p->next;
            p->next = q->next;
            q->next = p;
            p = s;
            q = pAET;
        }
        p = pAET->next;
        while (p && p->next)
        {
            for (float j = p->x; j <= p->next->x; j++)
                glVertex2f(j, i);
            p = p->next->next;//考虑端点情况
        }
    }
    NET* phead = NULL;
    NET* pnext = NULL;
    //释放活跃边表
    phead = pAET;
    while (phead != NULL)
    {
        pnext = phead->next;
        delete phead;
        phead = pnext;
    }
   /********** End **********/
    glEnd();
}

void LineGL(int i){
    glBegin(GL_LINES);
    glColor3f(0.0f, 1.0f, 0.0f);
    glVertex2f(polypoint[i].x, polypoint[i].y);
    glVertex2f(polypoint[i + 1].x, polypoint[i + 1].y);
    if (i == POINTNUM - 2) {
        glVertex2f(polypoint[0].x, polypoint[0].y);
        glVertex2f(polypoint[i + 1].x, polypoint[i + 1].y);
    }
    glEnd();
}

void MyDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(1.0f, 1.0f, 1.0f);
    for (int i = 0; i < POINTNUM - 1; i++) {
        LineGL(i);
    }
   PolyScan();

   glFlush();
}

void MyReshape(int w, int h)
{
    glViewport(0, 0, (GLsizei)w, (GLsizei)h);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, (GLdouble)w, 0.0, (GLdouble)h);
}

int main(int argc, char* argv[])
{
    glutInit(&argc, argv);//窗口的初始化
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//窗口模式的设定
    glutInitWindowPosition(100, 100);//窗口位置的设定
    glutInitWindowSize(400, 400);//窗口大小的设定
    glutCreateWindow("多边形的扫描填充");
    Init();
    glutDisplayFunc(MyDisplay);
    glutReshapeFunc(MyReshape);
    glutMainLoopEvent();

    /*************以下为评测代码，与本次实验内容无关，请勿修改**************/
	GLubyte* pPixelData = (GLubyte*)malloc(400 * 400 * 3);//分配内存
    GLint viewport[4] = {0};    
    glReadBuffer(GL_FRONT);
    glPixelStorei(GL_UNPACK_ALIGNMENT, 4);
    glGetIntegerv(GL_VIEWPORT, viewport);
    glReadPixels(viewport[0], viewport[1], viewport[2], viewport[3], GL_RGB, GL_UNSIGNED_BYTE, pPixelData);

	cv::Mat img;
    std::vector<cv::Mat> imgPlanes;
    img.create(400, 400, CV_8UC3);
    cv::split(img, imgPlanes);
 
    for(int i = 0; i < 400; i ++) {
        unsigned char* plane0Ptr = imgPlanes[0].ptr<unsigned char>(i);
        unsigned char* plane1Ptr = imgPlanes[1].ptr<unsigned char>(i);
        unsigned char* plane2Ptr = imgPlanes[2].ptr<unsigned char>(i);
        for(int j = 0; j < 400; j ++) {
            int k = 3 * (i * 400 + j);
            plane2Ptr[j] = pPixelData[k];
            plane1Ptr[j] = pPixelData[k+1];
            plane0Ptr[j] = pPixelData[k+2];
        }
    }
    cv::merge(imgPlanes, img);
    cv::flip(img, img ,0); 
    cv::namedWindow("openglGrab");
    cv::imshow("openglGrab", img);
    cv::imwrite("../img_step1/test.jpg", img);
	return 0;
}