Author Topic: Bresenham Integer Circle Algorithm  (Read 3287 times)

0 Members and 1 Guest are viewing this topic.

Offline AMSDOS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 3.939
  • Country: au
    • index.php?action=treasury
    • Programs for Turbo Pascal 3
  • Liked: 1158
  • Likes Given: 1924
Bresenham Integer Circle Algorithm
« on: 12:24, 02 December 15 »

As discussed in this thread, I took this routine and rewrote a couple of my own variations in BASIC & Pascal.
Code: [Select]
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]
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]
   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.
« Last Edit: 12:35, 02 December 15 by AMSDOS »
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Offline AMSDOS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 3.939
  • Country: au
    • index.php?action=treasury
    • Programs for Turbo Pascal 3
  • Liked: 1158
  • Likes Given: 1924
Re: Bresenham Integer Circle Algorithm
« Reply #1 on: 10:54, 04 December 15 »
I've had a look at the routine @FloppySoftware provided which appears to be more Amstrad friendly


Code: [Select]

/* 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]

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]
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Offline reidrac

  • Supporter
  • 6128 Plus
  • *
  • Posts: 962
  • Country: gb
  • Trying to gamedev!
    • index.php?action=treasury
    • usebox.net
  • Liked: 1757
  • Likes Given: 968
Re: Bresenham Integer Circle Algorithm
« Reply #2 on: 10:58, 04 December 15 »
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]
decision += 2 * y + 1;
could be expressed as:
Code: [Select]
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.
« Last Edit: 11:06, 04 December 15 by reidrac »
Released The Return of Traxtor, Golden Tail, Magica, The Dawn of Kernel, Kitsune`s Curse and Brick Rick for the CPC.

If you like my games and want to show some appreciation, you can always buy me a coffee.

Offline AMSDOS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 3.939
  • Country: au
    • index.php?action=treasury
    • Programs for Turbo Pascal 3
  • Liked: 1158
  • Likes Given: 1924
Re: Bresenham Integer Circle Algorithm
« Reply #3 on: 11:24, 04 December 15 »
a += b is equivalent to a = a + b.

So, for example:
Code: [Select]
decision += 2 * y + 1;
could be expressed as:
Code: [Select]
decision = decision + 2 * y + 1;


Cool, so my translation was correct! :)

Quote
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.  :)
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Offline arnoldemu

  • Supporter
  • 6128 Plus
  • *
  • Posts: 5.336
  • Country: gb
    • Unofficial Amstrad WWW Resource
  • Liked: 2278
  • Likes Given: 3478
Re: Bresenham Integer Circle Algorithm
« Reply #4 on: 11:38, 04 December 15 »

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?
My games. My Games
My website with coding examples: Unofficial Amstrad WWW Resource

Offline ZbyniuR

  • 464 Plus
  • *****
  • Posts: 324
  • Country: pl
  • 6128 A1230 PSX Win7
    • Jedyne polskie forum o CPC. :)
  • Liked: 348
  • Likes Given: 160
Re: Bresenham Integer Circle Algorithm
« Reply #5 on: 19:21, 04 December 15 »
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
In STARS, TREK is better than WARS.

Offline AMSDOS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 3.939
  • Country: au
    • index.php?action=treasury
    • Programs for Turbo Pascal 3
  • Liked: 1158
  • Likes Given: 1924
Re: Bresenham Integer Circle Algorithm
« Reply #6 on: 22:34, 04 December 15 »
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".
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Offline AMSDOS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 3.939
  • Country: au
    • index.php?action=treasury
    • Programs for Turbo Pascal 3
  • Liked: 1158
  • Likes Given: 1924
Re: Bresenham Integer Circle Algorithm
« Reply #7 on: 00:51, 05 December 15 »
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.  :D
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Offline AMSDOS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 3.939
  • Country: au
    • index.php?action=treasury
    • Programs for Turbo Pascal 3
  • Liked: 1158
  • Likes Given: 1924
Re: Bresenham Integer Circle Algorithm
« Reply #8 on: 06:03, 06 December 15 »
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]

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
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3

Offline ZbyniuR

  • 464 Plus
  • *****
  • Posts: 324
  • Country: pl
  • 6128 A1230 PSX Win7
    • Jedyne polskie forum o CPC. :)
  • Liked: 348
  • Likes Given: 160
Re: Bresenham Integer Circle Algorithm
« Reply #9 on: 07:44, 19 January 16 »
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. :)
In STARS, TREK is better than WARS.

Offline FloppySoftware

  • CPC6128
  • ****
  • Posts: 243
  • Country: es
  • The best team: Amstrad PCW, CP/M, and the Z80 cpu.
    • Floppy Software
  • Liked: 234
  • Likes Given: 171
Re: Bresenham Integer Circle Algorithm
« Reply #10 on: 09:26, 19 January 16 »
a += b is equivalent to a = a + b.

So, for example:
Code: [Select]
decision += 2 * y + 1;
could be expressed as:
Code: [Select]
decision = decision + 2 * y + 1;

Not exactly, but:

Code: [Select]
decision = decision + ( 2 * y + 1);
It's not important in this case, but it will in other cases.
« Last Edit: 09:30, 19 January 16 by FloppySoftware »
floppysoftware.es < NEW URL!!!
cpm-connections.blogspot.com.es

Offline AMSDOS

  • Supporter
  • 6128 Plus
  • *
  • Posts: 3.939
  • Country: au
    • index.php?action=treasury
    • Programs for Turbo Pascal 3
  • Liked: 1158
  • Likes Given: 1924
Re: Bresenham Integer Circle Algorithm
« Reply #11 on: 11:57, 19 January 16 »
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.
* Using the old Amstrad Languages :D   * with the Firmware :P
* I also like to problem solve code in BASIC :)   * And type-in Type-Ins! :D

Home Computing Weekly Programs
Popular Computing Weekly Programs
Your Computer Programs
Updated Other Program Links on Profile Page (Update April 16/15 phew!)
Programs for Turbo Pascal 3