Triangulation

[logank9]

Code: Select all

//use earclipping to generate a list of triangles to draw
std::vector<vec> calcTriDraw(std::vector<vec> poly)
{
    std::vector<double> polyAngles;
    //get angles
    for(unsigned int i = 0;i < poly.size();i++)
    {

        int p1 = i - 1;
        int p2 = i;
        int p3 = i + 1;

        if(p2 > int(poly.size()))
            p2 -= poly.size();
        if(p1 < 0)
            p1 += poly.size();
        //get the angle of the 3 points: line 1 angle - line 2 angle, I'm not sure of any other way to do it
        polyAngles.push_back((atan2(poly[p3].y - poly[p2].y,poly[p3].x - poly[p2].x) - atan2(poly[p2].y - poly[p1].y,poly[p2].x - poly[p1].x))*180/3.14159265);
    }
    std::vector<vec> triList;
    for(unsigned int i = 0;i < poly.size() && poly.size() > 2;i++)
    {
        int p1 = i - 1;
        int p2 = i;
        int p3 = i + 1;

        if(p3 > int(poly.size()))
            p3 -= poly.size();
        if(p1 < 0)
            p1 += poly.size();

        if(polyAngles[p2] > 180)
        {
            continue;
        }
        else
        {
            poly.erase(poly.begin()+p2);
            triList.push_back(poly[p1]);
            triList.push_back(poly[p2]);
            triList.push_back(poly[p3]);
            std::vector<vec> add = calcTriDraw(poly);
            triList.insert(triList.end(), add.begin(), add.end());
            break;
        }
    }
    return triList;
}

I am working on a simple 2D engine and right now I'm stuck on how to draw polygons when given the verts that make up their perimeter. To do this, I am using a method of polygon triangulation called ear clipping. From what I understand, you run through the verts and if you find one that can make a triangle with the 2 verts next to it that is inside the polygon you can remove that vert, and draw the triangle with those 3 points (sorry for the crappy explanation). Oh and if you're wondering, I'm using the STL vector class to make things easier.

I tried using this algorithm with a few different polygons with no luck. Sometimes it crashes, and others it draws the wrong shape.

Could someone please look over my code and tell me what I did wrong?

Edit:
OK, after a bit of troubleshooting it seems like its not counting the first vert for some reason. It still crashes sometimes though.

[schwarb]

I don't have time to look over the whole thing right now, but a couple of things jumped out to me.

In the first for loop where you have this...

Code: Select all

int p1 = i - 1;
int p2 = i;
int p3 = i + 1;

if(p2 > int(poly.size()))
      p2 -= poly.size();

the expression is never going to be true because of the limits of the for loop. I think you may have meant p3 and the expression should be

Code: Select all

p3 = int(poly.size())

(you want it to wrap back to zero when you subtract poly.size() right?)

This may or may not be the cause of all your problems. The only other thing I would pay close attention to is the recursive call near the end

Code: Select all

std::vector<vec> add = calcTriDraw(poly);

I think this is a really dangerous and difficult to comprehend way of solving the problem you have. If you are going to be using recursive calls, you'll want to have some data that persists through the calls. Pass pointers.

Good luck.

[logank9]

Thank you! I can't believe I didn't see that part where I had p2 instead of p3. I tested with the polygons I tried before and it no longer crashes, though it's still not counting that first vert for some reason, and I don't think it's because I'm not using pointers.

Edit:
I fixed one thing that should have been fowling it up: I do poly.erase(poly.begin()+p2) BEFORE I do triList.push_back(p2) but now it just draws a completely wrong shape instead of missing the first vert. I really don't understand what's happening here.

What I have now:

Code: Select all

//use earclipping to generate a list of triangles to draw
std::vector<vec> calcTriDraw(std::vector<vec> poly)
{
    std::vector<double> polyAngles;
    //get angles
    for(unsigned int i = 0;i < poly.size();i++)
    {

        int p1 = i - 1;
        int p2 = i;
        int p3 = i + 1;

        if(p3 > int(poly.size()))
            p3 -= poly.size();
        if(p1 < 0)
            p1 += poly.size();

        //get the angle from 3 points
        double dx, dy;
        dx = poly[p2].x - poly[p1].x;
        dy = poly[p2].y - poly[p1].y;
        double a = atan2(dy,dx);

        dx = poly[p3].x - poly[p2].x;
        dy = poly[p3].y - poly[p2].y;
        double b = atan2(dy,dx);

        polyAngles.push_back((a-b)*180/PI);
    }
    std::vector<vec> triList;
    for(unsigned int i = 0;i < poly.size() && poly.size() > 2;i++)
    {
        int p1 = i - 1;
        int p2 = i;
        int p3 = i + 1;

        if(p3 > int(poly.size()))
            p3 -= poly.size();
        if(p1 < 0)
            p1 += poly.size();

        if(polyAngles[p2] >= 180)
        {
            continue;
        }
        else
        {
            triList.push_back(poly[p1]);
            triList.push_back(poly[p2]);
            triList.push_back(poly[p3]);
            poly.erase(poly.begin()+p2);
            std::vector<vec> add = calcTriDraw(poly);
            triList.insert(triList.end(), add.begin(), add.end());
            break;
        }
    }

    return triList;
}

Oh, and it seems to be calculating the angles incorrectly (it says a square's angles are 90, 90, 90, and 176). This is most likely the source of all my problems.

OK, I cleaned up my angle code a bit, and I still don't understand what I am doing wrong.