Line drawing algorithm

[MrSterlingBS]

Dear all,

Do any of you have a very quick line drawing algorithm that you can share here?

The one I'm currently using is from the site https://retro64.altervista.org/blog/cat ... ogramming/
and probably not the fastest.
I would be very grateful for suggestions, tips and of course complete code.
With my knowledge I can't get it right.

[darkatx]

Mike has a pretty mean one with his Mini/Maxigrafik.

I have one myself but it's both convoluted and needlessly big but I was able to get it down to under 15 cycles per pixel on average?
Correction - I was way off closer to 70 cycles on average. Thanks Mike for clarifying.

Believe there is line code on here http://www.ffd2.com/fridge/chacking/
Mr. Judd had a pretty fast line drawing routine and that served as inspiration for taking it further when making my own.

Used to be some good ones on CSDB but it looks like they removed it

[Mike]

I was able to get it down to under 15 cycles per pixel on average?

That would imply your routine accesses/modifies each involved bitmap byte only once, i.e.:

• having LDA - ORA/EOR/AND #imm - STA present and inlined for all 36 possible horizontal line segments,
• removing all further address arithmetic by providing LDA ABS,Y and STA ABS,Y for all bitmap columns,
• unrolling the fast path of Bresenham (SBC/BCC),
• and yet, counting down the remaining pixels has to be done as well.

For line slopes with a magnitude less than 1, the Bresenham part of the algorithm is the limiting factor (5 cycles per step in the fast path, not including any necessary fix-up). With a slope magnitude of 1 or more, each step implies a bitmap byte access, i.e. 13..14 cycles per plot alone (including the implied INY or DEY).

[darkatx]

Nevermind, my memory is way off with my cycles and inner loops but Mike hit the nail on the head when I dug up the code.

[MrSterlingBS]

I use the line routine from Bitbreaker from codebase64.
https://codebase64.org/doku.php?id=base ... lgorithm_2

The results are very good.
Line x0,y0 to x1,y1 Cycles in total xxxx per pixel yy
00,00 to 99,00 5219 per pixel 52
00,00 to 00,99 5219 per pixel 52
00,00 to 99,99 5516 per pixel 39

Line-Cycle-Counter.zip

(3.9 KiB) Downloaded 14 times

Jumps and jumps back as well as the definition of the variables are taken into account.

The attached code can be run in VICE with 8k+.

[darkatx]

Codebase that's the place with the great tutorials sorry - glad you found it!

[Mike]

00,00 to 99,99 5516 per pixel 39

That should be 55 cycles/pixel.

You are improperly using the Euclidian distance here to pretend the line was 141 pixels long. The rasterization of lines with Bresenham plots max(dx,dy)+1 pixels, which is also 100 in the diagonal test case.

[MrSterlingBS]

Hi Mike,

of course, you are right. Thanks for the tip.

[MrSterlingBS]

Hi,

during my search of the best line algorithm i found this website.

Code: Select all

http://www.quiss.org/boo/

[Mike]

http://www.quiss.org/boo/

"BRR" is nothing new and effectively is an 8-bit 'randomized' DDA.

It is illusory to assume a line routine plots ~200000 pixels/second just because the 'deciding' part within it executes in 5 cycles. This is completely ignoring the other necessary parts of the routine that count the remaining pixels and do the actual pixel plots.

Furthermore, the 65xx (unfortunately) is missing a second accumulator register: at some point it is always necessary to swap out the deciding variable for the value being ORed/ANDed/EORed with the bitmap.

[MrSterlingBS]

… but the Demo is very impressive.

[Mike]

the Demo [...]

... uses overlapping sprites to render filled vectors on the C64 which is a method that does not transfer at all to the VIC-20 (again, that method is nothing spectacularly new. The demo "Snapshot" already did so in 2010, see the part at 7:14).

[MrSterlingBS]

I use the line routine from Bitbreaker from codebase64.
https://codebase64.org/doku.php?id=base ... lgorithm_2

The results are very good.
Line x0,y0 to x1,y1 Cycles in total xxxx per pixel yy
00,00 to 99,00 5219 per pixel 52
00,00 to 00,99 5219 per pixel 52
00,00 to 99,99 5516 per pixel 39Line-Cycle-Counter.zip

Jumps and jumps back as well as the definition of the variables are taken into account.

