C: Bresenham Line Algorithm And Generating Step Pulses
idbruce
Posts: 6,197
Hello Everyone
As mentioned in the Teacup thread, I have abandoned all hope of getting it to work, but I have not given up on writing my own parser and processor. In an effort to save myself a lot of wasted time, I am asking the community to lend a helping hand with my current task. I have what I believe is a nice section of source code, but I really do not know the proper location and method for generating the pulse. If you are familiar with this algorithm and generating step pulses, please help. This is the code that I do have:
As mentioned in the Teacup thread, I have abandoned all hope of getting it to work, but I have not given up on writing my own parser and processor. In an effort to save myself a lot of wasted time, I am asking the community to lend a helping hand with my current task. I have what I believe is a nice section of source code, but I really do not know the proper location and method for generating the pulse. If you are familiar with this algorithm and generating step pulses, please help. This is the code that I do have:
int32_t d;
int32_t delta_x;
int32_t delta_y;
static void bresenham_line(x_1, y_1, x_2, y_2)
{
int32_t counter;
int32_t pixels;
int32_t d_incline_1;
int32_t d_incline_2;
int32_t x;
int32_t x_incline_1;
int32_t x_incline_2;
int32_t y;
int32_t y_incline_1;
int32_t y_incline_2;
// initialize delta_x and delta_y
delta_x = abs(x_2 - x_1);
delta_y = abs(y_2 - y_1);
// initialize variable based upon whether x or y is independent
if(delta_x >= delta_y)
{
// declare x as the independent variable
pixels = delta_x + 1;
d = (2 * delta_y) - delta_x;
d_incline_1 = delta_y << 1;
d_incline_2 = (delta_y - delta_x) << 1;
x_incline_1 = 1;
x_incline_2 = 1;
y_incline_1 = 0;
y_incline_2 = 1;
}
else
{
// declare y as the independent variable
pixels = delta_y + 1;
d = (2 * delta_x) - delta_y;
d_incline_1 = delta_x << 1;
d_incline_2 = (delta_x - delta_y) << 1;
x_incline_1 = 0;
x_incline_2 = 1;
y_incline_1 = 1;
y_incline_2 = 1;
}
// set the proper directions for x and y
if(x_1 > x_2)
{
x_incline_1 = -x_incline_1;
x_incline_2 = -x_incline_2;
}
if(y_1 > y_2)
{
y_incline_1 = -y_incline_1;
y_incline_2 = -y_incline_2;
}
// starting point
x = x_1;
y = y_1;
// insert the pixels
for(counter = 1, counter < pixels, counter++)
{
insert_pixel(x, y);
if(d < 0)
{
d = d + d_incline_1;
x = x + x_incline_1;
y = y + y_incline_1;
}
else
{
d = d + d_incline_2;
x = x + x_incline_2;
y = y + y_incline_2;
}
}
}
static void insert_pixel(x, y) // insert a pixel at x and y
{
if(d < 0)
{
d = d + (2 * delta_y);
}
else
{
d = d + 2 * (delta_y - delta_x);
y = y + 1;
}
x = x + 1;
}
Comments
I break the line into two parts; the fast axis and the slow axis. I calculate an acceleration table for the fast axis and use the delays generated for both the start and end sections of the line. The rest of the line (the center) is made up of full speed delays.
I then generate the slow axis' acceleration table and create a similar list of delays for the slow axis. The acceleration periods for both axes should be about the same amount of time. The total time each axis moves should also be nearly equal. I found it was too much effort to get the intervals to match exactly but I think I've got them to match reasonably well. Of course my opinion of the level of success may change once I test the algorithm in my CNC router.
These lists of delays are stored to separate SD files (one for the x axis and one for the y axis). I'm hoping the Propeller can read these delays from the SD card fast enough to drive the two steppers. I'm using alternating buffers in hub RAM as a buffer between the SD card and PASM. The hub buffer is what is read from a cog running PASM code. I'm pretty sure the SD card can be read in blocks faster than when reading individual bytes or longs. My buffers are 100 longs each and I use two buffers per axis. One buffer is being filled from the SD card as the other buffer is being read from PASM. I haven't tested this code yet.
I honestly don't know if the route I'm taking is a good one or not but I thought I'd let you know how I'm attempting to solve this problem. I have a nagging suspicion, the SD card will be too slow but my initial tests of SD card reading rates look promising.
I suspect (and I've been told) that my approach of generating each individual delay isn't very practical. I believe the "normal" way to accelerate steppers is to progressively reduce the delay amount based on some time interval (using a timer interrupt on non-Prop micros). You can't just reduce the delay of each pulse by some set value since this gives a logarithmic acceleration.
I personally wanted to generate each delay of the acceleration period in order to achieve smooth acceleration at low speeds.
static void insert_pixel(x, y) // insert a pixel at x and y { if(d < 0) { d = d + (2 * delta_y); } else { d = d + 2 * (delta_y - delta_x); y = y + 1; STEP THE Y MOTOR HERE } x = x + 1; STEP THE X MOTOR HERE }This assumes the "pixel" size is equal to the step size.
Thanks a lot, I appreciate it. I will try to wrap my head around it and test within a day or so. I am also pondering how to work ramping in there.
@Duane
Please keep me posted how it goes, I may try to borrow a cup of code from you
-Phil
Agreed.
Based on what I've read, I think it's very important to properly ramp stepper speed or steps will likely be missed. I initially tried something similar to a Bresenham line algorithm in my code but I found the calculated delays of the slower motor were very inconsistent. The differences between delays (generated with the Bresenham algorithm) were greater than the differences in a properly accelerated list of delays.
PUB FillAccelTable(tablePtr, maxTableSize, minSpeed, maxSpeed, accelStepsPerSec, { } masterFlag, longDistance, shortDistance, localDebugFlag) | { } delayInTicks, scaledFreq, stepsTilHalf, columnCount '' This method needs to be executed with the masterFlag set before calculating '' the acceleration table for the slave (slow) speed. '' The values of "longDistance", "shortDistance" are not important when '' computing the master acceleration table. '' v = at ||longDistance ||shortDistance columnCount := 0 delayAtMaxSpeed[Header#MASTER_ACCELERATION] := CLK_FREQ / maxSpeed scaledFreq := CLK_FREQ / Header#SCALED_MULTIPLIER if masterFlag stepsTilHalf := longDistance / 2 minSpeed *= Header#SCALED_MULTIPLIER longDistance := 1 shortDistance := 1 else delayAtMaxSpeed[masterFlag] := TtaMethod(delayAtMaxSpeed[Header#MASTER_ACCELERATION], { } longDistance, shortDistance) stepsTilHalf := shortDistance / 2 minSpeed := minSpeed * shortDistance * Header#SCALED_MULTIPLIER / longDistance accelerationTime[masterFlag] := 0 timeTilFullSpeed[masterFlag] := 0 result := 0 repeat delayInTicks := TtaMethod(CLK_FREQ, Header#SCALED_MULTIPLIER, minSpeed) if localDebugFlag ifnot columnCount++ // 4 Pst.Str(string(11, 13, " long ")) else Pst.Str(string(", ")) Pst.Dec(delayInTicks) if result < stepsTilHalf timeTilFullSpeed[masterFlag] += delayInTicks long[tablePtr][result++] := delayInTicks accelerationTimeSlave[masterFlag] += delayInTicks minSpeed += TtaMethod(accelStepsPerSec * shortDistance, delayInTicks, longDistance * scaledFreq) while delayInTicks > delayAtMaxSpeed[masterFlag] and result < maxTableSize long[tablePtr][result - 1] := delayAtMaxSpeed[masterFlag] ' fix last time accelerationTimeSlave[masterFlag] -= delayInTicks ' fix total time accelerationTimeSlave[masterFlag] += delayAtMaxSpeed[masterFlag] Pst.str(string(11, 13, "elements in acceleration array = ")) Pst.Dec(result) Pst.str(string(11, 13, "stepsTilHalf = ")) Pst.Dec(stepsTilHalf) Pst.str(string(11, 13, "timeTilFullSpeed[")) Pst.Dec(masterFlag) Pst.str(string("] = ")) Pst.Dec(timeTilFullSpeed[masterFlag]) Pst.str(string(11, 13, "accelerationTimeSlave[")) Pst.Dec(masterFlag) Pst.str(string("] = ")) Pst.Dec(accelerationTimeSlave[masterFlag]) if result => maxTableSize and delayInTicks > delayAtMaxSpeed[masterFlag] Pst.str(string(11, 13, "Acceleration array too big. End of program.")) Pst.str(string(11, 13, "delayAtMaxSpeed[")) Pst.Dec(masterFlag) Pst.str(string("] = ")) Pst.Dec(delayAtMaxSpeed[masterFlag]) Pst.str(string(11, 13, "delayInTicks = ")) Pst.Dec(delayInTicks) repeat PUB TtaMethod(N, X, D) ' return X*N/D where all numbers and result are positive =<2^31 return (N / D * X) + (binNormal(N//D, D, 31) ** (X*2)) PUB BinNormal (y, x, b) : f ' calculate f = y/x * 2^b ' b is number of bits ' enter with y,x: {x > y, x < 2^31, y <= 2^31} ' exit with f: f/(2^b) =< y/x =< (f+1) / (2^b) ' that is, f / 2^b is the closest appoximation to the original fraction for that b. repeat b y <<= 1 f <<= 1 if y => x ' y -= x f++ if y << 1 => x ' Round off. In some cases better without. f++These are the values I'm using (for now) for max and min speeds and acceleration.
The speeds are in units of steps per second.
The table size of 1250 turns out to be exactly what is needed when using these parameter in the method.
The final parameters used will likely be different. I'll likely use a higher acceleration value and higher max and min speeds. I haven't figured out what the limits of my setup are.
The arrays with "masterFlag" as the index hold values for both the fast (aka master) and the slow (slave) elements.
It would be nice if these acceleration values could be calculated for both axes at once and as needed but I think these calculations would need to be performed in PASM. For now I'm seeing if I can get away with saving a list of delay values to the SD card and these use this list to control the motors. As I mentioned previously, I'm not at all sure I'm going about this the right way.
I believe you may want to rethink your strategy. It has been a couple years now, but it was either Gecko or Applied-Motion that told me, one to two revolutions should be added for every revolution. I believe that is what it was. I think the fastest that I was able to achieve was adding 2-1/4 ~ 2-1/2, but then I think I settled in at a maximum of adding 2 revs per rev, and it worked well in a no load situation. With a load, you drop that back.
EDIT: I am not saying that your code won't work, but perhaps it is possible that you may not get the best from your steppers.
Did you ever toy around with that code I wrote for the simultaneous steppers? I was wondering if they actually were in sync on a scope.
EDIT: If someone could verify for me, whether this code generates pulses that are simultaneous, I may end up doing something with this: http://forums.parallax.com/showthread.php/159926-Introducing-quot-SyncroStepper-quot-Syncronization-For-Multi-Axis-Machines
I just finished this, so it may have some errors, though it should get the idea across:
PUB StpLine(Xa,Xb,Ya,Yb) LnX := 1 LnY := 1 LnXD := Xb - Xa LnYD := Yb - Ya if Xa > Xb LnX = -1 LnXD = Xa - Xb if Ya > Yb LnY = -1 LnYD := Ya - Yb If Xa == Xb IF Ya > Yb FwdY(LnYD,ySpd) IF Ya < Yb BckY(LnYD,ySpd) RETURN If Ya == Yb IF Xa > Xb FwdX(LnXD,xSpd) IF Xa < Xb BckX(LnXD,xSpd) RETURN If LnXD => LnYD LnD := LnXD / LnYD REPEAT IF LnX > 0 FwdX(LnD,xSpd) Xa := Xa + LnD ELSE BckX(LnD,xSpd) Xa := Xa - LnD IF Ya <> Yb IF LnY > 0 FwdY(1,ySpd) Ya := Ya + 1 ELSE BckY(1,ySpd) Ya := Ya - 1 UNTIL Xa == Xb ELSE LnD := LnYD / LnXD REPEAT IF LnY > 0 FwdY(LnD,ySpd) Ya := Ya + LnD ELSE BckY(LnD,xSpd) Ya := Ya - LnD IF Xa <> Xb IF LnX > 0 FwdX(1,ySpd) Xa := Xa + 1 ELSE BckX(1,ySpd) Xa := Xa - 1 UNTIL Ya == YbIn that code I linked to above, it may appear that I base everything on seconds, but in reality, that is not really the case.
Time really comes into play for the start up speed and maximum speed. If you start too fast, you will never overcome the moment of inertia and if you go to fast.... well I don't know how that would be worded
When it comes to ramping, I just use the clock frequency as a convenient method of obtaining my one to two revs per rev.
The Bresenham Line Algorithm is pretty simple, and ramping should not be that hard to add to it. It uses the longer of the x or y travel as the reference and the shorter distance would be a fraction of that. For ramping the longer direction will determine the maximum rate of speed increase, and if the x and y motors are the same then the motor for the short direction will always ramp at the same or a lower rate.
As Phil says the Bresenham may not be the best choice for controlling x/y/ motors. Better to use the deltaX/deltaY to control the step rate directly.
Take a peek at this.... This guy is pretty darn knowledgable and I think he has a pretty slick setup going, but I think it is limited to 30V PSU.
https://www.youtube.com/watch?v=1ioctbN9JV8