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 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 alle Eckpunkte sich vor 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 an Geschwindigkeit auch deutlich unterlegen.

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