algorithm - 多边形三角剖分为 OpenGL ES 的三角形带

标签 algorithm cocos2d-iphone opengl-es-2.0 triangulation gl-triangle-strip

我正在寻找一种快速的多边形三角剖分算法，它可以将不是很复杂的 2D 凹多边形(没有孔)三角剖分成三角形带，准备发送到 OpenGL ES使用 GL_TRIANGLE_STRIP 绘图。

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

我开发的平台是:iOS、OpenGL ES 2.0、cocos2d 2.0。

谁能帮我做这样的算法？或者任何其他建议将不胜感激。

最佳答案

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

单调多边形很容易变成三 strip ，只需按 y 对值进行排序，找到最顶部和最底部的顶点，然后你就有了右边的顶点列表和向左(因为顶点以某种定义的顺序出现，比如顺时针顺序)。然后从最顶部的顶点开始，以交替方式从左侧和右侧添加顶点。

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

您可以尝试使用此代码:

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 坐标对顶点进行排序。然后循环该排列，寻找 split 点。一旦找到分割点，就会创建一个新的单调多边形。然后，将新多边形中使用的顶点从工作集中移除，并重复整个过程。最后，工作集包含最后一个无法拆分的多边形。最后，呈现单调多边形以及三角形带排序。它有点困惑，但我相信您会弄明白(这是 C++ 代码，只需将它放在 GLUT 窗口中，看看它会做什么)。

希望这有助于...

关于algorithm - 多边形三角剖分为 OpenGL ES 的三角形带，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8980379/

上一篇：algorithm - 以AI方式解决Hangman

下一篇：algorithm - 旧顶级编码器谜语 : Making a number by inserting +

相关文章：

iphone - 使用 Cocos2d 自动 Sprite 动画

ios - iPhone Multiplayer Code 有效，但 iPad 无效。委托(delegate)问题？

iphone - 编写 GLKBaseEffect 替代品

algorithm - 给定方向上两个凹多边形之间的交点

algorithm - 使用通配符对卡片进行排序

ios - 是否可以将声音和效果添加到 Cocos2D 中的动画 plist

java - 从 OpenGL ES 2.0 中读取纹理

使用 OpenGL ES 2.0 的 Android 绘图纹理在某些设备上运行缓慢

algorithm - 包装矩形 IOI 95

c++ - 散列范围为 10 亿的 100 个不同的值

©2024 IT工具网  联系我们