c++ - 在 OpenGL 中填充自相交多边形

Question

我有一个自相交的多边形，我正尝试使用奇偶规则来填充它，如下所示: 我使用扫描线，当我检测到多边形的边缘时，我会更改填充颜色。到目前为止，这是我的代码:

编辑代码:

#include<GL/glut.h>
#include<vector>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<limits>
using namespace std;
const int n = 7;

class Point{
public:
    int x, y;
    Point(){
    };
    Point(int a, int b){
        x = a;
        y = b;
    };
    void set(int a, int b){
        x = a;
        y = b;
    };
};
Point P[n];
int min(int x, int y)
{
    if (x <= y) return x;
    else return y;
}
int max(int x, int y)
{
    if (x >= y) return x;
    else return y;
}

Point solve(Point A, Point B, Point C, Point D)
{ //returns the intersection point between line segments [AB] and [CD]
    Point rez;
    rez.x = -1;
    rez.y = -1;
    //[AB]
    int A1 = B.y - A.y, B1 = A.x - B.x, C1 = (A1 * A.x) + (B1 * A.y);
    //[CD]
    int A2 = D.y - C.y, B2 = C.x - D.x, C2 = (A2 * C.x) + (B2 * C.y);

    int det = A1*B2 - A2*B1;
    if (det == 0){
        return Point(-1, -1);
    }
    else
    {
        rez.x = (B2*C1 - B1*C2) / det;
        rez.y = (A1*C2 - A2*C1) / det;
    }
    if (!(rez.x >= min(A.x, B.x) && rez.x <= max(A.x, B.x) && rez.x >= min(C.x, D.x) && rez.x <= max(C.x, D.x)))
    {
        rez.x = -1;
        rez.y = -1;
    }

    return rez;
}
bool intComparison(int i, int j) { return (i < j); }
void scanfill()
{
    int i, j, color = 1, k; //alb
    vector<int> inter[501];
    Point T;



    for (j = 0; j < 500; j++) //go line by line
    {
        for (k = 0; k < n - 1; k++) //loop through all the line segments
        {
            T = solve(Point(0, j), Point(499, j), P[k], P[k + 1]);
            if (!(T.x == -1 && T.y == -1))
            {
                inter[j].push_back(T.x); // save the x coord. of the intersection point between the line and the sweep line when y = j
            }
        }
        T = solve(Point(0, j), Point(499, j), P[n - 1], P[0]);
        if (!(T.x == -1 && T.y == -1))
        {
            inter[j].push_back(T.x);
        }
    }
    for (j = 0; j < 500; j++)
    {
        sort(inter[j].begin(), inter[j].end(), intComparison);
    }

    for (j = 0; j < 500; j++)
    {
        glColor3f(0.0, 0.0, 1.0);
        glBegin(GL_LINES);
        for (vector<int>::iterator it = inter[j].begin(); it != inter[j].end(); it++)
        {
            glVertex2i(*it, j); //draw the actual lines
        }
        glEnd();

    }



}


void display()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(0.0, 0.0, 0.0);

    P[0] = Point(100, 235);
    P[1] = (Point(100, 100));
    P[2] = (Point(230, 140));
    P[3] = (Point(40, 200));
    P[4] = (Point(20, 60));
    P[5] = (Point(300, 150));
    P[6] = (Point(150, 111));
    glBegin(GL_LINE_LOOP);
    for (int i = 0; i < n; i++)
    {
        glVertex2i(P[i].x, P[i].y);
    }
    glEnd();

    scanfill();


    glFlush();
}


void init()
{
    glClearColor(1.0, 1.0, 1.0, 1.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, 499.0, 0.0, 499.0);
}

void main(int argc, char **argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowSize(500, 500);

    glutCreateWindow("scanline");
    glutDisplayFunc(display);

    init();
    glutMainLoop();
}

由于某种原因，它似乎检测到扫描线和实际线之间的交点多于应有的交点。 以上代码的结果:

期望的结果:

Answer 1

我设法解决了这个问题。如果其他人有兴趣，这里是代码:

#include<GL/glut.h>
#include<vector>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<limits>
using namespace std;
const int n = 7;

class Point{
public:
    int x, y;
    Point(){
    };
    Point(int a, int b){
        x = a;
        y = b;
    };
    void set(int a, int b){
        x = a;
        y = b;
    };
};
Point P[n];
int min(int x, int y)
{
    if (x <= y) return x;
    else return y;
}
int max(int x, int y)
{
    if (x >= y) return x;
    else return y;
}
double solve(int y, Point A, Point B)
{
    if (y >= min(A.y, B.y) && y <= max(A.y, B.y))
    {
        return ((y * B.x) - (y * A.x) - (A.y * B.x) + (A.x * B.y)) / (B.y - A.y);
    }
    else return -1;
}

bool doubleComparison(double i, double j) { return (i < j); }
bool isVertex(int x, int y)
{
    for (int i = 0; i < n; i++)
    {
        if (P[i].x == x && P[i].y == y) return 1;
    }
    return 0;
}
void scanfill()
{
    int i, j, color = 1, k; 
    double x;
    vector<double> inter[501];

    for (j = 0; j < 500; j++)
    {
        for (k = 0; k < n - 1; k++)
        {
            x = solve(j, P[k], P[k + 1]);
            if (x != -1 && !isVertex(x,j))
            {
                inter[j].push_back(x);
            }
        }
        x = solve(j, P[n - 1], P[0]);
        if (x != -1 && !isVertex(x, j))
        {
            inter[j].push_back(x);
        }
    }
    for (j = 0; j < 500; j++)
    {
        sort(inter[j].begin(), inter[j].end(), doubleComparison);
    }

    for (j = 0; j < 500; j++)
    {
        glColor3f(0.0, 0.0, 1.0);
        glBegin(GL_LINES);
        for (vector<double>::iterator it = inter[j].begin(); it != inter[j].end(); it++)
        {
            glVertex2d(*it, j);
        }
        glEnd();

    }



}


void display()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(0.0, 0.0, 0.0);

    P[0] = Point(100, 235);
    P[1] = (Point(100, 100));
    P[2] = (Point(230, 140));
    P[3] = (Point(40, 200));
    P[4] = (Point(20, 60));
    P[5] = (Point(300, 150));
    P[6] = (Point(150, 111));
    glBegin(GL_LINE_LOOP);
    for (int i = 0; i < n; i++)
    {
        glVertex2i(P[i].x, P[i].y);
    }
    glEnd();

    scanfill();


    glFlush();
}


void init()
{
    glClearColor(1.0, 1.0, 1.0, 1.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, 499.0, 0.0, 499.0);
}

void main(int argc, char **argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowSize(500, 500);

    glutCreateWindow("scanline");
    glutDisplayFunc(display);

    init();
    glutMainLoop();
}