Grafiksystem selbst gemacht

Ein Grafiksystem ist brauchbar, wenn es, die dem Anwender notwendigen Funktionen erfüllt und wenn es seine Ausgabegeräte unterstützt. Manche fehlenden Grafikfunktionen können oft mit Hilfe der vorhandenen Funktionen gelöst werden. Schlimmer ist, wenn ein Grafiksystem eines unserer Ausgabegeräte nicht unterstützen kann. Man muß dann einen Treiber schreiben und installieren, und das erweist sich in der Regel, wegen Mangel an vielen notwendigen Informationen, als schwierig.
Deshalb habe ich mich entschlossen, ein einfaches, möglichst übertragbares Grafiksystem zu entwickeln.

Ein Grafiksystem sollte mindestens, von der Seite des Anwenders gesehen, die grundlegenden Grafikfunktionen erfüllen. Das sind meistens:

• Installation des Treibers eines bestimmten Ausgabegerätes;
• Löschen einer Zeichnung;
• Zeichnen eines Punktes mit den Koordinaten X Y;
• Testen eines Punktes mit den Koordinaten X Y;
• Verschiebung zu einem Punkt mit den Koordinaten X Y;
• Zeichnen einer Strecke oder einer Zackenlinie mit vorgegebenen Parametern;
• Ausfüllen einer Fläche, die durch eine Kontur oder Liste der Koordinaten der Ecken eines Vielecks deklariert ist.

Die oben angegebene Liste kann natürlich noch vervollständigt werden. Man kann noch Farben zugeben, Muster der Linien und Flächen (Ausfüllungen) ändern. Man kann neue Primitiven wie Bögen, Kreise, Rechtecke oder Texte zugeben. Man kann nicht nur zeichnen, sondern auch löschen oder bereits gezeichnete Punkte modifizieren. Das alles war aber nicht unser Ziel. Beachten wir doch, daß, obwohl das Hinzufügen von diesen Funktionen einfach ist (wir denken hier, daß jeder Leser dazu fähig wäre), sofort gewisse Probleme auftauchen. Nicht alle Ausgabegeräte sind fähig, zum Beispiel die Zeichnungen in Farbe zu bilden. Unmöglich ist auch zum Beispiel das Löschen einer einmal gezeichneten Linie mit Hilfe des Plotters. Bei einer genaueren Analyse kann man noch mehr ähnliche "Probleme" entdecken. Zusätzliche Schwierigkeiten bereiten verschiedene Auflösungen und Formate der Zeichnungen und (was besonders kläglich ist) verschiedene Pixelproportionen. Die Voraussetzung war dagegen das Erhalten von möglichst identischen Zeichnungen bei Anwendung der Ausgabegeräte verschiedener Typen. Unter dieser Voraussetzung wurde ein Programmpaket entwickelt (Listing 1). Es realisiert die vorher aufgeführten Funktionen mit Hilfe der Unterprogramme

OpenDevice, CloseDevice, Point, Dot, Plot, Draw, Line, Fill, Area.

Man sollte auch Reaktionen des Grafiksystems im Falle der Überschreitung des effektiven Bereiches der Zeichnung bestimmen.
Wir haben in diesem Falle Arbeit in den Regimen Abschneiden, Rollen oder Unterbrechung des Zeichnens (ähnlich wie in der Programmiersprache Logo) zugelassen. Korrekt konstruierte Prozeduren zum Abschneiden und Rollen sollten auch einwandfrei im Falle eines verkleinerten Formats des Bildes (Fenster) arbeiten.

Typische Ausgabegeräte für ein Grafiksystem sind die Bildschirme, Drucker und etwas seltener Plotter. Auf diese Geräte wurde beim Schreiben von Beispieltreibern besonders besonders geachtet. Es wurde angenommen, daß jedes der Ausgabegeräte ziemlich "unintelligent" ist. Das bedeutet, daß im Falle eines Zugriffs auf den Bildschirm der Zugriff nur auf den Bildspeicher gestattet ist, im Falle des Druckers die Möglichkeit der direkten Steuerung der Druckernadeln verfügbar ist, und bei dem Plotter das Zeichnen einer Linie zwischen zwei Nachbarpunkten und Verschiebung des Plotterköpfes in gezeigter Stellung möglich ist. Selbstverständlich bieten meistens die grafischen Geräte mehr Möglichkeiten an. Bei dem Monitor besteht oft die Möglichkeit der Ausnutzung von Systemprozeduren, die die ausgewählten Grafikfunktionen realisieren. Matrixdrucker bieten häufig eine ganze Menge von Grafikfunktionen, manchmal besitzen sie auch Plotteremulationen (was möglich ist, falls der Drucker die Welle in beiden Richtungen drehen kann). Plotter sind in der Regel ziemlich intelligente Geräte. Sie ermöglichen nämlich außer dem Zeichnen von Linien, auch die Ausgabe von Texten und manchmal auch eine Ausfüllung von Vielecken. Die Ausnutzung solcher zusätzlicher Möglichkeiten vereinfacht den Aufbau einiger Fragmente des Treibers.
Unser Treiber soll folgende Funktionen erfüllen:

