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