Bresenham-Algorithmus

Der Bresenham-Algorithmus ist ein Algorithmus in der Computergrafik zum Zeichnen (Rastern) von Geraden oder Kreisen auf Rasteranzeigen. Für Linienalgorithmen 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 $(n+1)^{2}=n^{2}+2\cdot n+1$ , wobei der Term $2\cdot n$ nicht als Multiplikation zählt, da er in Hardware bzw. auf Assemblerebene als einfache Shift-Operation implementiert wird und der Term $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).

Ansatz

Rastern einer Linie nach dem Bresenham-Verfahren, unten der Verlauf der Fehlervariablen

Die hier vorgestellte Variante ist ein sehr praxisnaher Ansatz und wurde zuerst von Pitteway^[2] veröffentlicht und von van Aken^[3] 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 $(x_{\mathrm {start} },y_{\mathrm {start} })$ zum Endpunkt $(x_{\mathrm {end} },y_{\mathrm {end} })$ . Seien $dx=x_{\mathrm {end} }-x_{\mathrm {start} }$ und $dy=y_{\mathrm {end} }-y_{\mathrm {start} }$ mit $0<dy\leq 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 die $y$ -Richtung). Man benutzt dabei eine Fehlervariable, die bei einem Schritt in $x$ -Richtung den (hier kleineren) Wert $dy$ subtrahiert bekommt. Bei Unterschreitung des Nullwerts wird ein $y$ -Schritt fällig und der (hier größere) Wert $dx$ zur Fehlervariablen addiert. Diese wiederholten „Überkreuz“-Subtraktionen und -Additionen lösen die Division des Steigungsdreiecks $m={\tfrac {dy}{dx}}$ in elementarere Rechenschritte auf.

Zusätzlich muss dieses Fehlerglied vorher sinnvoll initialisiert werden. Dazu betrachtet man den Fall von $dy=1$ , bei dem in der Mitte nach der Hälfte von $dx$ ein $y$ -Schritt kommen soll. Also initialisiert man das Fehlerglied mit ${\tfrac {dx}{2}}$ . Ob dabei zu einer ganzen Zahl aufgerundet oder abgerundet wird, spielt kaum eine Rolle.

Mathematisch gesehen wird die Geradengleichung

y=y_{\mathrm {start} }+(x-x_{\mathrm {start} })\cdot {\frac {dy}{dx}}

aufgelöst in

0=dx\cdot (y-y_{\mathrm {start} })-dy\cdot (x-x_{\mathrm {start} })

und die Null links durch das Fehlerglied ersetzt. Ein Schritt um 1 in $x$ -Richtung bewirkt eine Verminderung des Fehlerglieds um $1\cdot dy$ . Wenn das Fehlerglied dabei unter Null gerät, wird es durch einen Schritt um 1 in $y$ -Richtung um $1\cdot dx$ erhöht, was nach der Voraussetzung $dx\geq dy$ 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 $(x_{\mathrm {start} },y_{\mathrm {start} })$ , $(x_{\mathrm {start} },y_{\mathrm {end} })$ , $(x_{\mathrm {end} },y_{\mathrm {start} })$ , $(x_{\mathrm {end} },y_{\mathrm {end} })$ . Wenn $0<dy\leq dx$ ist, dann befindet sich in jeder Spalte des rechteckigen Rasters genau ein Pixel und die Linie besteht aus $dx$ Pixeln. Wenn $0<dx\leq dy$ ist, dann befindet sich in jeder Zeile genau ein Pixel und die Linie besteht aus $dy$ Pixeln. Der euklidische Abstand zwischen dem Startpunkt und Endpunkt beträgt $d={\sqrt {(x_{\mathrm {end} }-x_{\mathrm {start} })^{2}+(y_{\mathrm {end} }-y_{\mathrm {start} })^{2}}}$ . Eine gerade Linie mit der Linienstärke 1 müsste daher aus $d$ Pixeln bestehen. Die mit dem Bresenham-Algorithmus erzeugte Linie besteht jedoch nur aus $\max(dx,dy)$ Pixeln. Setzt man diese Anzahlen ins Verhältnis, dann ergibt sich als Quotient die mittlere Linienstärke

w={\frac {\max(dx,dy)}{d}}={\frac {\max(x_{\mathrm {end} }-x_{\mathrm {start} },y_{\mathrm {end} }-y_{\mathrm {start} })}{\sqrt {(x_{\mathrm {end} }-x_{\mathrm {start} })^{2}+(y_{\mathrm {end} }-y_{\mathrm {start} })^{2}}}}

