PROJEKT
DAS MAGAZIN FÜR COMPUTER-FANS ONLINE
Ein schneller "Drawline"-Algorithmus64'er Ausgabe 4/April 1984, S. 65-69Im folgenden wird eine Möglichkeit vorgestellt, schnell und einfach eine Strecke, die durch ihre beiden Endpunkte gegeben ist, zu plotten. Als Ausgabegerät können Bildschirm, Drucker oder Plotter eingesetzt werden. Der Algorithmus wird in einer Basic- und einer Assembler-Version für einen 6502-Mikroprozessor mit den Adressen für den Commodore 64 (der 6510 Mikroprozessor im C 64 ist im Befehlssatz identisch mit dem 6502) beschrieben. Die Programme können, da sie im Aufbau einfach sind und erklärt werden, ohne große Probleme für andere Systeme beziehungsweise andere Sprachen umgewandelt werden. Vor einiger Zeit suchte ich eine Möglichkeit, das in [1] auf Seite 97 abgedruckte, in Assembler geschriebene Programm um eine einfache aber doch effiziente "Drawline"-Routine zu erweitern. In [2] fand ich genau den Algorithmus, den ich brauchte - nur war er "leider" in Basic formuliert. Jedoch bereitete es, nachdem der Algorithmus verstanden war, nicht mehr allzu viel Mühe, eine Assemblerversion zu schreiben. Doch vor der Beschreibung der Programme eine kurze Erklärung des Algorithmus.  Bild 1. Eine Strecke mit der Steigung 1 dargestellt auf dem Bildschirm Ein Rasterbildschirm setzt sich aus einzelnen Punkten, die gesetzt oder auch gelöscht sein können, zusammen. Der Abstand der Punkte voneinander ist in der Richtung der Achsen immer gleich und jeweils eine Schrittweite groß (Bild 1). Um eine Gerade zwischen den Punkten P0 und P1 zu ziehen, muß daher schrittweise berechnet werden, welcher Punkt der Ideallinie (Bild 2) am nächsten ist und daher gesetzt werden muß.  Bild 2. Eine Strecke mit der Steigung 1 und den optimierten Rasterpunkten Geschwindigkeitsvorteile durch einfache Berechnungen Für diese Berechnungen gibt es verschiedene Möglichkeiten, doch sind sie meistens mit Multiplikationen und Divisionen in der Approximationsschleife verbunden und daher weder schnell noch einfach zu programmieren. Der hier vorgestellte Algorithmus verwendet dagegen nur eine Division und in der Schleife nur mehr Addition, Subtraktion und eine Vergleichsoperation. Da die Schleifenoperationen außerdem nur mehr an Integerzahlen durchzuführen sind, ist er besonders schnell, und er läßt sich auch einfach programmieren. Zur Erklärung soll eine Gerade mit einer Steigung zwischen 0 und 1 (0 bis 45 Grad) betrachtet werden. Wie man in Bild 2 unschwer erkennen kann, ist der Abstand der Punkte P0 und P1 entlang der X-Achse gleich der Anzahl der zu setzenden Punkte, DX = X1 - X0, das heißt es sind DX-Approximationen durchzuführen, um die Gerade zu zeichnen. Für jeden folgenden Punkt ist also X0 um IX (= 1) zu erhöhen, während Y0 gleichbleibt (IY = 0) oder ebenfalls um 1 (IY = 1) erhöht wird. Der Abstand der beiden Punkte entlang der Y-Achse ist demnach: DY = Y1 - Y0. Es bleibt also nur mehr festzustellen, wann IY = 0, beziehungsweise IY = 1 zu sein hat. Dazu wird vor Beginn der Schleife ein Approximationswert OF berechnet. Da beim Idealfall für eine Steigung von 1 (Bild 1) IY = IX, das heißt immer 1 ist, und DX = DY ist, wird OF = DX/2. Rasterpunkte optimieren Zu OF wird für jeden neuen Punkt DY addiert. Solange OF kleiner als DX bleibt, bleibt IY = 0, wird OF gleich oder größer, so wird IY = 1, das heißt Y0 um 1 erhöht. Damit diese Abfrage auch für die folgenden Punkte möglich ist, muß OF um DX vermindert werden. Wenn DX-Punkte gesetzt worden sind, sind alle Punkte der Geraden berechnet und die Schleife kann verlassen werden. Soweit also für eine Gerade mit positiver Steigung zwischen 0 und 45 Grad. Wie sieht es aber aus, wenn zum Beispiel X1 kleiner X0 ist? Nun, dann wird eben IX = -1, X0 also für jeden Approximationsschritt um 1 erniedrigt. Und wie sieht es für eine Steigung größer 1 aus? Auch dieses Problem läßt sich einfach lösen. Es werden für die Rechnung einfach die beiden Achsen vertauscht. Der Ablauf beider Programme ist im Nassi-Shneiderman-Diagramm (Bild 3) dargestellt. Zum leichteren Vergleich sind alle Variablenbezeichnungen in den Programmen identisch. Die Basic-Version gibt nur die Koordinaten der berechneten Punkte aus, da ich dafür keine "Setze-Punkt"-Routine schreiben wollte. Man kann aber die Wirkungsweise des Algorithmus schön verfolgen. Das Assemblerprogramm ist, wie schon oben gesagt, für den C 64 geschrieben mit einer möglichen Auflösung von 320 x 200 Punkten. Dadurch können die Werte für Y in einem Byte untergebracht werden, während für X zwei Byte benötigt werden. OF, DX und der Schleifenzähler CT benötigen deshalb ebenfalls 2 Byte. Die Länge der Werte muß beim Umstricken für ein anderes System berücksichtigt werden, da alle durchzuführenden Operationen dementsprechend 1 oder 2 Byte lang sind. In dieser Assemblerversion werden nur 2 Subroutinen aus dem Betriebssystem verwendet. Sie sind in Tabelle 1 beschrieben. Zusätzlich habe ich die Adressen für die anderen Commodore Computer angegeben. Die Subroutine "PLOT" muß, wenn sie sich im Betriebssystem wie bei den Commodoresystemen nicht findet, extra geschrieben werden. Für den C 64 findet man in [1] ein geeignetes Programm. Kein Problem: Variablen In Tabelle 2 sind alle verwendeten Variablen aufgelistet und beschrieben. Aufgerufen wird diese Version mit SYS aaaa,X0,Y0,X1,Y1 wobei aaaa die Startadresse der Routine, X0/Y0 und X1/Y1 die Koordinaten der beiden Punkte sind. Für die Koordinaten können auch Ausdrücke verwendet werden, da die Betriebssystemroutine "GETCOR" auch Ausdrücke auswertet. Zusätzliche Erweiterungen Den Lesern, die mit Assembler-Programmen noch etwas Probleme haben, sende ich gerne gegen einen Kostenbeitrag von 10 Mark eine Kassette mit einem Basic-Lader mit dem gesamten Programm zu. Es stehen dann neben den in [1] beschriebenen Befehlen noch DRAWLINE, ERASELINE, DRAWX-AXIS, ERASEXAXIS, DRAWY-AXIS und ERASEY-AXIS zur VerfÜgung. Bei der Anwendung dieses Algorithmus wünsche ich viel Spaß und Erfolg. (Michael Bauer) Literatur:
| ||||
8-Bit-Nirvana | Impressum