Diese Methode ist stark verbreitet, weil die Tiefensortierung ohne Behandlung der Sonderfälle
einfach zu implementieren ist und mit einem Aufwand von das Problem
löst. Meist wird der Schwerpunkt jedes Polygons als Sortierungskriterium herangezogen. Die
Polygone werden vom minimalen z-Wert zum maximalen z-Wert
nach ihren Schwerpunkte in der Prioritätsliste sortiert.
Abbildung 6.12 zeigt nochmals Kontaktanordnung aus Abschnitt 5.2.2. Hier wurde jedoch eine gewöhnliche Tiefensortierung ohne Behandlung der Sonderfälle verwendet. Betrachtet man die Struktur genauer, so sieht man z.B. an der oberen Leiterbahn an der linken vertikalen Seitenfläche eine fehlerhafte Stelle. Eine vertikales Dreieck wird vor einem Dreieck der Unterseite der Leiterbahn gezeichnet.
Abbildung 6.12: Gewöhnlicher Tiefensortierungsalgorithmus
Die Abbildung 6.13 zeigt einen Fall, der bei Sortierung nach den Schwerpunkten
eine richtige Polygonreihenfolge liefert. Tritt jedoch ein Sonderfall wie in Abbildung
6.14 ein, daß nämlich Dreiecke auf gleicher Höhe liegen und in
x/y-Ebene einander überlappen, so muß dieser Fall gesondert behandelt werden. Es müssen
jeweils zwei Flächen überprüft werden, welche vor der anderen Fläche liegt. Diese
Reihenfolge läßt sich am einfachsten mit der Ebenengleichung auswerten. Es wird Fläche
von
verdeckt, wenn alle Eckpunkte
von
der Ebenengleichung
von
mit
genügt. Dabei sollen alle z-Komponenten der Flächennormalvektoren in Richtung der
negativen z-Achse orientiert sein.
Analog ist liegt
hinter
, wenn
gilt. Es sind beide Überprüfungen notwendig, da der Sonderfall 2 in Abbildung 6.15 zeigt, daß Anordnungen existieren, wo keine der beiden Flächen vollständig hinter der anderen liegt. Die beiden Dreiecke werden dann auf die x/y-Ebene projiziert und auf Schnittpunkte überprüft. Ist kein Schnittpunkt vorhanden, so überlappen diese einander nicht. Ist mindestens ein Schnittpunkt vorhanden, so wird z.B. der erste Schnittpunkt herangezogen und darauf überprüft, welcher z-Wert der nichtprojizierten Kanten der größere ist. Das Dreieck mit dem kleineren z-Wert ist zuerst zu zeichnen und liegt daher in der Prioritätsliste immer hinter dem anderen Dreieck.
Der in Abbildung 6.16 gezeigte Sonderfall einer zyklischen Überlappung wird hier nicht behandelt, da dieser Fall bei dreidimensionalen Gitterstrukturen nicht auftritt. Ist jedoch auch dieser Sonderfall zu behandeln, so muß eine Fläche z.B. entlang der Überlappungsgrenze in zwei Flächen geteilt werden.
Bei einer Implementierung werden alle Flächen nach den kleinsten z-Werten jeder Fläche
sortiert. Beginnend mit der entferntesten Fläche wird überprüft, ob der größte
-Wert
mit dem kleinsten
-Wert anderer Flächen
Flächen überlappt. Ist dies nicht der Fall,
so wird diese Fläche als bearbeitet markiert.
Für alle unbearbeiteten Flächen wird zwischen und
überprüft, ob eine
Vertauschung notwendig ist. So wird in einer Vorprüfung
ermittelt, ob die rechtwinkeligen Boundingboxen der x/y-Ebene beider Flächen
einander überlappen. Ist dies nicht der Fall, so ist kein Vertauschen der Flächen
und
notwendig. Liegt jedoch eine Überlappung vor, so werden
und
in einer Funktion
auf die beiden oben genannten Sonderfälle 1 und 2 überprüft. Die Funktion bestimmt, ob eine
Vertauschung notwendig ist oder nicht. Die Überprüfung auf Sonderfälle zwischen
und
wird so lange durchgeführt, bis bei einem vollständigen Durchlauf
keine Flächen getauscht wurden. Das Vertauschen der Flächen entspricht einem Bubble-Sort,
damit liegt der maximale Aufwand bei
. Da aber bei den
Flächen durch
Vorprüfungen die Überprüfungen minimiert werden, ist der Aufwand akzeptabel. Die Abbildung
6.12 enthält 750 Dreieckselemente. Für eine korrekte Darstellung am Bildschirm
sind 61895 Überprüfungen notwendig.