Einsteigerguide: Was ist der Warnock Algorithmus?

Der Warnock-Algorithmus ist ein von John Warnock entwickelter Hidden Surface Algorithmus, der klassischerweise im Bereich der Grafik eingesetzt wird. Es erklärt die Probleme der Darstellung eines schwierigen Bildes durch rekursive Unterteilung einer Ansicht, bis Bereiche erreicht sind, die trivial zu bewerten sind.

Sofern die Ansicht einfach zu berechnen ist, dann wird Sie ebenso gerendert. Andernfalls wird sie in winzige Teile zerlegt, die ebenfalls der Einfachheit halber bewertet werden.

Dies ist ein Algorithmus mit der Laufzeit von O(np), wobei p die Anzahl der Pixel im Viewport und n die Anzahl der Polygone ist.

Der Input für den Warnock-Algorithmus sind Details von Polygonen und ein Ansichtsfenster. Ein positiver Fall liegt dann vor, wenn die Details von Polygonen sehr einfach sind und die Polygone im Ansichtsfenster erstellt werden. Der kontinuierliche Schritt besteht darin, das Ansichtsfenster in vier gleich große Quadranten aufzuteilen und den Algorithmus für jeden Quadranten rekursiv zu identifizieren, wobei eine Polygonliste so geändert wurde, dass sie Polygone enthält, die in diesem Quadranten erkennbar sind.

1. Initialisieren Sie den Bereich.
2. Erzeugen Sie eine Liste von Polygonen, indem Sie sie nach ihren Z-Werten sortieren.
3. Entfernen Sie Polygone, die sich außerhalb des Bereichs befinden.
4. Identifizieren Sie die Beziehung jedes Polygons.
5. Führen Sie die Analyse der Sichtbarkeitsentscheidung durch:
   1. Füllen Sie den Bereich mit der Hintergrundfarbe, wenn alle Polygone disjunkt sind,
   2. Füllen Sie den gesamten Bereich mit Hintergrundfarbe und füllen Sie einen Teil des Polygons, wenn es nur ein enthaltenes Polygon gibt,
   3. wenn es ein einzelnes umgebendes Polygon gibt, aber nicht enthalten ist, dann füllen Sie den Bereich mit der Farbe des umliegenden Polygons.
   4. Setzt den Pixel auf die Farbe des Polygons, die näher an dem zu betrachtenden Bereich des Pixels (x, y) liegt und wenn keiner von (a) bis (d) anwendet, berechnet die z-Koordinate am Pixel (x, y) des Polygons.
6. Wenn keiner der obigen Punkte korrekt ist, unterteilen Sie den Bereich und fahren Sie mit dem zweiten Schritt fort.

Damit sind wir soweit mit unserem Beitrag zum „Warnock Algorithmus“ durch und hoffen, dass Sie einen ersten kurzen Einblick in die Thematik gewinnen konnten. Falls Sie noch Fragen oder Anregungen haben sollten, hinterlassen Sie unten einen Kommentar.

Vielen Dank für Ihren Besuch.