הפיכת פוליגון למשולשים.

[Ghosthunter]

שלום,

במסגרת פרוייקט שאני עושה בC# אני צריך להפוך פוליגון לקבוצת משולשים. הפוליגון יכול להיות קמור או קעור.(עבור קמור אין בעיה, הבעיה היא עבור קעור).

רציתי לדעת האם יש ספרייה מוכנה בBCL שמאפשרת לעשות את זה בקלות ויעילות. אם לא, אשמח לקבל קישורים למקורות בנושא(חיפוש בגוגל תחת מילת החיפוש polygon trianglize לא העלה הרבה).

אם ידוע לכם על תוכנה חיצונית שמאפשרת לעשות את זה, אודה לכם אם תרשמו את שמה. לא אכפת לי לבצע את ההמרה מחוץ לתוכנית שאני בונה, ולקרוא את הנתונים לאחר מכן מקובץ.

תודה,

אופיר תדמור.

[עמיר]

http://www.codeproject.com/csharp/cspolygontriangulation.asp?print=true

[DOGMA]

בOpenGL אם אתה רוצה לעשות משהו גס ופשוט, מכל פוליגון אתה לוקח את הקורדינאטות של הקודקודים שלו.

אתה צריך שיהיה סדר לוגי בין הקדקודים, כלומר שאם תעביר קו בין ק-1 -> ק-2 -> ק-3 -> ק-4 אתה תקבל את הצורה ההיקיפית של הפוליגון שלך.

בשביל זה יש לך LineStrip וLineLoop תלוי מה יותר יתאים לך. לאחר מכן אתה יכול להשתמש בTriangleFan שיוצר מכל 3 קודקודים משולש, אבל בצורה שכל המשולשים שאתה יוצר יהיו בעלי צלעות משותפות, כלומר ימלאו את כל הפוליגון שהיה לך.

[k-o-b-y]

http://www.flipcode.org/cgi-bin/fcarticles.cgi?show=63943

זה ב c++ אבל תוכל בקלות להמיר אותו ל C#.

[DOGMA]

http://www.flipcode.org/cgi-bin/fcarticles.cgi?show=63943

זה ב c++ אבל תוכל בקלות להמיר אותו ל C#.

זה קלאס שלם שעושה את זה, ממה שהבנתי המשימה שלו זה לייצור אלגוריתם שעושה את זה, לא ממש חוכמה כשמתשמים בפונקציה מוכנה.

[Ghosthunter]

תאמת היא שחשבתי על האלגוריתם הזה. רק לא חשבתי על הפונ הזוSnip שבודקת האם קיבלנו "אוזן"(שם מוזר) לא טובה.

הרעיון שלי היה לעבור פעם אחת ימינה, ופעם אחת שמאלה וליצור את המשולש. הבעיה היא הייתה שכאשר יש פוליגון קעור הייתה בעיה מכיוון שהיה חלק שעלה על השני(אפילו רשמתי את זה בהודדעה למעלה). לא חשבתי פשוט לבדוק אם יש נקודה בתוך המשולש.

תודה. עזרת לי.

רגע יש לי בעיה מסויימת, כנראה זה לא מה שחשבתי עליו. הוא הולך שם אחד אחרי השני, לא פעם ימינה פעם שמאלה.

אני לא בטוח שהפתרון הזה נכון בכלל. לא בכל הפעמים נקודה בתוך המשולש היא זו שצריכה לתת לי שגיאה

מקרה כזה לדוגמא:

    .   
 /    \ 
 /     \
.     .
|     |
|     |
.   .  .
 \  /\  /
 \/  \/
 .   . 

ומתחילים לבדוק מהנקודה האמצעית למטה.

[DOGMA]

בקשר לאוזניים, ההגדרת של אוזן היא משולש עם 2 צלעות על קצוות הפוליגון, וצלע אחת שכולה בתוכו.

הפוקציה עצמה היא רקורסיבית ומחפשת משולשים שתואמים להגדרה של אוזן, עד שנשאר שלך משולש אחד שלא תואם להגדרה.

יש לה רק בעיה אחת, היא עובדת על פוליגונים פשוטים בלבד, ברגע שיש לך פוליגון עם נקודות שחופפות אחת עם השניה במימד אחד או יותר יהיו לך בעיות.

יש עוד אלגוריתם שמשתמש בSweep line כדי למצוא את המשולשים

http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html

האלגוריתם הזה יהיה דיי איטי יחסית אבל הוא עובד, אם אתה רוצה להשתמש בAPI מוכן יש פונקציות שלמות שעושות את זה, זה אחד הדברים הראשונים שהוטמע בחומרה, כיוון שכל תהליך תוכניתי כזה הוא איטי להחריד.

[Ghosthunter]

בידיוק. יש לי בעיה למצוא האם כל הצלע בתוך הפוליגוו. אם יש נקודה בתוך המשולש, זו אכן לא אוזן, אך אם אין נקודה, יכולה להיות שזו לא אוזן עדיין.

