Suche Algorhitmus für Kreisbogen.....

Moin!
Ich überarbeite grad meine Fräsensteuerung (jetzt mit Beschleuniguns- und Bremsrampen und variabler Geschwindigkeit), nun würde ich gern meinem Atmel auch beibringen, wie man Kreisbögen fräst, aber ich krieg es nicht hin.
Bei Google habe ich folgendes gefunden :
http://www.mikrocontroller.net/topic/42447
aber erstens raff ich es irgendwie nicht, und zweitens habe ich das ganze mal spaßeshalber nach C# portiert (geht fast per copy and paste :-) ), aber da kriege ich irgendwie nur einen Viertelkreis hin.....
Kann mir da jemand helfen???

MfG
Volker

Hallo Volker,

Zitat:

---

Zitat von vklaffehn

... Atmel ... beibringen, wie man Kreisbögen fräst ... aber da kriege ich irgendwie nur einen Viertelkreis hin ...

---

Der Kreis ist, mathematisch gesehen, eine dämliche Figur. Strenggenommen ist er nämlich nicht sooo einfach als Funktion darstellbar: in karthesischen Koordinaten gibt es ja für einen x-Wert zwei mögliche y-Werte. Diese Doppeldeutigkeit ist bei Funktionen nicht erlaubt. Daher trickst man gelegentlich und phantasiert sich eine abschnittweise definierte Funktion zurecht: den Viertel- oder Halbkreis (...siehste!). In sehr ähnlichen Fällen von Mehrdeutigkeit hatte ich mich schon mit recht gutem Erfolg durch eine Parameterisierung der Funktion aus der Patsche gerettet - das ist aber dann schon ein recht eigenes Thema.

Es gibt ja reichlich viel Möglichkeiten einen Kreis formelmäßig darzustellen. Eine übliche Art erinnert an den alten Pythagoras:

x2 + y2 = r2 und daraus die für positive y-Werte darstellbare Funktion:

y = wurzel(r2-x2)

Natürlich ist das für Deine Arbeit kein brauchbarer Zusammenhang. Ich habe leider vom Programmieren für CNCMaschinen keine Ahnung, aber ich kann mir vorstellen, dass die Lösung für einen Kreis aus drei Punkten (auf seinem Umfang) recht praktisch wäre: Anfangspunkt, Endpunkt und ein Punkt irgendwo dazwischen. Dazu gibt es beispielsweise hier eine hübsche Darstellung.

Übrigens bin ich bei mikrocontroller.net auch über diesen Thread gestolpert (habe den aber nicht ganz durchgelesen). Dann gibts noch diese Diskussion um Kreise mit CNC-Maschinen. Diese Site bzw. den vielversprechenden Link, der ganz unten, nach längerem Scrollen erreichbar ist, habe ich nicht weiter angesehen. Diese Site gibt eine gewisse Hilfe wo´s langgeht: "...Bei der Programmierung des Kreises wird zwischen der Mittelpunkt- oder Radiusprogrammierung unterschieden..." Schließlich: kennst Du das da? (Anm.: für die sprachliche Darstellung der verlinkten Seite übernimmt der Autor dieser Zeilen keinerlei Verantwortung.)

Langer Rede kurzer Sinn: ich verstehe Dein Problem, aber ich fürchte, dass ich nicht wirklich helfen kann.

Bei der CNC will man meistens den Kreis mit annähernd konstanter Geschwindigkeit abfahren. Die logische methode wäre also nicht eine Funktion für die eine korodinate als funktion der anderen, sondern mit mit dem Winkel als parameter zu arbeiten. Dann hat man 2 Funktionen für die x und y Koordinate in abhängigkeit von Radius und Winkel.
Ganz nebenbei ist man auch das Problem mit den 2 Werten los.

Das einzige Problem was man noch hat, ist das man dazu sinus und cosinusfunktion braucht. Die sind beide relativ langsam in der Berechnung. Da die Mechanik ja oft auch nicht so schnell ist sollte es aber noch reichen. Wenns unbedingt schneller gehen muß, gibt es da noch ein Möglichkeit das über eine Drehmatrix zu realiesieren. Da hat man aber eventuell Probleme mit Rundungsfehlern und für eine wirkliche Schnelle lösung müßte man Festkommaarithmetik nutzen, was die meisten Compiler nicht so direkt unterstützen.

Moin!
@Oberallgeier:
Vielen Dank für die Mühe! Link 1 ist evtl. ein Ansatz, der mir weiterhilft, Link2 habe ich auch schon gefunden und komplett durch :-) Wie meine G-Codes aussehen, habe ich nach ein wenig Herumprobieren schon herausgefunden :

Code:

---

G00 X20 Y10
G01 Z-5
G03 X10 Y10 I-5 J0

---

fährt an Position 20,10
5 mm runter
Kreisbogen von 20,10 zu 10,10. Mittelpunkt bei 15,10