Wenn entweder $dx=0$ oder $dy=0$ ist, ist offensichtlich $w=1$ . Für $dx=dy$ , also für die Steigung 1 mit dem Winkel 45 Grad ist die mittlere Linienstärke mit $w={\tfrac {1}{\sqrt {2}}}\approx 0{,}707$ minimal.

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

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 Stockton^[4] 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

REM Bresenham-Algorithmus für eine Linie in einem beliebigen Oktanten in Pseudo-Basic
dx = xend-xstart
dy = yend-ystart

REM Initialisierungen
adx = ABS(dx): ady = ABS(dy) ' Absolutbeträge Distanzen
sdx = SGN(dx): sdy = SGN(dy) ' Signum der Distanzen

IF adx > ady THEN
  ' x ist schnelle Richtung
  pdx = sdx: pdy = 0   ' pd. ist Parallelschritt
  ddx = sdx: ddy = sdy ' dd. ist Diagonalschritt
  deltaslowdirection  = ady: deltafastdirection  = adx ' Delta in langsamer Richtung, Delta in schneller Richtung
ELSE
  ' y ist schnelle Richtung
  pdx = 0  : pdy = sdy ' pd. ist Parallelschritt
  ddx = sdx: ddy = sdy ' dd. ist Diagonalschritt
  deltaslowdirection  = adx: deltafastdirection  = ady ' Delta in langsamer Richtung, Delta in schneller Richtung
END IF

x = xstart
y = ystart
SETPIXEL x,y
fehler = deltafastdirection/2

REM Pixelschleife: immer ein Schritt in schnelle Richtung, hin und wieder auch einer in langsame
FOR i=1 TO deltafastdirection          ' Anzahl der zu zeichnenden Pixel
   REM Aktualisierung Fehlerterm
   fehler = fehler - deltaslowdirection
   IF fehler < 0 THEN
      fehler = fehler + deltafastdirection ' Fehlerterm wieder positiv machen
      REM Schritt in langsame Richtung
      x = x + ddx: y = y + ddy ' Diagonalschritt
   ELSE
      REM Schritt in schnelle Richtung
      x = x + pdx: y = y + pdy ' Parallelschritt
   END IF
   SETPIXEL x,y
NEXT

C-Implementierung

In dieser Implementierung wird die Signumfunktion verwendet.

/* signum function */
int sgn(int x)
{
    if (x > 0) return +1;
    if (x < 0) return -1;
    return 0;
}

void gbham(int xstart, int ystart, int xend, int yend)
/*--------------------------------------------------------------
 * Bresenham-Algorithmus: Linien auf Rastergeräten zeichnen
 *
 * Eingabeparameter:
 *    int xstart, ystart        = Koordinaten des Startpunkts
 *    int xend, yend            = Koordinaten des Endpunkts
 *
 * Ausgabe:
 *    void SetPixel(int x, int y) setze ein Pixel in der Grafik
 *         (wird in dieser oder aehnlicher Form vorausgesetzt)
 *---------------------------------------------------------------
 */
{
    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 = sgn(dx);
    incy = sgn(dy);
    if (dx < 0) dx = -dx;
    if (dy < 0) dy = -dy;

    /* feststellen, welche Entfernung größer ist */
    if (dx > dy)
    {
        /* x ist schnelle Richtung */
        pdx = incx; pdy = 0;    /* pd. ist Parallelschritt */
        ddx = incx; ddy = incy; /* dd. ist Diagonalschritt */
        deltaslowdirection = dy;   deltafastdirection = dx;   /* Delta in langsamer Richtung, Delta in schneller Richtung */
    }
    else
    {
        /* y ist schnelle Richtung */
        pdx = 0;    pdy = incy; /* pd. ist Parallelschritt */
        ddx = incx; ddy = incy; /* dd. ist Diagonalschritt */
        deltaslowdirection = dx;   deltafastdirection = dy;   /* Delta in langsamer Richtung, Delta in schneller Richtung */
    }

    /* Initialisierungen vor Schleifenbeginn */
    x = xstart;
    y = ystart;
    err = deltafastdirection / 2;
    SetPixel(x,y);

    /* Pixel berechnen */
    for(t = 0; t < deltafastdirection; ++t) /* t zaehlt die Pixel, deltafastdirection ist Anzahl der Schritte */
    {
        /* Aktualisierung Fehlerterm */
        err -= deltaslowdirection;
        if(err < 0)
        {
            /* Fehlerterm wieder positiv (>=0) machen */
            err += deltafastdirection;
            /* Schritt in langsame Richtung, Diagonalschritt */
            x += ddx;
            y += ddy;
        }
        else
        {
            /* Schritt in schnelle Richtung, Parallelschritt */
            x += pdx;
            y += pdy;
        }
        SetPixel(x, y);
    }
}

