Maleralgorithmus

Der Maleralgorithmus (engl. painter's algorithm) ist eine einfache Lösung des Sichtbarkeitsproblems in der 3D-Computergrafik. Bei der Darstellung einer dreidimensionalen Szene auf einer zweidimensionalen muss häufig entschieden werden, welche Polygone sichtbar und welche verdeckt sind.

Zuerst werden die Berge gezeichnet, dann der Boden und zuletzt die Bäume

Der Name Maleralgorithmus ist eine Anspielung auf einen Maler, der die entfernten Objekte einer Szene zuerst zeichnet und sie dann mit den näher gelegenen übermalt. Entsprechend kann der Algorithmus in der Implementierung einer computergrafischen Anwendung eingesetzt werden: Zuerst werden alle Polygone ihrer Tiefe nach sortiert (Tiefensortierung, engl. depth sort) und dann werden sie der Reihenfolge nach gezeichnet. Durch das Überzeichnen der Bildanteile, die normalerweise nicht sichtbar sind, wird das Sichtbarkeitsproblem gelöst.

Woran der Maleralgorithmus scheitert

Diese Verfahrensweise führt zu etlichen Problemen. Was passiert, wenn Polygon A teilweise Polygon B, B teilweise C und C wiederum teilweise A überschneidet? Es kann nicht mehr entschieden werden, welches Polygon vor welchem liegt. Ein ähnlicher Fall liegt vor, wenn sich zwei Polygone gegenseitig im dreidimensionalen Raum überschneiden. In solchen Fällen muss mindestens eines der betroffenen Polygone unterteilt werden, damit die Sortierung möglich ist und der Maleralgorithmus ein korrektes Ergebnis liefert.

Ein anderes Problem ist, dass der Maleralgorithmus ineffizient ist, weil der Computer die Intensitäten aller Punkte eines Polygons berechnen muss, auch wenn das Polygon in der endgültigen Szene gar nicht sichtbar ist.

Diese und andere Probleme mit dem Maleralgorithmus führten zur Entwicklung des Z-Buffers, der als logische Weiterentwicklung des Maleralgorithmus betrachtet werden kann. Durch die Verwendung eines Z-Buffers müssen die Objekte nicht mehr in der Reihenfolge ihrer Tiefe gerendert werden.