Die Grafik-VDU

Der Linien-Algorithmus

Vielen Menschen ist es ein Adressierungsarten der Z80: Absolutabsolutes Rätsel, wie der Computer die einzelnen Punkte einer Linie berechnet. Um die DRAW-Befehle anzuwenden, muss man das natürlich auch nicht wissen. Wer einer Sache aber immer auf den Grund geht, der interessiert sich natürlich auch hierfür.

Eine beliebte Vermutung ist, der Computer bestimme die Entfernung zwischen den beiden Punkten, berechnet daraus die Anzahl der benötigten Punkte, daraus die Schrittweite in Die verwendeten Abkürzungen bedeuten: x:X- und Y-Richtung und geht dann in diesem Raster von einem Punkt auf den anderen zu:

100 Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 2:
Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 1:
Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 0:MODE 1                     ' Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 0
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 1
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 2Modus 1 -> Pixelabstand dx und dy = 2
105 PRINT CHR$(23);CHR$(1);    ' XOR-Grafik-Vordergrund-Modus
110 xa=50:ya=200
120 xe=600:ye=30
130 GOSUB 160                  ' mit Beispielwerten aufrufen.
140 GOTO 140
150 '
151 ' Der Algorithmus:
152 '
160 anzp=SQR(ABS((xa-xe))^2+ABS((ya-ye))^2)/2 ' Bestimmung der Diagonalen von
170 '                                         ' (xa,ya) nach (xe,ye)
180 dx=(xe-xa)/anzp          ' X-Schrittweite
190 dy=(ye-ya)/anzp          ' Y-Schrittweite
200 FOR n=1 TO anzp 210   xa=xa+dx:ya=ya+dy      ' xa und ya auf xe bzw. ye zubewegen
220   PLOT xa,ya             ' und Punkt setzen
230 NEXT
240 RETURN

lässt man dieses Programm ohne Zeile 105 laufen, ist das Ergebnis auch ganz akzeptabel. Mit Zeile 105 wird aber ein Der Linien-Algorithmus: Fehler 3Fehler offenbar: Die Anzahl der zu setzenden Punkte ergibt sich nicht als die Länge der Hypothenuse im rechtwinkligen dx-dy-Dreieck. Hier werden zuviele Punkte geplottet, manche heben sich deshalb wieder auf (Zeile 105 stellt den XOR-Modus ein).

Die Anzahl der zu setzenden Punkte ergibt sich aus dem Adressierungsarten der Z80: Absolutabsolut größern der beiden Werte dx oder dy:

160 anzp=MAX(ABS(xa-xe),ABS(ya-ye))/2

Soweit, sogut. Es funktioniert und man könnte an dieser Stelle aufhören. Diese Methode hat aber zwei Nachteile, die jeder Maschinencode-Programmierer gerne umgeht: Erstens wird mit Fließkommazahlen gerechnet (mit Integer funktioniert es nicht mehr) und zweitens muss man auch Dividieren. Das gilt es zu vermeiden.

Der Im Schneider CPC verwendete Algorithmus kommt nur mit Rechnen im Binärsystem: AdditionAddition und Rechnen im Binärsystem: SubtraktionSubtraktion von Integerwerten aus. Dass im nun folgenden Beispiel trotzdem Rechnen im Binärsystem: MultiplikationMultiplikationen mit 2 auftauchen, liegt daran, dass dies der Pixel-Abstand in Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 0
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 1
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 2Modus 1 ist. Diese Rechnen im Binärsystem: MultiplikationMultiplikation lässt sich aber auch einfach durch Shiften eines Registers erreichen!