@Besserwessi:
Geschwindigkeit ist bei meiner Fräse eher zweitrangig, da sie eh im Prinzip schon zu langsam ist :-)
Ich müsste also quasi den Startwinkel und Endwinkel anhand des Mittelpunktes sowie der Endpunkte ermitteln und dann einmal abfahren.... Ich könnte ja dann zwischen den Punkten Linien fräsen, das reduziert den Rechenaufwand, und wenn die Kreise in 1/10 mm Schritten z.B. gerastert sind, wäre mir das ja egal :-)
So als Stichwort würde ich also mal nach
Umrechnen zwischen karthesischen und Polarkoordinaten
schauen?
Da werd ich jetzt noch einmal bei Licht drüber nachdenken, sobald ich die Minifernsteuerautos meiner Neffen (und meins natürlich!) etwas gepimpt habe, damit sie statt mit Batterien auch mit Akkus laufen :-)

MfG
Volker

um die kreispunkte zu erechnen hab ich bisher das hier genommen (ist aber basic)

For winkel= start winkel to endwinkel
xpunktkreis = Cos(winkel * 22 / 7 / 180) * radius + xmittelpunkt
ypunktkreis = Sin(winkel * 22 / 7 / 180) *radius+ ymittelpunkt
next winkel

Ich selbst habe ja Mal angefangen, eine CNC-Firmware für AVR zu entwickeln, die auch die Rasterungs- und Motorsteuerungsaufgaben selbst übernehmen soll.
Der Teil, der die Kreisberechnungen durchführt, ist zwar noch eine Baustelle, funktioniert aber schon relativ gut, auf einem ATMega168 mit 20Mhz kommt meine Implementierung auf ~82000 Schritte/Sekunde bei Kreisradien < 10000 Einheiten und auf ~50000 Schritte/Sekunde bei Kreisradien > 10000.
Ich habe dabei Bresenhams Algorithmus verwendet, leicht modifiziert, um Viertelkreise zu berechnen und schalte dann in jedem Quadranten immer die Richtung um.
Bei jedem Funktionsaufruf wird immer ein struct mit Richtungsdaten (-1, 0, 1) für die erste und die zweite Achse zurückgegeben.
Es sind damit also nur ebene Kreisbewegungen notwendig, mehr lässt der G-Code-Standard zu Glück nicht zu, spiralförmige Bewegungen können einfach durch überlagern mit einer linearen Bewegung auf der dritten Achse erzeugt werden.

Bei Interesse kann ich den Sourcecode mal einstellen.

mfg
Markus

PS: Einige Details zu den Tests: Die Kreisberechnungen wurden eine Sekunde lange durchgeführt und die Ergebnisse in einem FiFo gepuffert, war dieser voll, wurde er entleert. Die reine Rechenzeit für den Algorithmus dürfte vermutlich noch etwas geringer sein.
Der FiFo ist ebenfalls eine Eigenimplementierung von mir.

Moin!
@markusj: An Deinem Quellcode wäre ich SEHR interessiert :-) Ich brauch auch nur den Krei in einer Ebene.
MfG
Volker

Moin, ich arbeite im Moment auch an einer Frässteuerung für einen Atmel.
Hab dazu allerdings das ganze erstmal mit einem Java Programm "simuliert", da hab ich auch längere Zeit an dieser eigentlich doch recht simplen Kreisfunktion geschrieben. Hier mal der Quellcode, ist zwar für Java, aber der Syntax ist eigentlich wie C, könnte man also mit kleinen änderungen direkt auf den µC portieren. Ist denk ich recht leicht zu durchschauen. Zuerst werden die Winkel berechnet bei denen der Kreisbogen anfängt und wo er aufhört. Dann fährt er vom Anfangswinkel zum Endwinkel den Kreisbogen ab. Ich verwende dort ein Funktion distance() die mir die Distanz zwischen zwei punkten berechnet und die funktion MoveTo welche die Fräse (ohne interpolation) zu den angegeben Koordinaten fährt. Die Funktion getposY() bzw. getposX() liefert die Aktuelle Position des Fräsers.
Der rest erschließt sich denke ich so.
x1, y1 gibt beim Funktionsaufruf den Zielpunkt an, xmid / ymid den Mittelpunkt und d die Richtug (1 CW, -1 CCW). Der Startpunkt ergibt sich ja aus der aktuellen Position des Fräsers.

Code:

