Malprogramm TT Paint 256, Teil 4
In der letzten Folge erhält unser Malprogramm RGB-Farbregler, Farbinterpolation, Füllfunktionen sowie eine Zoomfunktion bzw. Lupenfunktion mit drei Vergrößerungsstufen.
Das Grafikprogramm TTPaint 256 besitzt momentan grundlegende Malfunktionen. Wir vervollständigen das Programmskelett durch Einfügen der fehlenden Funktionen. Vorab noch ein kleiner Hinweis auf den Nachtrag im Listingteil. Ein typischer "Cut & Paste«-Error im ersten Kursteil sollte noch korrigiert werden, falls Sie dies nicht sowieso schon erledigt haben: Die Funktion »Memory« weist in der Pointer-Arithmetik einen Fehler auf, der jedoch während der Laufzeit und bei der Terminierung keine Auswirkungen hat. Die Funktion»free« gibt den von TTPaint reservierten Speicher nicht frei, weil die Variablen »mem1«, »mem2« und »mem3« nicht mit den von »malloc« gelieferten Pointern geladen werden. Der Pure-C-Startupcode gibt jedoch alle über malloc auf dem Heap reservierten Blöcke mittels »_FreeAll« frei. Das Listing Teil1 Korr.c enthält die korrigierten Programmteile. Sie müssen die fehlerhaften Programmzeilen im Hauptprogramm »main« lediglich durch die neuen Zeilen ersetzen. Die Funktion »Memory« sollte komplett ersetzt werden.
Doch nun zu den neuen Funktionen des Malprogramms TTPaint 256. Eine wichtige Malfunktion werden die meisten Leser noch vermissen: das Füllen von beliebigen Bildschirmbereichen mit einer ausgewählten Farbe. Die Funktion »Free_Fill« stellt diese Option bereit. Sie stellt einen Rahmen für einen Füllalgorithmus dar, der nach Ermittlung des Startpunkts und der Grundfarbe »FGround«, aufgerufen wird. » FGround« enthält den Index der Farbe des Bereichs, der gefüllt werden soll. Es stehen zwei Füllalgorithmen zur Auswahl, die beide recht interessant sind. Beide benötigen einen Stack, auf den Punktkoordinaten abgelegt werden können. Einer der Algorithmen ist punktorientiert, der alternative und schnellere Scanline-orientiert. »Free_Fill« initialisiert den Stack und legt den ersten Punkt auf ihm ab. Der punktorientierte Algorithmus »Seed« basiert auf dem sog. Flood-Fill-Algorithmus, der folgendermaßen funktioniert: »Flood_Fill« setzt den ihm übergebenen Punkt, falls er der zu füllenden Farbe entspricht, und ruft sich mit allen vier unmittelbaren Nachbarpunkten rekursiv auf.
[...] /* (x, y) sollte Startpunkt enthalten*/
FGround = color(x, y); /* Farbe des zu füllenden Bereiches */
if (Current_color != FGround)
Flood_Fill(x, y)
[...]
void Flood_Fill (int x, int y)
{
if (color(x, y) == FGround)
{
color(x, y) = Current_color;
Flood_Fill (x + 1, y); /* Nachbarpunkte */
Flood_Fill (x - 1, y);
Flood_Fill (x, y + 1);
Flood_Fill(x, y - 1);
}
}
Bei diesem Algorithmus wird von einer von Punkten umrandeten Fläche ausgegangen, Bildschirmränder sollten jedoch ebenfalls berücksichtigt werden. Der Speicher- und Zeitaufwand der Rekursion ist enorm. Man bedenke, daß ein Bildschirm in der Auflösung »TT-Low« aus 153600 Bildpunkten besteht. Aus diesem Grund wurde der rekursive Algorithmus in einen iterativen umgeschrieben, das Prinzip blieb erhalten.
»Seed« holt sich zunächst den aktuellen Punkt vom Stack und sucht danach alle vier unmittelbaren Nachbarn nach Farben der zu füllenden Farbe »FGround« ab. Ist ein solcher Punkt gefunden, wird er mit der Füllfarbe gesetzt und auf den Stack geschoben. Die Schleife wird mit Hilfe der unstrukturierten »continue«-Anweisung am Schleifenkopf fortgesetzt. Bildschirmrandbegrenzungen werden bei der Iteration berücksichtigt. Ist der Stack leer, sind alle Punkte der zu füllenden Fläche mit der Füllfarbe gesetzt bis auf einen, den Startpunkt. Dieser wird von »Free_Fill« nach »Seed« nachträglich gesetzt. Die Vorteile gegenüber dem rekursiven Algorithmus sind einerseits viele Bytes, weniger Speicherverbrauch (wegen Einsparung der Rücksprungadressen) und andererseits eine Geschwindigkeitssteigerung, da deutlich weniger Daten bewegt werden und der Aufwand der Rekursion wegfällt. Die Effizienz des Algorithmus ist jedoch nicht das Optimum, das theoretisch erreichbar wäre: Es werden zu viele Punkte mehrfach getestet. Eine Verbesserung wird im zweiten Algorithmus beschrieben.
Der scanline-orientierte Algorithmus »ScanSeed« geht folgendermaßen vor: Er holt sich einen Punkt vom Stack und ermittelt den linken und rechten Rand der Zeile, die den Punkt enthält. Der Rand ist entweder der Bildschirmrand oder eine Farbe ungleich der zu füllenden Grundfarbenhelligkeiten als Koordinaten im RGB-Farbraum den Farbe. Man erhält somit eine horizontale Linie, die komplett gefüllt werden kann. Dies geht natürlich wesentlich schneller über die Funktion »v_pline«, als das Setzen einer Sequenz von einzelnen Punkten. Die horizontale Linie wird sofort gezeichnet. Jetzt werden die beiden Zeilen ober- und unterhalb der aktuellen Zeile nach ungefüllten Punkten abgesucht. Es wird jedoch nur der äußerst rechte Punkt auf dem Stack abgelegt und der Vorgang wiederholt, bis der Stack leer ist. Dies hat den Vorteil, daß wesentlich weniger Punkte mehrfach getestet werden und weniger Speicherplatz für den Stack benötigt wird. Wenn Sie den besseren Algorithmus verwenden wollen, müssen Sie die neue Funktion »Scan_Line« noch nachträglich in das Programm einfügen.
Obwohl dieser Algorithmus schon um mindestens den Faktor zwei schneller ist als der punktorientierte, hat man doch nicht den Eindruck, einen 32-MHz-68030er vor sich zu haben. Die Implementierung eines Füllalgorithmus müßte idealerweise in Assembler erfolgen. Gerade die Ermittlung einer Punktfarbe sollte etwas hardwarenäher ausfallen, insbesondere weil es sich meistens um benachbarte Punkte handelt. Hochoptimierte Algorithmen sind jedoch nicht Ziel des Kurses...
Die Default-Farbpalette des TT bietet zwar reichlich Farbnuancen, selbstverständlich ist es aber notwendig, eigene Farbtöne aus den Grundfarben Rot, Grün und Blau mischen zu können. Hierzu werden drei Schieberegler verwendet, die sich mit der Maus beliebig manipulieren lassen. Befindet sich ein Regler am oberen Ende, liefert er den Wert 1000, was der höchstmöglichen Helligkeit der jeweiligen Grundfarbe entspricht.
Ein Regler am unteren Ende bedeutet, daß die gewählte Grundfarbe die Helligkeit 0 besitzen soll. Die Farben werden nach dem additiven Farbmischverfahren gemixt. Die drei Grundfarbenhelligkeiten kann man sich als Koordinaten im RGB-Farbraum vorstellen. Als Modell dient ein Würfel mit den Kantenlängen 1 (s. Abb. 1). Die Funktionen »Set_Slider« und »Draw_Slider« übernehmen die Verwaltung der RGB-Regler. Hierbei wird die Reglerstellung in geeigneter Weise dem GEM-Format im Intervall [0,1000] angepaßt. Die Regler können am Bildschirm die Positionen 0 bis 64 einnehmen, wobei sich 0 oben befindet. Die jeweilige Helligkeit der Grundfarbe errechnet sich einfach durch Multiplikation der Reglerstellung mit 15.625. Der maximale Ausschlag ist somit 64 x 15.625 = 1000.
fvalue = 1000.0 - (MouseY - (y + 10)) * 15.625;
mit: MouseY = y-Koordinate des Mauszeigers und
y = y-Koordinate der Sliderbox
Wir haben dafür gesorgt, daß der Wert 1000 oben erreicht wird, und die Reglermitte immer auf der Mauszeigerspitze liegt (y + 10). Die gemischte Farbe kann in einem Prüffeld kontrolliert werden. Bei der Auswahl einer Farbe aus der Palette, werden die drei Regler sofort aktualisiert. Bei einer umfangreichen Farbpalette von 256 Farben ist es oft wünschenswert, ganze Farbverläufe (z. B. Rot nach Gelb für Sonnenuntergänge) zu berechnen. Mit TTPaint 256 ist dies möglich. Ist eine Farbe selektiert, braucht man nur den im RGB-Regelfeld befindlichen »INT-Button» anzuklicken und danach die Zielfarbe auszuwählen. TTPaint berechnet sofort die günstigsten Zwischenwerte. Wie man zunächst annehmen könnte, ist eine lineare Interpolation über alle drei RGB-Werte von Farbe 1 nach Farbe 2 eine einfache und gute Lösung. In der Praxis zeigt sich aber, daß die so entstehenden Farbverläufe das menschliche Farbempfinden nicht immer voll ansprechen. Wir haben uns deshalb für eine Interpolation im HSV-Farbraum entschieden, die für den Betrachter optimale Farbverläufe erzeugt (s. Abb. 2). Das HSV-Farbmodell erklärt sich folgendermaßen:
»H« steht für »Hue«, den Farbton. Er wird in Grad [0,360] angegeben und gibt die Farbrichtung an. Die Saturation »S« [0,1] bestimmt die Sättigung einer Farbe, und damit die Entfernung von der Graumittelachse. Je kleiner S, desto mehr nähert sich die Farbe der unchromatischen Mittelachse. Die Helligkeit einer Farbe wird mit »V« für Value (manchmal auch »B« für Brightness) [0,1] bestimmt. Wenn S=0 ist, befindet sich die Farbe auf der Mittelachse und der Farbton H ist unrelevant (H = UNDEFINED). Ist S = 0 und H definiert, so liegt nach Konvention keine korrekte Farbe vor.
Die einfache lineare Interpolation der drei Werte ist somit nicht möglich. Will man beispielsweise von reinem Rot (0, 1, 1) nach Schwarz (UNDEFINED, 0, 0) interpolieren (0 nach UNDEFINED?), so ist dies ohne Berücksichtigung von Sonderfällen nicht möglich. Die Lösung ist allerdings einfach. Das jeweils definierte H wird über den gesamten Verlauf konstant gehalten. Sind beide H-Werte nicht definiert, ist die Interpolation trivial. Bei der linearen Interpolation über H muß unbedingt der kleinere Winkel zwischen beiden H-Werten gewählt werden. Von 240 (Blau) nach 120 (Grün) darf nicht über 0 (Rot) »gelaufen« werden, da sonst unerwartete Rottöne, die wahrlich nichts zwischen Blau und Grün zu suchen haben, auftreten würden. Der kürzeste Weg ist intuitiv der richtige. Der fließende Farbübergang auf einer Scheibe der Höhe V im HSV-Modell legt die Gewinnung guter Verläufe bei der Interpolation nahe. Die lineare Interpolation erfolgt in jedem Fall nach dem Schema der Abb. 3. Dabei berechnet der Algorithmus die Steigung in einer Geradengleichung sowie die Werte der Geraden an den gewünschten Zwischenstellen.
Es seien f1 und f2 zwei ganze Zahlen, die die Indizes der Start- und Endfarbe repräsentieren. Weiterhin sei x(n) eine der Komponenten einer Farbe mit dem Index n. Die Weite eines Interpolationsschrittes ergibt sich aus:
M = (x(f2) - x(f)) / (f2 - f1); /* Steigung der Geraden */
/* Die Interpolationsschleife hat folgende Gestalt: */
x = x(f1) ;
for (n = f1 + 1; n < f2; n++)
{
x += m;
x (n) = x;
}
Da die HSV-Verlaufsberechnung die ursprünglich für den Kurs geplante RGB-Interpolation bei weitem übertrifft, haben wir uns entschlossen, zwei nicht im Programmskelett vorgesehene Funktionen nachzureichen. Diese Funktionen dienen der Konvertierung einer Farbe von RGB nach HSV und umgekehrt. Zwei neue Funktionsdeklarationen und ein »#define« müssen oben ins Programm eingefügt werden.
Zum Abschluß des Kurses folgt nun die Funktion, die pixelgenaues und detailreiches Zeichnen ermöglicht. Aufgrund der recht hohen Auflösung des TT ist es einfach nicht möglich, jeden Bildschirmpunkt gezielt zu setzen. Besonders bei detailgenauen Bildern müssen jedoch Pixel sehr exakt eingefärbt werden können. Um dies zu ermöglichen, wurde in TTPaint 256 eine Lupenfunktion integriert, die drei Vergrößerungsstufen bereit stellt. TTPaint256 läßt Vergrößerungen um den Faktor 2, 4 und 8 zu. Eine Vergrößerung um den Faktor zwei bedeutet, daß ein Pixel des Originalbildes im Zoomausschnitt durch einen Block von 4 Punkten (2 x 2) repräsentiert wird. Entsprechend geschieht dies bei den anderen Vergrößerungen (4 x 4 und 8 x 8 Pixel). Wenn die Lupenfunktion angeklickt wurde und mittels rechter Maustaste auf das Arbeitsblatt umgeschaltet werden soll, erfolgt zunächst die Abfrage, welcher Vergrößerungsfaktor angewendet werden soll.
Diese Abfrage geschieht durch »form_alert«. Mit Hilfe einer Rubberbox kann der Benutzer nun auf dem Arbeitsblatt den Bereich wählen, der vergrößert dargestellt und bearbeitet werden soll. Ein Klick genügt, und der selektierte Bereich wird in der eingestellten Vergrößerung abgebildet. Es wurde eine ganze Bildschirmseite reserviert, um genug Platz zu schaffen, die komplette Farbpalette aus dem Menübild und den vergrößerten Bereich darzustellen. Dies erspart einerseits einen Neuaufbau des Menübildes und andererseits mühsames Hin- und Herschalten, falls der Benutzer eine neue Pinselfarbe wünscht. Mit der Maus kann jetzt ähnlich wie bei der Freihandfunktion im Bild gearbeitet werden. Die Farbpalette wird genauso bedient, wie in der Toolbox. Die maximale Vergrößerungsstufe (x8) verfügt zusätzlich über eine kleine originalgetreue Abbildung des vergrößerten Bereichs, um dem Benutzer die Gelegenheit zu geben, die Wirkung seiner Arbeit zu überwachen. Durch Druck der rechten Maustaste wird der bearbeitete Bereich ins Arbeitsblatt übernommen. Nun hat man die Möglichkeit, einen weiteren Bereich zu wählen, oder durch Betätigen der rechten Maustaste zur Toolbox zurückzukehren.
Die Zoomfunktion in TTPaint 256 wurde folgendermaßen realisiert: Um die Farbinformation des zu vergrößernden Bereichs zu erhalten, muß auf die GEM-Funktion »v_get_pixel« zurückgegriffen werden. Der rechteckige Bereich, der durch die Rubberbox umrahmt wurde, wird nun in zwei verschachtelten Schleifen über die Funktion »v_get_pixel« ausgelesen. Die gewonnenen Farbindizes werden in einem zweidimensionalen Feld »Zoomarray« abgelegt. Die Umschaltung auf den Zoombildschirm kann jetzt erfolgen. Nach Aufbau der Farbpalette mit »Show-Colors« wird, falls die größte Vergrößerung gewählt wurde, ein kleines Übersichtsfenster dargestellt, indem das Zoomarray ausgelesen und über die Funktion Plot in Originalgröße dargestellt wird. In der Variablen »Size« wird die Anzahl der Punkte pro Zeile und Spalte (32, 64 oder 128) festgehalten.
Die Größe eines vergrößerten Pixels errechnet sich wegen der Kantengröße des Zoombereichs von 256 Punkten zu 256/Size (PSize = 8, 4 oder 2). In einer Schleife werden durch die Funktion »v_bar« Blöcke entsprechender Größe und Farbe in den Zoombereich gezeichnet. Der Zoomvorgang ist abgeschlossen. Aus Geschwindigkeitsgründen wurde die Funktion »Box« nicht verwendet, da hier bei jedem Aufruf sämtliche Attributfunktionen durchgeschleift werden, was sich bei bis zu 16384 Aufrufen pro Zoomvorgang durchaus bemerkbar macht. Um in den vergrößerten Bereich zeichnen zu können, ist es notwendig, die Mauskoordinaten zu transformieren. Zunächst muß der Ursprung auf die linke obere Ecke des Zoomausschnitts, durch Subtraktion der Koordinaten der linken oberen Ecke desselben von den Mauskoordinaten, verschoben werden.
Am Beispiel der Vergrößerungsstufe x4 soll nun die weitere Funktionsweise erklärt werden. Da alle vier Pixel ein Block beginnt, starten die Blöcke sowohl in x- als auch in y-Richtung an den Koordinaten 0, 4, 8, 12,...,252. Die Zwischenkoordinaten sind demnach für die vergrößerten Blöcke unrelevant. Sie werden durch eine entsprechende Maskierung entfernt. Die Maske soll alle relevanten Bits der verschobenen Mauskoordinaten enthalten. Die Maske »Mask« wird mit dem Wert 0xFFFF initialisiert, alle Bits sind gesetzt. Dividiert man nun »Mask« durch »PSize« so werden notwendig viele Bits rechts hinausgeschoben, denn eine Integer-Division durch vier entspricht einem arithmetischen Shift nach rechts um 2 Bit. Die darauffolgende Multiplikation mit »PSize« führt dazu, daß »Mask« arithmetisch um 2 Bit nach links verschoben wird. Die zwei unteren Bits sind jetzt gelöscht. Dies funktioniert analog bei den anderen Vergrößerungsstufen. Die Koordinaten werden jetzt bitweise mit der Maske »UND«-verknüpft, wodurch, passend zu »PSize«, die unteren Bits gelöscht werden. Dadurch erfolgt eine Rasterung der Mauskoordinaten auf 2er, 4er oder 8er Schritte.
Die so gewonnenen Blockkoordinaten werden zum Zeichnen der Blöcke unter dem Mauszeiger verwendet. Um die Änderungen des Benutzers ins Arbeitsblatt übernehmen zu können, müssen sie ins Zoomarray eingetragen werden. Das Element des Feldes »Zoomarray« wird wie folgt bestimmt: Die Blockkoordinaten werden durch »PSize« dividiert. Man erhält so bei der Vergrößerungsstufe x4 die Indizes im Intervall [0,63]. Solange die linke Maustaste gedrückt bleibt, werden Blöcke in der gewählten Farbe in den Zoomausschnitt gezeichnet und das Zoomarray aktualisiert. Hat der Benutzer seine Arbeit im Zoomausschnitt beendet, werden die Daten aus dem Zoomarray über die Funktion »v_pline« ins Arbeitsblatt übertragen. Auch hier wurde aus Performancegründen auf die gekapselte Funktion »Plot« verzichtet. Damit wären wir am Ende des Programmierprojekts. Falls Sie Fragen, Anregungen oder Kritik haben, wenden Sie sich (bitte unbedingt schriftlich) an die Redaktion. Wir stellen gerne den Kontakt zu den Entwicklern her. Falls Sie alle vier Kurse inklusive Listings auf Diskette wünschen, schicken Sie uns eine formatierte Leerdiskette im frankierten Rückumschlag. Hier die korrekte neue Anschrift: AWi Verlags GmbH, Redaktion ST-Magazin, Stichwort »TT-Malprogramm«, Bretonischer Ring 13, 8011 Grasbrunn. (hu)