3D Bresenham's Line for 3D printers and CNC's
davidsaunders
Posts: 1,559
I have not yet tested this, though I am providing here a simple implementation of the Bresenham Line Drawing Algorithm for CNC and 3D printer type devices, I hope that it helps someone.
This works by doing a 2D X,Y implementation of Bresenham's Line, while using either X,Z (if X > Y) or Y,Z Bresenham's Line to calculate the Z axis change. Pretty simple, and in retrospect pretty obvious.
It does not handle the edge cases where the start and end value are equal, and that could cause a divide by 0, so it needs to be handled.
This works by doing a 2D X,Y implementation of Bresenham's Line, while using either X,Z (if X > Y) or Y,Z Bresenham's Line to calculate the Z axis change. Pretty simple, and in retrospect pretty obvious.
It does not handle the edge cases where the start and end value are equal, and that could cause a divide by 0, so it needs to be handled.
long OldX, OldY, OldZ;
void MvX(long d); //Used to move d distance in the X axis.
void MvY(long d); //Used to move d distance in the Y axis.
void MvZ(long d); //Used to move d distance in the Z axis.
long ABS(long v){
return (v < 0) ? -v : v;
}
long LineTo3D(long x,long y,long z){
long DX,DY,DZ;
long SX,SY,SZ
long ERR, ERR2, E, E2
DX = ABS(OldX - x); SX = (x == OldX) ? 0 : ((OldX < x) ? 1 : -1);
DY = ABS(OldY - Y); SY = (y == OldY) ? 0 : ((OLDY < y) ? 1 : -1);
DZ = ABS(OldZ - Z); SZ = (z == OldZ) ? 0 : ((OLDZ < z) ? 1 : -1);
if(DX > DY){
ERR = DX / 2;
ERR2 = ((DX > DZ) ? DX / 2 : (-DX) / 2;
} else {
ERR = (-DX) / 2;
ERR2 = ((DY > DZ) ? DY / 2 : (-DY) / 2;
}
while (OldX != x && OldY != Y && OldZ != z){
E = ERR;
if (E > (-DX)) { ERR -= DX; OldX += SX;MvX(SX)}
if (E < DY) {ERR += DX; OldY += SY; MvY(SY)}
if (DX > DY){
E2 = ERR2;
if (E2 > (-DX)) ERR2 -= DX;
if (E2 < DZ) {ERR2 += DX; OldZ += SZ; MvZ(SZ);}
} else {
E2 = ERR2;
if (E2 > (-DY)) ERR2 -= DY;
if (E2 < DZ) {ERR2 += DY; OldZ += SZ; MvZ(SZ);}
}
}
}
Comments
Now for the hard part...
Implement ramping based upon achievable speed of the various axes and the fastest axis
In my opinion, that will be the toughest job for both of us. I hope you beat me to it, because I am not looking forward to it
I have already been playing with some ideas for simple linear ramping, though inverse exponential ramping will be a bit more of a challenge, then there are a few other schemes that are often used, ouch.
I think that for mine I will likely stick to simple linear ramping, at least for the first few releases.
That is the route I will be taking. If someone wants something different, they can always write their own
One important thing to keep in mind, is that each axis of each machine will be different. The ramp incrementor/decrementor MUST be user configurable!!!!!!
EDIT: Although I suppose that would all depend on the size of the increment or decrement.
static long LineTo(long x,long y,long z){ long DX,DY,DZ; long SX,SY,SZ; long ERR, ERR2, E, E2; DX = ABS(OldX - x); SX = (x == OldX) ? 0 : ((OldX < x) ? 1 : -1); DY = ABS(OldY - y); SY = (y == OldY) ? 0 : ((OldY < y) ? 1 : -1); DZ = ABS(OldZ - z); SZ = (z == OldZ) ? 0 : ((OldZ < z) ? 1 : -1); if(DX > DY){ ERR = DX / 2; ERR2 = ((DX > DZ) ? DX / 2 : (-DX) / 2); } else { ERR = (-DX) / 2; ERR2 = ((DY > DZ) ? DY / 2 : (-DY) / 2); } while (OldX != x && OldY != y && OldZ != z){ E = ERR; if (E > (-DX)) { ERR -= DX; OldX += SX;MvX(SX);} if (E < DY) {ERR += DX; OldY += SY; MvY(SY);} if (DX > DY){ E2 = ERR2; if (E2 > (-DX)) ERR2 -= DX; if (E2 < DZ) {ERR2 += DX; OldZ += SZ; MvZ(SZ);} } else { E2 = ERR2; if (E2 > (-DY)) ERR2 -= DY; if (E2 < DZ) {ERR2 += DY; OldZ += SZ; MvZ(SZ);} } } }I'm just wondering because I've never seen my Printrbot move the "Z" axis with any other axis.
Maybe it's just Pronterface that does that ???
Bean
Z is the Z axis
E is the Extruder
Teacup documentation states that it is unusual for Z to move at the same time as X and Y, but just in case, they provide the code for it. I am not sure if CNC routers or mills move Z during X and Y movement, but I would assume that some of them do for inclines.
And to add to that is the 4th axis, where a chuck or vise rotates the workpiece while the 3 linear axes dance around those surfaces. We expect to be implemnting this on one of our mills in the next few weeks. Seems quite complicated to me, but will be a great feature to have. I should try to make some videos once that is up and running.
Cheers,
Peter (pjv)
Some printer only move it separately, though moving it along with the X and Y makes it possible to compensate for bed level (so you do not have to spend so much time tweaking the leveling screws).
Having differing rates of acceleration could be a huge problem in keeping step between 3 axis, and that could take a lot of code, as well as some buffering. I guess you could always just match all that are being used to the slowest acceleration rate of the 3. though there are 4 not three (the X,Y,Z speed will make a difference on the feed rate for the extruder to make for consistent lay down rates).
It is a difficult problem to say the least.
That's more undesirable, generally, than simply getting the table right is.
See attachment to this post.
Ramping isn't so hard if you don't want to tweak the last few percent of perfomance out of a system.
usually it is done through pre-calculating time-values into an array. If the maximum-frequency of the
step-pulses isn't too high you can do the timing-calculations on the fly.
For example 100 values until highest speed is reached.
Then the method that generates the step-pulses uses the time-values of the array.
Below a raw sketch of what I remember about the coding as pseudo-code:
MinTime := 1 / MaxSpeed MaxRamp := 100 for i := 1 to NrOfPulses / 2 'first half Pulse High WaitPulselength Pulse Low if i < MaxRamp WaitUntilNextPulse(WaitTime[i]) 'ramp up else WaitUntilNextPulse(MinTime) 'MaxSpeed for i := NrOfPulses / 2 downto 1 'second half Pulse High WaitPulselength Pulse Low if (NrOfPulses - i) < MaxRamp WaitUntilNextPulse(WaitTime[i]) 'ramp down else WaitUntilNextPulse(MinTime) 'max speedbest regards
Stefan
Thanks for sharing that document.
But is the issue of ramping (acceleration/deceleration) not a specific requirement of the path speed, regardless of what combination of axes are used? Perhaps with 3D printing the requirements are less demanding, but certainly for general CNC use such as milling, it is the tool's path that needs to be traversed at a specified speed.... not just a specific axis. And for those purposes this needs to be calculated on the fly, and each of the 3 (or 4) axes accelerated/decelerated accordingly so the net *path* speed is the correct value.
I would think it to be a real bear to control each axis in this manner if they were all in separate cogs; at least if one is trying to do that accurately. I would see a master "path ramping" calculation being done in a cog or SPIN, and that handed to a single motion cog which then calculates stepping rates for each axis accordingly.
If accuracy of path speed is deemed not important -perhaps the case in 3D printing- then ramping of the fastest axis would be a much simpler solution.
Anyhow, just some of my thoughts on implementing this.
Cheers,
Peter (pjv)
whenever the bresenham-algorithm is used the slower axles follow at the right speed-ratio.
Bresenham is based on creating step-pulses at the right ratio. With the Bresenham-algorithm only one cog creates the step-pulses for all axles.
This keeps the axles automatically in sync.
Example: Start at 0,0 drive to 300,100. With the Bresenham-algorithm this means every third step-pulse of the X-axle the Y-axle gets one pulse.
This means the slower-pulserate of the Y-axle is generated always as a fraction of the fastest axle.
Disadvantage of the Bresenham-algorithm is some jitter as f.e. at a X/Y Ratio of 2/3 the steppermotor
of slower axle gets a step-pulse every 1-2-1-2 step-pulses of the x-axle.
something like that
XX Y X Y XX YIf you want high-performance including constant toolpath-velocity I think it is easier to buy an off-the-shelf-solution.
As I mentioned earlier ManAtWork made some democode that works different.
For any given X/Y/Z-ratio the real and exact frequencies are calculated and a cog for each axle
creates the step-pulses through the counter-modules. The cogs start synchronised so everything is fine.
As a second step a PC-Software translates all G-Code-Commands into small 1millisecond-equivalent vectors to drive the axles
see this thread http://forums.parallax.com/showthread.php/142705-Step-Dir-signal-generator-for-CNC
best regards
Stefan
Now if the step rate is closer to the resolution I could see the issue of the surfaces becoming non-smooth in response to the bresenham algorithm. Though I see no reason to go with fewer steps per minimal unit (0.05mm in this case, which is 20.2 steps), unless speed is important enough to sacrifice quality (I would think that the minimum would be 10 steps per minimum resolution of the printer, for best quality, same for CNC).
As to helical paths, that would be interesting. I have been thinking about eventually adding a G2 and G3 to the supported commands, though that is neither here nor there at the moment.
Since many of the commercially available 3D printers use this method of compensating for bed level, it is logical to assume that the printing resolution is high enough to not create any noticeable artifacts.
Repeatability to .003" is likely to be acceptable for most cases.
Even .001" adds up quickly though.
It is not precision that is primary on operations that build on on another, or cut away, for that matter. It is also feature size.
For mill, a repeatability of .0002" is fine for a .040" mill, and it is a problem or worry to be careful of on a .017" mill.
And with a movement rate of aproximately 2.1 micrometers per step, the bresenham line algorithm should be good enough for any common CNC application, even with the directional jitter. I may be wrong, it would not be a first.
Stefan;
I was talking about the general CNC case which includes a lot of circular interpolation, and what you say will not work for that. The speeds of each axis vary as the circle is traced. Helical interpolation (linear) typically adds a constant velocity vertical vector, The machine I am building is targeted to have 3 axis simultaneous, possibly 4 if I get that far.
As for buying solutions, I have done that for heavy duty 4 axis milling, but am still working on a desk-top commercial product for sale..... driven by a propeller. Hence my interest in not buying the solution for that, as then I would just become a salesman for someone else, and that is not my goal.
Cheers,
Peter (pjv)
sign me up for one
Yes, there is no perfect, humans or not. Just acceptable levels of error.
In the case of a human table alignment, it is one error. As long as that error is not too large, the model impact is minimal. A human can position the table to a couple thousandths maybe a few consistently, assuming basic tools. With good tools, such as a micrometer with probe, much better repeatability can be expected.
From there, a 2D movement will not add any more error.
In the case of compensating for the table, there is the problem of matching the transform needed to the physical orientation of the table, and there are now three axis of motion for all the motions needed.
Repeatability in the Z will need to be very good to achieve a result comparable to a 2D solution and aligned table.
How does that transform get found?
A human measurement may in fact have more error as the transform is poorly aligned to the table. Or maybe probing makes sense. Z repeatability will need to be very good, not just precise.
In general, limiting axis of movement will improve the overall performance over what the same movements will look like when more axis are needed to move in a non orthogonal orientation.
Just a few move, print, move cycles could accumulate enough error to show artifacts.
There is the software, and there is mechanical considerations.
In the 2D scenario, Z will basically step one direction until done.
In the compensation scenario, Z will move a lot, and where that back and forth happens, repeatability will be impacted by mechanical slop in addition to whatever basic error is there. In particular, be sure and evaluate what happens when back and forth Z movement distances are in the range of mechanical slop.
All of this may be ignored with a large material bead size, and or overall accuracy and stability of the machine structure too.
A .030" bead and say .002 to .005" Z step is very different from a .010" bead and .0015" step.
The latter would easily show artifacts from the kinds of error discussed here, where the former wont, but us also coarse enough for table alignment issues to be easily managed too.
TL;DR version the effort for 3d concurrent moves may not yield a good return
Though I personally can deal with the slight loss do to the small inconsistencies of human measurement. I put 3 sheets of 20lb paper on the print bed, and make sure that the tip of the extruder just barely touches the paper all the way across the print bed in all directions with out moving the Z-Axis at all, that is a touch so light that you can tell it is touching, though it does not disturb the paper.
Though I want this to end up being a 3D printer that is both low cost, and is one people want to have. I am attempting to provide a way for some people, that can do the most basic mechanical and electronics build, to be able to have a 3D printer, even if they otherwise would not be able to afford a good enough one (like me, the $150 is the upper limit of my price range, and do to the modifications I have made over time to make it better and easier to build, I have spent a total of $215, ouch).
Z probe would be cool.