---

        void arc (int x1, int y1, int xmid, int ymid, int d) {
                  int        i;
                  int        X0 = x1,
                                        Y0 = y1,
                                        r = distance(X0, Y0, xmid, ymid);
                 
                 
                  d=-d;
                 
                  double alpha, w1, w2;
                  int dx, dy;
                 
                  //calcualtion of starting Angle w1****************************************
                  dy = getposY() - ymid;
                  dx =        getposX() - xmid;
                  if (dx == 0) {
                          if (dy >0) {
                                  w1 = 90;
                          }
                          else {
                                  w1 = 270;
                          }
                  }
                  else if (dy == 0) {
                          if (dx >0) {
                                  w1 = 0;
                          }
                          else {
                                  w1 = 180;
                          }
                  }
                  else {
                          alpha = Math.atan((double)dy / dx) * bg;

                          if ((dx >0) && (dy < 0)) {        //4. quadrant
                                  w1 = 360+alpha;
                          }
                          else        if ((dx< 0) && (dy < 0)) { //3. Quadrant
                                  w1 = 180+alpha;
                          }
                          else        if ((dx <0) && (dy > 0)) { //2. Quadrant
                                  w1 = 180+alpha;
                          }
                          else {        //1. Quadrant
                                  w1 = alpha;
                          }
                  }

                  // Calculation of end Angle w2
                  dy = y1 - ymid;
                  dx =        x1 - xmid;
                  if (dx == 0) {
                          if (dy >0) {
                                  w2 = 90;
                          }
                          else {
                                  w2 = 270;
                          }
                  }
                  else if (dy == 0) {
                          if (dx >0) {
                                  w2 = 0;
                          }
                          else {
                                  w2 = 180;
                          }
                  }
                  else {
                         
                          alpha = Math.atan((double)dy / dx) * bg;

                          if ((dx >0) && (dy < 0)) {        //4. quadrant
                                  w2 = 360+alpha;
                          }
                          else        if ((dx< 0) && (dy < 0)) { //3. Quadrant
                                  w2 = 180+alpha;
                          }
                          else        if ((dx <0) && (dy > 0)) { //2. Quadrant
                                  w2 = 180+alpha;
                          }
                          else {        //1. Quadrant
                                  w2 = alpha;
                          }
                  }

                 
                  if ((w2 < (w1)) && (d >0)) {
                          w2+=360;
                  }
                  if ((w2 > (w1)) && (d <0)) {
                          w2-=360;
                  }

                  //plot Circle
                  for (i = (int) w1 ; i != (int) w2; i+=d)
                  {
                  X0 = (int) (xmid + r * Math.cos((double)i / bg));
                           
                  Y0 = (int) (ymid + r * Math.sin((double)i / bg));

                  moveTo(X0, Y0, getposZ());


                  }
                  moveTo(x1, y1, getposZ());

        }

---

Ich wäre sehr interessiert daran wie du die Fräsgeschwindigkeit regeln willst, mir ist da noch nicht die richtige idee gekommen.
Vielleicht könnte man ja auch mal ein Gemeinschaftsprojekt zur Cnc Steuerung mit Atmel aufstellen. Ist ja irgendwie auch blöd wenn jeder alles neu erfinden muss. Oder gibts sowas schon?

Moin!
Danke, da werd ich mich mal durchwursteln :-) Die Geschwindigkeit wird bei mir nicht geregelt sondern stammt vom F-Kommando aus den GCode Dateien. Ich werte nicht präzise aus, sondern nur 'irgendwie', so dass F30 langsam ist und F300 10 mal schneller. Ist einfach über die Verzögerung zwischen den Steps der Schrittmotoren realisiert.

Ich fände es auch ganz nett, wenn man CNC Softwarelösungen mal öffentlich macht, werd ich mit meinem Programm auch machen, wenn die Z-Achse wieder richtig rum fährt :-)

MfG
Volker

Hallo,
bisher mache ich das mit der Geschwindigkeit auch nur so grob.
Das heißt für geringen Vorschub eine Größere Wartezeit zwischen den Schritten.
Problem dabei ist aber das ja je nach Fahrtrichtung mal mehr und mal weniger Schritte für die selbe Wegstrecke benötigt werden. Das müsste man dann ja irgenwie in die Berechnung der Verzögerung zwischen den Schritten mit einplanen, wenn man in jede Richtung eine konstante Geschwindigkeit haben möchte. Nur wie?!
Naja meine Maschine ist eh nicht so schnell von daher spielt das eigentlich auch erstmal keine so große Rolle, geht ja auch etwas am eigentlichen Thema vorbei.

Moin!
@Static:
Wieso brauchst Du bei gleicher Strecke unterschiedlich viele Schritte? meinst Du die Summe der X und Y Schritte? Bei mir liegt die Verzögerung direkt im Linienalgorithmus, der macht also entweder auf einer oder auf beiden Achsen einen Schritt und verzögert dann.

Hier mal mein Linienkrams, vielleicht nützt das ja schonmal wem.
Der Bresenham ist übrigens ziemlich direkt einfach qaus Wikipedia kopiert :-)

RAMP ist die Anzahl Schritte für die Beschleunigungs und Bremsrampe, bei mir 24
rampfactor ist ein Faktor, um die Beschleunigungskurve zu verbiegen, bei mir 16
gb_steps ist die Anzahl Schritte pro 1/10 mm, bei mir 96

