Index:
[thread]
[date]
[subject]
[author]
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 ?
Index:
[thread]
[date]
[subject]
[author]