Forum: Mikrocontroller und Digitale Elektronik Bresenham-Algorithmus - Kreisvariante


von Andreas (Gast)


Lesenswert?

Hallo,
ich beschäftige mich seit einiger Zeit damit eine CNC-Steuerung mit 
einem Mikrocontroller (Atmega 16) zu realisieren.

Ich bin auch schon soweit, dass die Geraden perfekt ausgeführt werden. 
Kreis machen allerdings noch Große Probleme:

Genauso wie ich es auch bei den Geraden gemacht habe, wollte ich bei den 
Kreisen auf den Bresenham-Algorithmus zurückgreifen, das Problem ist nur 
das der Bresenham-Algorithmus nur Achtelkreise erzeugt, welche dann 
gespiegelt werden, so das z.B. auf einem Bildschirm ein Vollkreis 
entsteht. Soweit ist das ja auch alles wunderbar, nur muss ich ja bei 
einer Fräsmaschine alle Schritte nacheinander ausführen, und von der 
Reihenfolge her in eine Richtung, d.h. ich muss den Algorithmus so 
umändern, das er mir auch das zweite Achtel in der gleichen Richtung wie 
das erste erzeugen kann.

Nur ist das leichter gesagt als getan, da ich die Herleitung des 
Algorithmus (welcher auf Wickipedia beschrieben ist 
http://de.wikipedia.org/wiki/Bresenham-Algorithmus#Kreisvariante_des_Algorithmus) 
nicht so ganz verstehe. Das der dort beschrieben Algorithmus in 
„Pseudo-Basic“ funktioniert, weis ich, da vom Prinzip her der gleiche 
Algorithmus in meinem Controller auch schon Achtelkreise erzeugt. Warum 
er funktioniert weiß ich allerdings nicht :).
Ich bin mir auch nicht so ganz sicher ob man den Algorithmus überhaupt 
so einfach "umdrehen" kann.

Eine Lösung des Problems währe allerdings die Koordinaten eines Kreises, 
wie bei einem Bildschirm zu spiegeln, diese dann ab zu speichern und in 
richtiger Reihenfolge anzufahren, dabei benötigt man allerdings einen 
relativ großen Speicher (bei großen Kreisen), der mir wohl nicht so 
einfach zu Verfügung steht. Daher finde ich diese Lösung sehr unschön.

Also, ich hoffe sehr das sich schon Leute, die hier auch vorbeischauen, 
bereits mit diesem Thema beschäftigt haben und mir weiterhelfen können.

ich bin ja nicht der Erste der eine solche Steuerung programmiert, und 
andre berechnen doch ihre Kreise auch im Controller oder?

MfG
Andreas

von Jankey (Gast)


Lesenswert?

