Im letzten Artikel haben wir besprochen, wie sich aus einzelnen Punktinformationen Dreiecke auf den Bildschirm zaubern lassen. Viel gekonnt haben wir damit allerdings nicht, da wir lediglich die Umrisse der Dreiecke zeichnen konnten. Was aber eigentlich benötigt ist, sind komplett ausgefüllte Dreiecke – und darum soll es heute gehen.
Ebenso wie beim Rastern von Linien gibt es natürlich auch beim Ausfüllen von Dreiecken die verschiedensten Methoden, um zum Ziel zu gelangen, wobei ich mich wie immer auf eine der einfacheren beschränke. Zu sagen ist noch, dass die beschriebene Methode natürlich nicht nur für Dreiecke funktioniert – für diese ist sie jedoch mit dem geringsten Rechenaufwand umsetzbar, weswegen das Dreieck auch (wie bereits erwähnt) die Grundlage der 3D-Grafik bildet.
Ausgangspunkt beim Rendern von Dreiecken sind wieder die in Bildschirmkoordinaten transformierten Eckpunkte des Dreiecks (wir erinnern uns). doch statt den Umriss des Dreiecks zu zeichnen, also die drei Eckpunkte durch Linien zu verbinden, wollen wir diesmal die durch die Eckpunkte beschriebene Fläche auf dem Bildschirm füllen.
Der triviale Ansatz zum Füllen des Dreiecks wäre nun natürlich, für jeden Bildschirm-Punkt zu bestimmen, ob er innerhalb oder außerhalb des Dreiecks liegt; das lässt sich durch drei relativ einfache Berechnungen bestimmen (indem nämlich geschaut wird, ob der zu betrachtende Punkt für alle drei Dreieckskanten auf der gleichen Seite liegt – ist dem so, liegt der Punkt auch im Dreieck). Aber dieser Ansatz ist uns a) zu einfach und b) ist er natürlich auch viel zu langsam, um in der Praxis relevant zu sein.
Wir wollen uns an dieser Stelle daher einen weitaus eleganteren Algorithmus anschauen, der (natürlich modifiziert) so auch in der Praxis zur Anwendung kommt. Da Algorithmen zum Zeichnen
von Dreiecken sehr schnell arbeiten müssen, sind sie meist relativ einfach gestrickt – so auch dieser. Die Rede ist vom sogenannten Edge-Flag-Algorithmus (eine für allgemeine Polygone geeignete Beschreibung findet sich hier – die Dreiecksvariante ist ein klein wenig einfacher). Das schöne ist, dass dieser Algorithmus wenigstens teilweise auch mit der Umrandung des Dreiecks arbeitet – unsere Bemühungen im vorherigen Artikel waren also nicht ganz umsonst.
Der Algorithmus besteht im Grunde aus 2 Schritten. Im ersten Schritt wird die Kontur des Dreiecks markiert; im zweiten Schritt werden dann die Pixel innerhalb der Kontur gefüllt.
Die Kontur ist so etwas ähnliches wie der Umriss des Dreiecks, mit einer kleinen Abweichung. Beim Umriss des Dreiecks haben wir unterschieden, ob eine Linie einen Anstieg von größer als 0.5 (oder kleiner als -0.5) hat – wenn dem so war, würde für jeden y-Wert der Linie ein passender x-Wert berechnet, ansonsten andersherum (wer sich nicht mehr erinnert, möge noch einmal den letzten Artikel lesen). Für die Kontur wird für alle Dreieckskanten, unabhängig von ihrem Anstieg, für alle möglichen y-Werte der Kante genau ein passender x-Wert, nämlich der am weitesten links liegende, berechnet – der sogenannte Konturpixel (x und y sowie links und rechts können beliebig ausgetauscht werden, mit entsprechender Anpassung des Algorithmus – wir halten uns hier aber an die Konvention).
Die Kontur eines Dreiecks lässt sich relativ leicht berechnen; dazu wird lediglich für jede einzelne der drei Linien des Dreiecks für jede Pixelzeile der Schnittpunkt der Linie mit der Zeile berechnet und der entsprechende Bildpunkt eingefärbt. Dazu ein kleines Beispiel; nehmen wir das folgende zu zeichnende Dreiecke mit der zugehörigen, bereits eingezeichneten Kontur an:
Der Unterschied der Kontur zum Umriss ist hier deutlich zu sehen, da für letzteren die untere Linie des Dreiecks einen y-Wert für jeden möglichen x-Wert aufweisen müsste. So aber wurden für alle 3 Linien für alle y-Werte mögliche x-Werte berechnet. Es fällt auf, dass sich durch dieses Vorgehen in jeder Zeile genau 2 eingefärbte Pixel befinden (das muss nicht immer so sein, dazu aber später noch ein Wort) – eine Eigenheit, die sich durch die Verwendung von Dreiecken erklären lässt.
Kommentare (3)