imported>Vfb1893: BKL Planarität aufgelöst

2024-05-25T19:16:54Z

Neue Seite

Der '''Depth-Sort-Algorithmus''' (englisch wörtlich „Tiefensortierungs-Algorithmus“) ist in der [[Computergrafik]] ein [[Algorithmus]] zur [[Sichtbarkeitsproblem|Verdeckungsberechnung]]. Er wurde 1972 von den Brüdern [[Martin Newell (Informatiker)|Martin E. Newell]] und [[Dick Newell|Richard G. Newell]] sowie Tom Sancha vorgestellt.

Der Grundgedanke besteht darin, die zu zeichnenden [[Polygon]]e nach ihrer Entfernung vom Betrachter zu sortieren und sie dann, mit dem am weitesten entfernten Polygon beginnend, alle nacheinander zu zeichnen. Dabei werden bereits gezeichnete Teile von näher liegenden Objekten überschrieben, wenn sie sich ganz oder teilweise überlappen. Wenn das Sortieren ordnungsgemäß ausgeführt wurde, liefert diese Vorgehensweise eine korrekte Ansicht verdeckter Oberflächen.

== Schritte ==

Das Sortieren von zwei Polygonen ''P'' und ''Q'' nach Tiefe (Z-Richtung) geschieht in mehreren Schritten.

[[Datei:Painters problem.png|rechts|gerahmt|Zyklische Polygone müssen verhindert werden, um korrekt nach Tiefe zu sortieren]]
# Wenn die Extremwerte der Z-Koordinaten aller [[Punkt (Geometrie)|Eckpunkte]] von ''P'' weiter hinten liegen als die von ''Q'', ist die Sortierung trivial. ''P'' wird weiter hinten einsortiert.
# Wenn die zu vergleichenden Polygone keine Überlappung ihrer Extremwerte in x, y haben, brauchen sie nicht sortiert zu werden, da sie sich nicht überlappen.
# Wenn alle Eckpunkte von ''P'' weiter vom Betrachter entfernt sind als die [[Ebene (Mathematik)|Ebene]] von ''Q'', wird ''P'' weiter hinten einsortiert.
# Wenn alle Eckpunkte von ''Q'' näher am Betrachter sind als die Ebene von ''P'', wird ''P'' weiter hinten einsortiert.
# Wenn die x, y Werte von ''P'' und ''Q'' sich nirgends überlappen, braucht nicht sortiert zu werden.
# Wenn hier immer noch keine Sortierung möglich war, handelt es sich um zyklische überlappende Polygone. In diesem Fall müssen diese aufgeteilt werden und die Sortierung mit den nicht mehr zyklisch überlappenden Teilen fortgeführt werden. Die Unterteilung geschieht an einem der Polygone an der Schnittkante mit dem anderen Polygon.

Die Polygone müssen [[Ebene (Mathematik)|planar]] sein, das heißt, alle [[Ecke|Eckpunkte]] müssen auf einer Ebene liegen. Die Prüfung, ob sich alle Eckpunkte auf einer Ebene befinden, wird durch Einsetzen der [[Koordinatensystem|Koordinaten]] aller Punkte in die [[Ebenengleichung]] durchgeführt.

Die Reihenfolge der Schritte ist so gewählt, dass die einfachen Tests zuerst und die komplexeren Prüfungen zum Schluss angewendet werden, um weniger Rechenzeit zu benötigen.

Der Depth-Sort-Algorithmus verwendet viel weniger Speicherressourcen als beispielsweise der häufiger verwendete [[Z-Buffer]]-Algorithmus zum Berechnen verdeckter Oberflächen, ist diesem aber in der Geschwindigkeit deutlich unterlegen.

== Siehe auch ==
* [[Maleralgorithmus]] (''Painter''-Algorithmus)

== Literatur ==
* M. E. Newell u. a.: ''A Solution to the Hidden Surface Problem.'' In: ''Proceedings of the ACM Annual Conference 1972.'' Volume 1, ACM, New York 1972.

[[Kategorie:Algorithmus (Computergrafik)]]
[[Kategorie:Bildsynthese]]

Depth-Sort-Algorithmus - Versionsgeschichte

imported>Vfb1893: BKL Planarität aufgelöst