Path: utzoo!mnetor!uunet!seismo!sundc!hqda-ai!yendor!gmg
From: gmg@yendor.UUCP (Gary Godfrey)
Newsgroups: comp.graphics
Subject: Re: Line Drawing Algorithms
Message-ID: <51@yendor.UUCP>
Date: 2 Jan 88 04:18:32 GMT
References: <174@nucleus.UUCP>
Organization: Applied Computing Technology, Reston, VA
Lines: 80

in article <174@nucleus.UUCP>, hacker@nucleus.UUCP (Thomas Hacker) says:
> 
> 
>    I'm working on a project that requires a very "quick" line drawing 
> algorithm (i.e. Draw (x1, y1, x2, y2)).  The fastest I know of is 
> Bresenham's algorithm, which is a DDA using integer arithmatic 
> instead of float.  If anyone knows of a superior algorithm, please
> let me know.
> 
> 		Thank You
> 
>     		   Thomas Hacker
>  		   Academic Computer Services
> 		   Oakland University

I'm not sure what DDA stands for, but the following is a short 'C' fragment
that will draw a line.  To make it easier to write, I'm going to assume
that x1<x2, y1<y2, and (x2-x1) > (y2-y1).  If you want to be fast but
code inefficient, you can write eight different routines for the eight
different types.  I usually use two: one for dx > dy, and another for
dy > dx.

draw (x1, y1, x2, y2)
int x1,y1,x2,y2;
{
int	tmp,dy,dx;

	dy = y2 - y1;			/* change in y */
	dx = x2 - x1;			/* change in x */
	tmp = dy / 2;			/* kind of a  running total.  the
					   "/2" should make the line
					   symmetrical */

	for (; x2 > x1 ; x1++) {
		plot(x1,y1);		/* standard plot */

		tmp+=dy;
		if (tmp >= dx) {
			tmp-=dx;
			y1++;
		}
	}
}


I'm writing this off the top of my head.  If it doesn't work, it's at
least fairly close.  I think.  Another thing you might want to consider
if you're working close to the hardware, is to mix the plot calculation
routines into the line drawing routine.  For instance, if your screen has
1024 pixels across, and one bit/pixel, the calculation for the memory
location/plotting is:

mem = VIDEO_RAM_OFFSET + y * 128 + (x / 8);
bit = 2 ^ (x & 3);
*mem |= bit;			/* assume set bit = pixel on */

Kind of a bad way of doing things.  However, instead of doing this calculation
every time for every pixel, you can initialize mem and bit before entering
the line drawing loop.  Then, inside the loop, you replace the y++ with
mem+=128, and the x++ with:

bit/=2;			/* shift right -- assume highest bit is leftmost */
if (! bit) {		/* if the bit disappeared */
	bit = 128;	/* set back to leftmost */
	mem++;		/* and move memory over... */
}


I NEEDED to do this on my old TRS-80 to get any speed at all.  It required
a division by three and two multiplys for every pixel!  More fun this way
anyway.


=============================================================================
You know, if I had a dime for every time I heard the word "the", I
would have an awful lot of dimes.


Gary Godfrey - ACT, Reston, VA			Phone:		(703)471-9433
UUCP: ..!mimsy!{prometheus,hqda-ai}!yendor!gmg