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

我正在寻找一种快速的 ,该 可以将不是很复杂的2D凹面多边形(无孔) 分成

准备发送给OpenGL ES进行绘制GL_TRIANGLE_STRIP

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

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

    • 该算法可以正常工作,但问题是它返回了无法使用的简单三角形GL_TRIANGLE_STRIP,需要使用GL_TRIANGLES它,在大量顶点上效率不高。

  • http://code.google.com/p/iphone-glu/

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

我正在开发的平台是:iOS,OpenGL ES 2.0,cocos2d 2.0。

谁能帮我一个这样的算法?或任何其他建议将不胜感激。

回答:

在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 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窗口中,然后看它能做什么)。

希望这可以帮助 …

以上是 OpenGL ES的多边形三角剖分成三角形带 的全部内容, 来源链接: utcz.com/qa/410628.html

回到顶部