Triangulation de polygone dans les bandes de triangle pour ouverts

Question

Je cherche un jeûne algorithme de triangulation en polygone qui peuvent trianguler les polygones concaves 2D pas très complexes (sans trous) dans bandes de triangle prêt à être envoyé à OpenGl es pour le dessin en utilisant GL_TRIANGLE_STRIP.

Je suis conscient de certains algorithmes, mais je n'en ai pas trouvé un qui répondra à mes besoins:

• http://www.flipcode.com/archives/efficient_polygon_triangulation.shtml
  • Cet algorithme fonctionne bien mais le problème est qu'il renvoie des triangles simples avec lesquels vous ne pouvez pas dessiner GL_TRIANGLE_STRIP, vous devez utiliser GL_TRIANGLES Ce qui n'est pas très efficace sur un grand nombre de sommets.
• http://code.google.com/p/iphone-glu/
  • Il n'a pas d'exemple associé et je n'ai trouvé personne qui l'a utilisé avec succès sur iOS avec OpenGL ES 2.0
  • Je ne sais pas ce qu'il retourne et il semble qu'il appelle également les commandes OpenGL correspondantes que je ne veux pas - je n'ai besoin que des triangles
  • Il divulgue la mémoire

La plate-forme pour laquelle je développe est: iOS, OpenGL ES 2.0, Cocos2d 2.0.

Quelqu'un peut-il m'aider avec un tel algorithme? Ou tout autre conseil sera grandement apprécié.

Answer 1

En 2D et sans trous, c'est assez facile. Tout d'abord, vous devez briser votre polygone en un ou plusieurs polygones monotones.

Les polygones monotones sont assez simples à transformer en triprists, trier simplement les valeurs par y, trouvez le sommet le plus haut et le plus bas, puis vous avez des listes de sommets à droite et à gauche (parce que les sommets sont définis dans un ordre défini dans le sens horaire). Ensuite, vous commencez avec le sommet le plus haut et ajoutez des sommets de la gauche et des côtés droits de manière alternative.

Cette technique fonctionnera pour tous les polygones 2D sans bords auto-insuffisants, qui comprend certains cas de polygones avec des trous (les trous doivent cependant être correctement enroulés).

Vous pouvez essayer de jouer avec ce 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
}

Ce code n'est pas optimal, mais il devrait être facile à comprendre. Au début, un polygone concave est créé. Ensuite, un "ensemble de travail" de sommets est créé. Sur cet ensemble de travail, une permutation est calculée qui trie les sommets par leur y coordonner. Cette permutation est ensuite enroulée, à la recherche de points de division. Une fois un point de division trouvé, un nouveau polygone monotone est créé. Ensuite, les sommets utilisés dans le nouveau polygone sont supprimés de l'ensemble de travail et l'ensemble du processus se répète. Enfin, l'ensemble de travail contient le dernier polygone qui n'a pas pu être divisé. À la fin, les polygones monotones sont rendus, ainsi que l'ordre de la bande triangulaire. C'est un peu désordonné, mais je suis sûr que vous le comprendrez (c'est du code C ++, mettez-le simplement dans une fenêtre de glut et voyez ce qu'il fait).

J'espère que cela t'aides ...

Answer 2

Vous pouvez extraire l'algorithme de teselation à partir de la mise en œuvre de l'échantillon OpenGL, comme décrit dans cet article http://choruscode.blogspot.de/2013/03/Extructing-Tesselation-from-opengl.html , il en a également un exemple.