• Zeichnen des Punktes mit den Koordinaten X Y;
• Testen des Punktes mit den Koordinaten X Y;
• Verschiebung zum Punkt mit den Koordinaten X Y;
• Löschen einer Zeichnung.

Die übrigen grafischen Funktionen, solche wie Zeichnen einer Linie oder Ausfüllen einer Fläche, sollten schon durch entsprechende Prozeduren des Grafiksystems realisiert werden.
Jetzt wären die Möglichkeiten der einzelnen Grafikgeräte an der Reihe. Der Monitor des Amstrad PCW besitzt die Auflösung 720 x 256. Der Bildspeicher befindet sich in der Speicherbank 0, zu dem man mit Hilfe der XBIOS-Funktion Nummer $E9 Zugriff erhalten kann. Die Adresse des Bytes, das den vorgegebenen Punkt enthält, wird anhand der X,Y-Koordinaten und des Inhaltes des sogenannten RAM-Roller-Bereiches, das die Anfangsadressen jeder der 256 Bildschirmlinien [1] sammelt, berechnet. Diese Berechnung wird durch die Funktion Adr ausgeführt. Die einzelnen Bytes im Bildschirmspeicher sind so organisiert, daß Entsendung zu ihnen der aufeinanderfolgenden Acht-Bytes-Zeichenmatrizen eine Textzeile auf dem Bildschirm bildet.

Der Computerdrucker ist (teilweise) mit dem Epson FX kompatibel. Zur Bildung der Zeichnung wurde eine höhere Bildqualität gewählt, die der Auflösung von 960 Punkten in einer Linie entspricht. Ich nahm 720 Linien an, damit ein für den Bildschirm typisches Verhältnis der Breite zu der Höhe des Bildes von vier zu drei gewährleistet wird. Diese Auflösung bestimmt die Größe des Bildspeichers von 90 kByte. Das Vorhandensein einer ziemlich großen RAM-Disk im Computer führte zu der Lösung, in welcher eine ensprechend große Datei mit direktem Zugriff den Bildspeicher für den Drucker emuliert. Es sollte eine einschlägige Struktur dieser Datei angenommen werden. Die Datei wurde in Blocks zu je einem kByte geteilt. Jeder Block nutzt jedoch nur 960 Bytes aus, was acht Linien des Bildes entspricht. Zur Beschleunigung der Ausgabe der Zeichnung auf den Drucker wurde angenommen, daß die aufeinanderfolgenden Bytes in der Datei die Information bilden, die direkt an den Druckkopf des Druckers ausgegeben wird. Es bedeutet, daß alle Bits jedes Bytes der selben X-Koordinate entsprechen. Um eine höhere Auflösung zu erreichen, entsteht jede Zeile der Zeichnung (16 Linien) durch zweimaliges Passieren des Druckkopfes. Aus diesem Grunde enthalten die Blocks mit geraden Nummern die Information über Punkte mit ungeraden Y-Koordinaten und umgekehrt. Eine solche Lösung beschleunigt bedeutend die Ausgabe der Zeichnung. Die Umrechnung der X,Y-Koordinaten auf die Blocknummer, Adresse im Block und Bitnummer erfolgt in der Prozedur Calculate. Eine weitere interessante Lösung ist der Datenaustausch mit der Datei mit Bitkarte. Der klassische direkte Zugriff zur Datei kann hier nicht angenommen werden, weil das Zeichnen von senkrechten Linien laufende Ein- und Ausgaben des Dateipuffers verursacht hätte. Man entschied sich also für das Modell des virtuellen Speichers aus der Programmiersprache Forth.
In jedem Augenblick befinden sich im Arbeitsspeicher immer zwei Blocks. Eine Forderung des Zugriffs auf einen bestimmten Block verursacht die Überprüfung, ob sich der Block mit der angegebenen Nummer im Arbeitspeicher befindet. Falls ja, erfolgt kein Einlesen des Blocks von der Disk. Sonst wird der geforderte Block von der Disk in den Puffer eingelesen. Um das jedoch durchführen zu können, muß man vorher den Puffer durch Löschen aus dem Speicher des am längsten verwendeten Blocks freimachen. Wenn dieser Block vorher modifiziert wurde, wird er auf die Disk geschrieben. Den virtuellen Zugriff zum Speicher realisiert die Funktion Block.