Kompakte Variante

Der Bresenham-Algorithmus kann auch in einer einfachen Variante in C implementiert werden:

void line(int x0, int y0, int x1, int y1)
{
    int dx =  abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2; /* error value e_xy */

    while (1) {
        setPixel(x0, y0);
        if (x0 == x1 && y0 == y1) break;
        e2 = 2 * err;
        if (e2 > dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */
        if (e2 < dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */
    }
}

Das Fehlerglied wird dabei sowohl für die langsame als auch die schnelle Richtung als Schritterkennung verwendet. Die vier Quadranten werden über das Vorzeicheninkrement (sx, sy) abgedeckt. Die Akkumulation des Fehlerglieds löst bei Überschreitung des Schwellwertes den bedingten Schritt aus, im Unterschied zur ursprünglichen Variante simultan in beide Richtungen: positive Fehlerwerte für x und negative für die y-Achse. Das Beispiel zeigt damit auch elegant die xy-Symmetrie des Bresenham-Algorithmus.

Kreisvariante des Algorithmus

Rastern einer Kreislinie nach dem Bresenham-Verfahren

Der Ansatz für die Kreisvariante des Bresenham-Algorithmus geht auch nicht auf Bresenham selbst zurück, er ähnelt der Methode von Horn aus dem Übersichtsartikel, siehe auch Pitteway und van Aken unten. Man geht entsprechend von der Kreisgleichung $x^{2}+y^{2}=r^{2}$ 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 trigonometrische oder Wurzelberechnungen vermeidet man wieder durch Auflösen in Einzelschritte und rekursive Berechnung der Terme aus den jeweils vorangehenden.

Mathematisch: Von der Kreisgleichung kommt man zur umgeformten Gleichung

0=x^{2}+y^{2}-r^{2}

,

wobei $r^{2}$ gar nicht explizit berechnet werden muss,

x^{2}=(x_{\mathrm {vorher} }-1)^{2}=x_{\mathrm {vorher} }^{2}-2\cdot x_{\mathrm {vorher} }+1

(entsprechend für

y

),

wobei auch hier $x_{\mathrm {vorher} }^{2}$ nicht als eigene Variable mitgeführt werden muss, sondern nur die Differenz von einem Schritt zum nächsten $(-2\cdot x_{\mathrm {vorher} }+1)$ dem Fehlerglied aufgeschlagen wird. Wieder wird die Null in der Gleichung durch das Fehlerglied ersetzt.

Zusätzlich muss man dann beim Setzen der Pixel noch die Mittelpunktskoordinaten hinzuaddieren. Diese ständigen Festkommaadditionen schränken die Performance aber nicht merkbar ein, da man sich ja Quadrierungen oder gar Wurzelziehungen in der innersten Schleife erspart.

Durch den Ansatz von der Kreisgleichung aus ist sichergestellt, dass die Koordinaten maximal um 1 Pixel, den Digitalisierungsfehler, von der Idealkurve abweichen. Die Initialisierung des Fehlerglieds soll nun bewirken, dass der erste Schritt in die langsame Richtung dann erfolgt, wenn die echte Kreiskurve um ein halbes Pixel in der langsamen Koordinate nach innen gekommen ist. Details zur Rechnung weiter unten, es läuft auf eine Initialisierung des Fehlerglieds mit dem Radius $r$ hinaus.

Die Pixel der Kreislinie bilden ein rechteckiges Raster mit den vier Eckpunkten $(-r,-r)$ , $(-r,r)$ , $(r,-r)$ , $(r,r)$ . Für $-{\tfrac {r}{\sqrt {2}}}\leq x\leq {\tfrac {r}{\sqrt {2}}}$ , also $y\leq -{\tfrac {r}{\sqrt {2}}}$ oder $y\geq {\tfrac {r}{\sqrt {2}}}$ , befinden sich in jeder Spalte des rechteckigen Rasters befinden sich genau 2 Pixel. Ebenso befinden sich für $-{\tfrac {r}{\sqrt {2}}}\leq y\leq {\tfrac {r}{\sqrt {2}}}$ , also $x\leq -{\tfrac {r}{\sqrt {2}}}$ oder $x\geq {\tfrac {r}{\sqrt {2}}}$ in jeder Zeile des rechteckigen Rasters genau 2 Pixel. Die Länge der Kreislinie, d. h. der Umfang des Kreises beträgt $2\cdot \pi \cdot r$ . Eine Kreislinie mit der Linienstärke 1 müsste daher aus etwa $2\cdot \pi \cdot r$ Pixeln bestehen. Die mit dem Bresenham-Algorithmus erzeugte Linie besteht jedoch wie gezeigt nur aus etwa $2\cdot 2\cdot \left({\tfrac {r}{\sqrt {2}}}-\left(-{\tfrac {r}{\sqrt {2}}}\right)\right)=4\cdot {\sqrt {2}}\cdot r$ Pixeln. Setzt man diese Anzahlen ins Verhältnis, dann ergibt sich als Quotient die mittlere Linienstärke

w={\frac {4\cdot {\sqrt {2}}\cdot r}{2\cdot \pi \cdot r}}={\frac {2\cdot {\sqrt {2}}}{\pi }}\approx 0{,}900

Die Formulierung des Algorithmus 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
x = r
y = 0
fehler = r
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 < x
   REM Schritt in schnelle Richtung
   dy = y*2+1 : REM bei Assembler-Implementierung *2 per Shift
   y = y+1
   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
      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

Eine mögliche Implementierung des Bresenham-Algorithmus für einen Vollkreis in der Programmiersprache C. Hierbei wird für die quadratischen Terme eine weitere Variable mitgeführt, die dem Term $2\cdot n+1$ von oben entspricht, sie muss von einem Schritt zum nächsten lediglich um 2 erhöht werden:

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 -= 1;
            ddF_y += 2;
            f += ddF_y;
        }
        x += 1;
        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);
    }
}

