Improvement on GcodeCNCDemo4axisV2

[Anonymous]

Hi to all,
I’ve been reading the source code of GcodeCNCDemo4AxisV2.ino because I’m developing
a CNC foam cutter based on Arduino Nano.
I’ve found that (sorry if I’m wrong) you can make more accurate the function line(), changing
the line:

if(a[j].over >= maxsteps) by
if(a[j].over >= 0.5*maxsteps)

Thus, the axis j will increment after pass the 0.5 and no the 1.
I’ve ported the code and I’ve tested. For example:

To draw a line from (0, 0) to (6, 1):
Original:
x, x, x, x, x, xy

Modified:
x, x, xy, x, x, x

I hope I’ve been clear.

Best regards, Mariano.

[Anonymous]

Also relevant: https://en.wikipedia.org/wiki/Bresenham’s_line_algorithm

[Anonymous]

In fact, I would use the equivalent expression:

if(2*a[j].over >= maxsteps)

which don’t use fractional numbers.

You can found the derivation of the algorithm on: http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

Regards, Mariano.

[Anonymous]

The algorithm explained in details:
Reference: http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

Naive form (Use fractional numbers)

e <- 0

y <- y1

m <- dy/dx



for x <- x1 to x2 do

plot(x, y)



if (e + m) < 0.5

e <- e + m

else

y <- y + 1

e <- e + m - 1

Discrete form
If we replace some expressions:

(1) If condition
e + m < 0.5
e + dy/dx < 0.5 Multiply both side by the positive number dx
dxe + dy < dx0.5 Multiply both side by 2 to remove the fractional 0.5
2dxe + 2dy < dx

e + m < 0.5 is equivalent to 2dxe + 2dy < dx

(2) Error accumulated
e <- e + m Replace m by its definition
e <- e + dy/dx
dxe <- dxe + dy

e <- e + m is equivalent to dxe <- dxe + dy

(3) Error updated
e <- e + m – 1
e <- e + dy/dx – 1
dxe <- dxe + dy – dx

e <- e + m – 1 is equivalent to dxe <- dxe + dy – dx

Replace dxe by e’:

If condition:
2dxe + 2dy < dx
2e’ + 2 dy < dx
2(e’ + dy) < dx

Error accumulated:
e <- e + m
e’ <- e' + dy

Error updated:
e <- e + m – 1
e’ <- e' + dy – dx

Error inicialization:
e <- 0
dxe <- 0
e’ <- 0

Updating (1), (2) and (3) on the algorithm:

e' <- 0

y <- y1



for x <- x1 to x2 do

plot(x, y)



if (2(e' + dy) < dx) < 0.5

e' <- e' + dy

else

y <- y + 1

e' <- e' + dy - dx

Is equivalent to:

e' <- 0

y <- y1



for x <- x1 to x2 do

plot(x, y)



e' <- e' + dy

if (2e' < dx)

(Do nothing e' was already updated.)

else

y <- y + 1

e' <- e' - dx

Is equivalent to:

e' <- 0

y <- y1



for x <- x1 to x2 do

plot(x, y)



e' <- e' + dy

if (not (2e' < dx))

y <- y + 1

e' <- e' - dx

Finally, is equivalent to:

e' <- 0

y <- y1



for x <- x1 to x2 do

plot(x, y)



e' <- e' + dy

if (2e' >= dx)

y <- y + 1

e' <- e' - dx

Which looks like the one implemented on function line().

[Anonymous]

yep. whole number math is much faster than fractional math, and with this algorithm is potentially more precise.

[Author]

Posts