Algorithm?

[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

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.