Herleitung der Fehlerglied-Initialisierung

Den Schnittpunkt, an dem die Kreislinie um ${\tfrac {1}{2}}$ Pixel nach innen gekommen ist, berechnet man nach der Kreisgleichung:

\,x^{2}+y^{2}=r^{2}

oder

y={\sqrt {r^{2}-x^{2}}}

Am gefragten Punkt $(x_{1},x_{2})$ soll gelten: $x_{1}=r-{\tfrac {1}{2}}$ , also ergibt sich:

y_{1}={\sqrt {r^{2}-\left(r-{\tfrac {1}{2}}\right)^{2}}}={\sqrt {r^{2}-\left(r^{2}-r+{\tfrac {1}{4}}\right)}}={\sqrt {r-{\tfrac {1}{4}}}}

Da bis hierhin noch kein $x$ -Schritt stattgefunden haben soll und der Fehler bei $y$ genau $y-1$ Mal angepasst wurde, ist das Fehlerglied mit

\sum _{y=0}^{y_{1}-1}(2\cdot y+1)=y_{1}^{2}

zu initialisieren, wobei $y_{1}^{2}$ durch Runden zu $r$ wird.

Beispiel

In der Abbildung rechts ist $r=11$ und $y_{1}=3$ (abgerundet), Das Fehlerglied bei $y=y_{1}=3$ ist $1+3+5=9$ , Fehlerglied bei $y=4$ ist $1+3+5+7=16$ . Wurde das Fehlerglied mit $r=11$ initialisiert, so findet der erste Vorzeichenwechsel und damit der erste $x$ -Schritt tatsächlich beim Übergang von $y_{1}$ zu $y_{1}+1$ statt.

Zeichnen nicht-vollständiger Oktanten

Die obigen Implementierungen zeichnen immer nur komplette Oktanten bzw. Kreise. Wenn man nur einen bestimmten Kreisbogen von einem Winkel $\alpha$ bis zu einem Winkel $\beta$ zeichnen will, muss man das so implementieren, dass man sich die $x$ - und $y$ -Koordinaten dieser Endpunkte im Vorhinein berechnet, wobei man unvermeidlich auf Trigonometrie oder Berechnung von Quadratwurzeln zurückgreifen muss (siehe Heron-Verfahren). Dann lässt man den Bresenham-Algorithmus über den kompletten Oktanten bzw. Kreis laufen und setzt die Pixel aber nur dann, wenn sie in den gewünschten Bereich fallen. Nach Beendigung dieses Kurvenstücks kann man den Algorithmus vorzeitig abbrechen.

Ellipsen

Auch für Ellipsen gibt es wieder mehrere mögliche Ansätze. Man kann bei achsenparallelen Ellipsen von der entsprechenden Gleichung

