Das Kefk Network Wiki befindet sich im Testbetrieb.
Bresenham-Algorithmus
Aus Kefk.
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 Geraden entworfen wurde, auch für das Rastern 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. Dabei ist er so einfach, dass er nicht nur in der Firmware solcher Geräte verwendet wird, sondern in Grafikchips direkt in Hardware gegossen werden kann.
Der Genauigkeit halber muss angemerkt werden, dass der Name „Bresenham“ heute für eine ganze Familie von Algorithmen verwendet wird, die eigentlich von Anderen später entwickelt wurden, jedoch in der Nachfolge von Bresenham und mit einem verwandten Ansatz. Siehe weiterführende Literaturhinweise unten.
Inhaltsverzeichnis |
Ansatz
Die hier vorgestellte Variante ist ein sehr praxisnaher Ansatz und wurde zuerst von Pitteway [2] veröffentlicht und von van Aken [3] verifiziert.
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. (Ob dabei zu einer ganzen Zahl auf- oder abgerundet wird, spielt kaum eine Rolle.)
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. Ein Schritt um 1 in x-Richtung (Variable x) bewirkt eine Verminderung des Fehlerglieds um ein Mal dy. Wenn das Fehlerglied dabei unter Null gerät, wird es durch einen Schritt um 1 in y-Richtung (Variable y) um ein Mal dx erhöht, was nach der Voraussetzung dx>=dy das Fehlerglied auf jeden Fall wieder positiv macht, bzw. mindestens auf Null bringt.
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. Die Verwendung des malloc()-Befehls bedeutet allerdings gewisse Performance-Einschränkungen.
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 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²+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 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²+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.
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 geht außerdem von einer Zugabe von ½ Pixel zu Anfang aus. Das bewirkt bis zum Schnitt mit der Senkrechten einen aufgelaufenen Betrag von ungefähr r im Fehlerglied, den man also als anfängliche Zugabe initialisiert. Diese Zugabe von einem halben Pixel stellt sicher, dass die gezeichnete Kurve in der x-Richtung gerade um ±½ Pixel von der Idealkurve abweicht.
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 = r
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
Eine mögliche Implementierung des Bresenham-Algorithmus für einen Vollkreis in C. Hierbei wird für die quadratischen Terme eine weitere Variable mitgeführt, die dem Term 2*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--;
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);
}
}
Zeichnen nicht vollständiger Oktanten
Die obigen Implementierungen zeichnen immer nur komplette Oktanten bzw. Kreise. Wenn man nur einen bestimmten Kreisbogen von einem Winkel α bis zu einem Winkel β 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 Wurzelrechnung zurückgreifen muss (s. a. Babylonisches Wurzelziehen). 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 b²x²+a²y²=a²b² (wobei a und b die beiden Achsenlängen angeben) ausgehen und dann ähnlich wie oben beim Kreis vorgehen.
Man kann aber auch durch Skalierung der gezeichneten x- und y-Werte (und ggf. 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 ggf. 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.
Literatur
- ↑ Algorithm for computer control of a digital plotter. IBM Systems Journal 4, 1 (1965): 25–30, ISSN 0018-8670 (PDF, 220 KB, engl.). Bereits 1963 als Vortrag auf der ACM National Conference in Denver präsentiert.
- ↑ Pitteway, M.L.V., "Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter", Computer J., 10(3) November 1967, pp 282-289 (engl.)
- ↑ Van Aken, J.R., "An Efficient Ellipse Drawing Algorithm", CG&A, 4(9), September 1984, pp 24-35 (engl.)
Weblinks
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Bresenham-Algorithmus, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
