Newells Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Newell, Newell, Sancha Algorithmus ist eine in der 3D-Computergrafik angewendete Prozedur zum Zeichnen von Polygonen mit Unterdrückung verdeckter Oberflächen. Er wurde 1972 vorgestellt von M.E. Newell, R.Newell und T.Sancha.
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.
[Bearbeiten] Schritte
Das Sortieren von zwei Polygonen P und Q nach Tiefe (Z-Richtung) geschieht in mehreren Schritten.
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.
Newell's 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.
[Bearbeiten] Literatur
- Ivan E. Sutherland, Robert F, Sproull, and Robert A, Schumacker, “A Characterization of Ten Hidden-Surface Algorithms”, Computing Surveys, Vol 6, No 1, März 1974
- Newell, M E, Newell R. G, and sancha, T.L, “ A New Approach to the Shaded Picture Problem”, Proc ACM National Conf. 1972