160 dx=xe-xa:dy=ye-ya
170 if abs(dx)<abs(dy) then f=1 else f=2:gosub 450:gosub 190:goto 460
180 '
190 if dy<0 then gosub 400:gosub 200:goto 410
200 z=dy\2:Die verwendeten Abkürzungen bedeuten: x:x=xa:dz=abs(dx):dx=2*sgn(dx)
205 '
210 for y=ya to ye step 2
220   z=z+dz:if z>=dy then Die verwendeten Abkürzungen bedeuten: x:x=Die verwendeten Abkürzungen bedeuten: x:x+dx:z=z-dy
230   if f=1 then plot Die verwendeten Abkürzungen bedeuten: x:x,y else plot y,Die verwendeten Abkürzungen bedeuten: x:x
240 next
250 return
390 '
400 dx=-dx:dy=-dy      ' Vertausche Anfang und Ende, weil dy<0
410 z=ya:ya=ye:ye=z    ' dadurch ist ye immer größer (über) ya
420 z=xa:xa=xe:xe=z    ' der Algorithmus arbeitet immer mit wachsenden y.
430 RETURN
440 '
450 z=dx:dx=dy:dy=z    ' Vertausche Die verwendeten Abkürzungen bedeuten: x:x und y, weil dx>dy.
460 z=xa:xa=ya:ya=z    ' Dadurch arbeitet der Algorithmus immer in Richtung
470 z=xe:xe=ye:ye=z    ' der Y-Achse und variiert in X-Richtung.
480 return             ' Das Vertauschen von Die verwendeten Abkürzungen bedeuten: x:x und y wird im Die Z80: Wirkung der Z80-Befehle auf die FlagsFlag f angemerkt
                         und beeinflusst das Plotten in Zeile 230.

Dieses Programm entspricht zwar nicht ganz exakt dem Algorithmus des Schneider CPC, kommt ihm aber schon sehr nahe. Die gravierendsten Unterschiede ergeben sich daraus, dass Die Grafik-VDU: Der Linien-Algorithmusder Linien-Algorithmus der Grafik-VDU natürlich stärker auf die Hardware-Gegebenheiten des Bildschirms zugeschnitten ist.

Der Grund-Gedanke ist, dass man in Richtung der größeren Differenz vorgeht. Ist dy also größer als dx, so geht man in Y-Richtung vor. In Y-Richtung muss man dy Schritte machen. Zwischendurch muss man aber auch mal in Quer-Richtung 'steppen', und zwar dx mal.

Alle wieviel Schritte in dy-Richtung muss ein solcher dx-Schritt kommen? Dafür muss man nur dy durch dx teilen. Nun kann man dazu streng nach Vorschrift dividieren und muss dann aber auch einen Rattenschwanz an Nachkommastellen berücksichtigen.

Aber eine andere Frage: Was gibt (dx*dy) / dx? Da muss man wohl nicht mehr dividieren, das 'sieht' man ja. dy natürlich. Dieser Gedanke steckt nun in diesem Algorithmus.

Zunächst einmal wird das ganze von der Schleife über dy, die längere Strecke, umfasst (Zeile 210 bis 230). Bei jedem Durchgang wird in Zeile 220 zu der Unterprogramme: VariablenVariablen z einmal dz addiert. dz ist aber ABS(dx) (Siehe Zeile 200). Vom ersten bis zum letzten Durchgang wird also dy mal der Wert dx addiert = dx*dy !!

Jedesmal wenn nun z den Betrag von dy erreicht oder übersteigt, wird wieder dy abgezogen. Wie oft wird dieser Fall im Verlauf des Linien-Plottens auftreten? Genau (dx*dy) / dy mal, und das ist dx. (Wie man sieht: Hier wird nicht nur multipliziert, indem man beständig addiert, sondern auch dividiert, in dem man ständig abzieht.) Immer wenn z den Wert von dy überschreitet, wird deshalb einmal zur Seite gesteppt: Die verwendeten Abkürzungen bedeuten: x:x=Die verwendeten Abkürzungen bedeuten: x:x+dx, wobei das dx in Zeile 220 als 2*SGN(dx) definiert wurde, das ist die Schrittrichtung und, wegen Bildschirmmodus 1, eine Schrittweite von 2.

Fehler 1 (korrigiert)

Es gibt allerdings noch weitere Unterschiede zwischen dem CPC-Algorithmus und dem gerade vorgestellten. Allerdings mehr prinzipieller Art.

Zwei davon wurden Garbage Collection: ... beim CPC 464beim CPC 664/6128 behoben. Der erste betrifft den ersten Punkt einer Linie. Mathematisch korrekt ist es, den ersten Punkt einer Linie nicht zu zeichnen! Warum? Das bedarf sicher einer Erklärung.

Nehmen wir einmal an, es soll ein Kreis gezeichnet werden. Dieser wird beispielsweise durch 50 einzelne Linien aproximiert. Es müssen also 50 Linien von P1 nach P2 nach P3 ... nach P50 und wieder nach P1 gezeichnet werden.

