From: Jon M. Taylor <taylorj@ecs.csus.edu>
  To  : ggi-develop@eskimo.com
  Date: Wed, 8 Jul 1998 18:53:06 -0700 (PDT)

Re: Fast lines

On Wed, 8 Jul 1998, Frank W. Miller 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. 
> > 
> 
> You could use a Cray and I still don't think you'd be able to beat
> Bresenham.  Its just plain the fastest there is.

	The fastest linedrawing/clipping routine possible uses the x and y
coordinates of the two endpoints of the line and two corners of the
clipping region as offsets into a sparse precalculated array of x,y pairs
stored as offsets into a linear framebuffer + one extra entry at the
beginning for the number of pixels in the line, making up all possible
lines.  For a 320x200x8bpp framebuffer, this would require ~3.5 heptabytes
of RAM, but the computational cost is: 

Setup:
* One memory read + one register write to set the pixel color
* three multiplies to get the array offset 
* One menory read + one register write to set the pixel count

Pixel-setting loop:
* One memory read + one register write to get the address of the next pixel
* One register read + one memory write to set the pixel at that address 
  with the value in the pixel color register
* One decrement-and-branch-if-not zero instruction that tests the pixel 
* count register

	No compares, multiplies, or adds in the loop at all!  If your
processor can do indirect writes with the offset coming from memory
without additional cycle cost, that loop reduces to one indirected write
and the conditional branch.  A good pipeline will reduce this loop to ONE
CYCLE per pixel.  Beat *that*! |->

Jon

---
'Cloning and the reprogramming of DNA is the first serious step in 
becoming one with God.'
	- Scientist G. Richard Seed