Depth-Sort-Algorithmus

Depth-Sort-Algorithmus

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

Der Grundgedanke besteht darin, die zu zeichnenden Polygone 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.

Zyklische Polygone müssen verhindert werden, um korrekt nach Tiefe zu sortieren
  1. Wenn die Extremwerte der Z-Koordinaten aller Eckpunkte von P weiter hinten liegen als die von Q, ist die Sortierung trivial. P wird weiter hinten einsortiert.
  2. Wenn die zu vergleichenden Polygone keine Überlappung ihrer Extremwerte in x, y haben, brauchen sie nicht sortiert zu werden, da sie sich nicht überlappen.
  3. Wenn alle Eckpunkte von P weiter vom Betrachter entfernt sind als die Ebene von Q, wird P weiter hinten einsortiert.
  4. Wenn alle Eckpunkte von Q näher am Betrachter sind als die Ebene von P, wird P weiter hinten einsortiert.
  5. Wenn die x, y Werte von P und Q sich nirgends überlappen, braucht nicht sortiert zu werden.
  6. 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 planar sein, das heißt, alle Eckpunkte müssen auf einer Ebene liegen. Die Prüfung, ob sich alle Eckpunkte auf einer Ebene befinden, wird durch Einsetzen der 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 Speicherresourcen als beispielsweise der häufiger verwendete Z-Buffer-Algorithmus zum Berechnen verdeckter Oberflächen, ist diesem aber in der Geschwindigkeit deutlich unterlegen.

Siehe auch

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

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Newells Algorithmus — Der Depth Sort Algorithmus ist in der Computergrafik ein Algorithmus zur Verdeckungsberechnung. Er wurde 1972 von M.E. Newell, R. Newell und T. Sancha vorgestellt. Der Grundgedanke besteht darin, die zu zeichnenden Polygone nach ihrer Entfernung… …   Deutsch Wikipedia

  • Maler-Algorithmus — Zuerst werden die Berge gezeichnet, dann der Boden und zuletzt die Bäume Der Maleralgorithmus (engl. painter s algorithm) ist eine einfache Lösung des Sichtbarkeitsproblems in der 3D Computergrafik. Bei der Darstellung einer dreidimensionalen… …   Deutsch Wikipedia

  • Painter's Algorithmus — Zuerst werden die Berge gezeichnet, dann der Boden und zuletzt die Bäume Der Maleralgorithmus (engl. painter s algorithm) ist eine einfache Lösung des Sichtbarkeitsproblems in der 3D Computergrafik. Bei der Darstellung einer dreidimensionalen… …   Deutsch Wikipedia

  • Hidden Surface Removal — Oben: Ansicht einer Szene mit Betrachter. Unten links: projizierte Objekte ohne Verdeckungsberechnung. Unten rechts: gerendertes Bild nach Verdeckungsberechnung, bei der ermittelt wurde, dass die blaue Kugel und das graue Dreieck die gelbe Kugel… …   Deutsch Wikipedia

  • Sichtbarkeitsentscheid — Oben: Ansicht einer Szene mit Betrachter. Unten links: projizierte Objekte ohne Verdeckungsberechnung. Unten rechts: gerendertes Bild nach Verdeckungsberechnung, bei der ermittelt wurde, dass die blaue Kugel und das graue Dreieck die gelbe Kugel… …   Deutsch Wikipedia

  • Verdeckungsberechnung — Oben: Ansicht einer Szene mit Betrachter. Unten links: projizierte Objekte ohne Verdeckungsberechnung. Unten rechts: gerendertes Bild nach Verdeckungsberechnung, bei der ermittelt wurde, dass die blaue Kugel und das graue Dreieck die gelbe Kugel… …   Deutsch Wikipedia

  • Sichtbarkeitsproblem — Oben: Ansicht einer Szene mit Betrachter. Unten links: projizierte Objekte ohne Verdeckungsberechnung. Unten rechts: gerendertes Bild nach Verdeckungsberechnung, bei der ermittelt wurde, dass die blaue Kugel und das graue Dreieck die gelbe Kugel… …   Deutsch Wikipedia

  • Maleralgorithmus — Der Maleralgorithmus (engl. painter s algorithm) ist eine einfache Lösung des Sichtbarkeitsproblems in der 3D Computergrafik. Bei der Darstellung einer dreidimensionalen Szene auf einer zweidimensionalen muss häufig entschieden werden, welche… …   Deutsch Wikipedia

  • Abkürzungen/Computer — Dies ist eine Liste technischer Abkürzungen, die im IT Bereich verwendet werden. A [nach oben] AA Antialiasing AAA authentication, authorization and accounting, siehe Triple A System AAC Advanced Audio Coding AACS …   Deutsch Wikipedia

  • Liste der Abkürzungen (Computer) — Dies ist eine Liste technischer Abkürzungen, die im IT Bereich verwendet werden. A [nach oben] AA Antialiasing AAA authentication, authorization and accounting, siehe Triple A System AAC Advanced Audio Coding AACS …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”