Algorithmus von Bresenham

Beispiel Fall 1: Erster Oktant (0°-45°)

• 
• Normalerweise 8 Fälle!
• Für unseren Fallt gilt:
• dx = x2 - x1 > 0
• dy = y2 - y1 > 0
• (y2 - y1)/(x2 - x1) <= 1
• x wird in jedem Schritt inkrementiert!
• y wird dann inkrementiert, wenn es den Fehler minimiert (siehe nächste Folie)

Slide 2

• 
• Prinzip des Algorithmus:
• In jedem Schritt wird x um eins erhöht. Dann wird der Fehler zur ursprünglichen Gerade berechnet. Ist dieser grösser als 0,5 bedeutet dass, dass wir einen kleineren Fehler machen, wenn wir y auch inkrementieren. So wird für jeden Schritt entschieden, ob y gleich bleibt oder um eins erhöht wird. Ein Beispiel ist links abgebildet.

Der Fehler

• Der Fehler am Anfang nach dem ersten Schritt ist dy/dx.
• Nach jedem weiteren horizontalen Schritt ändert sich der Fehler erneut um dy/dx. Wenn wir einen diagonalen Schritt machen, also y inkrementieren, verändert sich der Fehler wie folgt: dy/dx - 1
• Damit der Computer keine Fliesskommazahlen berechnen muss, können wir alles mit 2dx multiplizieren. Dann kann er das ganze nur mit Hilfe von Integern berechnen:
• Veränderung des Fehlers nach horizontalem Schritt: 2dy
• Veränderung des Fehlers nach diagonalem Schritt: 2(dy-dx)

Pseudocode

• // Runde x1, x2, y1, y2 und berechne dx, dy
• // Setze e = (Fehler - 1/2)*2dx = (dy/dx - 1/2)*2dx
• e = 2dy-dx
• loop: for i=0 to dx do
• setpixel(x,y)
• if e>0
• y = y+1
• e = e - 2dx
• x = x + 1
• e = e + 2dy
• endloop