Trong 2D và không có lỗ, điều này khá dễ dàng. Trước tiên, bạn cần phải chia đa giác của mình thành một hoặc nhiều monotone polygons.
Đa giác đơn điệu khá đơn giản để biến thành tristrips, chỉ cần sắp xếp các giá trị theo y, tìm đỉnh trên cùng và dưới cùng nhất, và sau đó bạn có danh sách các đỉnh ở bên phải và bên trái (vì đỉnh đi vào một số định nghĩa, theo chiều kim đồng hồ, trật tự). Sau đó, bạn bắt đầu với đỉnh trên cùng và thêm đỉnh từ bên trái và từ bên phải theo cách xen kẽ.
Kỹ thuật này sẽ hoạt động đối với mọi đa giác 2D không có các cạnh tự giao nhau, trong đó bao gồm một số trường hợp đa giác có lỗ (lỗ phải được vá chính xác).
Bạn có thể thử và chơi với mã nà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
}
Mã này không phải là tối ưu, nhưng nó phải là dễ hiểu. Khi bắt đầu, một đa giác lõm được tạo ra. Sau đó, một "bộ làm việc" của các đỉnh được tạo ra. Trên bộ làm việc đó, một hoán vị được tính toán sắp xếp các đỉnh theo tọa độ y của chúng. Sự hoán vị đó sau đó được lặp đi lặp lại, tìm kiếm các điểm phân tách. Sau khi tìm thấy điểm phân tách, một đa giác đơn âm mới được tạo. Sau đó, các đỉnh được sử dụng trong đa giác mới được lấy ra khỏi bộ làm việc và toàn bộ quá trình lặp lại. Cuối cùng, bộ làm việc chứa đa giác cuối cùng không thể tách rời. Cuối cùng, các đa giác đơn âm được trả lại, cùng với thứ tự dải tam giác. Đó là một chút lộn xộn, nhưng tôi chắc chắn bạn sẽ tìm ra nó (đây là mã C + +, chỉ cần đặt nó bên trong một cửa sổ GLUT và xem những gì nó làm).
Hope this helps ...
Mặc dù danh sách các hình tam giác có vẻ kém hiệu quả hơn một dải tam giác đơn, nó trả tiền khi bạn có nhiều hơn một đa giác lõm để vẽ (như một vật thể 3D thực được tạo từ chúng). Trong trường hợp này, bạn có thể vẽ toàn bộ đối tượng đa đa giác với một cuộc gọi vẽ duy nhất (nhiều danh sách tri có thể được nối thành một), trong khi với giải pháp dải tam giác bạn phải vẽ từng đa giác một cách ngẫu nhiên. Ngày nay giảm số lượng các cuộc gọi vẽ thường là một ý tưởng tốt hơn so với các đối tượng crunching vào một số nguyên thủy tinh vi, như tri-strips. Tôi đoán điều này cũng áp dụng cho các thiết bị ES ngày nay. –
Nếu bạn có một đối tượng hoàn toàn, tốt hơn là biến nó thành hình tam giác và đưa nó vào một thư viện sẽ tạo ra các dải tam giác, chẳng hạn như nvTriStrip hoặc Stripifier. Điều đó có thể được thực hiện ngoại tuyến trên PC vì vậy người ta không cần phải bận tâm chuyển thư viện sang iOS. Các thiết bị này cũng thường hỗ trợ khởi động lại nguyên thủy, cho phép ghép nối các tristrip để có thể render chúng bằng một lệnh đơn. Và sau đó có glMultiDrawElements() hoặc các dải thoái hóa. –