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.

View this post on Instagram

A post shared by Marginally Clever Robots (@imakerobots) on

## 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.