[CNCgr]

I don't know if it's the right place to post this.

Some time ago someone posted that he was developing his own motion control software and someone suggested he took a look on some algorithm of converting the motion to intermediate steps (essentially a vector to raster transformation).

The algorithm was named after the man who invented it, doesn anybody know what I'm talking about?

Thanks,
Nikolas

[WayneHill]

Bezier curves ?

[CNCgr]

No, but thanks for answering. The one I'm looking for is much simpler. I want to go from point A to point B. Say I'm using steppers so there's a finite amount of positions the machine can take. Which are the points that better represent the A to B line. I hope I made it clearer.

Nikolas

[gimbal]

Hi Nikolas,

The algorithm you are looking for is the Bresenham Algorithm.

Cheers,

Pat

[CNCgr]

Hi Nikolas,

The algorithm you are looking for is the Bresenham Algorithm.

Cheers,

Pat

:cheers: Yeaaaaah!!! Thank's a lot, I owe you a beer!

Nikolas

[DR-Motion]

Consider the process of connecting two points on a piece of paper by drawing a line between them. To do so we must move our pencil in two axes simultaneously... where the motion of one axis is in fixed proportion to the motion of the other. This fixed proportion is the ratio of the distance the secondary axis has to move compared to the primary axis... and is equivalent to the slope of the line between the two points.

The procedure we use to calculate this ratio can have a major impact on the maximum precise pulse rate that our controller can produce. The processing time, used for the calculation limits the minimum step delay time, which determines our maximum speed. When we extend the coordinated motion to three or four axes, this processing time becomes even more significant.

The most efficient approach adopts an algorithm from the old days... when men were men and computers were wimpy. In the early days of computing, processing power was extremely expensive and limited. The task of connecting two points with a line was solved, for the problem of plotting a line on the raster display of a typical monitor.

The solution was called Bresenham's algorithm and involved only integer arithmetic, using addition and subtraction.

Here's an example of some pseudo code that demonstrates the application of Bresenham's algorithm in coordinating two axes of movement from one point to another.

distance = master // master is the axis which has the longer
distance to travel.

error = zero // error tracks the distance from the ideal
position.

While distance > zero // loop until distance has been traveled

{

Step pulse on master axis // outputs a pulse for the master axis .

distance = distance - 1 // distance has one less step to take

error = error + slave // slave is the axis, which has the
shorter distance to travel.

If error > slave // compare error

{

error = error - master

step pulse on slave axis // outputs a pulse for the
slave axis.

}

}

It turns out that this algorithm can be adapted to more than two axes simply by having a separate error term for each slave axis term. So as the master axis is traversed one step at a time... each of the (shorter) slave axes are stepped in proportion to their ratio (to the master).

So now we have a method of coordinating the motion of multiple axes with a minimum of computational overhead. In fact, a similar algorithm exists for circular motion.

[acondit]

I thought that in 8 bit logic 2b = 00101011 and ~2b = 11010100.
So 2b | ~2b = 00101011 | 11010100 = 11111111. Or FFh or 255.

Alan

[DR-Motion]

Sorry that would be 0x2d | ~ 0x2d ( 0b00101101 | 0b11010010 )

Symbolic algebra does not imply any particlular number base.

To paraphrase another member's sig... there are 10 kinds
of people in this world, those who don't understand binary,
those who think binary is the greatest new thing and
those who routinely use a plethora of modulo number bases ;-)

[acondit]

Gary,

You are correct, (my bad).

Alan

[HuFlungDung]

Hey, I got it...."10 kinds of people", but that's two in decimal talk isn't it? So shouldn't it be 11 kinds of people?

Question on the application of this algorithm to machine motion: it would seem that none of the axis can move less than a pulse, so how do you prevent the loss of steps due to rounding off errors? Or how does the computer create what appears to be a smooth output over this bumpy road of digital bits? Is there some kind of averaging thing that is having all these "go, don't go" signals fed in?

[Geof]

Hey, I got it...."10 kinds of people", but that's two in decimal talk isn't it? So shouldn't it be 11 kinds of people?

Thanks Hu, I did wonder what I was missing.

[DR-Motion]

count 0,1,2,10 in base 3 (trinary numbers)
It's a Monte Python number base...
yes, no and perhaps ;-)

Hu, a step and direction system can never output a fractional step/microstep;
if you zoom in close enough all curves show as a staircase albeit smoothed
by the inertia and flex of the machine.

[unterhaus]

Question on the application of this algorithm to machine motion: it would seem that none of the axis can move less than a pulse, so how do you prevent the loss of steps due to rounding off errors? Or how does the computer create what appears to be a smooth output over this bumpy road of digital bits? Is there some kind of averaging thing that is having all these "go, don't go" signals fed in?

Bresenham's algorithm has advantages over the brute force method: it can be done with integer only math, errors don't acummulate, and it uses a very nice method to decide if you should move on the minor axis. If you think about how this works, one of the axis is going to move one step every time because it has more distance to cover. The other one - the minor axis - may or may not move. So if the error between where you are and where the line exceeds half a step (not how they calculate it, but it's equivalent) you move the minor axis. This minimizes the error. On a machine, cutting forces and inertia may be your friend. On your screen, they also blend colors to make the jaggies look less stark, can't really do this with a stepper motor.

I just used it for an image processing algorithm, and it worked great. Of course, I didn't care about jaggies at all, just speed and accumulated error. I did have to modify it a little from the normal computer video implementation, because I wanted to start in one place and end in the other. I looked it up on Wikipedia.

[hobby.club]

Hello,
I use an very simple algoritme .
i write a program for AT90S2313,it communicate to Pc via RS232
on the PC runs a program in VB6
maybe its usefull for you?
I am new on the internet i dont now how to attach the code,maybe i can
mail it to you?
Sorry for my english
my email adres:[email protected]

[mwalach]

I am working on a CNC driver program and am trying to wrap my head around the G2 and G3 codes. It looks like the Bresenham Algorithm is the answer, but I'm having trouble getting my head wrapped around this. How do I use the algarithm to generate my steps from a centerpoint and a radius as I would have in a G2 or G3 gcode?

[BartW]

Any one done a 3d version?

[Larken]

I've used this algoithm in both my controllers (Lcam and StarCam), The Starcam runs it in a 40 mhz PIC with 64K ram buffer. It can run 35000 steps/sec running a 16 bit 3d vector. My older DOS (Lcam) could run 90K /sec

Bresenham's Algorithm is a 'on the fly' integer divide. There are arc routines out there for drawing on screens, but I couldn't find a arc routine that would allow starting in the middle of a quadrant, but i developed a fast sqrt routine that can run in integer and decide whether an axis should step or not dependine on a pre-calculated radius.

Mach 3 works differently, it 'steers' 6 free running timers by correcting the trajectory at a periodic rate. This is great but the faster you go the more error and slop there is. A Bresenham loop is perfectly accurate at any speed, the draw back is pulse timing is not evenly spaced, ( but this doesn't matter on a servo or microstepping drive.)

Larry K


Larry K