Hi folks,


	I have seen a lot of slow and unoptimized line drawing routines,
in a lot of places, and not being happy with the performance of any of
them I decide to write my own. The following is a comparison between my
algorithm and the Bresenham.


Disadvantages of Bresenham algorithm
────────────────────────────────────

1) It uses too many registers in the line inner loop.
   deltaX, deltaY, Accumulator, errorTerm, directionX, directionY, counter...

2) It requires additions, subractions and comparisons in the inner loop.

3) It is kind of slow...


	Well, I develop a line drawing algorithm that has the fastest
possible inner loop for the 80x86 family. Yes, it is faster than the
Bresenham. The only requirement is one unsigned integer division, I know
it takes 40 clocks cycle on 486, and it's awful slow, but it's very
important to find the slope of the line. I also know that the Bresenhan
algorithm does not use any divison, so I agree that at setup time, I lost
for the Bresenham.
	But, do not forget, the setup is done only once, and then we
go to the line inner loop to draw all the pixels. At the line inner loop
my algorithm is about 2.0 to 2.5 times faster than the Bresenham. And
that is what is important. The most used part of the line routine is the
fastest part.


	The performance of the Minnitti's line inner loop
	─────────────────────────────────────────────────

line_xyseg:	mov	[di],al 		; 1   486 cycles
line_xyinc:	add	di,0FF00h		; 1
line_xyloop:	add	si,0FF00h		; 1
		jnc	line_xyseg		; 3,1
						; ──────────────
						; 6 cycles
line_yxinc:	add	di,0FF00h		; 1
		sub	esi,10000h		; 1 (forget about 66h prefix)
		jnc	line_xyseg		; 3,1
						; ──────────────
						; 9 cycles

	The inner loop takes 6 cycles for each pixel that moves
horizontally or vertically, and 9 cycles of each pixel that moves in the
diagonal. For example:

	   x1  y1    x2  y2
	 (100,100) (149,100)   To draw 50 horizontal pixels from x1=100 to
			       x2=149, we have:  50*6 = 300 cycles

	 (100,100) (100,149)   50 pixels vertically, 50*6 = 300 cycles

	 (100,100) (149,149)   50 pixels in diagonal, 50*9 = 450 cycles

	 (100,100) (149,104)   45 pixels horizontally, 5 pixels in diagonal
			       45*6 + 5*9 = 315 cycles

	Enyoy the savings... Use this line drawing routine in any
commercial, shareware or freeware application that you like.

	Thank you for your time reading this doc,


	Celso Minnitti Junior
	139 Linden St
	Wellesley, MA 02181
	phone: 617-235-4018
	email: celsomj@world.std.com