Der Krams mit dem last_ix und so ist zum Ausgleich des Umkehrspiels.
movex(steps,dir,speed) und movey(...) bewegen jeweils den Motor um 'steps' Schritte in Richtung 'dir' (incx bzw. incy sind entweder -1,0 oder 1, werden vom Bresenham genutzt) mit Geschwindigkeit 'speed'
sx(dir);sy(...) machen jeweils einen Schritt in Richtung 'dir'

Code:

---

void gbham(int32_t xstart,int32_t ystart,int32_t xend,int32_t yend, uint16_t speed)
/*--------------------------------------------------------------
 * 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)
 *---------------------------------------------------------------
 */
{
        int32_t x, y, t, dx, dy, es, el, err;
        int incx,incy, pdx, pdy, ddx, ddy;
        int rampdelay = RAMP;

       
        xstart *= gb_steps;
        ystart *= gb_steps;
        xend *= gb_steps;
        yend *= gb_steps;
        //speed=speed-M_MINIMUM;


/* 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;
               
        if ((incx != last_ix)&(incx != 0))
                {
                        movex(XCORR,incx,speed);
                        last_ix = incx;                       
                }
               
        if ((incy != last_iy)&(incy != 0))
                {
                        movey(YCORR,incy,speed);
                        last_iy = incy;
                }       


/* 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 */
              es =dy;  el =dx;  /* Fehlerschritte schnell, langsam */
          } else
          {
              /* y ist schnelle Richtung */
              pdx=0;    pdy=incy; /* pd. ist Parallelschritt */
              ddx=incx; ddy=incy; /* dd. ist Diagonalschritt */
              es =dx;  el =dy;  /* Fehlerschritte schnell, langsam */
          }
 
        /* Initialisierungen vor Schleifenbeginn */
          x = xstart;
          y = ystart;
          err = el/2;
          SetPixel(x,y);

        if (el < rampdelay)
                rampdelay = el / 2;
 
        /* Pixel berechnen */
        XYON;
          for(t=0; t<el; ++t) /* t zaehlt die Pixel, el ist auch Anzahl */
        {
               
            /* Aktualisierung Fehlerterm */
              err -= es;
              if(err<0)
              {
                  /* Fehlerterm wieder positiv (>=0) machen */
                  err += el;
                  /* Schritt in langsame Richtung, Diagonalschritt */
         
                          //x += ddx;
                  sx(ddx);
                          //y += ddy;
                          sy(ddy);
                       
              } else
              {
                  /* Schritt in schnelle Richtung, Parallelschritt */
         
                        //x += pdx;
                          sx(pdx);       
                  //y += pdy;
                          sy(pdy);
                }
                //ramp delay
                //XYOFF;
                mydelay(speed);
               
                if (t < RAMP)
                {
                        mydelay(rampdelay*rampfactor);
                        rampdelay--;
                }
                else if ((el-t)<RAMP)
                {
                        mydelay(rampdelay*rampfactor);
                        rampdelay++;
                }
                //XYON;
               
              //SetPixel(x,y);
        }
        XYOFF;
} /* gbham() */

---

MfG
Volker

Ok, ich poste jetzt einfach Mal den Source des Bresenham-Moduls hier rein.
Einige Anmerkungen vorweg:
1. Meine Firmware ist noch nicht mal ansatzweise fertig, daher kann es sein, dass die Schnittstelle des Bresenham-Moduls noch optimiert werden kann/muss
2. Diese Implementierung ist auf Geschwindigkeit getrimmt - daher wird die Berechnung zweigeteilt in int16 und int32 Werte (daher auch die unterschiedlichen Geschwindigkeiten).
3. Teilweise können die Kommentare falsch oder irreführend sein. Aufgrund meines Studiums ruht das Projekt leider momentan.
4. Meine Berechnung des Fehlerwertes ist stark vereinfacht - nämlich eine Initialisierung auf Null.
Die Begründung: Alle Werte sind bereits in Rastereinheiten (der ganze Algo arbeitet mit Rastereinheiten) angegeben, daher ist beim Start hoffentlich kein Fehler vorhanden (außer jemand hat den Kreis falsch initialisiert - selbst schuld)
5. Rückgabewerte: Ein einzelner Berechnungsschritt gibt einfach nur -1, 0 oder 1 für jede der beiden angesteuerten Achsen aus - diese Werte geben die Richtung an, und ob die jeweilige Achse angesteuert werden soll - evtl. wird dieses Interface später noch überarbeitet, das hängt davon ab, wie gut der Durchsatz ist.
6. In meiner Firmware werden alle Berechnungsergebnisse in einem Fifo zwischengepuffert (werden). So kann die Berechnung der Schritte asynchron in der Main-Routine erfolgen, die Ansteuerung der Schrittmotoren erfolgt in einer Interruptroutine.
Diese kümmert sich auch um Beschleunigungs- und Bremsvorgänge sowie um die Geschwindigkeitsregelung (durch Taktstreckung).
7. Der Code ist ausgelegt für den C-Standard GNU99 und avr-gcc.
8. Der Code selbst und die Kommentare sind im Hinblick auf eine später möglicherweise vollständig erfolgende Veröffentlichung des Sourcecodes in Englisch gehalten (mehr schlecht als recht).

