Einführung in die Rastergrafik

Ivan Sutherland (* 16. Mai 1938), gilt als Pionier der Computergrafik. Die theoretischen Grundlagen wurden 1963 in seiner Doktorarbeit veröffentlicht. Seit dieser Zeit schritt die Entwicklung stetig voran. Heute spielt die Computergrafik in vielen Anwendungsbereichen eine wachsende Rolle, wenn nicht sogar die entscheidende. Gesucht sind Algorithmen, die vor allem effizient in Bezug auf Speicher und Laufzeit sind. Gerade diese Algorithmen sind Gegenstand der theoretischen und praktischen Informatik.

DDA - Digital Differential Analyzer

Ein erster naiver Ansatz zum Zeichen einzelner Linien besteht in der Berechnung der Koordinaten eines Punktes aus den Koordinaten des vorangegangenen Punktes. Die Berechnung basiert dabei auf der Ermittlung des Anstiegs der Funktion aus zwei Punkten. Obwohl sich die Implementierung des Algorithmus einfach darstellt, ist seine Effizienz mangelhaft. Die Notwendigkeit der Berechnung von Gleitkommazahlen, verlangsamt den Algorithmus erheblich und macht ihn für moderne Anwendungen unbrauchbar. Eine verkürzte Darstellung der Implementierung unter Beachtung des Koordinatensystems im Grafikmodus wäre folgende.

01  .......
02 
03   def set_line (parent, x1, y1, x2, y2) :
04 
05      bsp = punkt() # Instanzierung der Klasse Punkt
06 
07      dy = float (y2 - y1)
08      dx = float (x2 - x1)
09 
10      if dx > 0 and dy >= 0 and dx < dy :
11          m = dx / dy
12          a = y1 - m * x1
13          while x1 <= x2 :
14                            x = m * y1 + a
15                            bsp.set_point (fenster, x, y1, farbe)
16                            parent.update()
17                            y += 1
18 
19  ............

Bresenham - Algorithmus

Die Nachteile des DDA Algorithmus sind :

- Gleitkommaarithmetik verbraucht Zeit und Ressourcen
- keine Definition des Anstiegs m für senkrechte Linien

Der Logik des Bresenham Algorithmus besteht nun darin, sich von der Gleitkommaberechnung zu lösen und Entscheidungsgrößen einzuführen, welche berechenbar sind. Die implizite Darstellung der Geradengleichung liefert den Ausgangspunkt für die Herleitung. Diese ist relativ komplex, beruht aber auf einem einfachen Gedanken. Ist die Differenz aus Anstieg der Linie und halbem Pixel negativ wird der Wert der y - Koordinate nicht erhöht und der Pixel unten gesetzt (Bild), im anderen Fall oben.

Herleitung des Algorithmus

01  .......
02 
03   def set_line (parent, x1, y1, x2, y2) :
04 
05      bsp = punkt() # Instanzierung der Klasse Punkt          
06 
07      dy = y2 - y1 
08      dx = x2 - x1
09                  
10      if dx > 0 and dy >= 0 and dx >= dy :
11          e = 2*dx - dy 
12          while x1 <= x2 :
13                   if e > 0 :
14                          x1 += 1    
15                          y1 += 1
16                          e  = e + 2 * (dy-dx)  
17                   else     :
18                          x1 += 1                   
19                          e  = e + 2* dy
20                   bsp.set_point (parent, x1, y1, farbe)   
21                   parent.update()
22 
23  ............

	heute	310
	gestern	423
	diese Woche	2186
	letzte Woche	4334
	Gesamt	1228231