Der Endpunkt einer Linie ist der Startpunkt der nächsten, diese 'Eck-Punkte' werden also doppelt gezeichnet, wenn man sowohl den ersten als auch den letzten Punkt jeder Linie setzt!

Das ist meist nicht so schlimm, weil 'doppelt gemoppelt hält besser'. Wenn man aber mit dem Vordergrund-Modus 'XOR' arbeitet, bedeutet 'doppelt gemoppelt hebt sich auf'. Die 'Eckpunkte' werden zu Loechern in der Kreislinie. Und dabei ist der XOR-Vordergrund-Modus kein exotischer Wunsch: Hiermit lässt sich nämlich 'löschbar' zeichnen:

  'Kreis gefällig? Bitte schön. Nicht Gut? Machen wir ihn wieder weg.'

Zum Löschen eines Linienzugen muss dieser im XOR-Modus einfach ein zweites Mal ausgeführt werden, weil: 'Doppelt gemoppelt hebt sich auf'!

So richtig ungünstig werden die Loecher, wenn man den Kreis nachher mit einem Fill-Algorithmus ausmalen will. Der 'läuft' dann durch die Loecher 'aus'.

Fehler 2 (korrigiert)

Zweiter Unterschied des CPC-Linien-Algorithmus Garbage Collection: ... beim CPC 464beim CPC 464 zum hier vorgestellten: Der CPC 464 unterteilt die größere Differenz (dx oder dy) in dy+1 (dx+1) Schritte! Wieso macht er das? Dadurch werden die einzelnen Linien etwas gefälliger. Mathematisch gesehen fast schon kriminell, einem Anfänger mag es Freude bereiten. Die folgende Grafik verdeutlicht den Unterschied:

  CPC-464-Methode:                     korrekt:

                     *****                           ***
                *****                          ******
           *****                         ******
      *****                        ******
 *****                          ***

Die kürzere Differenz dy beträgt in diesem Beispiel dy=4 Schritte. Der CPC unterteilt die Linie in 5 Stufen, korrekt wäre 4 = 1/2 + 3 + 1/2.

Na, aber die CPC-464-Methode sieht besser aus?? Anfänger! Dass die CPC-464-Methode nicht so ganz astrein ist, erkennt man, wenn man so zwei Linien zusammensetzt:

  2 mal CPC-464-Methode:                                   2 mal korrekt:
                                              *****
                                         *****
                                    *****
                               *****                                        ***
                     **********                                       ******
                *****                                           ******
           *****                                          ******
      *****                                         ******
 *****                                        ******
                                        ******
                                  ******
                               ***

Wird bei der dx+1-Methode ein Linienzug zweigeteilt, so ergibt sich an der Schnittstelle ein überlanger Abschnitt. Das dem tatsächlich so ist, kann man auf dem CPC 464 mit folgendem Programm zeigen:

100 PLOT 0,100
110 DRAWR 300,10
120 DRAWR 300,10
130 GOTO 130

Wenn beide Rechner im Freundeskreis vorhanden sind, so kann man sich den Unterschied 'in natura' anschauen.

Fehler 3

Aller guten Dinge sind drei. Aller schlechten scheinbar auch, nur hat sich das noch nicht bis zu Amstrad 'rumgesprochen. Sonst wäre der folgende Der Linien-Algorithmus: Fehler 3Fehler wohl auch Garbage Collection: ... beim CPC 664 und 6128beim CPC 664 und 6128 behoben Datenbreite: Wordsworden:

Bei den Koordinaten gibt es beim Null-Durchgang sowohl in Die verwendeten Abkürzungen bedeuten: x:X- als auch in Y-Richtung einen Stetigkeitssprung!

Alle Koordinaten, die man an PLOT, MOVE und Erklärung der Anschlussbelegung: TestTEST anhängt, werden zunächst einmal nach Integer gewandelt. Soweit, soschön. Dadurch wird beispielsweise Die Grafik-VDU: Die Koordinatendie Koordinate +67.5 nach +68, -55.5 nach -56 (und nicht -55) und +34.4 nach +34 gerundet.

Die Zwangs-Rundung von Fließkommazahlen nach Integer geschieht dabei mit der Die Fließkomma-Routinen: FunktionenFunktion ROUND(Die verwendeten Abkürzungen bedeuten: x:x). Bereits die Tatsache, dass 'halbe' ganze Zahlen (also: ?????.5) im positiven Bereich auf und im negativen Bereich abgerundet werden, bringt beim Nulldurchgang eine Unstetigkeit mit sich. Dies lässt sich aber meist noch verschmerzen.

