The problem with drawing a straight line on a computer screen, printer/plotter, or CNC machine is teaching the machine what a line is!

In maths, a straight line is a plot of values on a flat plane, measured in two directions, usually at a right angle to one another. By convention we use the letters X and Y to refer to the two axes, then known as the “X-axis” and the “Y-axis”.

If the line is horizontal, the line is drawn along the X-axis as an infinite number of dots with a Y value of 0 (zero) (i.e., ‘For all values of X from 0 to infinity, Y = zero’). Similarly, a vertical line is a line of an infinite number of dots, so ‘For all values of Y from 0 to infinity, X=0’.

Simple? Well what if the line is a diagonal? A true diagonal, if you remember your geometry, occurs when Y is equal to X for all values of X. So Y = X is a straight line at 45 degrees.

If the line doesn’t pass through zero, we can ‘correct’ the line by adding a value named ‘C’ that is the value of Y when X=0. Now we have a line of the formula Y = X+C, remembering that C may be a negative value, as may X and Y.

Our last problem is ‘What if the line isn’t horizontal, vertical or at 45 degrees?’

The angle of the line, when a number of degrees is not given can be referred to as the slope, which is the ratio between X and Y. Remember in our 45-degree line, that line would have a slope of 1, as Y/X = 1.

So finally we have a complete formula for any straight line; Y = MX + C.

Any line, straight or curved can be drawn as a number of straight segments. Think about a bicycle chain. Every link is a hard shape with a straight line between the two pins that join chain links. But the chain can make a seemingly easy curve around the pedal gear.

Computers can draw anything by joining together a lot of short links. However, calculating the X,Y position of every link, and at both ends, requires a lot of maths; simple maths, but a lot of calculations is required for any computer to draw a simple line.

PIXELS AND STEPS

Computer screens and stepper motors use a fixed number of pixels or steps, which must be coordinated to make a line that appears as a straight line, at any reasonable scale. Take out a magnifying glass, and take a close up look at a computer screen, and you will see a lot of tiny square pixels, that can only be turned on or off, and cannot be made to move into a straight line. Similarly, find a paved ground, and try to walk a straight line diagonally across the space without stepping on two paving stones at the same time. Yes, you may look like a nut, but tell people you’re investigating Bresenham’s Line Algorithm, and they’ll realise you’re just a nerd!

Look at Figure 2 as a stepper motor controller! Remember, you can only step forward or upward, and you want the error to be as small as possible. You have to step forward, or upward. Try it for each line.

The aim is to have the least error between the straight line and the staircase line. As the X-axis steps forward, a decision must be made about whether making one step in the Y-axis direction will create a greater error than staying at the same Y value.

BRESENHAM’S ALGORITHM

The most common solution to this conundrum is named after the guy who worked it out. The algorithm uses integer maths to decide whether a step in the Y direction will make a greater or lesser error between the [X,Y] position and the track of the straight line.

The maths requires only addition, subtraction and multiplication of integers, which can be achieved on a simple computer - even an old 8-bit clunker - to calculate what steps the stepper motor should take to draw a straight line.

Read the following pseudo code, and the comments added to the listing.

************************************************************
* Bresenham’s line algorithm */
* pseudo code */
*************************************************************
* Setup Numbers: based on the coil winder job for one turn.
* X = Coil Motor steps per full turn = 200, X1 = 0, X2 = 200
* Y = Spool Motor steps per wire width = 13, Y1 = 0, Y2 = 13
************************************************************
function Line(X1,Y1,X2,Y2)   // G-code without the feed rate.
int X1 = 0;       // X start position
int X2 = 200;     // X end position
int Y1 = 0;       // Y start position
int Y2 = 13;      // Y end position
int dX = X2 - X1; // X-distance (200)
int dY = Y2 - Y1; // Y-distance (80)
int D = 2*dY - dX // Bresenham’s value
int Y = Y0;       // beginning value
for X from X1 to X2 // Range of motion in x axis
step(X)         // CNC requires motion in 2 axis’
if D > 0
step(Y)      // CNC requires motion in 2 axis’
Y = Y + 1    // Keep track of current location
D = D - 2*dX
end if
D = D + 2*dY

This should be easily converted to most programming languages.

Spreadsheet of Bresenham’s Algorithm

X1 = 0
X2 = 200
dX = X2 – X1 = 200
2xdX = 400
Y1 = 0
Y2 = 13
dY =  Y2 – Y1 = 13
2xdY = 26
D = 2*dY-dX = -174 //Starting value

(The table below is only part of the 200 steps for X.)

Note: There are about three steps error, accounting for less than a quarter diameter of the wire, which would be of no concern in winding. The cause of the error is not known to me at this time.