NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/alt/sys/amiga/demos/1144

Internet Message Format | 1992-09-14 | 1.6 KB

Path: sparky!uunet!mcsun!corton!loria!loria.crin.fr!eker
From: [e-mail] (Steven Eker)
Newsgroups: alt.sys.amiga.demos
Subject: Re: Drawing lines
Message-ID: <[e-mail]>
Date: 14 Sep 92 08:37:01 GMT
References: <umage.715709408@mcl>
Sender: [e-mail]
Organization: CRIN (CNRS) Nancy - INRIA Lorraine
Lines: 27

In article <umage.715709408@mcl>, [e-mail] (androgyny) writes:
|> Yea me, the novitiate programmer again.
|> OK, i know the blitter will draw lines, but i wanted to try my hand at
|> writing a straight lin edrawer myself.  And now i want to compare with
|> folks here.  Keep in mind i've never had any teaching or theory in this,
|> and i've got a routine which requires 2 divides at the beginning of each
|> line, and from then on is simple adds and checks. (about 2 to 5 per pixel,
|> excluding actually drawing the pixel in ram)  How does this measure up?

Very badly... The algorithm you want is called "Bresenham's Algorithm"
which requires 2 adds & 1 subtract at the beginning of each line
and two adds & a test per pixel. You can actually unwind BA into spagetti
code to avoid the loop (with its test) bringing the cost down to just
3 68k instructions (16cy) /pixel (not including screen accesses).

This might still be to slow for some purposes in which case you want a
more complicated beast called "Bresenham's scanline algorithm" which
lets you draw whole runs of pixels with the same y coordinate in a single
instruction.

Both these algorithms generate the "optimal" line - no cumulative rounding errors.

|> Should i think some more ? ( Of course i should! )

Definitely.

Steven