Bresenham's Circle Algorithm
----------------------------
y Dies soll einen Kreis darstellen, wie
\ | / ja unschwer zu erkennen ist.
\ ..... / Zu den sch”nen Eigenschaften eines
. | . Kreises geh”ren seine Symmmtrie.
. \ | / . Ein Kreis hat unendlich viele
. \|/ . Symmetrieachsen, die alle durch den
---.----+----.---x Mittelpunkt gehen.
. /|\ . Zur Berechnung macht man sich aller-
. / | \ . dings nur acht dieser Achsen zunutze.
. | , Dies liegt an der Anordnung der
/ ..,,, \ Pixel, die man sp„ter zeichnen will.
/ | \ Diese acht Achsen erzeugen auf dem
| Kreis acht Punkte in den sogenannten
Oktanten und teilen somit den Kreis
in acht Kreisbogenteile. Im Kreisalgotithmus von Bresenham wird
nur ein einziger dieser acht Kreisbogenteile berechnet, es
handelt sich dabei um den Teil von 270ø bis 315ø, in der
Zeichnung durch die Kommas dargestellt. Die restlichen sieben
Kreisteile werden dann nur ber die Symmetrieeigenschaften des
Kreises berechnet.
Dies bedeutet fr die Berechnung:
1. Der Algorithmus berechnet 1 Pixel in einem Kreisbogenteil.
2. Dieses Pixel wird gesetzt.
3. Die restlichen sieben Pixel werden ber die Symmetrieachsen-
beziehungen 'berechnet' und gesetzt.
4. Dann wird das n„chste Pixel berechnet, womit der Algorithmus
wieder bei 2. anf„ngt.
Auf diese Art und Weise wird der gesamte Kreisbogenteil be-
rechnet, bis eine Abruchbedingung eintritt.
Danach ist der Kreis fertig.
Hier kommt jetzt in Pascalcode die Kreisprozedur.
Sie in andere Programmiersprachen umzusetzen, drfte wegen der
Kommentare nicht schwerfallen.
PROCEDURE Bresenham (X_koord, Y_koord, Radius, Color);
{šbergeben werden: die X-Koordinate des Mittelpunktes in Pixeln,
die Y-Koordinate des Mittelpunktes in Pixeln, der Radius des
gewnschten Kreises in Pixeln sowie fr die Pascal-PutPixel-
Anweisung die gewnschte Farbe des Kreises.
Nebenbei: die X- und die Y-Koordinate sollten grӇer als der
Radius sein, da der Algorithmus die Pixel relativ zum Kreis-
mittelpunkt berechnet.}
VAR Xvar, Yvar, Korr: INTEGER;
{Dies sind die Variablen, mit denen der Algorithmus rechnet:
Xvar steht fr die X-Koordinate RELATIV zum Kreismittelpunkt,
Yvar steht dementsprechend fr die Y-Koordinate RELATIV zum
Kreismittelpunkt.
Korr ist die zentrale Variable der Berechnung, sie sorgt dafr,
daá es wirklich ein Kreis wird. Experimente mit dieser
Variablen zeigen dies sehr deutlich [Probiert's mal aus].}
BEGIN
Korr:= 3 - (2 * Radius);
Xvar:= 0;
Yvar:= Radius;
{Dies ist die grundlegende Initialisierung der drei Variablen.
Gut zu erkennen: Xvar und Yvar werden so initialisiert, daá sie
den Punkt bei 270ø auf dem Kreis ergeben [also ganz unten].
Die Festlegung von Korr ist nicht ganz verst„ndlich, ist aber
im Vergleich zu sp„ter noch harmlos.}
FOR Xvar:= 0 TO Yvar - (ROUND(Radius / 3.4)) DO
{Hier wird nun die Schleife, mit der der Achtelkreisbogen be-
rechnet wird, initialisiert. Interessant ist dabei die Abbruch-
bedingung dieser Schleife [Round steht nur da, weil die
Schleife Integerwerte braucht]. Hierzu eine Zeichnung:
|<Radius>|
| |
0-----ø--.--------x Der Ausschnitt mit Kommas ist der Teil,
| \ ø . der berechnet wird [von 1 nach 2].
| \ ø . Wegen der 'schr„gen' Achse braucht man
| 2 nur bis Punkt 2 zu berechnen. Die X-Ko-
1,,, ' \ ordinate dieses Punktes betr„gt von 0
| \ aus gesehen aber nur ca. der Radius ge-
teilt durch 10/3 [ist ein Erfahrungs-
wert]. Da aber die Schleife die X-Koordinate Relativ zu 0 an-
gibt, darf diese nicht bis zum Radius laufen, sondern nur bis zu
einer Stelle, der als gepunktete Linie eingezeichnet ist.
[Interessant: L„át man Xvar bis Radius laufen, zeichnet der Al-
gorithmus diagonale Tangenten an den Kreis.] Klar? Wenn nicht:
1. šberlegen,
2. Experimentieren.}
BEGIN {Es geht los}
PUTPIXEL(X_koord + Xvar, Y_koord + Yvar, Color);
PUTPIXEL(X_koord + Xvar, Y_koord - Yvar, Color);
PUTPIXEL(X_koord - Xvar, Y_koord + Yvar, Color);
PUTPIXEL(X_koord - Xvar, Y_koord - Yvar, Color);
PUTPIXEL(X_koord + Yvar, Y_koord + Xvar, Color);
PUTPIXEL(X_koord + Yvar, Y_koord - Xvar, Color);
PUTPIXEL(X_koord - Yvar, Y_koord + Xvar, Color);
PUTPIXEL(X_koord - Yvar, Y_koord - Xvar, Color);
{Dies ist jetzt Anschauung pur. Am besten noch einmal die
1. Zeichnung anschauen. Dies sind die 8 Pixel, die hier gesetzt
werden. Die Werte bleiben gleich, nur die Vorzeichen „ndern
sich: Das ist die Ausnutzung der Symmetrie.}
IF Korr < 0 THEN Korr:= Korr + (4 * Xvar) + 6
ELSE
BEGIN
Korr:= Korr + 4 * (Xvar - Yvar) + 10;
Yvar:= Yvar - 1;
END;
END;
{Dies war der Hammer schlechthin.
Wer diese Zuweisungen versteht, hat einiges auf dem Kasten. Ich
kann dazu nur sagen, daá die Zahlenwerte 6 im THEN-Teil und die
10 im ELSE-Teil nur fr eine perfekte Rundung des Kreises
sorgen. Wenn man sie - mehr oder weniger groázgig - ver„ndert,
wird der entstehende Kreis zum an vier Seiten abgeplatteten Ei,
bei groáen Werten sogar zum Quadrat. Aber dies ist ebenfalls nur
auf Experimentbasis herauszufinden. Zu den Zuweisungen selbst
ist zu sagen: der Wert von Korr entscheidet darber, ob die
Y-Koordinate relativ zum Mittelpunkt um 1 erniedrigt [also der
Bogen gezeichnet wird] oder ob die Y-Koordinate gleichbleibt
[also die 'Pixelstufe' noch etwas weiter gezeichnet wird]. Um
dies dann auch einen Kreis ergeben zu lassen, muá die Ent-
scheidungsvariable Korr ebenfalls laufend ge„ndert werden.}
END; {Ende Prozedur}
Da diese Umsetzung der, wegen den - notwendigerweise ausfhr-
lichen - Kommentaren, etwas unbersichtlichen Prozedur gibt's das
Ganzeauch im Fertigpack als Pascal-Prog, wahrscheilich unter
BRESEN.PAS im Source-Verzeichnis von Microcode zu finden.
Dabei mit eingebaut: eine DELAY-Anweisung die gut zeigt, wie der
Kreis von 8 Stellen gleichzeitig aufgebaut wird. Ohne delay ist
dies nicht mehr zu erkennen.
Ich hoffe, dieser Exkurs in die Welt der Kreise war nicht zu
kompliziert.
Mit kreisenden Gedanken verabschiedet sich
!?Xap¨
---8<-----schanap----->8----