Vor einiger Zeit habe ich gefragt, wie man feststellt, wann ein Gesicht ein anderes überlappt. Der Rat war, einen Z-Puffer zu verwenden.
Ich kann jedoch keinen Z-Buffer in meinem aktuellen Projekt verwenden und möchte daher den Painter-Algorithmus verwenden. Ich habe allerdings keine Ahnung, wann sich eine Fläche hinter oder vor einer anderen befindet. Ich habe zahlreiche Methoden ausprobiert, aber alle scheitern in Randfällen oder sogar in allgemeinen Fällen.
Dies ist eine Liste der Sortiermethoden, die ich bisher ausprobiert habe:
- Abstand zum Mittelpunkt jedes Gesichts
- Durchschnittlicher Abstand zu jedem Scheitelpunkt jeder Fläche
- Durchschnittlicher z-Wert jedes Scheitelpunkts
- Höchster z-Wert der Eckpunkte jeder Fläche und zuerst zeichnen
- Niedrigster z-Wert der Eckpunkte jeder Fläche und zuletzt gezeichnete
Das Problem ist, dass ein Gesicht eine geringere Entfernung hat, aber immer noch weiter entfernt ist. Alle diese Methoden scheinen unzuverlässig.
Bearbeiten: Im folgenden Bild wird beispielsweise die Oberfläche mit dem blauen Punkt als Mittelpunkt über die Oberfläche mit dem roten Punkt als Mittelpunkt gezeichnet, da der blaue Punkt näher ist. Dies liegt jedoch daran, dass die Oberfläche des roten Punkts größer und der Mittelpunkt weiter entfernt ist. Die Oberfläche mit dem roten Punkt sollte über die blaue gemalt werden, da sie näher ist , während der Mittelpunktsabstand das Gegenteil besagt.
Was genau wird im Algorithmus des Malers verwendet, um die Reihenfolge zu bestimmen, in der Objekte gezeichnet werden sollen?
Antworten:
Normalerweise wird der Abstand des Mittelpunkts eines Polygons zur Kamera für die Z-Sortierung verwendet. Der Algorithmus des Malers kann von Natur aus nicht 100% genau sein. Es wird immer Fälle geben, in denen die Sortierung fehlschlägt, unabhängig davon, welchen Referenzpunkt Sie verwenden.
Wenn Sie mit dem Algorithmus des Malers eine korrekte Z-Sortierung erzielen möchten, müssen Sie überlappende Polygone in kleinere Teile aufteilen (z. B. mithilfe eines Quad-Baums) und diese Teile einzeln sortieren. Dies kann jedoch zu einer starken Belastung der CPU führen.
Ich habe diese Powerpoint-Datei gefunden , die das Problem gut illustriert ( PDF-Version ).
quelle
In solchen Fällen hat es bei mir immer mit BSP-Bäumen geklappt. Teilen Sie die Szene, bis Sie einen konvexen Satz von Polygonen im Knoten von bsp-tree haben. Anschließend können Sie Polygone innerhalb der Knoten problemlos sortieren. Beachten Sie, dass durch das Sortieren von Polygonen aus dem BSP-Baum-Knoten dasselbe Problem wie oben beschrieben auftritt, dass jedoch eine nicht so offensichtliche Bedingung vorliegt - nach dem Erstellen des BSP-Baums sind alle problematischen Fälle bereits gelöst -. Im Knoten sollten Sie enden Wenn Sie eine Ebene aus einem Polygon aus dieser Gruppe auswählen, befinden sich die restlichen Polygone entweder vor der Ebene oder hinter der Ebene. Die Verwendung dieser Informationen erleichtert das Sortieren. Der Sortierfunktor nimmt 2 Polygone auf. Überprüfen Sie, in welchem Halbraum das erste Polygon mit dem zweiten Polygon übereinstimmt, und überprüfen Sie auch die Platzierung der Kamera mit dem zweiten Polygon.
Beachten Sie auch, dass die Tests zur Bestimmung der Seite der Kameraposition gegen Polygone und zum Überqueren des bsp-Baums bei der orthografischen und perspektivischen Projektion geringfügig abweichen.
Wenn Sie es sich nicht leisten können, die Eingabepolygone aufzuteilen, haben Sie meines Erachtens Pech.
quelle