Bresenham Integer Circle Algorithm

[AMSDOS]

As discussed in this thread, I took this routine and rewrote a couple of my own variations in BASIC & Pascal.

Code Select Expand


void filcircle(int x0,int y0,int R)
{int dx,dy,curx,cury;
  for(curx=x0-R;curx<=(x0+R);curx++)
  for(cury=y0-R;cury<=(y0+R);cury++)
   {
    dx=curx-x0;
    dy=cury-y0;
    if(dx*dx+dy*dy<=R*R) setpixel(curx,cury);
    }
  }

The BASIC version looks like this:

Code Select Expand


10 MODE 0:DEFINT a-z
20 x0=320:y0=200:r=20
30 GOSUB 1000
40 END
1000 FOR curx=x0-r TO x0+r STEP 4
1010  FOR cury=y0-r TO y0+r STEP 2
1020    dx=curx-x0
1030    dy=cury-y0
1040    IF (dx*dx)+(dy*dy)<=r*r THEN PLOT curx,cury,1
1050  NEXT cury
1060 NEXT curx
1070 RETURN





And the Pascal (using HP4t):

Code Select Expand


   10 PROGRAM BresenhamCircle;
   20
   30 PROCEDURE mode(num : char);
   40 BEGIN
   50   ra:=num;
   60   user(#bc0e);
   70 END;
   80
   90 PROCEDURE plot(xpos,ypos : integer; col : char);
  100 BEGIN
  110   ra:=col;
  120   user(#bbde);
  130   rde:=xpos;
  140   rhl:=ypos;
  150   user(#bbea);
  160 END;
  170
  180 PROCEDURE circle(xpos, ypos, radius : integer);
  190 VAR curx : integer;
  200     cury : integer;
  210     dx   : integer;
  220     dy   : integer;
  230 BEGIN
  240   curx:=xpos-radius;
  250   WHILE (curx<=xpos+radius) DO BEGIN
  260     cury:=ypos-radius;
  270     WHILE (cury<=ypos+radius) DO BEGIN
  280       dx:=curx-xpos;
  290       dy:=cury-ypos;
  300       IF (dx*dx)+(dy*dy)<=(radius*radius) THEN plot(curx,cury,chr(1));
  310       cury:=cury+2
  320     END;
  330     curx:=curx+4
  340   END;
  350 END;
  360
  370 BEGIN
  380   mode(chr(0));
  390   circle(320,200,20);
  400 END.


to produce a circle, which seems to work. Because it's using Plot though spends some time filling in the circle.


An interesting idea I saw in the old article from Your Computer involves using Plot followed by DRAWR to draw a Circle, the idea implemented there is very quick, though the Z variable is being used to return the Square Root.



Was going to see if I could apply something for the routine above.

[AMSDOS]

I've had a look at the routine @FloppySoftware provided which appears to be more Amstrad friendly

Code Select Expand



/* Draw a circle in the current draw mode
   --------------------------------------
*/
DrawCircle(x0, y0, radius)
int x0, y0, radius;
{
int x, xh;
int y, yh;
int decision;
x = radius;
y = 0;
decision = 1 - x;
while(x >= y) {
  /* The PCW pixels are double in high */
  xh = x >> 1;  /* xh = x / 2 */
  yh = y >> 1;  /* yh = y / 2 */


  /**
  DrawPixel( x + x0,  y + y0);
  DrawPixel( y + x0,  x + y0);
  DrawPixel(-x + x0,  y + y0);
  DrawPixel(-y + x0,  x + y0);
  DrawPixel(-x + x0, -y + y0);
  DrawPixel(-y + x0, -x + y0);
  DrawPixel( x + x0, -y + y0);
  DrawPixel( y + x0, -x + y0);
  **/
  DrawPixel( x + x0,  yh + y0);
  DrawPixel( y + x0,  xh + y0);
  DrawPixel(-x + x0,  yh + y0);
  DrawPixel(-y + x0,  xh + y0);
  DrawPixel(-x + x0, -yh + y0);
  DrawPixel(-y + x0, -xh + y0);
  DrawPixel( x + x0, -yh + y0);
  DrawPixel( y + x0, -xh + y0);
  y++;
  if(decision <= 0) {
   decision += 2 * y + 1;
  }
  else {
   x--;
   decision += 2 * (y - x) + 1;
  }
}
}



I've tried converting the code into BASIC, though am having some troubles translating the C:

Code Select Expand



10 MODE 1:DEFINT a-z
20 x0=320:y0=200:radius%=20
30 GOSUB 1000
40 END
1000 ' Draw Circle Routine
1010 x% = radius%
1020 y% = 0
1030 decision% = 1 - x%
1040 WHILE (x% >= y%)
1050  xh% = x% / 2
1060  yh% = y% / 2
1070  PLOT (x%+x0),(y%+y0),1
1080  PLOT (y%+x0),(x%+y0),1
1090  PLOT (-x%+x0),(y%+y0),1
1100  PLOT (-y%+x0),(x%+y0),1
1110  PLOT (-x%+x0),(-y%+y0),1
1120  PLOT (-y%+x0),(-x%+y0),1
1130  PLOT (x%+x0),(-y%+y0),1
1140  PLOT (y%+x0),(-x%+y0),1
1145 '
1150  PLOT (x%+x0),(yh%+y0),1
1160  PLOT (y%+x0),(xh%+y0),1
1170  PLOT (-x%+x0),(yh%+y0),1
1180  PLOT (-y%+x0),(xh%+y0),1
1190  PLOT (-x%+x0),(-yh%+y0),1
1200  PLOT (-y%+x0),(-xh%+y0),1
1210  PLOT (x%+x0),(-yh%+y0),1
1220  PLOT (y%+x0),(-xh%+y0),1
1230  y%=y%+1
1240  IF (decision%<=0) THEN decision%=decision%+2*y%+1 ELSE x%=x%-1:decision%=decision%+2*(y%-x%)+1
1250 WEND
1260 RETURN



Though my output returns a Outline of an Circle with an Oval within that, think there's something wrong with the Decision process (Line 1240) while translating. Not sure what the operator "+=" means, so just took it as taking the Decision Variable to Equal itself Plus (+) the formula proceeding it.


[attachimg=1]

[reidrac]

Though my output returns a Outline of an Circle with an Oval within that, think there's something wrong with the Decision process (Line 1240) while translating. Not sure what the operator "+=" means, so just took it as taking the Decision Variable to Equal itself Plus (+) the formula proceeding it.

a += b is equivalent to a = a + b.

So, for example:

Code Select Expand

decision += 2 * y + 1;

could be expressed as:

Code Select Expand

decision = decision + 2 * y + 1;

EDIT: The problem is that the C code has the first block of "DrawPixel" calls commented, but your basic version has them in.

In C everything between /* and */ is commented and hence ignored by the compiler.

[AMSDOS]

a += b is equivalent to a = a + b.

So, for example:

Code Select Expand

decision += 2 * y + 1;

could be expressed as:

Code Select Expand

decision = decision + 2 * y + 1;

Cool, so my translation was correct!

EDIT: The problem is that the C code has the first block of "DrawPixel" calls commented, but your basic version has them in.

In C everything between /* and */ is commented and hence ignored by the compiler.

Thanks for picking up on that, I'm more used to using (* and *) when dealing with multiple line comments, so hopefully the Oval will go, leaving the Circle Outline. 

[arnoldemu]

Cool, so my translation was correct!


Thanks for picking up on that, I'm more used to using (* and *) when dealing with multiple line comments, so hopefully the Oval will go, leaving the Circle Outline. 

Don't forget to compensate for the cpc's plot functions. code probably assumes square pixels and 1:1 ratio.

But in basic, remember it's 640x400 for graphics, so double the y coordinate to fix the aspect?

[ZbyniuR]

This are my experiments with fast draw circle in Basic.
For start program compare how fast are 3 different method for full circle.
Any key and start drawing random circles, from line 60. First SQR full circle, later SQR empty, and SIN COS from table by 26 lines. (26 is variable g in line 40, less mean faster but less pretty). MODE 0 is fastest, MODE 2 slowest for any method

10 MODE 1:MOVE 0,0,1:DEFINT a-y:r=100:x=110:y=200:c=r*r:z=TIME:ORIGIN x,y:FOR b=1 TO r STEP 2:a=SQR(c-b*b):MOVE-a,b:DRAW a,b:MOVE-a,-b:DRAW a,-b:NEXT:z2=TIME:PRINT z2-z,
20 x=320:z=TIME:a=r:b=0:e=1-a:ORIGIN x,y:WHILE a>=b:MOVE-b,a:DRAW b,a:MOVE-a,b:DRAW a,b:MOVE-a,-b:DRAW a,-b:MOVE-b,-a:DRAW b,-a:b=b+2:IF e<0 THEN e=e+2*b+1 ELSE a=a-2:e=e+2*(b-a+1)
30 WEND:z2=TIME:PRINT z2-z,
40 DEFINT a-y:g=26:DEFREAL s,c:DEG:DIM si(360),co(360):FOR o=1 TO g:si(o)=SIN(360/g*o):co(o)=COS(360/g*o):NEXT:x=530:z=TIME:ORIGIN x,y:MOVE 0,r:FOR o=1 TO g:DRAW si(o)*r,co(o)*r:NEXT:MOVE 0,0:FILL 1:z2=TIME:PRINT z2-z:CALL &BB18
50 '
60 MODE 0:DEFINT a-z:WHILE INKEY$="":x=RND*640:y=RND*200*2:r=RND*100:k=RND*4:a=r:b=0:e=1-a:ORIGIN x,y:WHILE a>=b:MOVE-b,a:DRAW b,a:MOVE-a,b:DRAW a,b:MOVE-a,-b:DRAW a,-b:MOVE-b,-a:DRAW b,-a:b=b+2:IF e<0 THEN e=e+2*b+1 ELSE a=a-2:e=e+2*(b-a+1)
70 WEND:MOVE 0,0,RND*13:WEND:MOVE 0,0,1,0
80 MODE 1:WHILE INKEY$="":x=RND*640:y=RND*400:r=RND*150:k=RND*3+1:a=r:b=0:e=1-a:ORIGIN x,y:WHILE a>=b:PLOT a,b,k:PLOT b,a:PLOT-a,b:PLOT-b,a:PLOT-a,-b:PLOT-b,-a:PLOT a,-b:PLOT b,-a:b=b+2:IF e<0 THEN e=e+2*b+1 ELSE a=a-2:e=e+2*(b-a+1)
90 WEND:WEND:MOVE 0,0,1
100 DEFREAL s,c:MODE 2:WHILE INKEY$="":x=RND*640:y=RND*400:r=RND*150:ORIGIN x,y:MOVE 0,r:FOR o=1 TO g:DRAW si(o)*r,co(o)*r:NEXT:WEND:GOTO 60

[AMSDOS]

Don't forget to compensate for the cpc's plot functions. code probably assumes square pixels and 1:1 ratio.

But in basic, remember it's 640x400 for graphics, so double the y coordinate to fix the aspect?

I was going to use "SCR GET MODE" to work out the mode and assign the appropriate value to a variable, so "1" for mode 2, "2" for mode 1 & "4" for mode 0.


The y coordinate will constantly remain as "2".

[AMSDOS]

This are my experiments with fast draw circle in Basic.
For start program compare how fast are 3 different method for full circle.
Any key and start drawing random circles, from line 60. First SQR full circle, later SQR empty, and SIN COS from table by 26 lines. (26 is variable g in line 40, less mean faster but less pretty). MODE 0 is fastest, MODE 2 slowest for any method

That's interesting, is similar to Multicoloured Circles program from that Your Computer Article.


I had a play with that 3rd circle on the 1st screen that gets Filled in, thinking that a FILL from the edge of the Circle might of been quicker than from the Centre, by altering the MOVE to "MOVE -96,0", but had no bearing on time it took to complete funnily enough. 

[AMSDOS]

Don't forget to compensate for the cpc's plot functions. code probably assumes square pixels and 1:1 ratio.

But in basic, remember it's 640x400 for graphics, so double the y coordinate to fix the aspect?

This turned out to be more complicated than what I thought and was looking at @ZbyniuR 10-Liner before I could get the correct ratio's depending on the mode.


But the odd thing about is for Mode 0, the ratio remains at 2, for Mode 1 ratio can either be 2 or 1, it doesn't seem to have much difference in the result & Mode 2 has to be set to 1. If I go any bigger the result looks more like an outline of an Flower.

Code Select Expand



10 GOSUB 1100
20 MODE 0: CALL &100 : IF PEEK(&107)=0 THEN stp%=2 ELSE stp%=1
30 DEFINT a-z : x=320: y=200: r=100
40 xp=r: yp=0: decision=1-xp
50 ORIGIN x,y
60 WHILE xp>=yp
70  GOSUB 1000
80  yp=yp+stp%
90  IF decision<0 THEN decision=decision+2*yp+1 ELSE xp=xp-stp%:decision=decision+2*(yp-xp+1)
100 WEND
110 END
1000 PLOT -yp,xp : PLOT yp,xp
1010 PLOT -xp,yp : PLOT xp,yp
1020 PLOT -xp,-yp : PLOT xp,-yp
1030 PLOT -yp,-xp : PLOT yp,-xp
1040 RETURN
1100 FOR addr%=&100 TO &107
1110 READ a$
1120 POKE addr%,VAL("&"+a$)
1130 NEXT addr%
1140 RETURN
1150 DATA cd,11,bc,32,07,01,c9,00


[ZbyniuR]

In this program from my post #5 method in line 80 doing not hermetic circle in MODE 2, so it not good to FILL, unless draw circle twice with y+1 in second time.

Rest of method work the same in any MODE, exept small difference of speed. MODE 0 is fastest, and MODE 2 slowest.

[FloppySoftware]

a += b is equivalent to a = a + b.

So, for example:

Code Select Expand

decision += 2 * y + 1;

could be expressed as:

Code Select Expand

decision = decision + 2 * y + 1;

Not exactly, but:

Code Select Expand

decision = decision + ( 2 * y + 1);

It's not important in this case, but it will in other cases.

[AMSDOS]

In this program from my post #5 method in line 80 doing not hermetic circle in MODE 2, so it not good to FILL, unless draw circle twice with y+1 in second time.

Rest of method work the same in any MODE, exept small difference of speed. MODE 0 is fastest, and MODE 2 slowest.

The "Mode Friendly BASIC" version I came up with is based from your program in post #5, though I'm using GRA GET MODE (from the Machine Code) to workout which mode is being used and set stp% variable accordingly. Seems to work just fine with FILL.