אם יש בC# פונקציה מוכנה שעושה את זה אעדיף להשתמש בה משיקולי מהירות.

[DOGMA]

אתה יכול קודם כל לייצור את ההיקף של הפוליגון, ולאחר מכן אם יש 2 צלעות של משולש שחותכות אחת את השניה אז זה לא "אוזן".

שזה דיי דומה לפתרון הראשון שהצאתי לך, למרות שכאן לדעתי תצתרך לעבוד עם Surface normals, אבל כל עוד זה פוליגון פשוט אני לא מבין איפה הבעיה שלך.

הבעיה שלך תיהיה רק אם יש לך נקודה שחופפת במימד אחד עם המשולש, אבל לא באמת נמצאת "בתוכו", לדוגמא נקודנ שנמצאת מעל לפני שטח המשולש. כאן אתה תיהיה חייב להשתמש בsweep line, שאני אישית לא מכיר כלכך טוב, אבל שוב אני מציע לך לעבוד עם OpenGL או DirectDraw/3D בDraw יש אופציה לעבוד עם פוליגונים עם קודקודים תלת מיימדיים, בשביל RayCasting/SpriteCasting.

[Ghosthunter]

אז איך הופכים פוליגון למשולשים בDX?

[DOGMA]

אז איך הופכים פוליגון למשולשים בDX?

חפש DirectX polygon Tesselation

בOpenGL הקוד מסתכם בזה בערך..

GLU_TESS_BEGIN

This callback is invoked to indicate the start of a primitive, such as a triangle strip, a triangle fan, or a list of (unconnected) triangles.

void __stdcall begin(

GLenum type);

GLU_TESS_BEGIN_DATA

Same as GLU_TESS_BEGIN but takes the polygon_data parameter that was passed to the gluTessBeginPolygon function as an additional parameter.

void __stdcall beginData(

GLenum type,

void* polygon_data

);

GLU_TESS_END

This callback is invoked to indicate the end of a primitive.

void __stdcall end();

GLU_TESS_END_DATA

Same as GLU_TESS_END but takes the polygon_data parameter that was passed to the gluTessBeginPolygon function as an additional parameter.

void __stdcall endData(

void* polygon_data);

GLU_TESS_VERTEX

This callback is invoked any number of times between calls to the GLU_TESS_BEGIN and GLU_TESS_END callbacks. For a triangle list, for example, the GLU_TESS_VERTEX callback is called three times for each triangle.

void __stdcall vertex(

void* vertex_data);

GLU_TESS_VERTEX_DATA

Same as GLU_TESS_VERTEX but takes the polygon_data parameter that was passed to the gluTessBeginPolygon function as an additional parameter.

void __stdcall vertexData(

void* vertex_data,

void* polygon_data

);

GLU_TESS_EDGE_FLAG

This callback is used to indicate whether the following two vertices (as passed to the GLU_TESS_VERTEX callback) form a bounding edge, i.e., an edge that separates the polygon interior from the polygon exterior. When this callback is defined (whether or not you perform any action in the callback), the GLU tesselator converts all triangle strips and triangle fans to simple triangle lists.

void __stdcall edgeFlag(

GLboolean flag);

GLU_TESS_EDGE_FLAG_DATA

Same as GLU_TESS_EDGE_FLAG but takes the polygon_data parameter that was passed to the gluTessBeginPolygon function as an additional parameter.

void __stdcall edgeFlagData(

GLboolean flag,

void* polygon_data

);

GLU_TESS_COMBINE

This callback is invoked when a new vertex must be inserted, for example because two edges intersect. The GLU_TESS_COMBINE callback gives you a chance to add the new vertex to your internal vertex vector.

void __stdcall combine(

GLdouble coords[3],

void* vertex_data[4],

GLfloat weight[4],

void** outData

);

GLU_TESS_COMBINE_DATA

Same as GLU_TESS_COMBINE but takes the polygon_data parameter that was passed to the gluTessBeginPolygon function as an additional parameter.

void __stdcall combineData(

GLdouble coords[3],

void* vertex_data[4],

GLfloat weight[4],

void** outData,

void* polygon_data

);

GLU_TESS_ERROR

This callback is invoked when an error occurs.

void __stdcall error(

GLenum errno);

GLU_TESS_ERROR_DATA

Same as GLU_TESS_ERROR but takes the polygon_data parameter that was passed to the gluTessBeginPolygon function as an additional parameter.

void __stdcall errorData(

GLenum errno,

void* polygon_data

);

כל הפונקציות האלה הן חלק מה glu32.dll בC הספריית פונקציות שלהן נקראת glu.h.

בכל מקרה הGLU של הOpenGL עובד גם בDirect3D זה אחד הרכיבים היחידיים שמשותפים בין שני הAPIים, יכול להיות שסדר הקריאה והflagים קצת שונה לכן הייתי מחפש קוד או הסבר יותר מדוייק. בפורמים של MSDN עונים מהר יחסית.

כמו כן אתה יכול להעזר גם בזה http://www.codeproject.com/Purgatory/polygon_tesselation.asp.