Das letzte angewendete Gerät war der Plotter Sharp CE. Er kann Linien zeichnen und Texte ausgeben. Der von mir erstellte Treiber nutzt jedoch nur die Möglichkeit des Vorschubs des Plotterkopfes und Verbindung von zwei benachbarten Punkten mit einer Linie aus. Das Problem bildet beim Plotter die Ausfüllung, weil der Plotter den Punkt mit vorgegebenen Koordinaten nicht testen kann. Die Lösung dieses Problems erforderte die Reservierung einer ensprechenden Datei mit Bitkarte auch für Plotter. Weil die Auflösung des Plotters in der horizontalen Achse 960 Punkte betrug, war die Annahme der gleichen Auflösung wie bei dem Drucker möglich. Ähnlich ist auch die Größe der Datei mit der Bitkarte, die 90 kByte beträgt. Jeder Block sammelt nämlich Informationen über den Inhalt von acht aufeinanderfolgenden Bildlinien. Die folgenden Bits jedes Bytes entsprechen den nächsten Werten der X-Koordinate. Es vereinfacht und beschleunigt die Ausfüllung, welche der Plotter durch Straffierung mit horizontalen Linien realisiert. Die Umrechnung der X,Y-Koordinaten auf die Blocknummer, Adresse im Block und Bitnummer erfolgt in der Prozedur Calculate. Auch im Falle des Plotters wurde der vorher beschriebene Mechanismus des virtuellen Zugriffs auf die Datei mit der Bitkarte angewendet, obwohl in diesem Falle der Nutzen nicht so augenscheinlich wie beim Drucker ist.

Alle drei Treiber wurden als Überlappungsstrukturen (Overlays) implementiert, weil in jedem Augenblick nur einer von ihnen ausgenutzt wird. Diese Treiber sind in den Listings 2, 3 und 4 dargestellt.
Unter Ausnutzung der durch die Treiber angebotenen Möglichkeiten kann man weitere Funktionen des Grafiksystems entwickeln.
Die erste von ihnen ist die Prozedur Draw, die eine Strecke zeichnet. Sie nutzt den vielmals beschriebenen Algorithmus von Bresenham, deshalb wird Sie hier auch nicht genauer angesprochen.
Bemerken Sie bitte nur, daß diese Prozedur sich leicht so modifizieren läßt, daß statt einer stetigen eine Linie nach vorgegebenem Muster gezeichnet wird. Leider werden die horizontalen und senkrechten Linien wegen der Pixelproportionen unterschiedlich sein (besonders auf dem Bildschirm). Eine Vervollständigung der Prozedur Draw bildet die Prozedur Line, die eine Zackenlinie ausgibt.

Viel interessanter ist das Problem der Ausfüllung von Flächen. Die Aufgabe der Ausfüllung von Flächen kann wie folgt definiert werden:

• Bemalung einer Fläche, deren Kontur (nicht unbedingt regulär) vorgegeben ist.
• Bemalung des Inneren eines Vielecks (nicht unbedingt konvex), dessen Eckpunktkoordinaten gegeben sind.

Das vorgestellte Paket enthält die Lösung dieser beiden Aspekte auf eine, wie wir meinen, interessante Weise. Zuerst sollte jedoch der erste dieser Algorithmen, der durch die Prozedur Fill realisiert wird, besprochen werden. Dieser Algorithmus setzt das Vorhandensein einer geschlossenen Flächenkontur im Speicher und Kenntnis der Koordinaten eines Punktes, der in ihrem Inneren liegt, voraus. Die Koordinaten dieses Punktes, der Korn genannt wird, werden auf dem Stapel abgespeichert. Im nächsten Schritt nimmt man die Koordinaten des Kornes vom Stapel, zeichnet an der vorgegebenen Stelle einen Punkt, wonach aus diesem Punkt Linien, die den Punkt mit der Kontur verbinden, nach links und nach rechts von diesem Punkt gezeichnet werden. Während dieser Tätigkeit werden die Koordinaten der Grenzpunkte der Kontur Xleft und Xright bestimmt. Dann wird die Prozedur Scan aufgerufen, die die Linie testet, die über und unter der durch Xleft und Xright begrenzten, gezeichneten Strecke liegt. Dieses Testen bedeutet die Bestimmung neuer Körner, deren Koordinaten auf dem Stapel geschrieben werden. Die beschriebenen Tätigkeiten werden wiederholt, bis der Stapel leer wird.

