ZitierenOk, 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
bresenham_private.hCode:#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.cCode:#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
mfGCode:/* 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; }
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.
und dann mit 20Mhz betreiben - dadurch kannst du ein genaueres Timing bei der Motoransteuerung (insbesondere bei der Geschwindigkeitsregelung) erreichen.
Lesezeichen