{\frac {x^{2}}{a^{2}}}+{\frac {y^{2}}{b^{2}}}=1

wobei $a$ und $b$ die beiden Halbachsenlängen angeben, ausgehen und dann ähnlich wie oben beim Kreis vorgehen.

Man kann aber auch durch Skalierung der gezeichneten $x$ - und $y$ -Werte (und gegebenenfalls horizontaler bzw. vertikaler Linienerweiterungen) auf Basis des Kreisalgorithmus solche achsenparallele Ellipsen erzeugen. Dabei benutzt man den Kreisalgorithmus mit der kleineren Ellipsenachse als Radius und addiert in der anderen Richtung einen Wert hinzu, den man wiederum per Bresenham-Linienalgorithmus ansteigend vom Pol zum Äquator ermitteln kann. Da die Ellipse in die längere Achsenrichtung gestreckt werden muss, setzt man dann nicht nur einzelne Pixel, sondern muss gegebenenfalls eine Linie (allerdings eine einfache, horizontale oder vertikale) vom vorherigen Punkt zum nächsten ziehen.

Eine allgemeine Ellipse kann man aus so einer achsenparallelen gewinnen, indem man die komplette Grafik zusätzlich einer Scherung unterwirft. Wieder benutzt man einen zusätzlichen Bresenham-Linienalgorithmus, um den Versatz in eine der Achsenrichtungen ansteigend zu ermitteln und ihn bei jeder zu zeichnenden Koordinate einzubeziehen.

Die Linienstärke einer mit dem Bresenham-Algorithmus gezeichneten Ellipse lässt sich nicht so einfach berechnen wie für einen Kreis, weil sich der Umfang einer Ellipse nur näherungsweise mit einem Integral oder einer speziellen Reihenentwicklung berechnen lässt.

Kompakte Variante

Wie bei dem Algorithmus für die Linie kann auch die Kreisvariante xy-symmetrisch formuliert werden. Damit kann also ein kontinuierlicher Viertelkreis gezeichnet werden, was bei Ellipsen hilfreich ist.

void ellipse(int xm, int ym, int a, int b)
{
    int dx = 0, dy = b; /* im I. Quadranten von links oben nach rechts unten */
    long a2 = a*a, b2 = b*b;
    long err = b2-(2*b-1)*a2, e2; /* Fehler im 1. Schritt */

    do
    {
        setPixel(xm + dx, ym + dy); /* I. Quadrant */
        setPixel(xm - dx, ym + dy); /* II. Quadrant */
        setPixel(xm - dx, ym - dy); /* III. Quadrant */
        setPixel(xm + dx, ym - dy); /* IV. Quadrant */
        e2 = 2*err;
        if (e2 <  (2 * dx + 1) * b2) { ++dx; err += (2 * dx + 1) * b2; }
        if (e2 > -(2 * dy - 1) * a2) { --dy; err -= (2 * dy - 1) * a2; }
    }
    while (dy >= 0);

    while (dx++ < a) /* fehlerhafter Abbruch bei flachen Ellipsen (b=1) */
    {
        setPixel(xm+dx, ym); /* -> Spitze der Ellipse vollenden */
        setPixel(xm-dx, ym);
    }
}

Der Algorithmus testet dabei immer einen Diagonalschritt und korrigiert diesen bei zu großer Abweichung. Die Schritte enden aber immer im nächsten Quadranten und dann wird bei flachen Ellipsen, also für den Fall $b=1$ , zu früh abgebrochen. In diesen Fällen ist also eine Ergänzung notwendig. Die Fehlervariable muss den 3-fachen Wertebereich (Stellenanzahl, Bits) vom Radius (Halbachsen) aufweisen (etwa 64-bit oder Gleitkommazahl).

Die Methode kann auch für Kreise, also für den Fall $a=b=r$ , verwendet werden. Die Vereinfachung, indem etwa die Fehlervariable durch $2\cdot r^{2}$ gekürzt wird, führt dann zu den oben gezeigten Kreisbeispielen. Aus vier nahtlosen Viertelkreisen wird so ein kontinuierlicher Vollkreis, wie es etwa bei Plottern erforderlich ist.

Weitere Verallgemeinerungen