Die Schwierigkeit bei der Kodierung dieses Algorithmus ist mit der Art der Implementierung des Stapels verbunden. Am einfachsten kann man ihn in einer Art Tabelle realisieren, was jedoch seine Größe von vornherein begrenzt, die Notwendigkeit der laufenden Überprüfung des Wertes des Tabellenzeigers einführt und die Zugriffszeit verlängert. Die Implementierung des Stapels durch eine Liste ist auch nicht die glücklichste, weil sie mehr Speicherplatz erfordert (jedes Listenelement enthält zusätzlich einen Zeiger) und die Zugriffszeit verlängert. Ideal wäre wegen der Speicherbelegung und Zugriffszeit die Ausnutzung des Maschinen-Stacks (des Prozessors Z80). Das Problem besteht jedoch darin, daß der Prozessor Z80 nur einen Stack (Stapel) besitzt, dessen Zeiger sich im SP-Register (Stack Pointer) befindet, und daß dieser Stapel von Turbo-Pascal für die Aufbewahrung der Rückkehradressen und der Parameterübergabe ausgenutzt wird. Auch dieses Problem konnte ich jedoch mit Hilfe der Prozedur PushStack und der Funktion PopStack lösen. Die Prozedur PushStack lädt seinen Parameter auf dem Stapel unter ihrer Rückkehradresse, seinen Wert entnimmt die Funktion PopStack dagegen vom Stapel aus der Stelle unter der Rückkehradresse. Bei Benutzung der Prozedur PushStack und der Funktion PopStack sollte man etwas vorsichtig sein. In der Regel sollten alle Operationen auf dem Stapel innerhalb einer Prozedur durchgeführt werden. Wenn wir diese Operationen in einer anderen Prozedur ausnutzen möchten (so wie in der Prozedur Scan), so muß diese Prozedur mit der Anweisung:

Return : = PopStack ;

beginnen und mit der Anweisung:

PushStack (Return) ;

enden, was ein Vermischen der Adressen und Daten auf dem Stapel verhindert. Man sollte auch in solchen Prozeduren die Anweisung For, die die Operationen Push-Stack und PopStack benutzt, nicht anwenden, weil diese Anweisung den Maschinenstapel benutzt.

Im Falle anderer Prozessoren mit einer größerer Anzahl von Adreßregistern, aus denen jedes als Stapelzeiger angewendet werden kann, vereinfacht sich das beschriebene Problem wesentlich. Der zweite der Ausfüllalgorithmen, der durch die Prozedur Area realisiert wird, erfordert die Bestimmung der Koordinaten der Eckpunkte des zu bemalenden Vielecks. Er erfordert kein Vorhandensein einer Bildbitkarte, deshalb wird die Ausfüllung diesen Typs durch eingebaute Kommandos bei einigen Plottern realisiert. Dieser Algorithmus überprüft zuerst, ob die Kontur geschlossen ist (ob Koordinaten des letzten Eckpunkts identisch mit den des ersten sind). Falls nicht, so wird die Kontur durch Zufügen eines nächsten Eckpunktes geschlossen. Dann wird die Kontur mit Hilfe der Prozedur Line gezeichnet. Im nächsten Schritt bestimmt man den minimalen und maximalen Wert der Y-Koordinate durch Durchsuchen der Eckpunktliste. Dies führt die Prozedur RangeY aus. Jetzt bestimmt man für jede Y-Linie, die zum gegebenen Intervall gehört, die X-Koordinaten der Schnittpunkte mit allen Strecken, die zur Kontur gehören. Diese Koordinaten werden durch die Funktion Xcross berechnet. Man kann beweisen, daß, falls die Kontur geschlossen ist, die Anzahl ihrer Schnittpunkte mit der Gerade Y = const gerade ist. Um eine solche Kontur zu bemalen, muß man also die zuvor bestimmten Punkte entsprechend verbinden. Das Problem im diesem Falle liegt darin, daß die X-Koordinaten der Schnittpunkte nicht der Reihe nach bestimmt werden. Deshalb müssen die erhaltenen Koordinaten vor Beginn der Operation der Punkteverbindung sortiert werden. Weil wir wiederum von vornherein nicht wissen, wieviele Schnittpunkte wir erhalten, werden ihre X-Koordinaten üblich in einer Listenstruktur abgespeichert. Um diesen Algorithmus zu verbessern, werden nacheinander bestimmte X-Koordinaten im Maschinenstapel abgespeichert, wobei der Stapel jedesmal bei Eintragung einer neuen Zahl sortiert wird. Die Sortierung des Stapels wird in der Prozedur SortStack durchgeführt. Um diesen Prozeß zu optimieren, wurde ein zweiter Stapel angewendet. Einen Zugriff auf ihn gestatten die Prozedur PushHeap und die Funktion PopHeap. Dieser Stapel wächst in entgegensetzter Richtung zum Vergleich mit dem Maschinenstapel. Die Sortierung wird selbst durch Einschiebung realisiert. Sie beruht auf Wegnehmen vom Stapel aller Koordinaten, die kleiner als die eingeschobene Koordinate sind. Diese vom Maschinenstapel weggenommenen Koordinaten werden zeitweise auf dem zweiten Stapel abgelagert. Dann wird die eingeschobene Koordinate auf den Maschinenstapel geschrieben und alle vorher auf dem zweiten Stapel abgelagerten Koordinaten werden zurückgeschrieben. Diese Lösung ermöglicht die Ausnutzung des gesamten freien Hauptspeichers zum Sammeln der X-Koordinaten der Schnittpunkte. Nach der Bestimmung und Sortierung aller Schnittpunkte verbindet die Prozedur DrawScan durch Strecken die Punkte, deren X-Koordinaten auf dem Stapel abgespeichert sind, wodurch das Vieleck bemalt wird.

