Holger Schmidt

Am Anfang einer Grafikbibliothek stehen meist Befehle wie Einschalten des Grafikbildschirms, Löschen der Grafikseite, Setzen eines Punktes und Zeichnen einer Linie. Das Löschen ist zumindest bei einem memory-mapped Grafikspeicher unproblematisch (Man lösche einfach den entsprechenden Speicherbereich). Das Aktivieren des Grafikbildschirmes und das Setzen eines Punktes hingegen sind rechnerspezifisch; eine allgemeine Lösung läßt sich nicht angeben. Ist jedoch ein Weg zum Setzen eines Punktes gefunden, so läßt sich allgemein ein „Drawline-Algorithmus" angeben, da man das Zeichnen einer Linie als Setzen von Punkten nach einem bestimmten Verfahren verstehen kann. Doch wie so oft führen auch hier viele Wege zum Ziel, gefunden werden sollte jedoch der beste oder aber zumindest ein guter Weg.
Vorgestellt werden soll daher ein aus dem sogenannten „Bresenham-Algorithmus" abgeleiteter Algorithmus zum Zeichnen einer Linie (zusammengesetzt aus einzelnen Punkten), wobei wir jedoch zum Verständnis auch die Herleitung dieses Algorithmus und eine Geschwindigkeitsoptimierung nicht vernachlässigen wollen. Einige werden jetzt sagen, „Das interessiert doch gar nicht, Hauptsache es läuft", viele andere, und ich zähle mich selbst hinzu, finden diese Einstellung unbefriedigend. Bei Benutzung eines solchen Algorithmus möchte man doch auch etwas über den Hintergrund erfahren und deshalb gehen wir hier etwas ausführlicher darauf ein.

Die Herleitung des Algorithmus gliedert sich in vier Punkte:

1. Mathematische Formulierung einer Ursprungsgeraden
2. Übertragung auf Programmierebene
3. Geschwindigkeitsoptimierung
4. Verallgemeinerung für beliebige Geraden

Aufgabe des endgültigen Algorithmus wird es sein, zwei beliebige durch ihre Koordinaten gegebene Punkte P1(x1,y1) und P2(x2,y2) durch eine gerade Linie verbinden.

Zur Bestimmung der Funktion einer Ursprungsgeraden wie in Bild 1 ist lediglich deren Steigung m zu ermitteln. Da uns die Koordinaten von P2 (x2, y2) bekannt sind, gilt:

m = y2/x2 und damit die Geradengleichung [1]
f(x) = (y2/x2) * x

Bevor wir zur eigentlichen Entwicklung schreiten, treffen wir noch eine Einschränkung, und zwar:
y2 < = x2, d.h. m < = 1

Warum diese Einschränkung? Hierzu betrachten wir die zu zeichnende Linie genauer: Der Bildschirm ist in eine Punktmatrix, wie in Bild 2 gezeigt, eingeteilt. Wollen wir eine Linie zeichnen, so suchen wir die Punkte, die möglichst nahe an der Geraden liegen und setzen diese. Die Genauigkeit wird also maßgeblich durch den Abstand zwischen zwei möglichen Punkten, den Gitterabstand, beeinflußt. Betrachten wir diese Punktmatrix als Koordinatensystem mit den Einheiten gx (Gitterabstand in x-Richtung) und gy (Gitterabstand in y-Richtung): Wir zeichnen eine Linie, indem wir zu jedem Punkt x (x1 < = x < = x2, x ist ein Vielfaches von gx) den Punkt y suchen, der am nächsten an der Linie liegt. Die Darstellung in Bild 3 verdeutlicht dieses Verfahren (ein Kreuz bedeutet: Punkt gesetzt). Haben wir nun obige Einschränkung gemacht, so kann dies in einer Schleife durch Inkrementieren (≡ + 1, da gx/LE1 = 1) von x erreicht werden, bis x schließlich x2 erreicht. Was würde passieren, wenn wir diese Einschränkung nicht gemacht hätten? Verdeutlicht wird dies in Bild 4. Die Anzahl der Punkte zur Approximation einer Linie wäre unzureichend (Während in Bild 3 zur Approximation einer Linie 16 Punkte gesetzt werden, sind dies in Bild 4 für eine in etwa gleich lange Linie nur 7 Punkte; als Extremfall stelle man sich eine fast senkrechte Linie vor).
Unter den angegebenen Einschränkungen läßt sich eine Linie demnach wie folgt approximieren:
a) Man berechne für alle x (x1 < = x < = x2, xεQ) f(x), also den dazugehörigen Funktionswert auf der Geraden (eigentlich handelt es sich natürlich nur um eine Strecke)
b) Man berechne durch Rundung den dem berechneten Wert am nächsten gelegenen Punkt (Rundung auf ganze Zahlen, da x, yεQ).

