Polygon triangulation in triangle-strips für OpenGL ES

In 2D und ohne Löcher, das ist ziemlich einfach. Erste, Sie brauchen, um zu brechen das polygon, um eine oder mehrere monotone Polygone.

Die monotone Polygone sind ziemlich einfach zu biegen Sie in die tristrips, nur die Werte Sortieren, indem Sie y finden Sie die obersten und untersten Scheitelpunkt, und dann haben Sie Listen der Knoten auf der rechten und auf der linken Seite (weil vertices kommen, in eine bestimmte, sagen im Uhrzeigersinn, um). Dann beginnen Sie mit dem obersten Knoten und Scheitelpunkte hinzufügen von Links und von der rechten Seiten in abwechselnder Weise.

Diese Technik funktioniert für jede 2D-Polygone ohne sich selbst schneidende Kanten, die enthält einige Fälle von Polygonen, die Löcher (die Löcher müssen korrekt Wunde, obwohl).

Können Sie versuchen und spielen mit diesem code:

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glTranslatef(-.5f, -.5f, 0);

std::vector<Vector2f> my_polygon;

my_polygon.push_back(Vector2f(-0.300475f, 0.862924f));
my_polygon.push_back(Vector2f(0.302850f, 1.265013f));
my_polygon.push_back(Vector2f(0.811164f, 1.437337f));
my_polygon.push_back(Vector2f(1.001188f, 1.071802f));
my_polygon.push_back(Vector2f(0.692399f, 0.936031f));
my_polygon.push_back(Vector2f(0.934679f, 0.622715f));
my_polygon.push_back(Vector2f(0.644893f, 0.408616f));
my_polygon.push_back(Vector2f(0.592637f, 0.753264f));
my_polygon.push_back(Vector2f(0.269596f, 0.278068f));
my_polygon.push_back(Vector2f(0.996437f, -0.092689f));
my_polygon.push_back(Vector2f(0.735154f, -0.338120f));
my_polygon.push_back(Vector2f(0.112827f, 0.079634f));
my_polygon.push_back(Vector2f(-0.167458f, 0.330287f));
my_polygon.push_back(Vector2f(0.008314f, 0.664491f));
my_polygon.push_back(Vector2f(0.393112f, 1.040470f));
//from wiki (http://en.wikipedia.org/wiki/File:Polygon-to-monotone.png)

glEnable(GL_POINT_SMOOTH);
glEnable(GL_LINE_SMOOTH);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

glLineWidth(6);
glColor3f(1, 1, 1);
glBegin(GL_LINE_LOOP);
for(size_t i = 0, n = my_polygon.size(); i < n; ++ i)
    glVertex2f(my_polygon[i].x, my_polygon[i].y);
glEnd();
glPointSize(6);
glBegin(GL_POINTS);
for(size_t i = 0, n = my_polygon.size(); i < n; ++ i)
    glVertex2f(my_polygon[i].x, my_polygon[i].y);
glEnd();
//draw the original polygon

std::vector<int> working_set;
for(size_t i = 0, n = my_polygon.size(); i < n; ++ i)
    working_set.push_back(i);
_ASSERTE(working_set.size() == my_polygon.size());
//add vertex indices to the list (could be done using iota)

std::list<std::vector<int> > monotone_poly_list;
//list of monotone polygons (the output)

glPointSize(14);
glLineWidth(4);
//prepare to draw split points and slice lines

