تقسيم النموذج ثلاثي الأبعاد بواسطة حلقة الحافة

Question

لدي نموذج ثلاثي الأبعاد، يمثل شيئًا مثل هذا:

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;
}

بالطبع يمكن تحويل هذا إلى أي تمثيل أكثر ملاءمة.

أريد تقسيم هذا النموذج إلى عدة أجزاء منفصلة، ​​على طول حلقات متعددة من الحواف المتصلة، وإنشاء وجوه جديدة لتغطية الأطراف.مثال مع حلقة واحدة:

يجب أن تكون الوجوه الجديدة في نفس الموضع، ومتطابقة بصرف النظر عن ارتباطاتها بالوجوه الأخرى، ولكن في هذا المثال قمت بفصلها عن بعضها البعض.كيف أستطيع فعل هذا؟

لا يهم إذا كانت القمم مشتركة بين الأجزاء المنفصلة.

وبما أن كل حافة تربط وجهين بالضبط، فقد حاولت تقسيم كل حافة على حدة إلى نسختين (واحدة لكل وجه).يؤدي هذا إلى فصل النموذج كما هو مطلوب، ولكن بعد ذلك لا أستطيع رؤية طريقة لإضافة الوجوه الجديدة بشكل صحيح.

تم وضع علامة على هذا السؤال بخوارزمية الرسم البياني لأن هذه المشكلة تبدو وكأنها مرتبطة بطريقة ما بنظرية الرسم البياني.

Answer 1

• أصلح النموذج الخاص بك. 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 يمثل الجزء الآخر.