Die meisten CNC Controller sind doch eher dumme Port Expander als 
irgendwelche Intelligenten einheiten, größere Firmen ( Siemens, Isel, 
Bungard, die komplexen Bosch Steuerungen Rechnen die Kreise am PC aus, 
schicken sie in ein RAM, was dann vom uC Abgearbeitet wird, für soviel 
Intelligenz brauchst du was größeres als den Atmega16., im Prinzip 
bräuchstest du ein sehr Grosses externes Ram wenn du Vorberechnung & 
Ausführung in der Selben einheit durchziehen willst ...

von Karl H. (kbuchegg)


Lesenswert?

Sowas würde ich entweder mit Fixpoint Arithmetik oder
gleich mit Floating Point machen.

Der grosse Vorteil vom Bresenham ist ja nicht, dass
er besonders genau oder einfach wäre, sondern dass
er sauschnell ist. Das allerdings ist bei einer
CNC Steuerung wieder von untergeordneter Bedeutung.
Dein Mega16 kann mit Sicherheit schneller rechnen
als das Werkzeug verfahren kann.

von Jorge (Gast)


Lesenswert?

Das "Bresenham Verfahren" lenkt dich vom eigentlichen Problem ab.

Stell dir vor du müsstest Multiplikation oder Division nur auf Addition 
und Subtraktion mit Ganzzahlen zurückführen.

Du kannst mit Fliesskommazahlen versuchen einen Kreis zu zeichnen. Das 
Ergebnis wird schlecht sein, weil du auf dem Bildschirm nur Pixel hast.

Für dein praktisches Problem mit dem Schrittmotor sind allerdings 
Fliesskommazahlen besser. Eventuell kannst du die Genauigkeit erhöhen 
wenn du einen Jitter zur Überwindung der Haftreibung mit einbaust. Ich 
habe das zuerst bei HP-Plottern beobachtet...

von Andreas (Gast)


Lesenswert?

So, jetzt sind schon bald 2 Monate vergangen, seit dem ich meine Frage 
gestellt habe. Erstmal danke für die Antworten, allerdings ist nicht 
wirklich etwas Brauchbares dabei gewesen.

Das tolle ist jedoch ich habe es schon seit einiger zeit selbst auf die 
Reihe bekommen. Und zwar mit Hilfe dieses Links: 
http://algorithm.name/rasteralgorithmus_6.html . Hier wird der Bresenham 
so toll beschreiben, dass er sofort nachvollziehbar ist! Das tolle ist, 
das ich hier ohne Probleme, mehr als ein Achtel berechnen kann und so 
nicht wie vermutet einen riesigen Ram benötige!

Und das Professionelle Steuerungen das auf diese Weise lösen glaube ich 
nicht, also ich würde mir so ein teil nicht zulegen...

>“für soviel Intelligenz brauchst du was größeres als den Atmega16“

Also das ist ja nun wirklich nicht war, die Kreisinterpolation geht 
wunderbar, nebenher wird noch ein Zwischenspeicher (teil vom internen 
sram) beschrieben und es werden permanent die aktuellen Absolutwerte an 
den PC für die Anzeige übergeben.

Und zu Karl heinz Buchegger:
Das der Bresenham nicht genau währe, das verstehe ich gar nicht nicht, 
wenn ich den so berechne, das eine Einheit ein schritt bei den Motoren 
beträgt, habe ich den genausten Kreis der möglich ist! Und einfach ist 
er und zwar super einfach! Und zur Geschwindigkeit: Darauf kommt es 
absolut an, wenn ich hier mit Winkelfunktionen usw. anfange, würde der 
Mic da nie mehr hinterher kommen! Jedenfalls bei hohen Vorschüben!

Ach ja was Jorge da oben geschrieben hat ist mir ja ein komplettes 
Rätsel:
wenn ich mit Ganzzahlen arbeite, und eine Einheit ein Schritt groß ist 
kann ich wie gesagt die Genauigkeit nicht noch weiter erhöhen!

Und was war da wohl mit einem Jitter gemeint??? - Was ist das 
überhaupt???

Grüße
Andreas

von Karl H. (kbuchegg)


Lesenswert?

Eine Zwischenfrage:
Kannst du mit dem Kreisbresenham auch einen Bogen machen,
der bei 23.5° beginnt und bei 108.7° endet?

Solche Dinge werden in der CNC Programmierung wesentlich
häufiger vorkommen als reine Kreise.

> Darauf kommt es absolut an, wenn ich hier mit Winkelfunktionen
> usw. anfange, würde der Mic da nie mehr hinterher kommen!

Auch mit einem Mega16 kannst du ein paar Tausend Kreispunkte
in der Sekunde berechnen. Ich denke nicht, dass man im CNC
derartig schnelle Koordinatengenerierung braucht (kann mich aber
irren).

Viel wichtiger ist aber, dass der Kreisbresenham für Kreisbögen
und Ellipsen (Ellipsenbögen) nur bedingt tauglich ist.

Ein anderes Problem ist, dass du mit dem Bresenham die
Vorschubgeschwindigkeit entlang des Umfangs nur schlecht
kontrollieren kannst.

von Currywurst (Gast)


Lesenswert?

Heh.
Die CNC Technik ist schon einige Jahrzehnte alt. Von eine Mega16 konnten 
die damals nur träumen und es funktionierte doch. Die erste echte CNC 
hatte wahrscheinlich eine CPU aus diskreten Transistoren und 
magnetischen Ringkernspeichern. Ein Schrittmotorplotter hab ich schon 
vor 10 Jahren in QBasic angesteuert. Ich sehe auch nicht wo da 
Fliesskomma-Arithmetik oder mehr als ein einfaches MCU notwendig sind.

Wo es hart wird ist Anwendungen mit echten Servos mit 
Raumzeigermodulation und 5D-Bahnberechnung mit echten Bezierkurven.Aber 
das macht keiner mit seiner Eigenbau CNC.

von Pieter (Gast)


Lesenswert?

moin moin,

letzteres ist das geringste Problem. Es wird zwische der Berechnung und 
der Geschwindigkeit getrennt. Bei mir wird die vorgegebene Strecke 
interruptgesteuert gefahren. Die Geschwindigkeit ist dabei durch die 
Zeitkonstante des Timers realisiert. Im Vordergrund kann das Programm 
den nächsten Punkt berechnen unbd wartet eventuell auf das Ende des 
verfahren.
Dann wird dieser Weg gestartet. Grade, Kreis und Tasche sind so machbar.
Bei Gleitkommazahlen bin ich beim grübeln, wie die Rasterung laufen 
soll.

Mit Gruß
Pieter

von Hagen R. (hagen)


Lesenswert?

Die Rasterung bei Fließkommaberechnungen arbeitet genauso wie der 
Bresham Algorithmus. Im Grunde berechnet man immer die sich ergebenden 
Fehler/Abweichungen vom Idealkurs und korregiert dies im nächsten 
Schritt. Rasterung hast du nämlich immer, systembedingt. Dein Ansatz ist 
schon richtig.

Gruß Hagen

von Hagen R. (hagen)


Lesenswert?

>Viel wichtiger ist aber, dass der Kreisbresenham für Kreisbögen
>und Ellipsen (Ellipsenbögen) nur bedingt tauglich ist.

Halte ich für eine zu absolutistische Aussage. Selbst wenn man mit 
Fließkomma arbeitet so berechnet man den exakten Startpunkt eines 
Segmentes auf die möglichen Pixelkoordinaten bezogen (also auf die 
Auflösing der Schrittmototen und Mechanik). Danach wird man einen 
iterativen FLießkommaalgorithums benutzen der wiederum in Schritten 
arbeitet. Also aktuelle Koordinaten + aktuelle Fehlabweichung vom 
idealen Kurs ergibt nächste Koordinate. Also im Grunde die gleiche 
Philosophie die hinter Bresham steckt. Das ist nämlich eine Methode die 
zwei Informationen liefert, 1.) welche Koodinate muß angefahren werden 
und 2.) wie groß wird der Systembedingte Fehler/Abweichung dieser 
Koordinate.