Vor der Verwendung muss der Algorithmus initialisiert werden, die Parameter sind eigentlich selbsterklärend.
"quadrant" gibt den Viertekreis an, gezählt ab 1, im Uhrzeigersinn beginnend im rechen, oberen Viertel.

Ich stelle den Source unter keine explizite Lizenz, stelle aber folgende Forderungen auf:
1. Ohne meine Einwilligung darf der Sourcecode weder in Teilen noch als Ganzes kommerziell verwendet werden.
2. Wer (relevante) Änderungen am Sourcecode vornimmt, muss die Änderungen hier veröffentlichen oder mir zusenden, vielleicht ist ja auch etwas dabei wovon wir/ich profitieren und lernen können - unter relevant verstehe ich Optimierungen, Funktionserweiterungen und -verbesserungen sowie alle größeren Änderungen am Sourcecode
3. Für den veränderten Sourecode müssen bei der Veröffentlichung/Weitergabe (nach Punkt 2) die genannten Forderungen (1 bis 4) übernommen werden.
4. Ich würde mich natürlich darüber freuen, wenn ich Projekte, die meinen Source verwenden als ganzes einsehen könnte (oder zumindest das fertige Ergebnis betrachten) - auch hier ist die Hauptmotivation natürlich Neugierde.

So genug geredet, vermutlich wird der Source sowieso keinen kümmern ;)

bresenham.h

Code:

---

#ifndef BRESENHAM_H_INCLUDED
#define BRESENHAM_H_INCLUDED

/*

Plotting-functions using the Bresenham-algorithm: Header file

Moves a (fictional) cursor step by step clockwise on a circle using a Bresenham like algorithm.
It implements not exactly the bresenham algorithm because it wasn't possible to expand it to a quarter circle.

The algorithm has to be initialized first, otherwise it will create very random results.

Version 1.2.3
Last modified: 10.05.2009

by Markus Jung

*/

#include <stdint.h>

#define BRESENHAM_CCW -1
#define BRESENHAM_CW 1

typedef struct {
    int8_t  first_axis,
            second_axis;
} circle_movement_t;

/*
Sets the status of the bresenham-algorithm to the given parameters.
If direction is BRESENHAM_CCW (-1), the movement is counter-clockwise, if BRESENHAM_CW (1),
circle_step will step clockwise trougth the circle.
OTHER VALUES ARE NOT PERMITTED AND WILL CAUSE CRAZY RESULTS!
*/
extern void circle_init(uint32_t radius, uint32_t first_axis, uint32_t second_axis, uint8_t quadrant, int8_t direction);

/*
Calculates one single movement of the cursor. The current position of the algorithm can be read from the circle_config variable,
the neccessary transformation of the signs can be done using transform positions with the values (1,1).
The first and second axis values have to been multiplied with the transformation_result
*/
extern circle_movement_t circle_step(void);

#endif // BRESENHAM_H_INCLUDED

---

bresenham_private.h

Code:

---

#ifndef BRESENHAM_PRIVATE_H_INCLUDED
#define BRESENHAM_PRIVATE_H_INCLUDED

#include <stdint.h>
#include <stdlib.h>
#include "bresenham.h"

typedef struct {
    uint16_t    radius,
                first_axis,
                second_axis;
    int16_t    F;      //current position failure 16 bit calculation
} circle_calculations_16_t;

typedef struct {
    uint32_t    radius,
                first_axis,
                second_axis;
    int32_t    F;      //current position failure 32 bit calculation
} circle_calculations_32_t;

typedef union {
    circle_calculations_16_t    i16;
    circle_calculations_32_t    i32;
} circle_calculations_t;

typedef struct {
    circle_calculations_t  calc;
    circle_movement_t (*step_func)(void);
    uint8_t quadrant,  //current quadrant (clockwise, 1-4)
            disable_first_movement, //optimization: disables the calculation and comparation for the case that the first axis must not be moved any more
            axis_difference;    //used to reduce the check-frequency for first_axis-second_axis <=1
    int8_t  first_direction,    // -1 or 1
            second_direction,  //used to change movement-direction of the first and the second axis depending from quadrant
            rotation_direction; // 1 == clockwise, -1 == counterclockwise, everything else == strange behaviour
} circle_config_t;


#ifdef BRESENHAM_TESTCASE
extern circle_config_t circle_config;
#endif
#ifndef BRESENHAM_TESTCASE
static circle_config_t circle_config;

