将多边形三角剖分为 OpenGL ES 的三角形条带 [英] Polygon triangulation into triangle strips for OpenGL ES

查看：24 发布时间：2022/1/21 17:12:25 algorithm cocos2d-iphone opengl-es-2.0 triangulation gl-triangle-strip

本文介绍了将多边形三角剖分为 OpenGL ES 的三角形条带的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我正在寻找一种快速的多边形三角剖分算法，它可以将不太复杂的 2D 凹面多边形(无孔)三角剖分成 三角形条带，以便发送到 OpenGL ES使用 GL_TRIANGLE_STRIP 绘图.

I am looking for a fast polygon triangulation algorithm that can triangulate not very complex 2D concave polygons (without holes) into triangle strips ready to be sent to OpenGL ES for drawing using GL_TRIANGLE_STRIP.

我知道一些算法，但找不到适合我需要的算法:

I am aware of some algorithms but I couldn't find one that will fit my needs:

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

这个算法工作正常，但问题是它返回简单的三角形，你不能用 GL_TRIANGLE_STRIP 绘制，你需要使用 GL_TRIANGLES 这不是很有效大量的顶点.

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

this algorithm works ok but the problem is it returns simple triangles which you can't draw with GL_TRIANGLE_STRIP, you need to use GL_TRIANGLES which isn't very efficient on a large number of vertices.

它没有任何关联的示例，我找不到任何人在 iOS 上通过 OpenGL ES 2.0 成功使用它
我不知道它返回什么，而且它似乎还调用了我不想要的相应 OpenGL 命令 - 我只需要返回三角形
它会泄漏内存

我开发的平台是:iOS，OpenGL ES 2.0，cocos2d 2.0.

The platform I am developing for is: iOS, OpenGL ES 2.0, cocos2d 2.0.

谁能帮我用这样的算法?或者任何其他建议将不胜感激.

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

推荐答案

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

In 2D and without holes, this is fairly easy. First, you need to break your polygon to one or more monotone polygons.

单调多边形很容易变成三条带，只需按 y 对值进行排序，找到最顶部和最底部的顶点，然后你就可以得到右侧的顶点列表和向左(因为顶点有一些定义，比如顺时针，顺序).然后从最上面的顶点开始，以交替方式从左侧和右侧添加顶点.

The monotone polygons are pretty simple to turn into tristrips, just sort the values by y, find the top-most and bottom-most vertex, and then you have lists of vertices to the right and to the left (because vertices come in some defined, say clockwise, order). Then you start with top-most vertex and add vertices from the left and from the right sides in alternating manner.

此技术适用于任何没有自相交边的二维多边形，其中包括一些带有孔的多边形(但孔必须正确缠绕).

This technique will work for any 2D polygons without self-intersecting edges, which includes some cases of polygons with holes (the holes must be correctly wound though).

您可以尝试使用此代码:

You can try and play 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'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
}

这段代码不是最优的，但应该很容易理解.在开始时，创建了一个凹多边形.然后创建顶点的工作集".在该工作集上，计算一个排列，该排列按顶点的 y 坐标对顶点进行排序.然后循环该排列，寻找分裂点.一旦找到分割点，就会创建一个新的单调多边形.然后，新多边形中使用的顶点从工作集中移除，整个过程重复.最后，工作集包含最后一个无法分割的多边形.最后，渲染单调多边形以及三角形条带排序.这有点乱，但我相信你会弄明白的(这是 C++ 代码，只需将其放在 GLUT 窗口中，看看它会做什么).

This code is not optimal, but it should be easy to understand. At the beginnig, a concave polygon is created. Then a "working set" of vertices is created. On that working set, a permutation is calculated which sorts the vertices by their y coordinate. That permutation is then looped through, looking for split points. Once a split point is found, a new monotone polygon is created. Then, the vertices used in the new polygon are removed from the working set and the whole process repeats. Finally, the working set contains the last polygon which could not be split. At the end, the monotone polygons are rendered, along with triangle strip ordering. It is a little bit messy, but I'm sure you will figure it out (this is C++ code, just put it inside a GLUT window and see what it does).

希望这会有所帮助...

Hope this helps ...

这篇关于将多边形三角剖分为 OpenGL ES 的三角形条带的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

将多边形三角剖分为 OpenGL ES 的三角形条带 [英] Polygon triangulation into triangle strips for OpenGL ES

问题描述

推荐答案

相关文章

其他开发最新文章

热门教程

热门工具

登录关闭

将多边形三角剖分为 OpenGL ES 的三角形条带 [英] Polygon triangulation into triangle strips for OpenGL ES

问题描述

推荐答案

相关文章

其他开发最新文章

热门教程

热门工具

登录 关闭

登录关闭