Polygone de triangulation dans le triangle des bandes pour OpenGL ES

En 2D et sans trous, c'est assez facile. Tout d'abord, vous devez rompre votre polygone à un ou plusieurs monotone des polygones.

Le ton monotone de polygones sont assez simples pour se transformer en tristrips, juste trier les valeurs par y, trouver le plus haut et le plus bas du vertex, et puis vous avez des listes de sommets vers la droite et vers la gauche (parce que les sommets viennent dans certains régimes de, dire dans le sens horaire, de l'ordre). Ensuite, vous commencez avec le plus haut sommet et ajouter des sommets de la gauche et de la droite en alternance.

Que cette technique fonctionne pour toutes les polygones 2D sans auto-intersection d'arêtes, qui comprend certains cas de polygones avec des trous (les trous doivent être correctement de la plaie).

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 doit être facile à comprendre. Au départ, un polygone concave est créé. Ensuite, un "travail" de sommets est créé. Sur ce jeu de travail, une permutation est calculée qui trie les sommets par leur y coordonner. Cette permutation est alors bouclé, à la recherche de points de scission. Une fois le point de split est trouvé, une nouvelle monotone polygone est créé. Ensuite, les sommets utilisé dans le nouveau polygone sont retirés de l'ensemble de travail et l'ensemble du processus se répète. Enfin, l'ensemble de travail contient la dernière polygone qui pourrait ne pas être divisé. À la fin, le ton monotone de polygones sont rendus, avec triangle strip de la commande. C'est un peu bordélique, mais je suis sûr que vous allez le comprendre (c'est du code C++, il suffit de le mettre à l'intérieur d'une SURABONDANCE de fenêtre et de voir ce qu'elle fait).

Espère que cela aide ...

OriginalL'auteur the swine