/*
Internally, the algorithm calculates only the first quadrant all the time.
To transform the movement into a circle, the function transform_positions changes the given value (!ALWAYS 0 OR 1!)
into -1, 0, or 1, depending from the current quadrant
*/
static inline circle_movement_t circle_transform_positions(uint8_t movefirst, uint8_t movesecond);

/*
Updates the direction factors depending from the current quadrant
*/
static inline void update_direction_factors(void);

/*
Calculates the movement in case that the radius is smaller than (2^15-1)/3
*/
static circle_movement_t circle_step_16(void);

/*
Calculates the movment for big circles
*/
static circle_movement_t circle_step_32(void);

#endif

#endif // BRESENHAM_PRIVATE_H_INCLUDED

---

bresenham.c

Code:

---

/*

Plotting-functions using the bresenham-algorithm: Source

*/

#include "bresenham_private.h"

#ifdef BRESENHAM_TESTCASE
circle_config_t circle_config;

static inline void update_direction_factors(void);
static circle_movement_t circle_step_16(void);
static circle_movement_t circle_step_32(void);
#endif

void circle_init(uint32_t radius, uint32_t first_axis, uint32_t second_axis, uint8_t quadrant, int8_t direction)
{
    if (radius > 10000)
    {  //32 bit
        circle_config.calc.i32.radius = radius;
        circle_config.calc.i32.first_axis = first_axis;
        circle_config.calc.i32.second_axis = second_axis;
        circle_config.calc.i32.F = 0;    //the _F_ailure at the beginning is ZERO, the original calculations are a little bit strange^^
        circle_config.step_func = circle_step_32;
    }
    else
    {  //16 bit
        circle_config.calc.i16.radius = radius;
        circle_config.calc.i16.first_axis = first_axis;
        circle_config.calc.i16.second_axis = second_axis;
        circle_config.calc.i16.F = 0;    //the _F_ailure at the beginning is ZERO, the original calculations are a little bit strange^^
        circle_config.step_func = circle_step_16;
    }

    circle_config.quadrant = quadrant;
    circle_config.rotation_direction = direction;
    circle_config.disable_first_movement = (first_axis >= second_axis+1);  //both off

    if (!circle_config.disable_first_movement)
        circle_config.axis_difference = second_axis-first_axis+1; //may be optimized, perhaps a subtraction of the lsb is enougth

    update_direction_factors();
}

static inline circle_movement_t circle_transform_positions(uint8_t movefirst, uint8_t movesecond)
{
    circle_movement_t result;

    if (circle_config.quadrant & 0x01)
    {
        result.first_axis = circle_config.first_direction*(int8_t)movefirst;
        result.second_axis = circle_config.second_direction*(int8_t)movesecond;
    }
    else
    {
        result.first_axis = circle_config.first_direction*(int8_t)movesecond;
        result.second_axis = circle_config.second_direction*(int8_t)movefirst;
    }

    return result;
}

circle_movement_t circle_step(void)
{
    return circle_config.step_func();
}

static inline void update_direction_factors(void)
{
    if ( (circle_config.quadrant == 2) || (circle_config.quadrant == 3) )
        circle_config.first_direction = -1*circle_config.rotation_direction;
    else
        circle_config.first_direction = 1*circle_config.rotation_direction;

    if ( (circle_config.quadrant == 1) || (circle_config.quadrant == 2) )
        circle_config.second_direction = -1*circle_config.rotation_direction;
    else
        circle_config.second_direction = 1*circle_config.rotation_direction;
}

static circle_movement_t circle_step_16(void)
{
    int16_t Fsingle,
            Fboth;

    circle_movement_t result;

    Fboth = circle_config.calc.i16.F + 2*((int16_t)(circle_config.calc.i16.first_axis)-(int16_t)(circle_config.calc.i16.second_axis)+1);

    if (!circle_config.disable_first_movement)
    {
        Fsingle = circle_config.calc.i16.F + 2*(circle_config.calc.i16.first_axis) + 1;    //first axis movement

        if (abs(Fsingle) < abs(Fboth))
        {  //first direction is the best
            circle_config.calc.i16.F = Fsingle;
            circle_config.calc.i16.first_axis++;
            circle_config.axis_difference--;
            result = circle_transform_positions(1,0);
        }
        else
        {  //diagonal movement is the best
            circle_config.calc.i16.F = Fboth;
            circle_config.calc.i16.first_axis++;
            circle_config.calc.i16.second_axis--;
            circle_config.axis_difference -= 2;
            result = circle_transform_positions(1,1);

            //diagonal movement, check if last bytes from first and second differ more than 1, if yes, compare completely, if the difference is again less or equal to one, switch to secondary first movement
            if (circle_config.axis_difference <= 2)
            {  //perform full check
                circle_config.disable_first_movement = ((circle_config.calc.i16.second_axis - circle_config.calc.i16.first_axis + 1) <= 2);
            }
        }
    }
    else
    {
        Fsingle = circle_config.calc.i16.F - 2*(circle_config.calc.i16.second_axis) + 1;

        if (abs(Fsingle) < abs(Fboth))
        {
            //second direction is the best
            circle_config.calc.i16.F = Fsingle;
            circle_config.calc.i16.second_axis--;
            result = circle_transform_positions(0,1);
        }
        else
        {
            //diagonal movement is the best
            circle_config.calc.i16.F = Fboth;
            circle_config.calc.i16.first_axis++;
            circle_config.calc.i16.second_axis--;
            result = circle_transform_positions(1,1);
        }
    }

    if (*(uint8_t *)&circle_config.calc.i16.second_axis == 0)
    {
        if ( *( ((uint8_t *)&circle_config.calc.i16.second_axis) +1) == 0 )
        {
            circle_config.calc.i16.first_axis = 0;
            circle_config.calc.i16.second_axis = circle_config.calc.i16.radius;
            circle_config.calc.i16.F = 0;    //same as in init.

            if (++circle_config.quadrant > 4)
                circle_config.quadrant = 1;

            circle_config.disable_first_movement = 0;  //we are at the beginning, first axis is main axis.

            circle_config.axis_difference = (*(uint8_t *)&circle_config.calc.i16.second_axis)+1; //get only ls-byte

            update_direction_factors();
        }
    }

    return result;
}

