OpenGL ES的多边形三角剖分成三角形带

OpenGL ES的多边形三角剖分成三角形带

在2D且无孔的情况下，这相当容易。首先，您需要将多边形分解为一个或多个单调多边形。

单调多边形很容易变成三条纹，只需将值排序为

y

，找到最顶部和最底部的顶点，然后您就可以在左右两边找到顶点列表（因为顶点已定义，顺时针说）。然后，从最顶部的顶点开始，并从左侧和右侧以交替方式添加顶点。

此技术适用于任何不具有自相交边的2D多边形，其中包括某些情况下带有孔的多边形（但必须正确缠绕孔）。

您可以尝试使用以下代码：

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 polygonstd::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 linesfor(;;) {    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 polygonstd::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}

该代码不是最佳代码，但应该易于理解。在开始时，将创建一个凹面多边形。然后创建顶点的“工作集”。在该工作集上，将计算一个排列，该排列按顶点的

y

坐标对它们进行排序。然后，将该排列循环遍历，以寻找分裂点。一旦找到分割点，就会创建一个新的单调多边形。然后，将新多边形中使用的顶点从工作集中删除，然后重复整个过程。最后，工作集包含无法分割的最后一个多边形。最后，将渲染单调多边形以及三角带顺序。有点混乱，但是我敢肯定您会弄清楚的（这是C
++代码，只需将其放在GLUT窗口中，然后看它能做什么）。

希望这可以帮助 …