Polygone sortieren - funktioniert das nicht?

Ich bin ziemlich neu in der Programmierung in einer 3D-Welt.

Ich versuche, eine Leinwand zu erstellen, auf der alle Objekte in der Reihenfolge vom weitesten zum nächsten und von unten nach oben gezeichnet werden - damit sie sich nicht überlappen, aber es gibt Probleme.

Geben Sie hier die Bildbeschreibung ein

Wie Sie sehen können, überlappen sich einige der Objekte. Keines der Objekte auf dem Bildschirm bewegt sich, daher habe ich mich gefragt: Gibt es einen Algorithmus, um die Objekte in der richtigen Reihenfolge zu sortieren? Im Moment habe ich sie in der Z-Achse aufsteigend sortiert, dann X absteigend und Y absteigend.

c# 3d isometric Peter
quelle

Ich werde nur willkürlich fragen, da Sie sagten, Sie sind neu in der 3D-Programmierung, nicht die Engine, die Sie verwenden, unterstützt Tiefenprüfungen? Die Tiefensortierung bringt Sie nur so weit. Selbst wenn Sie dieses eine Problem lösen, verursachen L- oder T-förmige Blöcke beispielsweise Artefakte

Dreta

+1, da dies ein Thema ist, das für 3D im Allgemeinen von großem Interesse ist und Ihre Illustration großartig ist.

Patrick Hughes

Antworten:

Wie in den Kommentaren von @dreta erwähnt, lösen 3D-Engines dies normalerweise mit einem Tiefenpuffer und unter Verwendung des Hardware-Tiefentests, mit dem Sie beliebig geformte Objekte in beliebiger Reihenfolge zeichnen und die nächstgelegene Oberfläche an jedem Pixel verfolgen können . Das manuelle Sortieren von Objekten ist ebenfalls möglich, behandelt jedoch nicht unbedingt nicht konvexe Objekte oder überlappende Objekte nicht korrekt.

Wenn Sie jedoch Objekte sortieren möchten, müssen Sie für jedes Objekt einen Tiefenwert berechnen und dann nach absteigender Tiefe sortieren. Um die Tiefe zu ermitteln, müssen Sie bei Verwendung eines typischen 3D-Engine-Setups den Mittelpunkt jedes Objekts durch Ihre Ansichtsmatrix (die vom Weltraum zum Ansichtsraum verläuft) transformieren und dann das Negativ der Z-Koordinate von nehmen das Ergebnis. (Negativ, da in rechtshändigen Koordinaten mit X und Y, die am Bildschirm ausgerichtet sind, Z aus dem Bildschirm zeigt.)

Wenn es sich immer um eine isometrische Ansicht wie diese handelt, können Sie wahrscheinlich mit der Berechnung der Tiefe = ± X ± Y - Z davonkommen, wobei ± bedeutet: Wählen Sie das Zeichen, das die Tiefe erhöht, wenn Sie sich weiter von der Kamera entfernen. Dies hängt von der Ausrichtung Ihrer X- und Y-Achse ab.

Nathan Reed
quelle

Selbst mit einer isometrischen Ansicht ist es nicht möglich, Formen anhand eines Tiefenwerts zu sortieren. Das einzige, was Sie tun können, vorausgesetzt, die Formen und die Szenenorganisation sind nicht zu kompliziert (und dies ist normalerweise der Fall ), ist eine Teilreihenfolge zu erstellen ( dh bei zwei Formen anzugeben, welche zuerst gezeichnet werden soll). Aus diesem Grund müssten Sie die Formen sortieren (z. B. mit topologischer Sortierung), und das allein ist normalerweise eine O (n²) -Operation, wenn Sie Glück haben, aber ich wette stattdessen auf O (n²logn).

Sam Hocevar

