Important firmware update corrects overstepping errors
This weekend I pushed an important firmware update that corrects overstepping errors in many robot projects. They include:
– the Delta Robot 3,
– the Rotary Stewart Platform 2,
– the Makeleangelo,
– the GCodeCNCDemo,
and possibly others.
Bresenham’s line algorithm
All of these projects move more than one stepper motor at the same time. They are all based on Bresenham’s line algorithm. Bresenham walks one pixel at a time from one end to the other – or in the case of a CNC machine, stepping motors as the tool moves along the line. Now this is the really important bit: even though pixels are very small, they have a width and a height. For Bresenham to be most accurate, the equation should start in the center of each pixel, not on the edge. I learned Bresenham in my early teens and somehow that little fact fell out of my head. Every one of my implementations assumed a start on the edge of the pixel.
Processing example
Here’s an example of the difference between the right and the wrong ways to do Bresenham’s algorithm. Copy/Paste this code into Processing 3 and run it. Green lines are correct, red lines are wrong.
/**
* Processing 3 sketch to show the problem
*/
void setup() {
size(500, 500);
float total=10;
int i;
float HALFPI = PI / 2;
// draw lots of lines with the broken algorithm
stroke(255,0,0);
for(i=0;i<=total;++i) {
lineWrong(0,0,
(int)(sin(HALFPI*i/total)*width*0.9),
(int)(cos(HALFPI*i/total)*height*0.9));
}
// draw lots of lines with the fixed algorithm
stroke(0,255,0);
for(i=0;i<=total;++i) {
lineCorrect(0,0,
(int)(sin(HALFPI*i/total)*width*0.9),
(int)(cos(HALFPI*i/total)*height*0.9));
}
}
void draw() {}
void lineWrong(int x0,int y0,int x1,int y1) {
if(x0>x1) {
int t = x1;
x1=x0;
x0=t;
t = y1;
y1=y0;
y0=t;
}
int dx = x1-x0;
int dy = y1-y0;
// does line slope up or down?
int direction = dy>0?1:-1;
dy *= direction;
if(dx<dy) {
int over = 0; // <-- WRONG!
for(int i=0;i<dy;++i) {
point(x0,y0);
y0+=direction;
over += dx;
if( over > dy ) {
over -= dy;
++x0;
}
}
} else { // dy<dx
int over = 0; // <-- WRONG!
for(int i=0;i<dx;++i) {
point(x0,y0);
++x0;
over += dy;
if( over > dx ) {
over -= dx;
y0+=direction;
}
}
}
}
void lineCorrect(int x0,int y0,int x1,int y1) {
if(x0>x1) {
int t = x1;
x1=x0;
x0=t;
t = y1;
y1=y0;
y0=t;
}
int dx = x1-x0;
int dy = y1-y0;
// does line slope up or down?
int direction = dy>0?1:-1;
dy *= direction;
if(dx<dy) {
int over = dy/2; // <-- RIGHT!
for(int i=0;i<dy;++i) {
point(x0,y0);
y0+=direction;
over += dx;
if( over > dy ) {
over -= dy;
++x0;
}
}
} else { // dy<dx
int over = dx/2; // <-- RIGHT!
for(int i=0;i<dx;++i) {
point(x0,y0);
++x0;
over += dy;
if( over > dx ) {
over -= dx;
y0+=direction;
}
}
}
}
So what’s the big deal with overstepping errors?
There are two really nasty bits to this problem. The first is that the overstepping errors are cumulative – on Marginally Clever robots the tiny error adds up, getting worse over time. The second is that the problem can cancel itself out – Draw line A to B, then B to A and the error is gone. This meant that the error took a long time to diagnose, but a very short time to fix.
The proof is in the drawings
This drawing of Iron Maiden’s mascot used to be impossible. Now it draws flawlessly.
Special thanks
I want to take a moment here to thank Joshua Portway for sending in a reproducible test case that demonstrates the problem every single time and makes it easy to test and fix the issue.
How to update your robot
– Grab the latest version of Arduino.
– Grab the latest version of the firmware (linked above).
– Open the code in Arduino.
– Make sure the robot has power and is connected to your computer with a USB cable.
– Make sure your Tools > Port and Tools > Board are correctly set. RUMBA boards should use “Mega 2560”.
– Press the upload button:
That’s it!
Final thoughts
If you have any further issues with the firmware upload, please use the support forums.
