6.4.3 Die Tiefensortierungsmethode



next up previous contents
Next: 7 Anwendungen Up: 6.4 Entfernung verdeckter Flächen Previous: 6.4.2 Objektraumalgorithmen

6.4.3 Die Tiefensortierungsmethode

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.



next up previous contents
Next: 7 Anwendungen Up: 6.4 Entfernung verdeckter Flächen Previous: 6.4.2 Objektraumalgorithmen



Martin Stiftinger
Fri Nov 25 16:50:24 MET 1994