Beizer Curve code for sprinter

It would be awesome to implement a #define in the configuration.h that would enable a bezier curve replacement of the current line / segment linear moving. Ill be taking a look to seem what I can do with it, but heres the base code for it.

My main hope would be to look ahead in the command buffer and grab the next few points well be moving to and plot a bezier curve movement path through them.

My initial thoughts would be to primary use this code then fall back to straight lines when we reach a very sharp angle.

p1, p2, and p3 are points the bezier curve will travel through, mu is how far along the path you want to calculate.

/*
Three control point Bezier interpolation
mu ranges from 0 to 1, start to end of the curve
*/
XYZ Bezier3(XYZ p1,XYZ p2,XYZ p3,double mu)
{
double mum1,mum12,mu2;
XYZ p;

mu2 = mu * mu;
mum1 = 1 - mu;
mum12 = mum1 * mum1;
p.x = p1.x * mum12 + 2 * p2.x * mum1 * mu + p3.x * mu2;
p.y = p1.y * mum12 + 2 * p2.y * mum1 * mu + p3.y * mu2;
p.z = p1.z * mum12 + 2 * p2.z * mum1 * mu + p3.z * mu2;

return(p);
}

would a larger buffer help as well?

the thing that people need to understand about curve acceleration is it accelerates one axis as the other is slowing down, eliminating the stop time that normally happens with gcode lines. since the longest time of a move is at start up especially with acceleration, this method could shave off 20-30% of build time.

how are you going to ensure even steps to prevent stalls? or are you only going to recommend it for belts and 1/8step or greater?

The tricky part here is probably to get curved movements into the Bresenham algorithm. I've thought quite a bit on how to get this, but so far no elegant solution in sight. Standard Bresenham implementations divide curves where they cross an octant, so you have to prepare to sub-divide each of the curves further.

Other CNC controllers, like EMC2, don't use Bresenham, but run a clock at a constant rate. Problem with this approach is, the clock has to run very fast, at least as fast as the highest step rate of any of the steppers, all the time. Also, running at 80% top speed produces substantial jitter (uneven step events), so the clock should run even faster.

That said, any implementation of curved movements is better than what we (Sprinter, Teacup) have at the moment, so, please go ahead without fear!

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

It's a lovely algorithm, but we need to rearrange it into a midpoint (bresenham) style algorithm:

Say we divide a 2D space into regular rectangles (not squares! X and Y can have different steps/mm! A square is a special type of rectangle). We have a current rectangle, and we need to know which of the 8 neighbouring rectangles is closest to the bezier curve, moving in the proper direction. If we can work that out with only a few math-ops, we can certainly integrate this into teacup or some other firmware.

Our acceleration algorithms already need to calculate the distance spent accelerating and decelerating, I propose that m[0].end-m[0].decel_distance is P1, and m[0].end=m[1].start=p2, and m[1].start+m[1].accel_distance is p3. This way we're doing our curve across the region that we would otherwise have spent decelerating and accelerating, while leaving the cruise sections alone.

We also need to know /when/ to step, while obeying per-axis acceleration limits, and the resultant feedrate so we can step E at appropriate times.

I'm thinking that combining per-axis for E and bresenham for XYZ is the way to go, it's already been discussed that E must lead the other axes, and this further demands that E can run independently.

---

-----------------------------------------------
Wooden Mendel
Teacup Firmware

this page has a diagram of those rectangles description of Bresenham

[en.wikipedia.org]



I have yet to be able to easily explain issues with acceleration on ball/screw to people. If using a stepper on x and y axis at high speed, something will just not work with the current Bresenham setup

Edited 2 time(s). Last edit at 06/06/2011 11:37PM by jamesdanielv.

One thing that I noticed with curves is that it implies a small degree of automatic acceleration and deceleration just going around the curve.

We can amplify the acceleration just by increasing and decreasing the MU value in the algorithm above.

//////////////this is really just pseudo code////////////////////
for example :

// plot steps along the curve, based on what our hardware can handle 0.05=5% of curve distance each segment
Acceleration= 0.01; // percentage of distance along curve accelerate by

PositionAlongCurve=0.0 // start at 0 percent along the curve and plot a point
while (PositionAlongCurve<=1.0) // until we have calculated 100% of the curve keep working
{
if (PositionAlongCurve <0.5) // if were less than 1/2 way along the curve then accelerate.
{ PositionAlongCurve +=Acceleration;
Acceleration+=0.01;
} else
{ PositionAlongCurve -=Acceleration; // deccelerate bacause were passed the 1/2 way point
Acceleration-=0.01;
}

NextBeizerPoint = Bezier3(currentPoint,NextPoint, FuturePoint, PositionAlongCurve )
extrusion speed = distance(LastBezierPoint, NextBezierPoint) // much pseudo code here

// calculate steps based on distance between X,Y,Z of Last and Next Bezier Points here
XYZE = CalculateSteps(LastBezierPoint,NextBezierPoint, LastE, NextE);
LastBezierPoint=NextBezierPoint
}

With the above code, accelleration and curves may be pretty close functionally implemented and we have a psedo curve algrithim that can drive our current bresenham line algorithm, and we can tame down to what our hardware can handle based on tracing a segmented line (Bresenham alg) around a bezier curve. If we choose really low values of CurveResolutionPercent then it will be a nearly perfect curve but also based on what the hardware can handle.

With this, you could also pass it to the same stepper code because from your current point, to the next point on the bezier curve you have a simple segment / line and the same code we have now could handle stepping it.

Ill see how far I can get with this and let you guys know.

this pdf is an interesting read, especially page 15

---

-----------------------------------------------
Wooden Mendel
Teacup Firmware

Quote

I have yet to be able to easily explain issues with acceleration on ball/screw to people. If using a stepper on x and y axis at high speed, something will just not work with the current Bresenham setup

Why? I use ball screws on HydraRaptor and I use a Bresenham algorithm with acceleration up to 80mm/s. What is the issue?

---

[www.hydraraptor.blogspot.com]

Triffid_Hunter Wrote:
-------------------------------------------------------
> this pdf is an interesting read, especially page
> 15


What you need to bear in mind when applying graphics algorithms to motion is that we want constant and known velocity along the path. This isn't a consideration for graphics plotting pixels. The Bresenham line algorithm has a constant velocity along the axis that moves the furthest. Fortunately it is easy to compensate for that with Pythogoras. I am not sure about circles and curves though.

---

[www.hydraraptor.blogspot.com]

Bresenham in its current implementation averages out errors. Threshold is reached above 0.5 then an extra step is added.
it works OK on systems designed to start and stop fast without acceleration. nophead you have something special. If you say there is no issue, then there probably is nothing of an issue.

We need to replace Bresenham eventually. I don't want to get to far off subject here.


I am concerned that averaging out steps while curving and using acceleration will cause the motor to stall and miss steps. This may not be an issue as by the time a curve is in process the line segment leading to it should have slowed back down to a speed that the motor can compensate inertia forces. I would probably state that if using corner acceleration slow down the start speed for the curve slightly. it still will be faster than stopping and starting the next line.

Edited 2 time(s). Last edit at 06/07/2011 04:10PM by jamesdanielv.