Bresenham-Algorithmus

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.^[1] 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 ${\displaystyle (n+1)^{2}=n^{2}+2\cdot n+1}$, wobei der Term ${\displaystyle 2\cdot n}$ nicht als Multiplikation zählt, da er in Hardware bzw. auf Assemblerebene als einfache Shift-Operation implementiert wird und der Term ${\displaystyle n^{2}}$ 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).

1. ↑ J. E. Bresenham: Algorithm for computer control of a digital plotter. In: IBM Systems Journal, 4, 1, 1965, S. 25–30, ISSN 0018-8670, 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.