Der Painter`s Algorithmus, auch bekannt als Priority Fill, ist eine der einfachsten Lösungen für das Sichtbarkeitsproblem in 3D-Computergrafiken. Bei der Projektion einer 3D-Szene auf eine 2D-Ebene ist es irgendwann notwendig zu entscheiden, welche Polygone sichtbar und welche ausgeblendet sind.

Was ist der Painter`s Algorithmus?

Die Bezeichnung „Painter`s Algorithmus“ bezieht sich auf die von vielen Malern angewandte Technik, entfernte Teile einer Szene vor näheren Teilen zu malen und so einige Bereiche entfernter Teile abzudecken. Der Painter`s Algorithmus sortiert alle Polygone in einer Szene nach Ihrer Tiefe und malt sie anschließend in dieser Reihenfolge, am weitesten entfernt vom nächsten. Sie übermalt normalerweise nicht sichtbare Teile – und löst damit das Sichtbarkeitsproblem – auf Kosten der Bemalung von unsichtbaren Bereichen entfernter Objekte. Die vom Algorithmus verwendete Ordnung wird als „Depth Order“ bezeichnet und muss die numerischen Abstände zu den Teilen der Szene nicht beachten:

Die wesentliche Eigenschaft dieser Ordnung ist vielmehr, dass, wenn ein Objekt einen Teil eines anderen verdeckt, das erste Objekt nach dem Objekt gemalt wird, das es verdeckt. Somit kann eine endgültige Ordnung als eine topologische Ordnung eines gerichteten azyklischen Graphen beschrieben werden, der Occlusions zwischen Objekten darstellt.

Der Algorithmus kann in einigen Fällen fehlschlagen, einschließlich zyklischer Überlappung oder durchdringender Polygone. Im Falle einer zyklischen Überlappung, wie in der Abbildung unten dargestellt, überlappen sich die Kreise A, B und C derart, dass es unmöglich ist, zu bestimmen, welcher Kreis über den anderen liegt. In diesem Fall müssen die störenden Kreise abgeschnitten werden, um eine Sortierung zu ermöglichen. Der 1972 vorgeschlagene Newell-Algorithmus bietet ein Verfahren zum Schneiden solcher Objekte. Zahlreiche Methoden wurden auch im Bereich der Computergeometrie vorgeschlagen.

kreise e

Der Fall von durchdringenden Polygonen tritt auf, wenn ein Polygon ein anderes schneidet. Wie bei der zyklischen Überlappung kann dieses Problem durch das Abschneiden der störenden Polygone gelöst werden.

In grundlegenden Implementierungen kann der Painter`s Algorithmus ineffizient sein. Es zwingt das System, jeden Punkt auf jedem Polygon im sichtbaren Satz darzustellen, auch wenn dieses Polygon in der fertigen Szene eingeschlossen ist. Das bedeutet, dass der Painter`s Algorithmus bei detaillierten Szenen die Computerhardware regelmäßig belasten kann.

Manchmal wird der Reverse Painter`s Algorithmus verwendet, bei dem zuerst Objekte in der Nähe des Betrachters gemalt werden – mit der Regel, dass Farbe niemals auf bereits gemalte Teile des Bildes angewendet werden darf (es sei denn, sie sind teilweise transparent). In einem Computergrafiksystem kann dies sehr effizient sein, da es nicht notwendig ist, die Farben (durch Beleuchtung, Texturierung etc.) für Teile einer weit entfernten Szene zu berechnen, die durch nahe Objekte verdeckt sind. Der Reverse Algorithmus hat jedoch viele der gleichen Probleme wie die Standardversion.

Diese und andere Fehler des Algorithmus führten zur Entwicklung von Z-Buffer-Techniken, die als eine Entwicklung des Painter`s Algorithmus angesehen werden können, indem Depth-Konflikte pixelweise gelöst werden, wodurch die Notwendigkeit einer tiefenbasierten Renderingordnung reduziert wird. Da Z-Buffer-Implementierungen im Allgemeinen auf in Hardware implementierten Registern mit fester Genauigkeit basieren, gibt es Spielraum für Sichtbarkeitsprobleme aufgrund von Rundungsfehlern. Dies sind Überlappungen oder Lücken an den Verbindungstellen zwischen den Polygonen.

Um dies zu vermeiden, „überschreiben“ einige Implementierungen der Grafik-Engine, indem sie die betroffenen Kanten beider Polygone in der vom Painter`s Algorithmus vorgegebene Reihenfolge zeichnen. Das bedeutet, dass einige Pixel tatsächlich zweimal gezeichnet werden (wie im Algorithmus des Full Painters), aber dies geschieht nur bei kleinen Teilen des Bildes und hat einen vernachlässigbaren Performance-Effekt.

Wir hoffen, dass wir Ihnen einen ersten Einblick in die Thematik bieten konnten. Wenn Sie Anregungen oder Fragen zu dieser Thematik haben sollten, hinterlassen Sie uns unten einen Kommentar.

Vielen Dank für Ihren Besuch.