for(;;) {
    std::vector<int> sorted_vertex_list;
    {
        for(size_t i = 0, n = working_set.size(); i < n; ++ i)
            sorted_vertex_list.push_back(i);
        _ASSERTE(working_set.size() == working_set.size());
        //add vertex indices to the list (could be done using iota)

        for(;;) {
            bool b_change = false;

            for(size_t i = 1, n = sorted_vertex_list.size(); i < n; ++ i) {
                int a = sorted_vertex_list[i - 1];
                int b = sorted_vertex_list[i];
                if(my_polygon[working_set[a]].y < my_polygon[working_set[b]].y) {
                    std::swap(sorted_vertex_list[i - 1], sorted_vertex_list[i]);
                    b_change = true;
                }
            }

            if(!b_change)
                break;
        }
        //sort vertex indices by the y coordinate
        //(note this is using bubblesort to maintain portability
        //but it should be done using a better sorting method)
    }
    //build sorted vertex list

    bool b_change = false;
    for(size_t i = 0, n = sorted_vertex_list.size(), m = working_set.size(); i < n; ++ i) {
        int n_ith = sorted_vertex_list[i];
        Vector2f ith = my_polygon[working_set[n_ith]];
        Vector2f prev = my_polygon[working_set[(n_ith + m - 1) % m]];
        Vector2f next = my_polygon[working_set[(n_ith + 1) % m]];
        //get point in the list, and get it's neighbours
        //(neighbours are not in sorted list ordering
        //but in the original polygon order)

        float sidePrev = sign(ith.y - prev.y);
        float sideNext = sign(ith.y - next.y);
        //calculate which side they lie on
        //(sign function gives -1 for negative and 1 for positive argument)

        if(sidePrev * sideNext >= 0) { //if they are both on the same side
            glColor3f(1, 0, 0);
            glBegin(GL_POINTS);
            glVertex2f(ith.x, ith.y);
            glEnd();
            //marks points whose neighbours are both on the same side (split points)

            int n_next = -1;
            if(sidePrev + sideNext > 0) {
                if(i > 0)
                    n_next = sorted_vertex_list[i - 1];
                //get the next vertex above it
            } else {
                if(i + 1 < n)
                    n_next = sorted_vertex_list[i + 1];
                //get the next vertex below it
            }
            //this is kind of simplistic, one needs to check if
            //a line between n_ith and n_next doesn't exit the polygon
            //(but that doesn't happen in the example)

            if(n_next != -1) {
                glColor3f(0, 1, 0);
                glBegin(GL_POINTS);
                glVertex2f(my_polygon[working_set[n_next]].x, my_polygon[working_set[n_next]].y);
                glEnd();
                glBegin(GL_LINES);
                glVertex2f(ith.x, ith.y);
                glVertex2f(my_polygon[working_set[n_next]].x, my_polygon[working_set[n_next]].y);
                glEnd();

                std::vector<int> poly, remove_list;

                int n_last = n_ith;
                if(n_last > n_next)
                    std::swap(n_last, n_next);
                int idx = n_next;
                poly.push_back(working_set[idx]); //add n_next
                for(idx = (idx + 1) % m; idx != n_last; idx = (idx + 1) % m) {
                    poly.push_back(working_set[idx]);
                    //add it to the polygon

                    remove_list.push_back(idx);
                    //mark this vertex to be erased from the working set
                }
                poly.push_back(working_set[idx]); //add n_ith
                //build a new monotone polygon by cutting the original one

                std::sort(remove_list.begin(), remove_list.end());
                for(size_t i = remove_list.size(); i > 0; -- i) {
                    int n_which = remove_list[i - 1];
                    working_set.erase(working_set.begin() + n_which);
                }
                //sort indices of vertices to be removed and remove them
                //from the working set (have to do it in reverse order)

                monotone_poly_list.push_back(poly);
                //add it to the list

                b_change = true;

                break;
                //the polygon was sliced, restart the algorithm, regenerate sorted list and slice again
            }
        }
    }

    if(!b_change)
        break;
    //no moves
}

if(!working_set.empty())
    monotone_poly_list.push_back(working_set);
//use the remaining vertices (which the algorithm was unable to slice) as the last polygon

std::list<std::vector<int> >::const_iterator p_mono_poly = monotone_poly_list.begin();
for(; p_mono_poly != monotone_poly_list.end(); ++ p_mono_poly) {
    const std::vector<int> &r_mono_poly = *p_mono_poly;

    glLineWidth(2);
    glColor3f(0, 0, 1);
    glBegin(GL_LINE_LOOP);
    for(size_t i = 0, n = r_mono_poly.size(); i < n; ++ i)
        glVertex2f(my_polygon[r_mono_poly[i]].x, my_polygon[r_mono_poly[i]].y);
    glEnd();
    glPointSize(2);
    glBegin(GL_POINTS);
    for(size_t i = 0, n = r_mono_poly.size(); i < n; ++ i)
        glVertex2f(my_polygon[r_mono_poly[i]].x, my_polygon[r_mono_poly[i]].y);
    glEnd();
    //draw the sliced part of the polygon

    int n_top = 0;
    for(size_t i = 0, n = r_mono_poly.size(); i < n; ++ i) {
        if(my_polygon[r_mono_poly[i]].y < my_polygon[r_mono_poly[n_top]].y)
            n_top = i;
    }
    //find the top-most point

    glLineWidth(1);
    glColor3f(0, 1, 0);
    glBegin(GL_LINE_STRIP);
    glVertex2f(my_polygon[r_mono_poly[n_top]].x, my_polygon[r_mono_poly[n_top]].y);
    for(size_t i = 1, n = r_mono_poly.size(); i <= n; ++ i) {
        int n_which = (n_top + ((i & 1)? n - i / 2 : i / 2)) % n;
        glVertex2f(my_polygon[r_mono_poly[n_which]].x, my_polygon[r_mono_poly[n_which]].y);
    }
    glEnd();
    //draw as if triangle strip
}

Dieser code ist nicht optimal, aber es sollte einfach sein zu verstehen. Am Anfang, eine konkave polygon erstellt wird. Dann ein "working set" von Scheitelpunkten erstellt. Auf, die arbeiten eingestellt, eine permutation berechnet, die Art der vertices durch Ihre y koordinieren. Dass die permutation wird dann durchgeschleift, auf der Suche für split-Punkte. Einmal eine split-Punkt gefunden wird, eine neue Monotones polygon erstellt wird. Dann die Eckpunkte der neuen polygon entfernt von der Arbeitsgruppe festgelegt und der gesamte Vorgang wiederholt. Endlich, das working-set enthält die letzten polygon, das konnte nicht aufgeteilt werden. Am Ende, das monotone Polygone gerendert werden, zusammen mit Dreieck-Streifen bestellen. Es ist ein bisschen chaotisch, aber ich bin sicher, Sie werden es herausfinden (diese ist C++ - code, nur legte es in ein GLUT-Fenster und sehen, was es tut).

Hoffe, das hilft ...