The attached code can be run in VICE with 8k+.

Hello,

I have adapted the code so that the two main loops are now stored in the zero page.

Here are the results.
Line x0,y0 to x1,y1 Cycles in total xxxx per pixel yy
00,00 to 99,00 4420 per pixel 44
00,00 to 00,99 4419 per pixel 44
00,00 to 99,99 4714 per pixel 47

Line-Cycle-Counter-ZP.zip

(3.78 KiB) Downloaded 14 times

[Mike]

Here's my take on this subject:

Before any questions come up in this regard: MINIGRAFIK already contains a line routine, which is not as fast as the routine below, however it is much more compact (just about 100 bytes extra beyond the pixel set function otherwise already provided within the MG code) and also more capable (also works for multi-colour and sets the colour RAM along as necessary). The speed of the built-in line routine, about 4000 pixels per second, is entirely sufficient within the context of a running BASIC program. You would not see any substantial speed difference with the faster line routine shown below, as the surrounding overhead of BASIC takes the majority of time spent.

That being said, here is an implementation of Bresenham very similar to MrSterlingBS's port of "Bitbreaker's" line routine. Unlike the latter, my implementation gets the rounding right, and it only needs one single main loop. That main loop is heavily "self-modified" to handle all 8 possible octants. The code itself is fairly compact (just 151 bytes), however it needs another 3x160 = 480 bytes of tables worth for table lookups of low bytes, high bytes and bit positions for each X co-ordinate. The routine is embedded into a small BASIC test rig, just decompress the *.zip file and drag the file "boot" into the main window of VICE with at least a +8K RAM expansion (download):

Code: Select all

10 POKE55,0:POKE56,60:CLR:FORT=15360TO15510:READA:POKET,A:NEXT
11 :
12 DATA 56,162,232,165,253,229,251,176,6,162,202,73,255,105,1,134,5,133,3,56,160,200
13 DATA 165,254,229,252,176,6,160,136,73,255,105,1,132,6,133,4,166,251,164,252,165,3
14 DATA 197,4,176,34,141,121,60,165,6,141,116,60,165,4,141,125,60,74,133,3,165,5,141
15 DATA 126,60,169,192,141,146,60,165,254,141,147,60,76,129,60,141,125,60,74,133,3,165
16 DATA 5,141,116,60,165,4,141,121,60,165,6,141,126,60,169,224,141,146,60,165,253,141
17 DATA 147,60,76,129,60,232,56,165,3,233,0,176,3,105,0,200,133,3,189,0,61,133,5,189,0
18 DATA 62,133,6,177,5,29,0,63,145,5,224,0,208,222,96
19 :
20 BI=128:FORX=0TO159
21 AD=4352+192*INT(X/8)
22 HI=INT(AD/256):LO=AD-256*HI
23 POKE15616+X,LO
24 POKE15872+X,HI
25 POKE16128+X,BI
26 BI=BI/2:IFBI<1THENBI=128
27 NEXT
28 :
29 @ON:@CLR
30 POKE251,RND(1)*160:REM X1
31 POKE252,RND(1)*192:REM Y1
32 POKE253,RND(1)*160:REM X2
33 POKE254,RND(1)*192:REM Y2
34 SYS15360
35 GETA$:IFA$=""THEN35
36 GOTO30

The tables are not contained in the DATA lines, but calculated and written by the loop in lines 20 to 27. They have been aligned on page starts to avoid the odd extra cycle on page-crossing accesses.

The routine approaches a speed of roughly 20000 pixels per second. Roughly 130 cycles are spent until the first pixel is plotted, all subsequent pixels then are drawn at about 51 cycles per pixel. The archive contains the source code.

...

I do have another implementation of Bresenham in hand, which approaches 30000 pixels per second, i.e. it is roughly 50% faster than the routine presented here. For a comparison, that routine spends 150 cycles on average until the first pixel is plotted, all subsequent pixels then are drawn at about 33 cycles per pixel. Break even already happens for the second pixel plot. The routine (including some *small* tables) weighs in at about 800 bytes.

Unlike the routine here, I reserve the use of that routine for serious applications, and I have no intentions to publish its source just for seeing it used in toy programs (and that includes benchmark tests).

Greetings,

Michael

[MrSterlingBS]

Who decides what legitimate applications are?