3D-Modell durch Kantenschleife teilen

Question

Ich habe ein 3D-Modell, das etwa so dargestellt ist:

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

Natürlich kann dies in die Darstellung umgewandelt werden, die am bequemsten ist.

Ich möchte dieses Modell entlang mehrerer Schleifen verbundener Kanten in mehrere getrennte Teile aufteilen und neue Flächen erstellen, um die Enden abzudecken.Beispiel mit einer Schleife:

Die neuen Flächen sollten sich an derselben Position befinden und abgesehen von ihren Verbindungen zu anderen Flächen identisch sein, aber für dieses Beispiel habe ich sie auseinander verschoben.Wie könnte ich das machen?

Es spielt keine Rolle, ob Scheitelpunkte zwischen den ansonsten getrennten Teilen geteilt werden.

Da jede Kante genau zwei Flächen verbindet, habe ich versucht, jede Kante einzeln in zwei Kopien aufzuteilen (eine für jede Fläche).Dadurch wird das Modell zwar nach Bedarf getrennt, aber dann sehe ich keine Möglichkeit, die neuen Flächen korrekt hinzuzufügen.

Diese Frage trägt den Tag „Graph-Algorithmus“, da dieses Problem irgendwie mit der Graphentheorie zusammenhängt.

Answer 1

• Reparieren Sie Ihr Modell. class Edge sollte Hinweise darauf enthalten Face Und Vertex statt Werte.
• Sie möchten eine Art verwenden set anstatt List in deinem class Model.Dies erleichtert das Auffinden und Entfernen von Dingen und stellt sicher, dass keine Duplikate vorhanden sind.

• Überlegen Sie sich einen Prototyp Ihrer Funktion.Ich schlage vor

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

• Erstellen Sie beispielsweise zwei neue, leere Modelle ma Und mb.Fügen Sie die Kanten hinzu loop zu jedem von ihnen.
• Wählen Sie eine Kante aus loop.Nennen wir die beiden damit verbundenen Gesichter fa Und fb.
• hinzufügen fa zum Modell ma.Ab fa, führen Sie eine vollständige Diagrammsuche durch, indem Sie allen angeschlossenen Kanten folgen fa, und alle an diesen Kanten befestigten Flächen usw.Alle angetroffenen Flächen und Kanten müssen befolgt und dem Modell hinzugefügt werden ma.Wenn Sie auf Flächen oder Kanten stoßen, die bereits Teil von sind ma du folgst ihnen nicht.Dies geschieht insbesondere immer dann, wenn Sie auf eine Kante stoßen, die zu gehört loop Sie überschreiten also nie die Grenze.Auf diese Weise führen Sie eine vollständige Suche aller Kanten und Flächen auf einer Seite durch und erhalten am Ende ein vollständiges Modell ma.Zum Schluss fügen Sie eine Fläche hinzu, die den Schnitt darstellt.Die Scheitelpunkte können hier größtenteils ignoriert werden, aber natürlich möchten Sie am Ende wahrscheinlich alle Scheitelpunkte hinzufügen, die zu den von Ihnen hinzugefügten Flächen gehören.
• Wiederholen Sie diesen Schritt beginnend mit dem Gesicht fb um das Modell zu erstellen mb repräsentiert den anderen Teil.