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
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 (
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).