From: Martin Eli Erhardsen <mee@daimi.aau.dk>
  To  : ggi-develop@eskimo.com
  Date: Thu, 09 Jul 1998 00:46:17 +0200

Re: Fast lines

Alexander Larsson wrote:
> 
> > Why are the linear targets using the sliced runlength bresenham
> > linedrawing algoritm, when a straight bresenham linedraw is
> > faster and much simpler.
> >
> I did the sliced bresenham implementation. It was generally quite a bit faster
> than the previous bresenham version (measured on a 486 100MHz). It got a bit
> slower when i did the pixel-perfect clipping though, that code is *not* nice...

Did the previous bresenham algoritm have completely inlined putpixels.
If it did putpixel function calls, which clip each pixel, it should be really slow.

> 
> The speed issue is quite complex i think. The sliced version should be faster
> for longer lines, but has larger setup time. It should also be faster on lines
> that are near horizontal or vertical, and at pure diagonal it degenerates and
> draws just spans of one pixel (special-cased in this code).
> Another factor is the memory bandwidth vs cpu speed for a fast machine it can
> fill up the memory bandwidth with the 'slower' brezenham code too, and thus
> the difference will not be noticed.

I noticed that too when comparing bersenham and fixedpoint algoritms on
my Pentium.
Because of this I used a 128x128 array of main memory instead of vga memory 
to get the largest possible speed difference.

> Cache size matters too, as the smaller brezenham might fit better in the cache.
> 

8k instruction cache should be enough for the sliced bresenham,
but I don't know about associotivity though.

By the way I tried it out on a R5000 too, and there the bresenham
with the if's instead of the complicated logical expression is
faster. The same thing happens on a pentium.

On a R4600 or a microsparc both have approximately same speed;

The R10000 can execute two integer instructions per cycle, 
and it has enough registers to unroll the whole thing so it can
execute a lot of logical instructions, while the if's limit the 
parallelism achievable and slow everything down.
I expect that the same thing would happen on a alpha.

Is there any preprocessor sumbol, which I can test to see if the CPU
is superscalar, so I can select the right version ?

> > I think that a fixedpoint linedrawing algoritm could be
> > a good idea too, but it requires an extra division compared
> > with bresenham, and the decision variable must be
> > twice as wide for the same precision.
>  Fixedpoint is a bit unnice as it has finite precision. The bresenham algo
> always draws the right pixels. a fixedpoint algo gets it wrong for large lines.
> 

Not if you have enough precision. I think that you need a little more
than twice as many bits though.

>  This is the X-target, which is in main memory. Try it on a 486 with the kgi
> target, vga memory behaves differently. Might give another view... I don't
> have ggi installed right now. But you better do some more testing before you
> change algorithms to make sure it really is faster.

I too don't have a 486 with ggi, because I gave mine away. 
How fast is Vesa Local Bus anyway compared with PCI ?