多边形三角成三角形条带的OpenGL ES [英] Polygon triangulation into triangle strips for OpenGL ES

查看：766 发布时间：2015/11/30 14:29:51 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.flip$c$c.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的，2.0的cocos2d

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

谁能帮我这样的算法？还是有其他意见，将大大AP preciated。

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.

单调多边形是pretty的简单变成tristrips，只是是的值进行排序，找到最顶层和底层最顶点，然后你有顶点列表向右和向左（因为顶点进来一些规定，比如顺时针顺序）。然后，你开始用最顶部的顶点，并从左侧和右侧两侧交替的方式增加其顶点。

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).

您可以尝试用此code玩：

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
}

这code不是最优的，但它应该是很容易理解。在beginnig，凹多边形被创建。然后顶点的工作组创建。在那工作集，一个排列的计算方法进行排序的顶点由他们是坐标。该置换则环通，找分割点。一旦一个分割点被发现，一个新的单调多边形生成。然后，在新的多边形用的顶点从工作集合和重复整个过程除去。最后，工作组中包含的最后一个多边形而无法进行拆分。在结束时，单调多边形渲染，随着三角形条顺序。这是一个有点乱，但我相信你会找到答案（这是C ++ code，只要把它过剩窗口内，看看它做什么）。

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).

希望这有助于...

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

查看全文

多边形三角成三角形条带的OpenGL ES [英] Polygon triangulation into triangle strips for OpenGL ES

问题描述

推荐答案

相关文章

C/C++最新文章

热门教程

热门工具

登录关闭

多边形三角成三角形条带的OpenGL ES [英] Polygon triangulation into triangle strips for OpenGL ES

问题描述

推荐答案

相关文章

C/C++最新文章

热门教程

热门工具

登录 关闭

登录关闭