المضلع التثليث مع ثقوب
https://stackoverflow.com/questions/406301
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أبحث عن خوارزمية أو مكتبة (أفضل) لكسر المضلع إلى مثلثات.وسوف تستخدم هذه المثلثات في Direct3D التطبيق.ما هي أفضل الخيارات المتاحة ؟
هنا هو ما وجدت حتى الآن:
- بن Discoe ملاحظات
- قبضة:سريع الصناعية-قوة التثليث من المضلعات
- وأنا أعلم أن CGAL يوفر التثليث ولكن لست متأكدا إذا كان يدعم الثقوب.
أقدر لك بعض الآراء من ذوي الخبرة السابقة في هذا المجال.
تحرير:هذا هو 2D المضلع.
المحلول
جوناثان Shewchuk هو مثلث المكتبة هي الهائل ؛ أنا استخدامها لأتمتة التثليث في الماضي.يمكنك أن تطلب إلى محاولة تجنب الصغيرة/ضيق مثلثات ، وما إلى ذلك ، إذا كنت تأتي مع "جيدة" triangulations بدلا من مجرد أي التثليث.
نصائح أخرى
لتعطيك المزيد من الخيارات من المكتبات هناك:
Polyboolean.لم يسبق لي أن حاولت هذا واحد ، ولكن يبدو واعدا: http://www.complex-a5.ru/polyboolean/index.html
العامة المضلع المقص.هذا يعمل بشكل جيد جدا في الممارسة ولا التثليث وكذلك لقطة و الثقوب ثقوب: http://www.cs.man.ac.uk/~توبي/آلان/البرامج/
توصيتي الشخصية:استخدام tesselation من غلو (OpenGL فائدة المكتبة).رمز هو الصخرة الصلبة أسرع من المؤتمر الشعبي العام يولد أقل مثلثات.أنت لا تحتاج إلى تهيئة OpenGL-مقبض أو أي شيء من هذا القبيل استخدام lib.
إذا كنت لا تحب فكرة أن تشمل OpenGL نظام يبس في تطبيق DirectX هناك حل أيضا:مجرد تحميل SGI OpenGL الإشارة كود التنفيذ ورفع triangulator من ذلك.هو فقط يستخدم OpenGL-Typedef أسماء اليد كاملة من enums.هذا هو.يمكنك استخراج رمز قائمة بذاتها ليب في ساعة أو ساعتين.
عموما نصيحتي أن يكون استخدام شيء alreay يعمل و لا تبدأ في الكتابة الخاصة بك التثليث.
فمن المغري أن لفة الخاص بك إذا كنت قد قرأت عن الأذن-لقطة أو اكتساح خط الخوارزمية ، ولكن الواقع هو أن الهندسة الحسابية الخوارزميات لا يصدق من الصعب أن تكتب في الطريقة التي عمل ثابت, أبدا تحطم العودة دائما نتيجة مجدية.العددية roundoff الأخطاء تتراكم وقتل في نهاية المطاف.
كتبت التثليث الخوارزمية في ج عن الشركة التي أعمل معها.الحصول على الخوارزمية الأساسية العمل استغرق يومين.الحصول على العمل مع جميع أنواع تحولت المدخلات استغرق عامين آخرين (لم أكن أعمل بدوام كامل على ذلك, ولكن ثق بي - قضيت المزيد من الوقت على ذلك مما يجب).
CGAL وقد الأداة التي تحتاج إليها:مقيدة Triangulations
يمكنك ببساطة تقديم حدود المضلع الخاص بك (بما في ذلك حدود الثقوب) كما قيود (أفضل أن يكون إدراج جميع القمم ، ومن ثم تحديد القيود أزواج Vertex_handles).
ثم يمكنك الوسم مثلثات من التثليث أي اجتياز الخوارزمية:تبدأ مع مثلث الحادث إلى لانهائية vertex الوسم كما يجري في الخارج ، وفي كل مرة كنت عبور عقبة التبديل إلى الآخر الوسم (الداخل إذا كانت علامات مثلثات كما من الخارج, الخارج إذا كانت علامات مثلثات من الداخل كما من قبل).
لقد وجدت poly2tri المكتبة أن تكون بالضبط ما كنت بحاجة للحصول على التثليث.وتنتج الكثير من نظافة مش من مكتبات أخرى لقد حاولت (بما في ذلك libtess), وأنه لا دعم الثقوب أيضا.إنه تم تحويلها إلى مجموعة من اللغات.الترخيص جديد BSD, لذا يمكنك استخدامه في أي مشروع.
يمكنك إضافة الثقوب بسهولة نسبيا نفسك.أساسا تثليث إلى بدن محدب من المدخلات نقطة ، كما في CGAL ثم حذف أي المثلث الذي incentre يكمن داخل أي من ثقب المضلعات (أو الخارج أي من الحدود الخارجية).عند التعامل مع الكثير من الثقوب في بيانات كبيرة, تقنيات اخفاء يمكن أن تستخدم إلى حد كبير في سرعة هذه العملية.
تحرير:امتداد شائع أن هذا الأسلوب هو أن الحشيش ضعيفة مثلثات على بدن, حيث أطول حافة أو أصغر زاوية داخلي يتجاوز قيمة معينة.هذا النموذج أفضل مقعر هال.
محاولة libtess2
https://code.google.com/p/libtess2/downloads/list
على أساس الأصلي SGI غلو tesselator (مع الليبرالية الترخيص).يحل بعض مشاكل إدارة الذاكرة حول الكثير من الصغيرة mallocs.
هذه مشكلة شائعة في تحليل العناصر المحدودة.انه دعا "مش التلقائي جيل".جوجل وجدت هذا الموقع مع الروابط التجارية والبرمجيات مفتوحة المصدر.وعادة ما يفترض نوعا من CAD تمثيل الهندسة للبدء.
خيار آخر (مع مرنة جدا رخصة) هو ميناء الخوارزمية من VTK:
هذه الخوارزمية تعمل بشكل جيد إلى حد ما.استخدامه مباشرة ممكن لكنه يتطلب الروابط VTK ، والتي قد يكون لها أكثر الحمل من تريد (على الرغم من أنه لديه العديد من الميزات الأخرى لطيفة ، وكذلك).
وهو يدعم القيود (الثقوب/حدود/الخ) ، وكذلك تثليث السطح الذي ليس بالضرورة في XY.كما يدعم بعض الميزات أنا لم أر في أي مكان آخر (انظر الملاحظات على القيم ألفا).
لقد نفذت 3D المضلع triangulator في C# باستخدام الأذن لقطة الأسلوب.فمن السهل الاستخدام, يدعم الثقوب ، العدد القوية ، ويدعم aribtrary (ليس الذاتي المتقاطعة) محدب/غير محدب المضلعات.
