Line drawing...

[Virtual Cowboy]

Hi...
I'm looking for a fast way of drawing lines...
I made me a little Bresenham in asm, but it's still "slow" :)
Ok... it's fast... But is there a faster way of doing Lines ? (Mayber a
optimized version of Bresenham ??) Thx...
C'ya
--
___ -+- ____________________ __________________________________
\ \__ /\_____/_ ____________/ / / _______________/ ____ ______ \___
// / // / _ \// / / / _ // / // / /. / / / / __ \/. / / /
/ / / // / // / // / /__ / /__/ / / / / //__ / / /__ . /
\____/__/__/__/__/_____/__/__/_____/ \____/_____/________/_____/_____/_____/

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.3i

mQBtAzNbtlwAAAEDAOsilyHKFPvoEV0ZCb2jIiGChE1W1PNmR23qFeKA/qrwrWuU
uY7dkgRf+RetV8OT0G9wJCZE1eZt5LqLVhI5oOTd2w2cOBHz+HguVHNJ/sPQ5x6q
aC6heD2iT7dQ0YfMsQAFEbQdVmlydHVhbCBDb3dib3kgdmljdGhjQGlibS5uZXSJ
AHUDBRAzW7Zdok+3UNGHzLEBAd7nAv9A5HmpaHmX/ccQTZEALe3olMvMR5nw5+Y7
6kBHlWxFCVMbbXL+KPiuc0sa+pfoLJZpyDtPXPS+X4sgdneb6JIoL7kD1PIBamAE
nDay87lcUgHv36M0f03xomNNV6H+DEU=
=X+2D
-----END PGP PUBLIC KEY BLOCK-----

[Thomas Richter]

Virtual Cowboy <muf...@ibm.net> writes:

Howdy!

>Hi...
>I'm looking for a fast way of drawing lines...
>I made me a little Bresenham in asm, but it's still "slow" :)
>Ok... it's fast... But is there a faster way of doing Lines ? (Mayber a
>optimized version of Bresenham ??) Thx...
>C'ya

If you wanna draw these lines in ChipMem, the blitter is still fastest, of
course (I think even compared to a '60 since access to chipmem is slow).

But I know there's some modified bresenham that draws certain adjacent
horizontal pixels at once. Too bad I don't remember the details... It's BTW
used in the MAC "Quickdraw" routines.

Greetings,
Thomas

______________don't_cut_here,_it_could_damage_your_terminal____________________
_______ _____ _____
/ / / / / / / EMAIL: th...@einstein.math.tu-berlin.de
/ /____/ / / /____/
/ / / / / / \ http://www.math.tu-berlin.de/~thor/thor/index.html

/ / / /____/ / /

_______________________________________________________________________________

[David Virebayre]

Thomas Richter <th...@math.tu-berlin.de> a écrit dans l'article
<thor.86...@math.tu-berlin.de>...

> Virtual Cowboy <muf...@ibm.net> writes:
>
> Howdy!
>
> >Hi...
> >I'm looking for a fast way of drawing lines...
> >I made me a little Bresenham in asm, but it's still "slow" :)
> >Ok... it's fast... But is there a faster way of doing Lines ? (Mayber a
> >optimized version of Bresenham ??) Thx...
> >C'ya
>
> If you wanna draw these lines in ChipMem, the blitter is still fastest, of
> course (I think even compared to a '60 since access to chipmem is slow).
>
> But I know there's some modified bresenham that draws certain adjacent
> horizontal pixels at once. Too bad I don't remember the details... It's BTW

Here is a *ROUGH* idea for a horizontal line going from the left to the right,
so don't blame me please:

You can manage to be always going righ by sorting your points before drawing
the line. Remains 2 cases: the line goes down or up. You can handle then using
either 2 different routines or only one with a constant for the y dir.

let's say you have a line to draw from (xa,ya) to (xb,yb) xa<xb

1) you calc dx=xb-xa dy=abs(yb-ya) sgny=(yb-ya>0)?1:-1
2) if dx>dy you go for a horizontal line, else for a vertical one.

1) you calc p=dx/(dy+1) using fixed point arithmetic (important !).
2) st (span start) = xa
3) you loop dy+1 times doing:

a) se (span end) = st+p
b) draw (st-se) horizontal pixels at (st,ya)
c) st=se+1
d) ya=ya+sgny

Example draw (10,5) -> (106,10)

gives:
dx=96
dy=5
p=100/(5+1) = 16
st=10

step 1: ya=5 se= 10+16 = 26 draw horizontal span 10-26 line 5
step 2: ya=6 se= 26+16 = 42 draw horizontal span 27-42 line 6
step 3: ya=7 se= 42+16 = 58 draw horizontal span 43-58 line 7
step 4: ya=8 se= 58+16 = 74 draw horizontal span 59-74 line 8
step 5: ya=9 se= 74+16 = 90 draw horizontal span 75-90 line 9
step 6: ya=10 se= 90+16 = 106 draw horizontal span 91-106 line 10

When doing this for real do not use screen coordinates but try to use (bitmap
adress, start bit), to avoid calculating this for each point.

For small horizontal spans, I am not sure this algorith is better than
bresenham...

--

David
vi...@easynet.fr