@SamHocevar Ja, wie ich in meiner Antwort festgestellt habe, behandelt die Objektsortierung nach Tiefe nicht alle Fälle korrekt, insbesondere (aber nicht beschränkt auf) nicht konvexe oder überlappende Objekte. Es ist bestenfalls eine Annäherung. Übrigens glaube ich, dass das topologische Sortieren eines Graphen immer in O (V + E) erfolgen kann (es ist so ziemlich nur DFS). Die Kantenzahl kann O (V ^ 2) sein, aber ich vermute, dass es normalerweise nicht so schlimm ist.

Nathan Reed

@SamHocevar In einer isometrischen Ansicht mit allen Objekten nicht schneidende Achse ausgerichteten Rechtecken, obwohl - das ist , was das Beispiel zeigt - es scheint wahrscheinlich , dass Sie wahrscheinlich können Formen sortieren? Kennen Sie eine Konstruktion einer Figur, die unter diesen Bedingungen nicht sortiert werden kann (z. B. etwas, das eine zyklische Überlappung aufweist)?

Steven Stadnicki

@StevenStadnicki Hier ist ein Fall, in dem eine naive Sortierung nach Tiefe nicht funktionieren würde. Die richtige Zeichenreihenfolge in diesem Diagramm wäre Rot, Grün, Blau, aber die Tiefensortierung basierend auf der Mitte jedes Rechtecks (schwarze Punkte) würde Blau, Grün, Rot ergeben. (Die gepunktete Linie verläuft senkrecht zur Ansicht, sodass Sie die Beziehung zwischen den Tiefen der Zentren klar erkennen können.) Sams topologische Sortierung würde hier funktionieren, um die "Ist-Hinter" -Relationen zwischen den Rechtecken zu bestimmen.

Nathan Reed

Hier ist ein Beispiel für achsenausgerichtete

sam hocevar

Schauen Sie sich den Painters-Algorithmus und seine Nachteile an.

Valmond
quelle

Im Allgemeinen lautet die Antwort auf Ihre Frage ("Gibt es einen Algorithmus zum Sortieren der Objekte in der richtigen Reihenfolge?") In beliebigen 3D-Einstellungen " Nein" - ein solcher Algorithmus kann nicht existieren, selbst wenn die Objekte so einfach wie Dreiecke sind. Es ist einfach, drei Dreiecke mit einer zyklischen Überlappung zu konstruieren. Stellen Sie sich zum Beispiel vor, Sie blicken entlang der Z-Achse auf drei lange, dünne Dreiecke:

A: (2,1, 1,9, 1), (1,9, 2,1, 1), (-1, -1, 0)
B: (-2,1, 1,9, 0), (-1,9, 2,1, 0), (1, -1, 1)
C: (2,1, 1, 0), (1,9, 1, 0), (-2, 1, 1)

Wenn sich A und B auf dem Bildschirm überlappen (in der Nähe des XY-Punkts (0,0)), befindet sich B oben (hat den höheren Z-Wert): Sein Z-Wert beträgt ungefähr 0,66, während A ungefähr 0,33 beträgt. In ähnlicher Weise befindet sich A oben, wenn sich A und C überlappen (nahe dem XY-Punkt (1, 1)). und wo sich B und C überlappen (nahe dem XY-Punkt (1, -1)), ist C oben. Es gibt keine Möglichkeit, diese drei Dreiecke so zu ordnen, dass das Zeichnen in der angegebenen Reihenfolge das richtige Ergebnis liefert.

Wie Nathan Reed vorschlägt, bedeutet die Tatsache, dass Sie sich in einer isometrischen Ansicht befinden, dass Sie dieses spezielle Problem wahrscheinlich vermeiden können. Die Frage ist, ob es sich lohnt, dies zu vermeiden oder nicht. Dies hängt mehr von Ihrer Umgebung und den verfügbaren Funktionen ab. Die meisten Plattformen, auf denen Sie entwickeln könnten, verfügen jedoch über mindestens eine Form von 3D-Rendering, und meine erste Neigung wäre, für Ihre Zwecke nur darüber hinaus zu huckepack.

Steven Stadnicki
quelle