Diviser le modèle 3D par boucle de bord

Question

J'ai un modèle 3D, représenté quelque chose comme ceci :

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

Bien sûr, cela peut être transformé en la représentation la plus pratique.

Je souhaite diviser ce modèle en plusieurs parties déconnectées, le long de plusieurs boucles d'arêtes connectées, et créer de nouvelles faces pour coiffer les extrémités.Exemple avec une seule boucle :

Les nouvelles faces doivent être dans la même position et identiques en dehors de leurs connexions avec d'autres faces, mais pour cet exemple, je les ai éloignées.Comment pourrais-je faire ça ?

Peu importe si les sommets sont partagés entre les parties autrement déconnectées.

Étant donné que chaque arête relie exactement deux faces, j'ai essayé de diviser chaque arête individuellement en deux copies (une pour chaque face).Cela sépare le modèle selon les besoins, mais je ne vois pas de moyen d'ajouter correctement les nouveaux visages.

Cette question est étiquetée algorithme graphique car ce problème semble être lié d'une manière ou d'une autre à la théorie des graphes.

Answer 1

• Corrigez votre modèle. class Edge devrait contenir des pointeurs vers Face et Vertex au lieu de valeurs.
• Vous souhaitez utiliser une sorte de set au lieu de List au sein de votre class Model.Cela aide à rechercher et à supprimer des éléments, et vous assure qu'il n'y a pas de doublons.

• Créez un prototype de votre fonction.je suggère

pair<Model*, Model*> split_model( const Model* mx, const List<Edge*>& loop );

• créer deux nouveaux modèles vides, disons ma et mb.Ajoutez les bords de loop à chacun d'eux.
• choisissez un bord du loop.Appelons les deux visages qui y sont attachés fa et fb.
• ajouter fa au modèle ma.A partir de fa, effectuez une recherche graphique complète en suivant toutes les arêtes attachées à fa, et toutes les faces attachées à ces bords, et ainsi de suite.Toutes les faces et arêtes rencontrées doivent être suivies et ajoutées au modèle ma.Si vous rencontrez des faces ou des arêtes qui font déjà partie de ma vous ne les suivez pas.En particulier, c'est ce qui se produit chaque fois que vous rencontrez un bord appartenant à loop donc vous ne traversez jamais la frontière.De cette façon, vous effectuez une recherche complète de toutes les arêtes et faces d'un côté et vous obtenez un modèle complet. ma.Enfin vous ajoutez une face représentant la coupe.Les sommets peuvent être pour la plupart ignorés ici, mais bien sûr, à la fin, vous souhaiterez probablement ajouter tous les sommets appartenant aux faces que vous avez ajoutées.
• Répétez cette étape en commençant par le visage fb pour créer le modèle mb représentant l’autre partie.