Dividi il modello 3D per loop del bordo

Question

Ho un modello 3D, rappresentato qualcosa del genere:

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

Naturalmente questo può essere trasformato in qualunque rappresentazione sia più conveniente.

Voglio dividere questo modello in più parti sconnesse, lungo più anelli di bordi collegati e creare nuove facce per coprire le estremità.Esempio con un ciclo:

I nuovi volti dovrebbero essere nella stessa posizione e identici a parte le connessioni con gli altri volti, ma per questo esempio li ho spostati.Come potrei farlo?

Non importa se i vertici sono condivisi tra le parti altrimenti disconnesse.

Poiché ogni bordo collega esattamente due facce, ho provato a dividere ciascun bordo individualmente in due copie (una per ciascuna faccia).Questo separa il modello come richiesto, ma non riesco a vedere un modo per aggiungere correttamente i nuovi volti.

Questa domanda è etichettata come algoritmo dei grafi perché questo problema sembra essere in qualche modo correlato alla teoria dei grafi.

Answer 1

• Correggi il tuo modello. class Edge dovrebbe contenere puntatori a Face E Vertex invece che valori.
• Vuoi usare qualche tipo di set invece di List dentro il tuo class Model.Questo aiuta a trovare e rimuovere cose e ti assicuri che non ci siano duplicati.

• Realizza un prototipo della tua funzione.suggerisco

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

• creare due nuovi modelli vuoti, diciamo ma E mb.Aggiungi i bordi da loop a ciascuno di essi.
• scegli un bordo da loop.Chiamiamo le due facce ad esso collegate fa E fb.
• aggiungere fa al modello ma.A partire da fa, esegui una ricerca grafica completa seguendo tutti gli spigoli collegati a fa, e tutte le facce collegate a tali bordi e così via.Tutte le facce e i bordi incontrati devono essere seguiti e aggiunti al modello ma.Se incontri facce o bordi che fanno già parte ma non li segui.In particolare questo è ciò che accade ogni volta che si incontra un bordo che gli appartiene loop quindi non attraversi mai il confine.In questo modo esegui una ricerca completa di tutti i bordi e le facce su un lato e ti ritroverai con un modello completo ma.Infine aggiungi una faccia che rappresenta il taglio.I vertici possono essere per lo più ignorati qui, ma ovviamente alla fine probabilmente vorrai aggiungere tutti i vertici che appartengono alle facce che hai aggiunto.
• Ripeti questo passaggio partendo dal viso fb per creare il modello mb rappresentare l'altra parte.