static circle_movement_t circle_step_32(void)
{
    int32_t Fsingle,
            Fboth;

    circle_movement_t result;

    Fboth = circle_config.calc.i32.F + 2*((int32_t)(circle_config.calc.i32.first_axis)-(int32_t)(circle_config.calc.i32.second_axis)+1);

    if (!circle_config.disable_first_movement)
    {
        Fsingle = circle_config.calc.i32.F + 2*(circle_config.calc.i32.first_axis) + 1;    //first axis movement

        if (labs(Fsingle) < labs(Fboth))
        {  //first direction is the best
            circle_config.calc.i32.F = Fsingle;
            circle_config.calc.i32.first_axis++;
            circle_config.axis_difference--;
            result = circle_transform_positions(1,0);
        }
        else
        {  //diagonal movement is the best
            circle_config.calc.i32.F = Fboth;
            circle_config.calc.i32.first_axis++;
            circle_config.calc.i32.second_axis--;
            circle_config.axis_difference -= 2;
            result = circle_transform_positions(1,1);

            //diagonal movement, check if last bytes from first and second differ more than 1, if yes, compare completely, if the difference is again less or equal to one, switch to secondary first movement
            if (circle_config.axis_difference <= 2)
            {  //perform full check
                circle_config.disable_first_movement = ((circle_config.calc.i32.second_axis - circle_config.calc.i32.first_axis + 1) <= 2);
            }
        }
    }
    else
    {
        Fsingle = circle_config.calc.i32.F - 2*(circle_config.calc.i32.second_axis) + 1;

        if (labs(Fsingle) < labs(Fboth))
        {
            //second direction is the best
            circle_config.calc.i32.F = Fsingle;
            circle_config.calc.i32.second_axis--;
            result = circle_transform_positions(0,1);
        }
        else
        {
            //diagonal movement is the best
            circle_config.calc.i32.F = Fboth;
            circle_config.calc.i32.first_axis++;
            circle_config.calc.i32.second_axis--;
            result = circle_transform_positions(1,1);
        }
    }

    if (*(uint8_t *)&circle_config.calc.i32.second_axis == 0)
    {
        if (circle_config.calc.i32.second_axis == 0)
        {
            circle_config.calc.i32.first_axis = 0;
            circle_config.calc.i32.second_axis = circle_config.calc.i32.radius;
            circle_config.calc.i32.F = 0;    //same as in init.

            if (++circle_config.quadrant > 4)
                circle_config.quadrant = 1;

            circle_config.disable_first_movement = 0;  //we are at the beginning, first axis is main axis.

            circle_config.axis_difference = (*(uint8_t *)&circle_config.calc.i32.second_axis)+1; //get only ls-byte

            update_direction_factors();
        }
    }

    return result;
}

---

mfG
Markus

Edit: Kritik und Kommentare zu dem Source und meinem Programmierstil sind erwünscht - ich habe mir C selbst beigebracht und kann daher sicherlich noch viel lernen.

...ignore......ignore...

...ignore......ignore...

Ich sehe momentan nicht, wo es viele Probleme gibt - man muss nur einmalig die Startkoordinaten richtig initialisieren (dieser Teil fehlt noch bei meinem Source) und danach läuft das ganze relativ flink.
Ob man dafür auf Winkelberechnungen zurückgreift oder einfach beim Viertel vorher anfängt und dann solange die Koordinaten verwirft bis man bei seiner Startposition ist, ist eine Implementierungsfrage.
Insbesondere halte ich einen Co-Prozessor mit knapp 100Mhz für etwas - Oversized - der Bresenham-Ansatz ist mit der oben gezeigten Implementierung wesentlich schneller wie die meisten hier gebauten Fräsen - auf 20Mhz und ohne Assembler-Optimierungen.