Üblicherweise erscheint am Ende eines solchen Artikels eine Beispielprozedur oder ein Demonstrationsprogramm.

Endgültig wählte ich eine Prozedur, die (pseudo-) dreidimensionale Zeichnungen der Funktionen von zwei Variablen bildet. Diese Prozedur, genannt FnGraph, sucht selbst die Art des installierten Ausgabegerätes aus, paßt ihm die Auflösung der Zeichnung an und skaliert die Zeichnung. Die Parameter der Prozedur FnGraph bildet die Funktion, deren Zeichnung wir ausgeben wollen, und der Bereich, in dem die Zeichnung abgebildet werden soll. Dieser Bereich ist ein Würfel, der durch die Werte der Parameter Xmin, Xmax, Ymin, Ymax, Zmin und Zmax begrenzt ist. Einige Schwierigkeiten macht im Turbo-Pascal die Übergabe der Funktion als Parameter (Turbo-Pascal läßt keine Parameter zu, die Prozeduren sind). Dieses Problem wurde bereits in [3] [4] gelöst. Als Parameter wird zur Prozedur der Wert der Adresse der Funktion, die den Parameter bildet.

Diese Adresse kann man mit Hilfe der Funktion Addr erreichen. Innerhalb der Prozedur FnGraph wird der Aufruf der den Parameter darstellenden Funktion durch die Funktion CallFunc realisiert. Dies ist eine Ein-Parameter-Funktion, die durch Inline-Anweisung realisiert wurde. Ihr Parameter bestimmt die Adresse, die man anspringen soll. Es bleibt noch das Problem der Parameterübergabe. Turbo-Pascal übergibt die Parameter auf dem Stapel, wobei durch ihn jedesmal nach Eingang in die Prozedur oder Funktion automatisch eine Anweisungssequenz generiert wird, die die Parameter vom Stapel löscht. Ausnahme bilden alle als externe deklarierte (external) Prozeduren, die das selbst machen sollten. Diese Tatsache nutzte ich bei Deklaration der externen Prozedur PushReal aus. Diese ist in Wirklichkeit keine externe Prozedur, und ihr Code bildet nur die Maschineninstruktion RET (Rückkehr aus dem Unterprogramm). Ein Aufruf dieser Prozedur verursacht also im Endeffekt nur eines, daß nämlich der Parameter auf dem Stapel gelassen wird. Diese Parameter werden dann durch die Funktion ausgenutzt, die wiederum Parameter der Prozedur FnGraph ist. Ein weiteres Problem, das man bei der Konstruktion solcher Zeichnungen antrifft, ist das Verdecken der durch den Beobachter nicht gesehenen Zeichnungsfragmente. Die Prozedur FnGraph löst es ganz einfach durch das Vergleichen von zwei benachbarten Zeichnungskurven.

[1] Andrew R. M. Clarke, David Powys-Lybbe, The Amstrad CP/M Plus, M.M.L. Systems Ltd., London 1986.

[2] Michael Anton, Im Herzen von CP/M Plus - XBIOS zerlegt, Joyce-Sonderheft 1'87.

[3] Namir Clement Shammas, Turbo-Pascal Procedural Parameters, Software Tools December 86.

[4] Bernd Rüffer, Noch ein Turbo-Tip - Prozedurale Parameter in Turbo-Pascal, C'T September 86.

(Zbigniew Szkaradnik/rs)