Also gilt [2]:
Y: = ROUND (x * y2/x2),
x1 < = x < = x2, xεQ.

Prinzipiell liefert dieser Algorithmus natürlich (unter den angesprochenen Restriktionen) ein richtiges Ergebnis. Die Ausführungsgeschwindigkeit wird jedoch durch REAL-Multiplikation und REAL-Division negativ beeinflußt.

Will man den so gewonnenen Algorithmus optimieren, muß man zweifellos an dem Rundungsbefehl ansetzen. Das Ziel ist dabei, die Berechnung auf INTEGER-Anweisungen zurückzuführen und möglichst nur die Grundrechenarten + und - zu verwenden. Ist dieses Ziel erreicht, wäre auch eine hardwaremäßige Lösung denkbar.
Schritt für Schritt wollen wir den oben gefundenen Algorithmus [2] optimieren:
Y: = ROUND (x * y2/x2)
Gemäß [2] muß gelten, daß der zu berechnende y-Wert gleich oder um eins größer ist als der vorherige. Bei Einhaltung der gefundenen Regeln ergibt sich das in Bild 5 wiedergegebene Programm.

(IF x*y2/x2-1/2 <= y THEN y: = y ENDIF (Abrundung) (IF x*y2/x2-1/2 >= y THEN y: = y+1 (ENDIF (Aufrundung) (IF x*y2-1/2*x2 <= y*x2 THEN y: = y ENDIF (IF x*y2-1/2*x2 >= y*x2 THEN y: = y+1 ENDIF (IF 2*x*y2-x2-2*y*x2 <= 0 THEN y: = y ENDIF (IF 2*x*y2-x2-2*y*x2 >= 0 THEN y: = y+1 ENDIF (e: = 2*x*y2-x2-2*x2*y (IF e <= 0 THEN y: = y ENDIF (IF e >= 0 THEN y: = y+1 ENDIF (e: = 2*y2*(x+1)-x2-2*x2*y (Inkrementierung von x) (Die erste Zeile stellt eine Anfangsbedingung dar. Die folgenden drei Zeilen werden innerhalb einer Schleife durchlaufen) (e: = 2*x*y2-x2-2*x2*y (IF e <= 0 THEN e: = 2*y2*(x+1)-2*x2*y-x2 ; y: = y ENDIF (IF e >= 0 THEN e: = 2*y2*(x+1)-2*x2*(y+1)-x2 ; y: = y+1 ENDIF (e: = 2*x*y2-2*x2*y-x2 (IF e <= 0 THEN e: = e+2*y2 ENDIF (IF e >= 0 THEN y: = y+1; e: = e+2*y2-2*x2 ENDIF Somit ergibt sich grob skizziert folgender Algorithmus: a:= 2*y2 b:= 2*x2-a e:= a-x2 (Erster Schritt: x = 1; y = 0) (x,y): = (0,0) (Anfangspunkt P1 (0,0)) PLOT(x,y); WHILE x<=x2 LOOP x:= x+1 IF e <= 0 THEN e:= e+a ENDIF IF e >= 0 THEN y:= y+1; e:=:e-b ENDIF PLOT(x,y) ENDLOOP Die beiden IF-Anweisungen können noch wie folgt ersetzt werden: IF e >= 0 THEN y:= y+1; e: = e-b ELSE e:=e+a ENDIF

Bild 5. Der Algorithmus wird optimiert

Eine hohe Verarbeitungsgeschwindigkeit ergibt sich aus drei Gründen:

- Die Anzahl der Operationen in der Schleife ist minimal.
- Es kann ausschließlich mit INTEGER-Variablen gearbeitet werden.
- Es treten (abgesehen von der Multiplikation mit 2, die sich durch ein „shift left" realisieren läßt) nur Addition und Subtraktion (keine zeitraubenden Punktrechnungen) auf.

Um einen allgemeingültigen „Drawline-Algorithmus" für beliebige Geraden zu erhalten, versucht man alle möglichen Fälle des Linienverlaufes auf den besprochenen „Original-"Bresenham-Algorithmus zurückzuführen. Speziell müssen der beliebige Anfangspunkt sowie alle möglichen Steigungen der Geraden berücksichtigt werden.

a) Berücksichtigung des Anfangspunktes

Benutzt man einen beliebigen Anfangspunkt, so ergeben sich zwei Änderungen:
- Die Steigung der Geraden ist nicht mehr m = y2/x2. Statt dessen wird sie mit m = (y2-y1)/(x2-x1) berechnet. In diesem Sinne werden die beiden Variablen dx und dy definiert mit

dx: = (x2-x1)
dy: = (y2-y1)

Entsprechend sind in dem Algorithmus aus Bild 5 x2 durch dx und y2 durch dy zu ersetzen.

- Die Gerade soll erst ab dem Punkt P1 (x1,y1) gezeichnet werden. Dazu sind die Variablen (x,y), die den jeweils zu setzten Punkt bezeichnen, auf diesen Anfangswert zu setzen. Von diesem Punkt aus wird die Gerade dann, wie in Bild 5 gezeigt, gezeichnet.

b) Berücksichtigung der Steigung der Geraden

Mit Hilfe geeigneter Umrechnungen versucht man die möglichen Lagen der Gerade auf den Algorithmus aus Bild 5 zurückzuführen. Insgesamt sind vier Fälle zu unterscheiden:
- Die Gerade genügt den Restriktionen aus Bild 5, d.h. der „Original-Algorithmus" kann angewandt werden.

- Die Steigung der Geraden ist größer als m = 1. In diesem Fall muß eine Spiegelung an der Winkelhalbierenden erfolgen, d.h.

(x,y) → (y,x)

Der Algorithmus aus Bild 5 kann somit angewandt werden.
- Um den Originalalgorithmus verwenden zu können, muß die Gerade an der y-Achse gespiegelt werden, d.h. die Schleife aus Bild 5 muß in umgekehrter Richtung durchlaufen werden, (x → -x)
- Die Gerade muß an der y-Achse gespiegelt werden, um den Originalalgorithmus anzuwenden (y → -y). U.U. muß die Schleife in y-Richtung in entgegengesetzter Richtung durchlaufen werden (falls m ≤ -1).
Allgemein wird also bei Spiegelung an einer der Achsen in Abhängigkeit von der Steigung die Durchlaufrichtung der Schleife geändert, wobei gleichzeitig die Reihenfolge der Eingabe der Endpunkte P1 und P2 berücksichtigt wird.
Der in dieser Form verallgemeinerte Algorithmus ist in Bild 6 in einer Pascal-Prozedur entwickelt worden (das Struktogramm zeigt Bild 7).

Procedure Line (x1, y1, x2, y2, farbe : INTEGER); { Die Prozedur verbindet die Punkte P1(x1,y1) und P2(x2,y2) mit der in } { 'farbe' spezifizierten Zeichenfarbe. } VAR xl, yl, x, y, { Hilfsvariablen } dx, dy, a, b, e, help, { Variablentausch } ende : INTEGER; { Kennzeichnung Linienende } winkelhalbierende : BOOLEAN; BEGIN { Prozedur 'Line' Anfang } { Defaultwerte für Variablen } xl := 1; yl := 1; x := x1; y := y1; ende := x2; dx := x2 - x1; dy := y2 - y1; winkelhalbierende := False; { Spiegelung an y-Achse } IF dx < 0 THEN BEGIN dx := -dx; xl := -1; END; { Spiegelung an x-Achse } IF dy < 0 THEN BEGIN dy := -dy; yl := -1; END; { Spiegelung an Winkelhalbierender des 1. Quadranten } IF dx < dy THEN BEGIN help := x; x := y; y := help; help := dx; dx := dy; dy := help; help := xl; x1 := yl; yl := help; ende := y2; winkelhalbierende := True; END; { Hilfsvariablen } a := dy shl 1; b := dx shl 1 - a; e := a - dx; { Zeichnen der Geraden } IF winkelhalbierende THEN BEGIN Plot (y, x, farbe); WHILE x <> ende DO BEGIN x := x + xl; IF e > 0 THEN BEGIN y := y + yl; e := e - b; END ELSE e := e + a; Plot (y, x, farbe); END END ELSE BEGIN Plot (x, y, farbe); WHILE x <> ende DO BEGIN x := x + xl; IF e > 0 THEN BEGIN y := y + yl; e := e - b; END ELSE e := e + a; Plot (x, y, farbe); END END: END; { Prozedur 'Line' Ende }
[Listing]
Bild 6. Die vollständige Linie-Prozedur 1

Bild 7. Der Programmablauf im Nassi-Shneidermann-Diagramm. [Rechts das Original mit Fehlern]

Zur Prüfung des Zeitverhaltens ist dieser Algorithmus auf einem Commodore PC10 unter Turbo-Pascal getestet worden.
Mit Hilfe der den Bildern 8 und 9 zu entnehmenden Programme wurde der Bresenham-Algorithmus mit dem unter Turbo-Pascal vorhandenen DRAW-Algorithmus verglichen. Das Ausfüllen des Bildschirms mit senkrechten Linien dauerte mit dem implementierten Algorithmus ca. 27 Sekunden und mit dem in Pascal programmierten Bresenham-Algorithmus ca. 28 Sekunden. Für einen in Pascal programmierten Algorithmus eine ansehnliche Zeit.

Program Linetest; { Programm zur Einordnung der Ausführungsgeschwindigkeit des Bresennam- } { Algorithmus } { Benutzung des unter Turbo-Pascal implementierten Draw-Algorithmus } { Der gesamte Bildschirm wird mit vertikalen Linien gefüllt. } VAR i : INTEGER; { Schleifenvariable } Eingabe : Char; BEGIN { Programm 'Linetest' Anfang } GraphMode; Palette (0); REPEAT UNTIL KeyPressed; READ (KBD, Eingabe); FOR i := 0 TO 319 DO Draw (i, 0, i, 199, 1); REPEAT UNTIL KegPressed; READ (KBD, Eingabe); TextMode; END. { Programm 'Linetest' Ende }
[Listing]
Bild 8. Der Bildschirm wird mit dem DRAW-Befehl gefüllt

Program Linestest; { Programm zur Einordnung der Ausführungsgeschwindigkeit des Bresenham- } { Algorithmus } { Benutzung des programmierten Bresenham-Algorithmus } { Der gesamte Bildschirm wird mit vertikalen Linien gefüllt. } VAR i : INTEGER; { Schleifenvariable } Eingabe : Char; {$I Line.pas } { Einbinden des Line-Algorithmus } BEGIN { Programm 'Linetest' Anfang } GraphMode; Palette (0); REPEAT UNTIL KeyPressed; READ (KBD, Eingabe); FOR i := 0 TO 319 DO Line (i, 0, i, 199, 1); REPEAT UNTIL KeyPressed; READ (KBD, Eingabe); TextMode; END. { Programm 'Linetest' Ende }
[Listing]
Bild 9. Mit der Prozedur Linie wird der Bildschirm gefüllt