Der Bresenschinken-Algorithmus ist ein Algorithmus in der Computergrafik zum Zeichnen von Geraden oder Kreisen auf Rasteranzeigen.
Dieser wurde 1962 von Jack Bresenham, damals Programmierer bei IBM, entwickelt. 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 Geraden entworfen wurde, auch für das Zeichnen von Kreisen verwenden. Sogar die Quadratterme, die beim Kreis vorkommen, lassen sich rekursiv ohne jede Multiplikation aus dem jeweils vorhergehenden Term ableiten nach (n+1)² = n² + 2 · n + 1, wobei der Term 2 · n nicht als Multiplikation zählt, da er in Hardware bzw. auf Assemblerebene als einfache Shift-Operation implementiert wird.
Aufgrund obiger Eigenschaften ist die Bedeutung des Bresenham-Algorithmus bis heute ungebrochen, und er kommt unter anderem in Plottern, in den Grafikchips moderner Grafikkarten und in vielen Grafikbibliotheken zur Verwendung.
Ansatz
Zum Verständnis des Algorithmus beschränkt man sich auf den ersten Oktanten, also eine Linie mit einer Steigung zwischen 0 und 1 von (xstart,ystart) nach (xend,yend). Seien dx=xend-xstart und dy=yend-ystart mit 0<dy<=dx. Für andere Oktanten muss man später Fallunterscheidungen über Vorzeichen von dx und dy und die Rollenvertauschung von x und y treffen.
Der Algorithmus läuft dann so, dass man in der „schnellen“ Richtung (hier die positive x-Richtung) immer einen Schritt macht und je nach Steigung hin und wieder zusätzlich einen Schritt in der „langsameren“ Richtung (hier y). Man benutzt dabei eine Fehlervariable, die bei einem Schritt in x-Richtung den (kleineren) Wert dy subtrahiert bekommt. Bei Unterschreitung des Nullwerts wird ein y-Schritt fällig und der (größere) Wert dx 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 dy=1, wo man gern in der Mitte (nach der Hälfte von dx) den einen y-Schritt hätte. Also initialisiert man mit dx/2.
Mathematisch gesehen wird die Geradengleichung y=ystart+(x-xstart)*dy/dx aufgelöst in 0=-dx*(y-ystart)+dy*(x-xstart) und die Null links durch das Fehlerglied ersetzt.
Der originale Ansatz nach Bresenham (s. u. in Literatur) geht übrigens mehr geometrisch vor, wodurch in seinen Iterationsformeln auf beiden Seiten (bis auf das Fehlerglied) ein zusätzlicher Faktor 2 mitgeschleppt wird und auch die Fehlergliedinitialisierung anders hergeleitet wird.
Einfache Implementierung
Eine erste Implementierung ist nicht sehr elegant, demonstriert das Prinzip des Algorithmus aber sehr gut.
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
Elegantere Implementierung
Als weiteres Beispiel folgt der Quellcode eines eleganter formulierten Unterprogramms in C, das die Fallunterscheidung in acht Oktanten nicht ausdrücklich vornehmen muss. Hier ist der Aufrufer dafür verantwortlich, dass die zurück gelieferten Koordinaten-Arrays wieder freigegeben werden. Diese Form wurde gewählt, weil der Aufrufer so keine Interna des Algorithmus (Anzahl der erzeugten Koordinatenpaare) im Voraus kennen muss. Zu klein dimensionierte Arrays sind ein nicht enden wollender Quell von Pufferüberläufen.
void gbham(int xstart,int ystart,int xend,int yend,int *npix,int **xpix,int **ypix)
/*--------------------------------------------------------------
* Bresenham-Algorithmus: Linien auf Rastergeräten zeichnen
*
* Eingabeparameter:
* int xstart, ystart = Koordinaten des Startpunkts
* int xend, yend = Koordinaten des Endpunkts
*
* Ausgabeparameter:
* int *npix = Anzahl der Pixel
* int (*xpix)[i],(*ypix)[i] = Koordinaten des i-ten Pixels
*---------------------------------------------------------------
*/
{
int x, y, t, dist, xerr, yerr, dx, dy, incx, incy;
/* Entfernung in beiden Dimensionen berechnen */
dx = xend - xstart;
dy = yend - ystart;
/* Vorzeichen des Inkrements bestimmen */
if(dx<0)
{
incx = -1;
dx = -dx;
}
else if (dx > 0)
{
incx = 1;
}
else
{
incx = 0;
}
if(dy < 0)
{
incy = -1;
dy = -dy;
}
else if (dy > 0)
{
incy = 1;
}
else
{
incy = 0;
}
/* feststellen, welche Entfernung größer ist */
dist = (dx > dy)?dx:dy;
/* Initialisierungen vor Schleifenbeginn */
x = xstart;
y = ystart;
xerr = dx;
yerr = dy;
*npix = dist + 1;
*xpix = (int*)malloc( *npix * sizeof( int));
if( NULL == *xpix)
{
*npix = 0;
return;
}
*ypix=(int*)malloc( *npix * sizeof( int));
if( NULL == *ypix)
{
free( *xpix);
*npix = 0;
return;
}
/* Pixel berechnen */
for(t = 0; t < dist; ++t)
{
(*xpix)[t] = x;
(*ypix)[t] = y;
xerr += dx;
yerr += dy;
if(xerr > dist)
{
xerr -= dist;
x += incx;
}
if(yerr>dist)
{
yerr -= dist;
y += incy;
}
}
(*xpix)[dist] = xend;
(*ypix)[dist] = yend;
} /* gbham() */
Kreisvariante des Algorithmus
Der Ansatz für die Kreisvariante des Bresenham-Algorithmus geht entsprechend von der Kreisgleichung x²+y²=r² aus. Man betrachtet zunächst wieder nur den ersten Oktanten. Hier möchte man eine Kurve zeichnen, die beim Punkt (r,0) anfängt und dann nach oben links bis zum Winkel von 45° fortgesetzt wird.
Die „schnelle“ Richtung ist hier die y-Richtung. Man macht immer einen Schritt in die positive y-Richtung, und ab und zu muss man auch einen Schritt in die „langsame“, negative x-Richtung machen.
Die ständigen Quadratberechnungen (siehe Kreisgleichung) oder womöglich sogar Wurzelberechnungen vermeidet man wieder durch Auflösen in Einzelschritte und rekursive Berechnung der Terme aus den jeweils vorangehenden.
Von der Kreisgleichung kommt man zur umgeformten Gleichung 0=x²+y²-r² mit r² ein einziges Mal während der Initialisierung berechnet, x²=(xvorher+1)²=xvorher²+2*xvorher+1 (entsprechend für y), wobei xvorher² als eigene Variable mitgeführt wird. Zusätzlich muss man dann beim Setzen der Pixel noch die Mittelpunktskoordinaten hinzuaddieren. Diese ständigen Festkommaadditionen schränken die Performance nicht merkbar ein, da man sich ja Quadrierungen oder gar Wurzelziehungen in der innersten Schleife erspart. Wieder wird die Null in der Gleichung durch das Fehlerglied ersetzt. Dessen Initialisierung ist hier nicht so trivial.
Die Formulierung wird hier wieder nur für den ersten Oktanten gezeigt, und wieder ergeben sich die anderen Oktanten durch Vorzeichenwechsel in dx und dy und Rollenvertauschung von x und y. Die Erweiterung auf den Vollkreis, wie sie für Grafikdisplays, aber nicht für Plotter geeignet ist, ist in Kommentaren beigefügt.
REM Bresenham-Algorithmus für einen Achtelkreis in Pseudo-Basic
REM gegeben seien r, xmittel, ymittel
REM Initialisierungen für den ersten Oktanten
r2 = r*r : REM einzige Multiplikation
x = r
x2 = r2
y = 0
y2 = 0
fehler = r2/2 : REM dieser Ansatz ist diskutierbar
REM Achtung, Gefahr von Rundungsfehlern:
yend = INT(r*0.70710678) : REM = INT(SQR(r2/2)) = INT(r*SQR(1/2)), Konstante verwendbar
REM "schnelle" Richtung ist hier y!
SETPIXEL xmittel + x, ymittel + y
REM Pixelschleife: immer ein Schritt in schnelle Richtung, hin und wieder auch einer in langsame
WHILE y < yend
REM Schritt in schnelle Richtung
dy = y*2+1 : REM bei Assembler-Implementierung *2 per Shift
y = y+1
y2 = y2+dy
fehler = fehler-dy
IF fehler<0 THEN
REM Schritt in langsame Richtung (hier negative x-Richtung)
dx = 1-x*2 : REM bei Assembler-Implementierung *2 per Shift
x = x-1
x2 = x2+dx
fehler = fehler+dx
END IF
SETPIXEL xmittel+x, ymittel+y
REM Wenn es um einen Bildschirm und nicht mechanisches Plotten geht,
REM kann man die anderen Oktanten hier gleich mit abdecken:
REM SETPIXEL xmittel-x, ymittel+y
REM SETPIXEL xmittel-x, ymittel-y
REM SETPIXEL xmittel+x, ymittel-y
REM SETPIXEL xmittel+y, ymittel+x
REM SETPIXEL xmittel-y, ymittel+x
REM SETPIXEL xmittel-y, ymittel-x
REM SETPIXEL xmittel+y, ymittel-x
WEND
Durch Skalierung der gezeichneten x- und y-Werte (und ggf. horizontaler bzw. vertikaler Linienerweiterungen) kann man auf diese Weise sogar achsenparallele Ellipsen erzeugen.
Eine mögliche Implementierung des Bresenham-Algorithmus für einen Vollkreis in C:
void rasterCircle(int x0, int y0, int radius)
{
int f = 1 - radius;
int ddF_x = 0;
int ddF_y = -2 * radius;
int x = 0;
int y = radius;
setPixel(x0, y0 + radius);
setPixel(x0, y0 - radius);
setPixel(x0 + radius, y0);
setPixel(x0 - radius, y0);
while(x < y)
{
if(f >= 0)
{
y--;
ddF_y += 2;
f += ddF_y;
}
x++;
ddF_x += 2;
f += ddF_x + 1;
setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);
setPixel(x0 + x, y0 - y);
setPixel(x0 - x, y0 - y);
setPixel(x0 + y, y0 + x);
setPixel(x0 - y, y0 + x);
setPixel(x0 + y, y0 - x);
setPixel(x0 - y, y0 - x);
}
}