3D-Modell durch Kantenschleife teilen
-
21-12-2019 - |
Frage
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.
Lösung
- Reparieren Sie Ihr Modell.
class Edge
sollte Hinweise darauf enthaltenFace
UndVertex
statt Werte. - Sie möchten eine Art verwenden
set
anstattList
in deinemclass 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
Undmb
.Fügen Sie die Kanten hinzuloop
zu jedem von ihnen. - Wählen Sie eine Kante aus
loop
.Nennen wir die beiden damit verbundenen Gesichterfa
Undfb
. - hinzufügen
fa
zum Modellma
.Abfa
, führen Sie eine vollständige Diagrammsuche durch, indem Sie allen angeschlossenen Kanten folgenfa
, und alle an diesen Kanten befestigten Flächen usw.Alle angetroffenen Flächen und Kanten müssen befolgt und dem Modell hinzugefügt werdenma
.Wenn Sie auf Flächen oder Kanten stoßen, die bereits Teil von sindma
du folgst ihnen nicht.Dies geschieht insbesondere immer dann, wenn Sie auf eine Kante stoßen, die zu gehörtloop
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 Modellma
.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 erstellenmb
repräsentiert den anderen Teil.