Gruß Hagen

von Wolfram (Gast)


Lesenswert?

Warum zeichnest du deinen Kreis/Elipse/Kurvenbogen nicht mit Geraden?

Ja, ich weiß das erste woran man denkt ist ein Kreis der aussieht wie 
ein Achteck...
Tatsache ist aber folgendes:
Du weißt welchen Durchmesser dein Kreis besitzt und welche Abweichung 
von der Kreisform du maximal tolerierst. Selbst ein Achteck würde ab 
einem gewissen Minimaldurchmesser des Kreises nicht mehr auffallen (und 
liegt dann auch unter deinen Minimaltoleranzen). Wenn der 
Kreisdurchmesser größer wird, müssen mehr Geraden benutzt werden, so daß 
ein 16/32/.. Eck entstehen würde. Also je größer der Radius wird, um so 
mehr Punkte brauchst du zwischen denen du Geraden aufspannst. Diese 
Geraden werden der jetzigen Motorsteuerung übergeben(die hast du ja 
schon). Die Berechnungen für die einzelnen (Zwischen)Punkte schafft auch 
ein ATMEGA spielend. Das klappt auch mit anderen Formen. Niemand hindert 
dich daran auch Bezierkurven analog in Geraden zu zerlegen. Der 
Rechenaufwand bleibt ebenfalls im Rahmen, da nur eine begrenzte Anzahl 
von Punkten auf der Kurve berechnet werden muß. Dies kann auch iterativ 
erfolgen, so daß die Kurve auch von Punkt zu Punkt berechnet wird.


von Hagen R. (hagen)


Lesenswert?

