Faster Line Drawing

[Julian Skidmore]

Hi guys,

Although I haven't tested any of this yet - fool that I am ;-) - I've just realized we can speed up line drawing quite a bit!

The previous line drawing code used an 8:8 fixed point algorithm for generating the new points of a line - it's not terribly accurate and it turns out it's slower than it needs to be. The key part of a line drawing algorithm is adding the fraction representing the gradient to the coordinate on the minor axis. For example, if we draw 12,4 then we want to move up a pixel for every 3 pixels we move along.

There's a simpler way to generate that behaviour in FIGnition Forth. Consider this routine:

: drawRight ( yFrac y0 xEnd xStart dy --)

  dup do ( dy is in i and i' now)

    do ( only 0 y0 is on the stack now)

       r 0 d+ ( [yFrac y0] d+ [dy y0] => yFrac' y0')
       i over plot ( \ x y0' \)

    loop

    leave ( forces loop to quit)

  loop

  drop drop

;

The central loop only needs 5 simple instructions + plot vs 26 + plot on the examples page:

https://sites.google.com/site/libby8dev/fignition/examples#lines

The main drawing loop for turtle graphics needs 15 + plot instructions:

: fd ( dist--)
  >r dx @ x @ y @ dy @
  r 0 do
    >r r + >r over +
    dup 8 >> r 8 >> plot
    r> r>
  loop
  drop y ! x ! drop
  r> drop
;

The new performance can be estimated as 2.5*5+23us (plot) +12us (loop) = 42.5us vs 2.5*26+23us + 12us = 100us for the normal plot routine. Or 2.5*15+23us+12us = 72.5us.

I.e. 70% faster for turtle graphics or 135% faster for the given routine. The setup would be a bit more complex though.... I haven't worked that out yet.

-cheers from Julz

--
                             
                  The DIY 8-bit computer from nichemachines™