Viel schlimmeres lässt Die Abteilungen des Betriebssystems: Die Grafik-VDUdie Grafik-VDU danach aber den ganzen Zahlen angedeihen:

Da die Datentypen: Realrealen Bildschirmpunkte (Pixel) in Y-Richtung immer zwei und in X-Richtung je nach Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 0
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 1
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 2Modus 1, 2 oder 4 Koordinaten umfassen, muss auch hier festgelegt werden, welches Pixel nun mit PLOT 101,-3 eingefärbt werden soll. Dabei ist man bei Amstrad auf die *@&&@^##:;@ Idee verfallen, immer zur Real: NullNull hinzurunden. Was das bringt, zeigt das folgende Programm:

100 Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 2:
Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 1:
Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 0:MODE 1                    ; --> Pixelbreit in X-Richtung: 2 Koordinaten
110 PRINT CHR$(23);CHR$(1);   ; XOR-Modus
120 ORIGIN 320,200            ; Origin ( (0,0)-Kreuz ) in die Bildschirm-Mitte
130 FOR Die verwendeten Abkürzungen bedeuten: x:x=-50 TO +50 STEP 2
140   PLOT Die verwendeten Abkürzungen bedeuten: x:x,10               ; Ergebnis o.k.
150 NEXT
160 '
170 FOR Die verwendeten Abkürzungen bedeuten: x:x=-49 TO +49 STEP 2
180   PLOT Die verwendeten Abkürzungen bedeuten: x:x,0                ; Lücke beim Nulldurchgang!!!
190 NEXT
200 GOTO 200

In der ersten Schleife mit Die verwendeten Abkürzungen bedeuten: x:x von -50 bis +50 läuft alles glatt. Bei der zweiten Schleife mit ungeraden Werten gibt es plötzlich eine Lücke beim Nulldurchgang.

Der Grund ist, dass in Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 0
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 1
Die 3 verschiedenen Betriebsarten der PIO 8255: Modus 2Modus 1 zwei X-Koordinaten das selbe Pixel ansprechen:

   -5 und -4,
   -3 und -2,
-1, 0 und +1,
   +2 und +3 oder
   +4 und +5,

nur beim Nulldurchgang nicht! -1 wird zur 0 gerundet, +1 aber auch. Dadurch wird beim Nulldurchgang mit den Werten Die verwendeten Abkürzungen bedeuten: x:X= -1 und Die verwendeten Abkürzungen bedeuten: x:X= +1 das selbe Pixel angesprochen und im XOR-Modus hebt sich das wieder auf.

Aber auch ohne XOR-Modus bringt das Der Linien-Algorithmus: Fehler 3Fehler:

120 Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 2:
Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 1:
Die Kodierung der Tintennummern in den Bildschirm-Bytes: Mode 0:MODE 0                         *
110 ORIGIN 320,200                 *
120 Die verwendeten Abkürzungen bedeuten: x:x=-25                         *
130 FOR y=-50 TO 50 STEP 2        *
140   PLOT Die verwendeten Abkürzungen bedeuten: x:x,y:Die verwendeten Abkürzungen bedeuten: x:x=Die verwendeten Abkürzungen bedeuten: x:x+1             *
150 NEXT                         * <---- Nulldurchgang
160 GOTO 160                     *
                                 *
                                *
Das Ergebnis sieht              *
etwa so aus:                   *
----------------------->       *
                              *
                              *

Weil 4 Koordinaten-Einheiten in X-Richtung sich jeweils auf das selbe Pixel beziehen, muss Die verwendeten Abkürzungen bedeuten: x:x viermal erhöht werden, bevor sich in dieser Richtung 'was tut'. Nur beim Nulldurchgang nicht. Hier werden 7 (in Worten: Sieben) X-Koordinaten zur Real: NullNull hingerundet: von -3 bis +3.

Wenn dieser Der Linien-Algorithmus: Fehler 3Fehler Probleme bereitet, muss man auf die ansonsten sehr nützliche Möglichkeit, den Grafik-Origin zu verlegen, verzichten, und die Koordinatenachsen wieder aus dem Bild verbannen.