تثليث المضلع إلى شرائح مثلثة لبرنامج OpenGL ES
https://stackoverflow.com/questions/8980379
-
12-11-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أبحث عن سريع خوارزمية التثليث المضلع يمكنها تثليث المضلعات المقعرة ثنائية الأبعاد غير المعقدة للغاية (بدون ثقوب) في شرائط المثلث جاهز لإرساله إلى 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/
- لا يحتوي على أي مثال مرتبط ولم أتمكن من العثور على أي شخص استخدمه بنجاح على iOS مع OpenGL ES 2.0
- لا أعرف ما الذي يُرجعه ويبدو أنه يستدعي أيضًا أوامر OpenGL المقابلة التي لا أريدها - أحتاج فقط إلى إرجاع المثلثات
- فإنه يسرب الذاكرة
المنصة التي أقوم بتطويرها هي:آي أو إس، برنامج OpenGL ES 2.0، cocos2d 2.0.
يمكن لأي شخص أن يساعدني مع مثل هذه الخوارزمية؟أو أي نصيحة أخرى سيكون موضع تقدير كبير.
المحلول
في الوضع ثنائي الأبعاد وبدون ثقوب، يعد هذا أمرًا سهلاً إلى حد ما.أولاً، تحتاج إلى تقسيم المضلع الخاص بك إلى واحد أو أكثر مضلعات رتيبة.
من السهل جدًا تحويل المضلعات الرتيبة إلى أشرطة ثلاثية، فقط قم بفرز القيم حسبها 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 وانظر ماذا يفعل).
أتمنى أن يساعدك هذا ...
نصائح أخرى
يمكنك استخراج خوارزمية التغطية بالفسيفساء من تطبيق نموذج OpenGL، كما هو موضح في هذا المنشور http://choruscode.blogspot.de/2013/03/extracting-tesselation-from-opengl.html ، وله أيضًا مثال.
