The idea of using (dx+1)2=dx2+2*dx+1 to track circle's edge was given by Frederic Elisei (ArmOric/Arm's Tech), and i got the threshold% optimisation from the circle routine of Jan Vlietinck (Jan/BASS). All the rest (clipping, using r+0.5) was devised by me.
Before going on let's have some physical modelisation: the screen is composed of picture cells (pixels) we'll assimilate to small circles, and the integer coordinates (x;y) of a pixel will refer to its center where the electron beam hits the screen, luminosity then decreasing with the distance (thus explaining the circular model).
A circle of center (x0;y0) and of radius r is the set of points (x;y) so that dx2+dy2<r2, where dx=x-x0 and dy=y-y0. We'll use this definition with a slight modification, using (r+1/2)2 instead of r2, because it gives better results. Let's have an example, where the center (x0;y0) is the bottom-left pixel, and the radius is 3.
We start at scanline y0 by drawing the segment between x0-3 and x0+3 (green pixel at the bottom). Then we go up one line and compute the new distance between the center and (x0+3;y0+1), it is still lower than (r+1/2)2 so this pixel is an edge for scanline y0+1 (the other one is at x0-3). Go up one more line, but this time the distance to (x0+3;y0+2) is too big. So we go left one pixel, and since the distance to (x0+2;y0+2) is lower than (r+1/2)2 anew, this is an edge for this scanline...
We notice that when we know the distance between the center and a pixel, we can compute the one between the center and the 4 adjacent pixels with additions only (eg dx2+(dy+1)2=dx2+dy2+2*dy+1). So we'll use this to track the edges of the circle, beginning at (x0+r;y0). The algorithm looks like this:
REMUnclipped CircleFill by Alain Brobecker (aka baah/Arm's Tech)
DEFPROCcirclefill(x%,y%,r%)
dx%=r%
IFdx%=0THENENDPROC
dist%=r%*r%
distmax%=dist%+r% :REMshould be (r%+0.5)^2=r%^2+r%+0.25
LINEx%-dx%,y%,x%+dx%,y% :REMdraw central line
dist%+=1
dy%=1
WHILEdy%<=r%
WHILEdist%>distmax%
dist%+=-2*dx%+1 :REMdist%=(dx%-1)^2+dy^2=dist%-2*dx%+1
dx%-=1
ENDWHILE
LINEx%-dx%,y%+dy%,x%+dx%,y%+dy% :REMdraw double lines
LINEx%-dx%,y%-dy%,x%+dx%,y%-dy%
dist%+=2*dy%+1 :REMdist%=dx%^2+(dy+1)^2=dist%+2*dy%+1
dy%+=1
ENDWHILE
ENDPROC
We can optimise by noticing that only the sign of threshold%=dist%-distmax% interests us, so we don't need to compute r%*r%, we spare a register and the while can be implemented more cunningly in assembly. Jan also did use more symmetries since he didn't clip the circle, having four lines drawn and at most one correction with the dx term per iteration.
The horizontal clipping will be performed during the line drawing. Of course if we draw symmetrical lines at position y0+dy and y0-dy, this clipping needs to be made once only. For vertical clipping, the important note is that we can know beforehand how the circle will be clipped:
The algorithm below may seem complex since it comes from the assembly version (which was written first =), and the GOTOs may frighten you, but many parts are duplicated, so it is not that big. The variables nbd% and nbs% are the number of double and single lines to draw.
1 : MODE9:ORIGIN0,256:OFF:scrx%=320:scry%=128 2 : REPEAT 3 : GCOL3,1 4 : x%=RND(480)-80 5 : y%=RND(316)-80 6 : r%=RND(120) 7 : PROCcirclefill(x%,y%,r%):CIRCLEFILLx%<<2,y%<<2,r%<<2 8 : UNTIL0 9 : 10 : REMCircleFill by Alain Brobecker (aka baah/Arm's Tech) 11 : DEFPROCcirclefill(x%,y%,r%) 12 : IFr%<0THENENDPROC 13 : IF(x%+r%<0)OR(y%+r%<0)THENENDPROC 14 : IF(x%-r%>=scrx%)OR(y%-r%>=scry%)THENENDPROC 15 : dx%=r% 16 : inc%=1 :REMscrx for an assembly version 17 : IFy%<0THENGOTO 60 :REMSkipU2D 18 : IFy%>=scry%THENGOTO 77 :REMSkipD2U 19 : LINE x%-dx%<<2,y%<<2,x%+dx%<<2,y%<<2 20 : IFy%<scry%/2THEN 21 : nbd%=y% 22 : ELSE 23 : inc%=-inc% 24 : nbd%=scry%-1-y% 25 : ENDIF 26 : y1%=y%+inc% 27 : y2%=y%-inc% 28 : IFr%<nbd%THENnbd%=r% 29 : nbs%=r%-nbd% 30 : IFscry%-(2*nbd%+1)<nbs%THENnbs%=scry%-(2*nbd%+1) 31 : threshold%=r%-1 32 : dy%=1 33 : WHILEnbd%<>0 34 : WHILEthreshold%<0 35 : threshold%+=2*dx%-1 36 : dx%-=1 37 : ENDWHILE 38 : LINEx%-dx%<<2,y1%<<2,x%+dx%<<2,y1%<<2 39 : LINEx%-dx%<<2,y2%<<2,x%+dx%<<2,y2%<<2 40 : y1%+=inc% 41 : y2%-=inc% 42 : threshold%-=2*dy%+1 43 : dy%+=1 44 : nbd%-=1 45 : ENDWHILE 46 : REMdraw the single lines 47 : WHILEnbs%<>0 48 : WHILEthreshold%<0 49 : threshold%+=2*dx%-1 50 : dx%-=1 51 : ENDWHILE 52 : LINEx%-dx%<<2,y1%<<2,x%+dx%<<2,y1%<<2 53 : y1%+=inc% 54 : threshold%-=2*dy%+1 55 : dy%+=1 56 : nbs%-=1 57 : ENDWHILE 58 : ENDPROC 59 : 60 : REMy<0 so skip -y lines by computing -y-1 times the loop without drawing 61 : y1%=0 62 : nbs%=y%+r%+1:IFnbs%>scry%THENnbs%=scry% 63 : threshold%=r%-1 64 : dy%=1 65 : WHILEy%<>-1 66 : WHILEthreshold%<0 67 : threshold%+=2*dx%-1 68 : dx%-=1 69 : ENDWHILE 70 : threshold%-=2*dy%+1 71 : dy%+=1 72 : y%+=1 73 : ENDWHILE 74 : GOTO 46 75 : 76 : REMy>scry so skip y-scry lines 77 : y1%=scry%-1 78 : nbs%=scry%-(y%-r%):IFnbs%>scry%THENnbs%=scry% 79 : inc%=-inc% 80 : threshold%=r%-1 81 : dy%=1 82 : WHILEy%>scry% 83 : WHILEthreshold%<0 84 : threshold%+=2*dx%-1 85 : dx%-=1 86 : ENDWHILE 87 : threshold%-=2*dy%+1 88 : dy%+=1 89 : y%-=1 90 : ENDWHILE 91 : GOTO 46