تقسيم النموذج ثلاثي الأبعاد بواسطة حلقة الحافة
-
21-12-2019 - |
سؤال
لدي نموذج ثلاثي الأبعاد، يمثل شيئًا مثل هذا:
class Vertex
{
double x, y, z;
}
class Edge
{
Vertex *v1, *v2; // no particular order
Face *f1, *f2; // no particular order. f2 may be null.
}
class Face
{
List<Vertex*> vertices; // clockwise order
List<Edge*> edges; // clockwise order
}
class Model
{
List<Face*> faces;
List<Vertex*> vertices;
List<Edge*> edges;
}
بالطبع يمكن تحويل هذا إلى أي تمثيل أكثر ملاءمة.
أريد تقسيم هذا النموذج إلى عدة أجزاء منفصلة، على طول حلقات متعددة من الحواف المتصلة، وإنشاء وجوه جديدة لتغطية الأطراف.مثال مع حلقة واحدة:
يجب أن تكون الوجوه الجديدة في نفس الموضع، ومتطابقة بصرف النظر عن ارتباطاتها بالوجوه الأخرى، ولكن في هذا المثال قمت بفصلها عن بعضها البعض.كيف أستطيع فعل هذا؟
لا يهم إذا كانت القمم مشتركة بين الأجزاء المنفصلة.
وبما أن كل حافة تربط وجهين بالضبط، فقد حاولت تقسيم كل حافة على حدة إلى نسختين (واحدة لكل وجه).يؤدي هذا إلى فصل النموذج كما هو مطلوب، ولكن بعد ذلك لا أستطيع رؤية طريقة لإضافة الوجوه الجديدة بشكل صحيح.
تم وضع علامة على هذا السؤال بخوارزمية الرسم البياني لأن هذه المشكلة تبدو وكأنها مرتبطة بطريقة ما بنظرية الرسم البياني.
المحلول
- أصلح النموذج الخاص بك.
class Edge
يجب أن تحمل مؤشرات لFace
وVertex
بدلا من القيم. - تريد استخدام نوع من
set
بدلاً منList
داخل الخاص بكclass Model
.يساعد هذا في العثور على الأشياء وإزالتها، والتأكد من عدم وجود تكرارات.
- ابتكر نموذجًا أوليًا لوظيفتك.أقترح
pair<Model*, Model*> split_model( const Model* mx, const List<Edge*>& loop );
- إنشاء نموذجين جديدين وفارغين، على سبيل المثال
ma
وmb
.أضف الحواف منloop
لكل واحد منهم. - اختر حافة واحدة من
loop
.لنسمي الوجهين المرتبطين بهfa
وfb
. - يضيف
fa
إلى النموذجma
.بدءا منfa
, ، قم بإجراء بحث كامل في الرسم البياني باتباع جميع الحواف المرفقة بهfa
, ، وكل الوجوه ملتصقة بتلك الحواف، وهكذا.يجب متابعة جميع الوجوه والحواف التي تمت مواجهتها وإضافتها إلى النموذجma
.إذا واجهت وجوهًا أو حوافًا تعد جزءًا منها بالفعلma
أنت لا تتبعهم.وهذا ما يحدث على وجه الخصوص عندما تواجه حافة تنتمي إليهاloop
لذلك لن تعبر الحدود أبدًا.بهذه الطريقة تقوم بإجراء بحث كامل لجميع الحواف والوجوه على جانب واحد وينتهي بك الأمر بنموذج كاملma
.وأخيرا قمت بإضافة وجه يمثل القطع.يمكن تجاهل القمم في الغالب هنا، ولكن بالطبع في النهاية ربما تريد إضافة جميع القمم التي تنتمي إلى الوجوه التي أضفتها. - كرري هذه الخطوة بدءًا من الوجه
fb
لإنشاء النموذجmb
يمثل الجزء الآخر.