Not Endorsed by the IOC
Last weekend, I decided to take a break from the ZX81 to play with something more colourful, a Recreated ZX Spectrum that we picked up at the same time. When looking at the extra BASIC commands on offer, I noticed CIRCLE, and before I knew it had whipped up something topical:
This was pleasingly easy to do, and also reveals the Spectrum’s characteristic colour clash. For comparison, I decided to do the same thing on the Electron:
Pro: no colour clash. Con: had to write my own circle-drawing routine. Pro: in BBC BASIC, you can do this as a PROC.
I posted a video of the Electron laboriously drawing the circles, and then quickly folowed by tweak that made it approximately as fast the Spectrum. It was at this point an old friend nerd-sniped me by pointing out that I’d used a naive algorithm, and there was a far smarter one available.
100 REM Circle drawing using simple trigonometry 110 DEF PROCcircleT(cx%,cy%,r%,s) 120 tau=PI*2+0.3 130 MOVE cx%,cy%+r% 140 FOR t=0 TO tau STEP s 150 DRAW cx%+SIN(t)*r%, cy%+COS(t)*r% 160 NEXT 170 ENDPROC
Suitably chastened (and switching to Owlet for convenience), I implemented Jesko’s method, an extension of Bresenham’s line drawing algorithm that draws accurate circles with only integer additions. (Forgive the repetitious PLOTs; I wanted a quick proof of concept.)
200 REM Bresenham circle drawing 210 DEF PROCcircleB(cx%,cy%,r%) 220 t1% = r%/16 230 x% = r% 240 y% = 0 250 REPEAT 260 PLOT 69,cx%+x%,cy%+y% 270 PLOT 69,cx%-x%,cy%+y% 280 PLOT 69,cx%+x%,cy%-y% 290 PLOT 69,cx%-x%,cy%-y% 300 PLOT 69,cx%+y%,cy%+x% 310 PLOT 69,cx%-y%,cy%+x% 320 PLOT 69,cx%+y%,cy%-x% 330 PLOT 69,cx%-y%,cy%-x% 340 y% = y% + 1 350 t1% = t1% + y% 360 t2% = t1% - x% 370 IF t2% >= 0 THEN t1% = t2%: x% = x% - 1 380 UNTIL x%=y% 390 ENDPROC
The result were a bit of a surprise; it was slower by a factor of two when compared to my naive trigonometry method (7.88s vs 3.86s), as you can see here. For comparison, the circle plot function in the Acorn Graphics Extension ROM (available in Owlet, but obviously not my Electron) clocks in at 0.01s.
A bit of thought revealed the problem; the above implementation takes unit steps in coordinate space. BBC BASIC keeps this fixed at 1280x1024, no matter what how many pixels are actually available. I was running in MODE 2 (the only mode capable of displaying enough simultaneous colours to recreate those Olympic rings), which as a resolution of 160x256 pixels, meaning that each pixel was eight by four coordinate units. Hence, my naive implementation was plotting each physical pixel many times.
Fixing this fully would involve taking into account the non-square pixels, making the symetry between the octants far trickier. However, we can get most of the way there by taking a simpler approach and skipping four pixels at a time (the smaller edge). Here, we’re still double-drawing some pixels, but the symetry remains intact and the resulting circle doesn’t have any gaps. Making that change brings the time down to a far more respectable 2.02s. Flushed with success, I managed to get it down to 1.6s by moving the PLOTs into assembler.
The next step would be to move the main loop into assembler, but that’s a fair but of work due to the bigger-than-a-byte integer maths, so I decided to call it a day. It was an enjoyable diversion; the well-defined problem on a limited system meant the above was only a few five- and ten-minute stretches of playing around between other things, rather than a major commitment. A brain-teaser rather than a whole project. Sometimes, that’s exactly what you’re after.