Geek Answers Handbook

Triangle polygon in triangular stripes for OpenGL ES

I am looking for a quick polygon triangulation algorithm that can triangulate not very complex two-dimensional concave polygons (without holes) into triangular stripes , ready to be sent to OpenGL ES for using GL_TRIANGLE_STRIP .

I am aware of some algorithms, but I could not find one that would fit my needs:

  • http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
    • this algorithm works fine, but the problem is that it returns simple triangles that cannot be drawn with GL_TRIANGLE_STRIP , you need to use GL_TRIANGLES , which is not very efficient for a lot of vertices.
  • http://code.google.com/p/iphone-glu/
    • it does not have a related example, and I could not find anyone who successfully used it on iOS with OpenGL ES 2.0
    • I don’t know what it returns, and it seems that it also calls the corresponding OpenGL commands that I don’t need - I only need triangles back
    • memory leak

The platform I'm developing is: iOS, OpenGL ES 2.0, cocos2d 2.0.

Can someone help me with such an algorithm? Or any other advice would be greatly appreciated.

+7
source share
2 answers

In 2D and without holes, this is pretty simple. First, you need to split your polygon into one or more monochrome polygons .

Monotone polygons are pretty simple to turn into tristrips, just sort the y values, find the top and bottom vertices, and then you have lists of vertices on the right and left (because the vertices fall into some specific order, for example, clockwise). Then you start at the top of the vertex and add the vertices on the left and right with alternating image.

This method will work for any two-dimensional polygons without self-intersecting edges, which includes some cases of polygons with holes (holes should be properly wound, though).

You can try playing with this 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 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 }

This code is not optimal, but it should be easy to understand. At the beginning, a concave polygon is created. Then a "working set" of vertices is created. On this working set, a permutation is computed that sorts the vertices by their y coordinate. This permutation then loops around looking for split points. After the split point is detected, a new monotonic polygon is created. Then the vertices used in the new polygon are removed from the working set, and the whole process is repeated. Finally, the working set contains the last polygon that cannot be broken. At the end, monotone polygons are displayed, as well as the order of the triangular strip. It's a bit dirty, but I'm sure you figure it out (this is C ++ code, just put it in the GLUT window and see what it does).

Hope this helps ...

+9
source

You can extract the tessellation algorithm from the OpenGL Sample Implementation, as described in this post http://choruscode.blogspot.de/2013/03/extracting-tesselation-from-opengl.html , it also has an example.

+1
source

More articles:


All Articles