Der Bresenham-Algorithmus ist ein Algorithmus in der Computergrafik zum Zeichnen (Rastern) von Geraden oder Kreisen auf Rasteranzeigen. Zum Thema Rasterung von Linien gibt es einen eigenen Übersichtsartikel, hier wird mehr die konkrete Implementierung erläutert.
Der Algorithmus wurde 1962 von Jack Bresenham, damals Programmierer bei IBM, entwickelt.J. E. Bresenham: Algorithm for computer control of a digital plotter. In: IBM Systems Journal, 4, 1, 1965, S. 25–30, , cse.iitb.ac.in (PDF; 223 kB; englisch) Bereits 1963 als Vortrag auf der ACM National Conference in Denver präsentiert.Die erste Veröffentlichung der Grundidee für die Kreisgenerierung findet sich in: H. B. Keller, J. R. Swenson: Experiments on the lattice problem of Gauss. (PDF; 222 kB) In: Math. Comp., 17, 1963, S. 223–230, Section 3. Das Besondere an seinem Algorithmus ist, dass er Rundungsfehler, die durch die Diskretisierung von kontinuierlichen Koordinaten entstehen, minimiert, und gleichzeitig einfach implementierbar ist, mit der Addition von ganzen Zahlen als komplexeste Operation, und somit ohne Multiplikation, Division und Gleitkommazahlen auskommt.
Durch eine geringfügige Erweiterung lässt sich der ursprüngliche Algorithmus, der für die Rasterung von Linien entworfen wurde, auch für die Rasterung von Kreisen verwenden. Sogar die Quadratterme, die beim Kreis vorkommen, lassen sich rekursiv ohne jede Multiplikation aus dem jeweils vorhergehenden Term ableiten nach , wobei der Term nicht als Multiplikation zählt, da er in Hardware bzw. auf Assemblerebene als einfache Shift-Operation implementiert wird und der Term im Endeffekt ganz vermieden werden kann.
Auf heutiger Grafikhardware kommt der Bresenham-Algorithmus nicht mehr zum Einsatz, da er weder vektorisier- noch parallelisierbar ist, auf heutigen frei programmierbaren Shaderarchitekturen liegt nicht mehr das Augenmerk auf Vermeidung von Multiplikationen, Divisionen und Gleitkommaarithmetik, sondern auf die optimale Ausnutzung dieser Gleitkommavektorprozessoren. Weiterhin haben sich die Anforderungen geändert: nichtganzzahlige Koordinaten, Antialiasing und dickere Linien sind Standard. Hauptaugenmerk liegt auf 3D-Performance, 2D fällt dabei nebenbei mit ab.
Der Name Bresenham wird heute zudem für eine ganze „Familie“ von Algorithmen verwendet, die eigentlich von Anderen später entwickelt wurden, jedoch in der Nachfolge von Bresenham und mit einem verwandten Ansatz (siehe Einzelnachweise unten).
Ansatz 320px|mini|Rastern einer Linie nach dem Bresenham-Verfahren, unten der Verlauf der Fehlervariablen mini|Die Rasterung von Linien kann durch Nutzung von Symmetrieeigenschaften vereinfacht werden. Der zulässige Bereich (Oktant) des Originalverfahrens ist farbig dargestellt, durch Fallunterscheidungen der Variablen dx und dy werden auch die anderen Bereiche erschlossen.
Die hier vorgestellte Variante ist ein sehr praxisnaher Ansatz und wurde zuerst von PittewayM. L. V. Pitteway: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter. In: Computer J., 10(3) November 1967, S. 282–289 (englisch) veröffentlicht und von van AkenJ. R.Van Aken: An Efficient Ellipse Drawing Algorithm. In: CG&A, 4(9), September 1984, S. 24–35 (englisch) verifiziert. Weiter unten wird die Variante mit der originalen Formulierung von Bresenham verglichen und gezeigt, dass die Lösungen äquivalent sind.
Zum Verständnis des Algorithmus beschränkt man sich auf den ersten Oktanten, also eine Linie mit einer Steigung zwischen 0 und 1 vom Startpunkt zum Endpunkt . Seien und mit . Für andere Oktanten muss man später Fallunterscheidungen über Vorzeichen von und und die Rollenvertauschung von und treffen.
Der Algorithmus läuft dann so, dass man in der schnellen Richtung (hier die positive -Richtung) immer einen Schritt macht und je nach Steigung hin und wieder zusätzlich einen Schritt in der langsameren Richtung (hier die -Richtung). Man benutzt dabei eine Fehlervariable, die bei einem Schritt in -Richtung den (hier kleineren) Wert subtrahiert bekommt. Bei Unterschreitung des Nullwerts wird ein -Schritt fällig und der (hier größere) Wert zur Fehlervariablen addiert. Diese wiederholten „Überkreuz“-Subtraktionen und -Additionen lösen die Division des Steigungsdreiecks in elementarere Rechenschritte auf.
Zusätzlich muss dieses Fehlerglied vorher sinnvoll initialisiert werden. Dazu betrachtet man den Fall von , bei dem in der Mitte nach der Hälfte von ein -Schritt kommen soll. Also initialisiert man das Fehlerglied mit . Ob dabei zu einer ganzen Zahl aufgerundet oder abgerundet wird, spielt kaum eine Rolle.
Mathematisch gesehen wird die Geradengleichung
aufgelöst in
und die Null links durch das Fehlerglied ersetzt. Ein Schritt um 1 in -Richtung bewirkt eine Verminderung des Fehlerglieds um . Wenn das Fehlerglied dabei unter Null gerät, wird es durch einen Schritt um 1 in -Richtung um erhöht, was nach der Voraussetzung das Fehlerglied auf jeden Fall wieder positiv macht, bzw. mindestens auf Null bringt.
Der originale Ansatz nach Bresenham (siehe unten) geht mehr geometrisch vor, wodurch in seinen Iterationsformeln auf beiden Seiten bis auf das Fehlerglied ein zusätzlicher Faktor 2 mitgeführt wird und auch die Fehlergliedinitialisierung anders hergeleitet wird.
Der Startpunkt und der Endpunkt des Rasters bilden ein rechteckiges Raster mit den vier Eckpunkten , , , . Wenn ist, dann befindet sich in jeder Spalte des rechteckigen Rasters genau ein Pixel und die Linie besteht aus Pixeln. Wenn ist, dann befindet sich in jeder Zeile genau ein Pixel und die Linie besteht aus Pixeln. Der euklidische Abstand zwischen dem Startpunkt und Endpunkt beträgt . Eine gerade Linie mit der Linienstärke 1 müsste daher aus Pixeln bestehen. Die mit dem Bresenham-Algorithmus erzeugte Linie besteht jedoch nur aus Pixeln. Setzt man diese Anzahlen ins Verhältnis, dann ergibt sich als Quotient die mittlere Linienstärke
Wenn entweder oder ist, ist offensichtlich . Für , also für die Steigung 1 mit dem Winkel 45 Grad ist die mittlere Linienstärke mit minimal.
Einfache Implementierung REM Bresenham-Algorithmus für eine Linie im ersten Oktanten in Pseudo-Basic. dx = xend - xstart dy = yend - ystart REM Im ersten Oktanten muss 0 < dy <= dx sein.
REM Initialisierungen x = xstart y = ystart SETPIXEL x, y fehler = dx / 2
REM Pixelschleife: immer ein Schritt in schnelle Richtung, hin und wieder auch einer in langsame WHILE x < xend REM Schritt in schnelle Richtung x = x + 1 fehler = fehler - dy IF fehler < 0 THEN REM Schritt in langsame Richtung y = y + 1 fehler = fehler + dx END IF SETPIXEL x, y WEND
Vergleich mit der originalen Formulierung von Bresenham
REM Quasi-Bresenham-Algorithmus REM Original-Bresenham dx = xend-xstart dx = xend-xstart dy = yend-ystart dy = yend-ystart
d = 2*dy – dx dO = 2*dy dNO = 2*(dy - dx)
x = xstart x = xstart y = ystart y = ystart SETPIXEL x,y SETPIXEL x,y fehler = dx/2 fehler = d
WHILE x < xend WHILE x < xend x = x + 1 x = x + 1 fehler = fehler-dy IF fehler < 0 THEN IF fehler <= 0 THEN fehler = fehler + dO ELSE y = y + 1 y = y + 1 fehler = fehler + dx fehler = fehler + dNO END IF END IF SETPIXEL x,y SETPIXEL x,y WEND WEND
Abgesehen von der Anpassung an den verwendeten BASIC-Dialekt sind folgende Unterschiede bei der originalen Formulierung zu beachten: Das Fehlerglied wird mit umgekehrtem Vorzeichen verwendet. Das Fehlerglied wird auf sein Vorzeichen abgefragt, bevor es aktualisiert wird, dadurch wird die zusätzliche Initialisierung mit dem dy-Term notwendig. Das Fehlerglied ist um den Faktor 2 erweitert, so dass bei der Initialisierung keine Division durch 2 stattfindet, dafür aber die Schrittvariablen für die Fehleraktualisierungen doppelt so groß sind.
Wenn man diese Unterschiede in der Formulierung berücksichtigt, stellt sich heraus, dass beide Formulierungen identisch arbeiten und somit äquivalent sind.
Elegantere Implementierungen Als eleganter formulierte Beispiele folgen als erstes der Quellcode eines BASIC-Programmes und anschließend eines Unterprogramms in C, welche die Fallunterscheidung in acht Oktanten nicht ausdrücklich vornehmen müssen.
Der Algorithmus soll für alle Oktanten gültig werden. Dabei müssen die Vorzeichen der Koordinatendistanzen und die eventuelle Vertauschung der Rollen von x und y berücksichtigt werden. Wenn man diese Fallunterscheidungen innerhalb der innersten Schleife treffen würde, also in hoher Anzahl, würde das die Geschwindigkeit der Berechnungen deutlich verringern. Eine effiziente Lösung versucht, all diese Fallunterscheidungen in der Initialisierungsphase des Verfahrens vor der inneren Hauptschleife abzuarbeiten, so dass innerhalb der inneren Schleife weiterhin nur die eine Abfrage für das Bresenham-Fehlerglied erfolgen muss.
Diese Formulierung führt (wie schon StocktonF. G. Stockton: XY Move Plotting. In: Communications of the ACM, vol. 4, no. 6, April 1963, S. 161 (englisch) indirekt vorschlug) diverse Abstraktionen ein: Zunächst wird der Schritt in die schnelle Richtung jetzt als Parallelschritt (parallel zu einer Koordinatenachse) angesehen, und wenn zusätzlich ein Schritt in die langsame Richtung erfolgt, wird das zu einem Diagonalschritt. Dann kann man in der Initialisierung Variablenwerte ermitteln, die für diese Fälle die Schrittweiten in den beiden Koordinatenrichtungen vorab festlegen und somit die Verallgemeinerung für die acht Oktanten erreichen. Beispielsweise ist bei einem Parallelschritt die Schrittweite in die dazu senkrechte Richtung eben Null. Zweitens rechnet man den Fehlerterm weiterhin wie im ersten Oktanten, mit Absolutbeträgen der Distanzen. In der innersten Schleife wird dann nicht mehr zuerst der Schritt in der schnellen Richtung ausgeführt, sondern als Erstes der Fehlerterm aktualisiert, und danach erst werden die Schrittweiten zu den bisherigen Koordinaten addiert, je nachdem, ob ein Parallel- oder ein Diagonalschritt erfolgen muss:
BASIC-Implementierung ' Bresenham-Algorithmus für eine Linie in einem beliebigen Oktanten in Pseudo-Basic dx = xend - xstart dy = yend - ystart
adx = ABS(dx) : ady = ABS(dy) ' Absolutbeträge der Distanzen sdx = SGN(dx) : sdy = SGN(dy) ' Vorzeichen der Distanzen
IF adx > ady THEN ' x ist die schnelle Richtung pdx = sdx : pdy = 0 ' pd. ist Parallelschritt ddx = sdx : ddy = sdy ' dd. ist Diagonalschritt deltaslowdirection = ady ' Delta in langsamer Richtung deltafastdirection = adx ' Delta in schneller Richtung ELSE ' y ist die schnelle Richtung pdx = 0 : pdy = sdy ' pd. ist Parallelschritt ddx = sdx : ddy = sdy ' dd. ist Diagonalschritt deltaslowdirection = adx ' Delta in langsamer Richtung deltafastdirection = ady ' Delta in schneller Richtung END IF
x = xstart y = ystart SETPIXEL x, y fehler = deltafastdirection / 2
' Pixelschleife: immer ein Schritt in der schnellen Richtung, ' hin und wieder auch einer in der langsamen Richtung. FOR i = 1 TO deltafastdirection ' Anzahl der zu zeichnenden Pixel ' Fehlerterm aktualisieren fehler = fehler - deltaslowdirection IF fehler < 0 THEN fehler = fehler + deltafastdirection ' Fehlerterm wieder positiv machen ' Diagonalschritt in langsamer Richtung x = x + ddx : y = y + ddy ELSE ' Parallelschritt in schneller Richtung x = x + pdx : y = y + pdy END IF SETPIXEL x, y NEXT
C-Implementierung
In dieser Implementierung wird die Signumfunktion verwendet. int signum(int x) { return x > 0 ? +1 : x < 0 ? -1 : 0; }
/* * Bresenham-Algorithmus: Linien auf Rastergeräten zeichnen * * Eingabeparameter: * xstart, ystart Koordinaten des Startpunkts * xend, yend Koordinaten des Endpunkts */ void DrawLineBresenham(int xstart, int ystart, int xend, int yend) { int x, y, t, dx, dy, incx, incy, pdx, pdy, ddx, ddy, deltaslowdirection, deltafastdirection, err;
/* Entfernung in beiden Dimensionen berechnen */ dx = xend - xstart; dy = yend - ystart;
/* Vorzeichen des Inkrements bestimmen */ incx = signum(dx); incy = signum(dy); if (dx < 0) dx = -dx; if (dy < 0) dy = -dy;