Die minimalste Länge einer solchen Geraden ist die mechanische Auflösung 
der Schrittmotoren. Damit stimmt diese minimale Länge der Gerade exakt 
überein mit der von Hause aus vorgegebenen Schrittweite eines Bresham 
Algorithmus. Und in fakt ist der Bresham für Kreise nichts anderes als 
das Zeichnen von Geraden, entweder 1 Pixel waagerecht oder 1 Pixel 
(Schritt) senkrecht. Würde man diese Schrittweite größer machen und 
diese Koordinaten mit einem Bresham für Linien verbinden dann kommst du 
auf deinen Vorschlag, eben nur andersrum ;)

Gruß Hagen

von Andreas (Gast)


Lesenswert?

1. Ein Hinweis: mir kommt es so vor als wenn einige Leute die hier rein 
schreiben, den bisherigen Verlauf der Diskussion nicht mitverfolgt haben 
und ohne zu lesen einfach auf meine ursprüngliche Frage antworten!

Wie gesagt der Kreis funktioniert, und Grundlegendes ist soweit auch 
geklärt (siehe oben)!
Danke an  Hagen Re, der das unnötige Gerede auf den Punkt bringt!

Wobei ich natürlich trotzdem toll finde wie hier alle mitdenken, also 
nicht falsch verstehen...

>Kannst du mit dem Kreisbresenham auch einen Bogen machen,
>der bei 23.5° beginnt und bei 108.7° endet?

logisch, ich lass mir die punkte im PC vorrechnen, übergebe den 
Anfangspunkt (ist Endpunkt des letzten Weges) und übergebe den Endpunkt! 
- Ich kann an jeder Stelle in den Bresenham einspringen, da ich immer 
errechnen kann welcher punkt nun am nächsten an der Idealkurve liegt! 
Und am ende bin ich einfach dann, wenn die "schnellere" Achse ihren 
Endpunkt erreicht hat (und die Vorzeichen beider Achsen stimmen)!


>Ein anderes Problem ist, dass du mit dem Bresenham die
>Vorschubgeschwindigkeit entlang des Umfangs nur schlecht
>kontrollieren kannst.

Mir fällt auf, dass habe ich noch gar nicht eingebaut, war mit anderen 
Problemen beschäftigt und habe das somit verdrängt. Aber als Problehm 
sehe ich das nicht, da ich doch einfach immer nur dann wenn sowohl in x 
als auch in y ein Schritt ausgeführt den Vorschub entsprechen verringern 
muss (bzw. den Timer anders vorlade). Und wenn mich nicht alles täuscht 
einfach um F/Wurzel(2).

Grüße Andreas

von Hagen R. (hagen)


Lesenswert?

Suche mal hier in der DP nach meiner GLCD (fürs Nokia oder S65 Display 
in Lib Ordner). Da drinnen ist ein Ellipsen-Bresham. Mit dem zeichne ich 
Kreise, Ellipsen und abgerundete Rechtecke. Allerdings keine Segmente, 
Kreisbögen etc. ;) da mein Code diese Figuren auch ausfüllen können muß 
(ohne extra SRAM).

