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

Re: Fast lines

WolfWings ShadowFlight wrote:
> 
> On Wed, 8 Jul 1998, James A Simmons wrote:
> 
> >Why does anyone use floting point. I have created line drawing algorthims
> >that used floating point. On most ix86 and RISC this is much faster. Also
> >you don't have to woory about which quadrant the line is in.
> 
> Okay, this needs to be said:
> We've hashed, and rehashed the line-drawing algo discussion too many times
> already, the existing implementation is best overall for _ALL_
> architectures. Yes, it flat-out sucks on some, but overall, it's the best
> one that was agreed upon. Floating-point, straight bressenham, all have
> been brought up before, and on many arch's they're better than the current
> one, but not on all architectures GGI runs on currently, like the piddly
> little 386/16 behind me, or the 486/7Mhz to my right. (286 I ripped apart
> and plugged one of those illicit 486 upgrade chip boards into. :-)
> 

Why bother optimizing for these ancient machines anyway.

> On these, the FPU simply doesn't exist, so floating-point algo's are out,
> and fixed-point is in the same boat as the shifts can murder the speed,

Shifts aren't necessary in the fixed-point inner loop.
You could either use use a if, or maybe use the special x86 instruction
that sign extends a number to twice the width.

On the Y-major lines it is possible to use the carry bit, which 
simplifies things.

> while the run-length bresenham works best, as it can take advantage of the
> REP STOSx, and also it can be a simple 2-line loop at the innermost layer
> most of the time, which is very good for these older machines.
> 
> Then, there's the P200MMX I'm sitting at now. Heh. :-)
> FPU is just great, but not that great.
> Fixed-point can be good if you abuse the MMX just right.
> Sliced-bresenham is still king though, due to the great loop prediction
> the CPU has, so again, at the low and high end of the x86
> spectrum, the sliced-bresenham is best due to the ultra-tight nature of
> the inner loops.
> 
> Then, there's the P2 series... Anything works there, end of discussion.
> 
> The original Pentiums... well, that's pretty much a 486 in disguise,
> really, aside from the beefed-up FPU. The jump prediction has a fatal set
> of flaws, so it's useless, etc, etc. In fact, this is the only chip where
> a 2-3 line innermost loop is a _bad_ thing as it hits the jump prediction
> too often. Yes, the jump prediction in an original Pentium can't be beaten
> on rapid-fire. :-)
>              _

Have you got any numbers for those processors.

On the machines that I have tested (Pentium,MIPS R4600, R5000, R10000,
microsparc)
both of my straight bresenham algoritms were faster than a sliced
bresenham.
The fixed-point algotitm was fast too, especially on the longer lines.

PS The x86 architecture sucks, because it has too few registers,
   so it isn't possible for the compiler to unroll the loops.