Re: A83: Re: line drawing algorithm


[Prev][Next][Index][Thread]

Re: A83: Re: line drawing algorithm




Actually, calculating the slope of a line before drawing it is not
necessarily bad.  There are two accepted algorithms for drawing lines using
only integers.  Both (I believe) were first invented by Bresenham at IBM in
the 60' (1965?).  The first algorithm that is the most widely known is
generally termed "Bresenham's Algorithm" (he also came up with a nice circle
algorithm).  It works by keeping an error term and using that determine
where the next pixel should be, relative to the "true line".  This routine
actually has many uses besides drawing lines.  It is applicable in most
situations where specific values are needed when the value is determined by
a fixed non-integral value.

Another line drawing algorithm that was written about in one of Michael
Abrash's articles is Bresenham's run-sliced algorithm.  If you look at the
lines drawn by the first algorithm, you will notice that all of the segments
are of two lengths, say three or four pixels.  So instead of calculating the
slope as you go by using the error term, the exact slope and lengths of the
line segments can be precalculated, thus allowing the line to be drawn
faster.  The segments at the beginning and end of the line will not
necessarily be full and will have to be adjusted.  This algorithm is
generally faster on lines that have at least 80-100 pixels, and slower on
shorter lines.  Thus on the z80 calcs, that have a small screen, it is
probably more efficient to use the first algorithm.

> I think part of the reason Harper's is slower than mine is that he
actually
> calculates the slope, which requires (relativly) slow division and more
> complicated increments.





References: