Tiefensortierverfahren

Maler-Algorithmus (painters-algorithm)

Idee: Sortiere die zu zeichnenden Polygone so, dass die Liste vollständig von ``hinten nach vorne'' (oder auch von vorne nach hinten) gezeichnet werden kann.

Problem: Wie bestimmt man die Zeichenreihenfolge?

Beschränken wir uns auf die Darstellung von Polygonen (Fassetten von Polyedern).

Wir benötigen eine Vergleichsfunktion, die für zwei gegebene Flächen entscheidet, welche von beiden zuerst gezeichnet werden soll.

Leider liefert uns eine solche Vergleichsfunktion keine Ordnung auf den Flächen, wie folgendes Beispiel zeigt:

Mit anderen Worten, es gibt Situationen, die zyklische Überlappungen beinhalten; diese müssen einerseits erkannt und andererseits aufgelöst werden.

Im ersten Schritt sortiert man die Polygone entsprechend der minimalen $z$-Koordinate seiner Ecken.

Hierbei sollte man darauf achten, ein ``gutartiges'' Sortierverfahren zu verwenden, da in der Praxis davon auszugehen ist, dass die Polygone im Wesentlichen fast sortiert vorliegen. Dies hat zwei Gründe: die Polygone sind bereits durch die Modellierung angeordnet, oder wird die Kameraposition (geringfügig) bewegt, so bleibt die Sortierung erhalten.

Im zweiten Schritt wird die im ersten Schritt erzeugte Liste von hinten nach vorne abgearbeitet, dabei führt man weitere Vergleiche durch, um sicherzustellen, dass ein Polygon komplett gezeichnet werden kann.

Die Vergleiche führt man zweckmässigerweise mit den folgenden Operationen in dieser Reihenfolge aus:

• besteht keine Tiefenüberlappung, kann das tiefere Polygon sofort gezeichnet werden
• mit allen den Tiefenbereich von $F_i$ überlappenden Polygonen (hier mit $F_j$ bezeichnet) führe folgende Tests (in dieser Reihenfolge) durch
  1. keine Überlappung geeigneter umgebender Formen (meist Rechtecke oder Kreise) in der Bildebene
  2. Berechnung der Orientierung aller Punkte von $F_i$ bezüglich der Ebene von $F_j$ (damit stellt man fest, ob $F_i$ ``weiter weg'' als $F_j$ liegt)
  3. Berechnung der Orientierung aller Punkte von $F_j$ bezüglich der Ebene von $F_i$ (damit stellt man fest, ob $F_j$ ``näher'' als $F_i$ liegt)
  4. keine Überlappung der Projektionen von $F_i$ und der $F_j$
  • Ist einer der Tests erfüllt, muss keine Umordnung von $F_i$ und $F_j$ erfolgen
  • Ist kein Test erfolgreich, wird $F_i$--falls noch nicht bewegt--mit $F_j$ vertauscht und dabei $F_i$ als ``schon bewegt'' markiert. Man starte wieder bei Punkt 2
  • Kann das Vertauschen nicht ausgeführt werden ($F_i$ wurde schon bewegt), dann liegt eine zyklische Überlappung vor, $F_i$ wird geeignet unterteilt (z.B. an der Überlappungsgrenze mit $F_j$) und startet wieder bei Punkt 2.
• Ist für alle $F_j$ mindestens ein Test erfüllt, so kann $F_i$ gezeichnet werden

Ist keine Transparenz vorhanden, kann man einen Pixelzähler und einen Pixelbitpuffer verwenden, um festzustellen, dass kein Pixel mehr zu zeichnen ist. Die Idee ist folgende: man zeichnet die Flächen von vorne nach hinten (d.h. man erzeugt zuerst die komplette Zeichenreihenfolge), wird ein Pixel zum ersten Mal gezeichnet, setzt man das entsprechende Pixelbit und erhöht den Zähler. Hat der Zähler den Wert der Anzahl aller Pixel erreicht, kann das Zeichnen beendet werden. Ist Transparenz vorhanden, so setzt man das Pixelbit erst, wenn ein undurchsichtiges Objekt gezeichnet wurde.

• Der Tiefensortieralgorithmus kann verwendet werden, um transparente Objekte korrekt darzustellen.
• Das notwendige Sortieren und die u.U. komplexen Vergleiche machen den Algorithmus für große Szenen unpraktisch.

Hat man keine generellen Szenen, sondern z.B. spezielle Visualisierungsanforderungen, so kann man durch eine geeignete Vorberechnung einer Datenstruktur dafür sorgen, dass die Sortierfunktion in Linearzeit erfolgen kann.