Warnock-Algorithmus

Der Warnock-Algorithmus ist eine Methode aus der Computergrafik zur Verdeckungsberechnung, also um zu ermitteln, welche Teile von Objekten vom Betrachter aus sichtbar sind. Er wurde 1969 von John Warnock entwickelt und meistens auf polygonale Szenen angewandt.

Prinzip

Ein Polygon kann mit einem Flächenelement auf vier Arten in Beziehung stehen: a) umgebend, b) überlappend, c) enthalten, d) getrennt.

Der Warnock-Algorithmus teilt die Bildfläche in vier gleiche Quadrate auf. Diese Teilung wird rekursiv fortgesetzt. Bei jedem Schritt des Teilungsprozesses kann ein Polygon auf vier verschiedene Arten mit einem Flächenelement in Beziehung stehen (siehe Bild). Die Teilung wird in folgenden Fällen abgeschlossen, da über die Darstellung eines Flächenelements eine einfache Entscheidung getroffen werden kann:

• Alle Polygone sind von der Fläche getrennt: In diesem Fall wird die Fläche mit der Hintergrundfarbe eingefärbt.
• Es gibt genau ein Polygon, und dieses Polygon überlappt die Fläche oder ist in ihr enthalten. In diesem Fall wird die Fläche zunächst mit der Hintergrundfarbe gefüllt, dann wird der in der Fläche enthaltene Teil des Polygons gerastert.
• Es gibt ein einziges umgebendes Polygon, aber kein überlappendes oder enthaltenes Polygon. Hier wird die Fläche mit der Farbe des umgebenden Polygons gefüllt.
• Es gibt mehr als ein überlappendes, enthaltenes oder umgebendes Polygon, eines davon ist jedoch ein umgebendes Polygon, das vor allen anderen liegt. Um zu testen, ob ein umgebendes Polygon vor den anderen liegt, werden die z-Koordinaten der Ebenen, die die Polygone enthalten, an jeder der vier Ecken des Flächenelements verglichen. Wenn die Koordinaten des umgebenden Polygons an jeder Ecke kleiner als die der restlichen sind, so liegt es am Nächsten, und die Fläche kann mit der Farbe dieses Polygons eingefärbt werden.

Wenn soweit unterteilt wurde, dass die Flächenelemente nur noch ein einziges Pixel umfassen, und keiner der obigen vier Fälle eingetreten ist, so wird die z-Koordinate aller Polygone am Mittelpunkt der Fläche berechnet. Das Polygon mit der z-Koordinate, die am nächstem zum Betrachter liegt, bestimmt dann die Farbe des Pixels. Um Antialiasing zu erreichen, können die Flächen noch weiter unterteilt werden, sodass sich die Farbe eines Pixels aus dem Mittelwert der dazugehörigen Flächenelemente ergibt.

Literatur

• James D. Foley u. a.: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6
• William Newman, Robert Sproull: Principles of Interactive Computer Graphics, S. 297–302. McGraw-Hill, New York 1973, ISBN 0-07-046337-9
• David Rogers: Procedural Elements for Computer Graphics. WCB/McGraw-Hill, Boston 1998, ISBN 0-07-053548-5
• John Warnock: A Hidden-Surface Algorithm for Computer Generated Halftone Pictures. Technical Report TR 4-15, NTIS AD-753 671, Computer Graphics Department, University of Utah, Salt Lake City 1969 (PDF, 1,3 MB)