by

(abrobecker@yahoo.com or rte de Dardagny; 01630 CHALLEX; FRANCE).

The idea of using (dx+1)^{2}=dx^{2}+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 (x_{0};y_{0}) and of radius r is the set of points (x;y) so that dx^{2}+dy^{2}<r^{2}, where dx=x-x_{0} and dy=y-y_{0}. We'll use this definition with a slight modification, using (r+1/2)^{2} instead of r^{2}, because it gives better results. Let's have an example, where the center (x_{0};y_{0}) is the bottom-left pixel, and the radius is 3.

We start at scanline y_{0} by drawing the segment between x_{0}-3 and x_{0}+3 (green pixel at the bottom). Then we go up one line and compute the new distance between the center and (x_{0}+3;y_{0}+1), it is still lower than (r+1/2)^{2} so this pixel is an edge for scanline y_{0}+1 (the other one is at x_{0}-3). Go up one more line, but this time the distance to (x_{0}+3;y_{0}+2) is too big. So we go left one pixel, and since the distance to (x_{0}+2;y_{0}+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 dx^{2}+(dy+1)^{2}=dx^{2}+dy^{2}+2*dy+1). So we'll use this to track the edges of the circle, beginning at (x_{0}+r;y_{0}). 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 y_{0}+dy and y_{0}-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:

- if y
_{0}is out of the screen, we begin to compute the edges without drawing, and once y_{0}+dy is in the screen we draw single lines only. - if y
_{0}is in the screen, we draw double lines until the top or the bottom of the circle goes out of the screen (if this happens at all) and then draw single lines only (same routine as case 1). To know which side (top or bottom) is clipped first, we check if y_{0}<screen_height/2 or not.

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