Gruß Hagen
1
void glcdSetPixel4(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdColor_t color) {
2
3
    glcdSetPixel(x1, y1, color);
4
    glcdSetPixel(x2, y1, color);
5
    glcdSetPixel(x1, y2, color);
6
    glcdSetPixel(x2, y2, color);
7
}
8
9
void glcdLine2(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdColor_t color) {
10
11
    glcdFillRect(x1, y1, x2, y1, color);
12
    glcdFillRect(x1, y2, x2, y2, color);
13
}
14
15
void glcdRoundRect(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdCoord_t a, glcdCoord_t b, glcdColor_t fgcolor, glcdColor_t bkcolor) {
16
17
    if (x1 > x2) glcdSwapCoord(x1, x2);
18
    if (y1 > y2) glcdSwapCoord(y1, y2);
19
    glcdCoord_t t;
20
    t = x2 - x1;
21
    t >>= 1;
22
    if (a > t) a = t;
23
    t = y2 - y1;
24
    t >>= 1;
25
    if (b > t) b = t;
26
    x1 += a;
27
    x2 -= a;
28
    if (fgcolor != NONE) glcdLine2(x1, y1, x2, y2, fgcolor);
29
    uint16_t as = a * a, bs = b * b;
30
    int32_t dx = 0, dy = as, ee = bs;
31
    dy *= b;
32
    ee += as / 4;
33
    ee -= dy;
34
    dy += dy;
35
    while (dx < dy) {
36
      if (fgcolor != NONE) glcdSetPixel4(x1, y1, x2, y2, fgcolor);
37
      x1--;
38
      x2++;
39
      if (ee >= 0) {
40
        y1++;
41
        y2--;
42
        dy -= as;
43
        dy -= as;
44
        ee -= dy;
45
        if (bkcolor != NONE) glcdLine2(x1, y1, x2, y2, bkcolor);
46
      }
47
      dx += bs;
48
      dx += bs;
49
      ee += bs;
50
      ee += dx;
51
  }
52
  int32_t tt = as;
53
    tt -= bs;
54
  tt *= 3;
55
  tt >>= 1;
56
  tt -= dx;
57
  tt -= dy;
58
  tt >>= 1;
59
    ee += tt;
60
    while (y1 <= y2) {
61
      if (bkcolor != NONE) glcdLine2(x1, y1, x2, y2, bkcolor);
62
      if (fgcolor != NONE) glcdSetPixel4(x1, y1, x2, y2, fgcolor);
63
      y1++;
64
      y2--;
65
      if (ee < 0) {
66
        x1--;
67
        x2++;
68
        a++;
69
        dx += bs;
70
        dx += bs;
71
        ee += dx;
72
      }
73
      dy -= as;
74
      dy -= as;
75
      ee += as;
76
      ee -= dy;
77
    }
78
}
79
80
void glcdEllipse(glcdCoord_t x1, glcdCoord_t y1, glcdCoord_t x2, glcdCoord_t y2, glcdColor_t fgcolor, glcdColor_t bkcolor) {
81
82
    if (x1 > x2) glcdSwapCoord(x1, x2);
83
    if (y1 > y2) glcdSwapCoord(y1, y2);
84
    glcdRoundRect(x1, y1, x2, y2, (x2 - x1) / 2, (y2 - y1) / 2, fgcolor, bkcolor);
85
}
86
87
void glcdCircle(glcdCoord_t x, glcdCoord_t y, glcdCoord_t r, glcdColor_t fgcolor, glcdColor_t bkcolor) {
88
89
    glcdRoundRect(x - r, y - r, x + r, y + r, r, r, fgcolor, bkcolor);
90
}

von Tishima (Gast)


Lesenswert?

Hallo!

Ich spiel auch grade mit Hernn Bresenham und da les ich grade das ein 
per Bresenham erzeugter Kreis:

"Die Anzahl der erzeugten Punkte des Bresenham-Algorithmus für den 
vollen Kreis beträgt  4  * sqr(2) *  r Punkte. Verglichen mit dem 
Kreisumfang von  2  pi r liegt dieser Wert um 10% zu tief."

Das waere fuer eine CNC Anwendung nicht tauglich, oder ?

Kann einer diese Aussage bestätigen, oder ist das nonsens.

mfg,
Bjoern

von Tishima (Gast)


Lesenswert?

@Hagen

>Und in fakt ist der Bresham für Kreise nichts anderes als
>das Zeichnen von Geraden, entweder 1 Pixel waagerecht oder 1 Pixel
>(Schritt) senkrecht.

Kleiner Einspruch, eine CNC Maschine kann sich in 8 Richtungen bewegen.
Die X und Y Achse kann auch gleichzeitig gefahren werden.

mfg,
Bjoern

von Hagen R. (hagen)


Lesenswert?

Jaaa ;) Der Bresham kann auch beide Bewegungen berechnenen, man bewegt 
sich also nicht erst 1 Schritt X und 0 Schritt Y und danach 0 Schritt X 
und 1 Schritt Y sondern sofort 1 Schritt X und 1 Schrit Y. Das ist doch 
nur eine Frage der Berechnung, das Prinzip bleibt gleich. Auch der 
betragsmäßige Abstand einer solchen "Geraden" beträgt immer noch 1 
Schritt, bezogen auf die Auflösung des Systemes.

Anders ausgerückt: Kümmelspalter ;)

Gruß Hagen

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.