Faster, More accurate Line Drawing!

[Julian Skidmore]

Hi folks,

Thanks to the new double-number commands in Firmware 1.0.x, it's possible to write faster, more accurate line drawing on FIGnition :-)

Here's the code:

: qLine ( DX DY X Y n)

  0 do

    d>r d>r ( DX DY : X Y)

    2over dr> d+ ( DX DY X' : Y)

    2over dr> d+ ( DX DY X' Y')

    swap >r 2dup plot ( .. Xl Xh Yh /Xh Yh/ : Yl)

    r> swap ( .. Xl Xh Yl Yh)

  loop

  2drop 2drop

  2drop 2drop

;

: /line ( dx dy max)

  swap ( dx max dy )

  0< 1 or d>r ( dx : max -1|1 )

  $8000 swap dup abs ( $8000 dx |dx| : max -1|1 )

  swap r> swap >r ( $8000 |dx| max : dx -1|1)

  u/ swap drop 0 ( FX : dx -1|1)

  r> d+- 0 r> ( DX : -1|1)

; ( -- DX DY)

: line ( x y dx dy)

  2swap 2dup plot d>r ( dx dy : x y)

  over abs over abs ( dx dy |dx| |dy| : x y)

  over max >r r - if ( dx dy : max x y)

    r /line ( DX DY : max x y)

  else

    swap r /line 2swap ( DX DY : max x y)

  then ( WH:nxy)

  r> 0 swap r> swap ( WH 0 x n : y)

  0 swap r> swap qline ( WH 0 x 0 y n )

;

I think this should draw lines at over 10K points/s on PAL video (slower on NTSC) and will work in all video modes and all plot modes :-) 

The reason it's both faster and more accurate is because, although line drawing on FIGnition uses fractions to increment along the minor axis, in the old code we used 8-bit pixels + an 8-bit fraction all in one 16-bit value. So, 8-bit fractions weren't that accurate and extracting the whole number part slowed it down a lot. This time we can use 16 bits for both parts!

Check it out!

-cheers from Julz

--
                             
                  The DIY 8-bit computer from nichemachines™

[Julian Skidmore]

Comparing it with the old code (again):

: linePlot
  0 do 2dup >r >r
    rot  + >r + r>
    2dup 8 >> swap 8 >>
    swap plot r> r>
  loop
  drop drop drop drop ;

: >xp8 8 << ;
: xp8> 256 m* swap drop
 ;
: linePrep
  2dup abs swap abs max
  >r >xp8 r / swap >xp8
  r / swap >r >r >xp8
  128 + swap >xp8 128 +
  swap r> r> r> ;

: line ( x y dx dy )

  linePrep linePlot ;

This code takes about 80µs within the main loop, but loop and plot take this up to 107.5µs and 150µs respectively, a plot rate of 6.7Kpoints/second.

By comparison the inner loop of the new code should be about 45µs with loop and plot taking it to 72.5µs and 115µs respectively, a plot rate of 8.7Kpoints/second, a 30% improvement (estimated).

A ZX Spectrum draws lines at about 5100 pixels per second (but it does have to manage attributes too).

An Acorn Electron: 7.3-1.46 for 320 points per line x 100 lines in mono mode => 5.5Kpoints per second (doesn't have to manage attributes).

This puts FIGnition firmly in the 8-bit category for drawing performance, which is fine!

Slight correction for qline (to handle 0 length lines):

: qLine ( DX DY X Y n)

  ?dup if

    0 do

      d>r d>r ( DX DY : X Y)

      2over dr> d+ ( DX DY X' : Y)

      2over dr> d+ ( DX DY X' Y')

      swap >r 2dup plot ( .. Xl Xh Yh /Xh Yh/ : Yl)

      r> swap ( .. Xl Xh Yl Yh)

    loop

  then

  2drop 2drop

  2drop 2drop

;

-cheers from Julz

--
                             

[Julian Skidmore]

Hi folks,

Using a simple test program:

: tline

  1 vmode cls

  clock i@ >r

  0 do

    0 0 2over line

  loop

  clock i@

  0 vmode

  r> - .

;

It takes 20.26ms - 52ms for a 1000 lines of 159 pixels =>

This is for 159*1000/((1013-26)/50) => a score of 8.1K pixels per second, pretty close to my estimate.

Actually, I have a correction for the code (which didn't properly handle 45º lines):

: qLine ( DX DY X Y n)

  0 do

    d>r d>r ( DX DY : X Y)

    2over dr> d+ ( DX DY X' : Y)

    2over dr> d+ ( DX DY X' Y')

    swap >r 2dup plot ( .. Xl Xh Yh /Xh Yh/ : Yl)

    r> swap ( .. Xl Xh Yl Yh)

  loop

  2drop 2drop

  2drop 2drop

;

: /line ( dx dy max)

  swap 0< 1 or d>r ( dx : max -1|1 )

  $8000 swap dup abs ( $8000 dx |dx| : max -1|1 )

  dup r = if

   drop r> drop >r drop ( : dx -1|1)

   0 r> 0< 1 or

  else

    swap r> swap >r ( $8000 |dx| max : dx -1|1)

    u/ swap drop 0 ( FX : dx -1|1)

    r> d+-

  then

  0 r> ( DX : -1|1)

; ( -- DX DY)

: line ( x y dx dy)

  2swap 2dup plot d>r ( dx dy : x y)

  over abs over abs ( dx dy |dx| |dy| : x y)

  over max >r r - if ( dx dy : max x y)

    r /line ( DX DY : max x y)

  else

    swap r /line 2swap ( DX DY : max x y)

  then ( WH:nxy)

  r> 0 swap r> swap ( WH 0 x n : y)

  0 swap r> swap qline ( WH 0 x 0 y n )

;

-cheers from Julz