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