mfG
Markus

Moin!
@Peter1060: Dein Programm habe ich in den Weiten des Web schonmal gefunden, nützt mir aber ohne Quellcode nicht soo viel :-)

Ich denke auch, dass meine Fräse eh so langsam ist, dass mein Mega8 mit 8MHZ genug Zeit zum Rechnen hat ...
Sobald ich irgendeine Art von Kreisbogenfräsen implementiert habe, werde ich das hier mal posten.

MfG
Volker

Volker: Ich würde den Mega8 durch nen Mega168 ersetzen (oder sogar 328) und dann mit 20Mhz betreiben - dadurch kannst du ein genaueres Timing bei der Motoransteuerung (insbesondere bei der Geschwindigkeitsregelung) erreichen.
Dort bekommst du dann auch andere Goodies wie mehr Timer.

mfG
Markus

Moin! Im Prinzip hast Du recht, aber bisher reicht er mir locker :-) Das Timing läuft bei mir im Moment eh über blockierende delays (_delay_loop_2), und noch (!) habe ich genug Platz im Flash. Sollte das mal eng werden, werde ich wohl tauschen, vielleicht fallen mir ja noch ein paar Sachen ein, die die Fräse können soll. Im Moment schummele ich ja etwas, weil ich den GCode in einem C# Programm interpretiere und dort in Byte-Kommandos übersetze, die dann recht einfach vom µC ausgewertet werden können.
MfG
Volker

So in der Art ist meine Umsetzung auch geplant - es macht keinen Sinn, die ganze Syntax- und Stringverarbeitung in einen AVR zu gießen, dafür gibt es ein schlankes Protokoll zwischen AVR und PC.
Im übrigen kann man die "aufwändigen" Vorberechnungen zur Kreisinitialisierung auf diesem Wege z.Bsp vom PC vorberechnen lassen, sodass der AVR wieder nur den Pattern-Generator (in dem Falle den Bresenham) anstoßen muss.

mfG
Markus

Die Idee gefällt mir, ich hab mir nämlich gerade einen abgebrochen die ganze Stringverarbeitung auf den Mega32 zu portieren bis ich dann gemerkt hab das das nich der richtige Weg sein kann.

Besonders gefällt mir auch die Sache mit der Pufferung der Berechnungsergebnisse in einem fifo. Das ist dann ja fast sowas wie Multithreading auf einem µC. Speicherst du da direkt die berechneten Schrittfolgen ab, oder wie?

Es ist im Endeffekt etwas ähnliches wie Multithreading.
Der Pattern-Generator erzeugt das Bewegungsmuster (wie oben die Bresenham-Implementierung), das landet im Fifo.
Eine Timer-ISR soll dann selbstständig Anfahr- und Bremsrampen sowie die Geschwindigkeitsregelung übernehmen, indem sie ein Muster einfach länger als eine Takteinheit am Port anliegen lässt.
Es hat allerdings zwei Nachteile:
1. Insgesamt wird ein leichter Overhead erzeugt, da die FiFo-Verwaltung noch dazu kommt
2. Es bedarf eines ausgeklügelten Mechanismus, damit die Berechnung der Rampen funktioniert und insbesondere rechtzeitig abgebremst wird. Wie ich das realisieren werde, steht noch nicht endgültig fest, insbesondere ist es gerade bei Kreisen schwer/fast unmöglich, die Anzahl der Schritte vorherzusagen.
Hier kommt auch ein Haken beim Bresenham zum Tragen: Eine konstante Bahngeschwindigkeit zu Regeln ist schwer bis unmöglich und erfordert auf jeden Fall zusätzlichen Aufwand, will man verhindern, dass die Geschwindigkeit im Bereich der Diagonalen um Faktor Wurzel 2 schneller als bei einer einfachen Bewegung parallel zu den Koordinatenachsen ist.

Es gibt aber auch einen ganz klaren Vorteil:
Die Fräse muss nicht nach jedem einzelnen G-Code-Element erst einmal neu Rechnen, während die letzten Einträge aus dem FiFo noch abgearbeitet werden, kann der Decoder bereits mit der Berechnung des nächsten Eintrags fortfahren.

mfG
Markus

Danke für diese Ausführung. Ich hab das jetzt mit einem Ring Buffer realisiert in dem einfach als Byte Werte die Schrittfolgen gespeichert werden. So können dann bis zu 400 Schritte gepuffert werden. Das funktioniert mit dem Bresenham zusammen auch schon sehr gut, nur meine Kreisfunktion geht leider noch nicht. Jetzt suche ich aber erstmal nach einem Algorithmus um die Daten möglichst schnell und vorallem Fehlerfrei über den uart zu schieben.