Bereits im Jahr 1968 wurde die Idee publiziert, den Bresenham-Algorithmus für die Digitalisierung von durch kubische Gleichungen beschriebenen Kurven zu verallgemeinern.^[5] Wirklich ausgeführt wurden die Details erst 1993 unter anderem von Pitteway^[6] und unabhängig davon in einem Patent aus dem Jahre 1993.^[7] Eine Anwendung zur Strukturierung im Sub-Mikrometer-Bereich von durch rationale kubische Bézierkurven berandeten geometrischen Figuren fand das Verfahren in dem Lithografie-Tool LION-LV1.^[8]

Siehe auch

Weblinks

Commons: Bresenham-Algorithmus – Sammlung von Bildern, Videos und Audiodateien

Rosetta Code: Bitmap/Bresenham's line algorithm
Rosetta Code: Bitmap/Midpoint circle algorithm
www.javatpoint.com: Bresenham's Line Algorithm
www.javatpoint.com: MidPoint Circle Algorithm
GeeksforGeeks: Bresenham’s Line Generation Algorithm
GeeksforGeeks: Mid-Point Circle Drawing Algorithm
Oliver Vornberger, Institut für Informatik, Universität Osnabrück: Computergrafik
National Institute of Standards and Technology, U.S. Department of Commerce: Bresenham's algorithm
Alois Zingl, Vienna, Austria: The Beauty of Bresenham’s Algorithm – Eine einfache Implementierung zum Zeichnen von Linien, Kreisen, Ellipsen und Bézierkurven
Alois Zingl, Vienna, Austria: Rasterizing curves – Web Application in JavaScript

Einzelnachweise

↑ 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.
↑ M. L. V. Pitteway: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter. In: Computer J., 10(3) November 1967, S. 282–289 (englisch)
↑ J. R.Van Aken: An Efficient Ellipse Drawing Algorithm. In: CG&A, 4(9), September 1984, S. 24–35 (englisch)
↑ F. G. Stockton: XY Move Plotting. In: Communications of the ACM, vol. 4, no. 6, April 1963, S. 161 (englisch)
↑ R. J. Botting, M. L. V. Pitteway: Cubic extension of a conic section algorithm. In: Computer Journal, 11, 1968, S. 120
↑ Fiaz Hussain, Michael L. V. Pitteway: Rasterizing the outlines of fonts. (PDF; 162 kB) In: Electronic Publishing, Band 6, 1993, Nr. 3, S. 171–181
↑ Patent EP0954618B1: Verfahren zur Generierung von ebenen technischen Kurven oder Konturen. Angemeldet am 23. Dezember 1993, veröffentlicht am 29. September 2004, Erfinder: Traugott Schulmeiss.‌
↑ R. Plontke: LION-LV1: Ein Lithographie-System für Integrierte Optik und Nanostrukturen. In: Jenaer Jahrbuch zur Technik- und Industriegeschichte, Band 9, 2006, S. 535–566

[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.

[2] M. L. V. Pitteway: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter. In: Computer J., 10(3) November 1967, S. 282–289 (englisch)

[3] J. R.Van Aken: An Efficient Ellipse Drawing Algorithm. In: CG&A, 4(9), September 1984, S. 24–35 (englisch)

[4] F. G. Stockton: XY Move Plotting. In: Communications of the ACM, vol. 4, no. 6, April 1963, S. 161 (englisch)

[5] R. J. Botting, M. L. V. Pitteway: Cubic extension of a conic section algorithm. In: Computer Journal, 11, 1968, S. 120

[6] Fiaz Hussain, Michael L. V. Pitteway: Rasterizing the outlines of fonts. (PDF; 162 kB) In: Electronic Publishing, Band 6, 1993, Nr. 3, S. 171–181

[7] Patent EP0954618B1: Verfahren zur Generierung von ebenen technischen Kurven oder Konturen. Angemeldet am 23. Dezember 1993, veröffentlicht am 29. September 2004, Erfinder: Traugott Schulmeiss.‌

[8] R. Plontke: LION-LV1: Ein Lithographie-System für Integrierte Optik und Nanostrukturen. In: Jenaer Jahrbuch zur Technik- und Industriegeschichte, Band 9, 2006, S. 535–566

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Bresenham-Algorithmus

Inhaltsverzeichnis

Ansatz

Einfache Implementierung

Vergleich mit der originalen Formulierung von Bresenham

Elegantere Implementierungen

BASIC-Implementierung

C-Implementierung

Kompakte Variante

Kreisvariante des Algorithmus

Herleitung der Fehlerglied-Initialisierung

Beispiel

Zeichnen nicht-vollständiger Oktanten

Ellipsen

Kompakte Variante

Weitere Verallgemeinerungen

Siehe auch

Weblinks

Einzelnachweise