В 2D и без отверстий это довольно легко. Во-первых, вам нужно разбить свой многоугольник на один или несколько monotone polygons.
Монотонные многоугольники довольно просто превратить в трехцветные, просто отсортируйте значения по 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. Эта перестановка затем зацикливается, ища точки разделения. После обнаружения точки разделения создается новый монотонный многоугольник. Затем вершины, используемые в новом многоугольнике, удаляются из рабочего набора, и весь процесс повторяется. Наконец, рабочий набор содержит последний многоугольник, который нельзя разбить. В конце отображаются монотонные многоугольники, а также порядок треугольной полосы. Это немного беспорядочно, но я уверен, что вы это выясните (это код на C++, просто поместите его в окно GLUT и посмотрите, что он делает).
Надеется, что это помогает ...
Хотя список треугольников может казаться менее эффективным, чем одна полоса треугольника, он платит, когда у вас есть более чем один такой вогнутый многоугольник для рисования (например, из реального 3D-объекта, построенного из них). В этом случае вы можете нарисовать весь многопользовательский объект с помощью одного вызова рисования (многие три-листы могут быть объединены в один), тогда как при решении треугольной полосы вы должны индивидуально рисовать каждый полигон. В настоящее время сокращение количества обратных вызовов часто является лучшей идеей, чем хруст объектов в некоторые сложные примитивы, например три-полоски. Я думаю, это также относится к сегодняшним ES-устройствам. –
Если у вас есть целый объект, лучше превратить его в треугольники и подать в библиотеку, которая будет генерировать треугольные полосы, такие как nvTriStrip или Stripifier. Это можно сделать офлайн на ПК, поэтому вам не нужно беспокоиться о переносе библиотеки на iOS. Устройства также обычно поддерживают примитивный перезапуск, что позволяет объединять трискапы с возможностью их рендеринга с использованием одной команды. И тогда есть glMultiDrawElements() или вырожденные полосы. –