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

0 Members and 1 Guest are viewing this topic.

#### AMSDOS

• Supporter
• 6128 Plus
• Posts: 3.939
• Country:
• 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-z20 x0=320:y0=200:r=2030 GOSUB 100040 END1000 FOR curx=x0-r TO x0+r STEP 41010  FOR cury=y0-r TO y0+r STEP 21020    dx=curx-x01030    dy=cury-y01040    IF (dx*dx)+(dy*dy)<=r*r THEN PLOT curx,cury,11050  NEXT cury1060 NEXT curx1070 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    * with the Firmware
* I also like to problem solve code in BASIC    * And type-in Type-Ins!

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

#### AMSDOS

• Supporter
• 6128 Plus
• Posts: 3.939
• Country:
• 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-z20 x0=320:y0=200:radius%=2030 GOSUB 100040 END1000 ' Draw Circle Routine1010 x% = radius%1020 y% = 01030 decision% = 1 - x%1040 WHILE (x% >= y%)1050  xh% = x% / 21060  yh% = y% / 21070  PLOT (x%+x0),(y%+y0),11080  PLOT (y%+x0),(x%+y0),11090  PLOT (-x%+x0),(y%+y0),11100  PLOT (-y%+x0),(x%+y0),11110  PLOT (-x%+x0),(-y%+y0),11120  PLOT (-y%+x0),(-x%+y0),11130  PLOT (x%+x0),(-y%+y0),11140  PLOT (y%+x0),(-x%+y0),11145 '1150  PLOT (x%+x0),(yh%+y0),11160  PLOT (y%+x0),(xh%+y0),11170  PLOT (-x%+x0),(yh%+y0),11180  PLOT (-y%+x0),(xh%+y0),11190  PLOT (-x%+x0),(-yh%+y0),11200  PLOT (-y%+x0),(-xh%+y0),11210  PLOT (x%+x0),(-yh%+y0),11220  PLOT (y%+x0),(-xh%+y0),11230  y%=y%+11240  IF (decision%<=0) THEN decision%=decision%+2*y%+1 ELSE x%=x%-1:decision%=decision%+2*(y%-x%)+11250 WEND1260 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    * with the Firmware
* I also like to problem solve code in BASIC    * And type-in Type-Ins!

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

#### reidrac

• Supporter
• 6128 Plus
• Posts: 962
• Country:
• Trying to gamedev!
• 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.

#### AMSDOS

• Supporter
• 6128 Plus
• Posts: 3.939
• Country:
• 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    * with the Firmware
* I also like to problem solve code in BASIC    * And type-in Type-Ins!

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

#### arnoldemu

• Supporter
• 6128 Plus
• Posts: 5.336
• Country:
• 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

#### ZbyniuR

• 464 Plus
• Posts: 324
• Country:
• 6128 A1230 PSX Win7
• 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.

#### AMSDOS

• Supporter
• 6128 Plus
• Posts: 3.939
• Country:
• 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    * with the Firmware
* I also like to problem solve code in BASIC    * And type-in Type-Ins!

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

#### AMSDOS

• Supporter
• 6128 Plus
• Posts: 3.939
• Country:
• 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.
* Using the old Amstrad Languages    * with the Firmware
* I also like to problem solve code in BASIC    * And type-in Type-Ins!

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

#### AMSDOS

• Supporter
• 6128 Plus
• Posts: 3.939
• Country:
• 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 110020 MODE 0: CALL &100 : IF PEEK(&107)=0 THEN stp%=2 ELSE stp%=130 DEFINT a-z : x=320: y=200: r=10040 xp=r: yp=0: decision=1-xp50 ORIGIN x,y60 WHILE xp>=yp70  GOSUB 100080  yp=yp+stp%90  IF decision<0 THEN decision=decision+2*yp+1 ELSE xp=xp-stp%:decision=decision+2*(yp-xp+1)100 WEND110 END1000 PLOT -yp,xp : PLOT yp,xp1010 PLOT -xp,yp : PLOT xp,yp1020 PLOT -xp,-yp : PLOT xp,-yp1030 PLOT -yp,-xp : PLOT yp,-xp1040 RETURN1100 FOR addr%=&100 TO &1071110 READ a\$1120 POKE addr%,VAL("&"+a\$)1130 NEXT addr%1140 RETURN1150 DATA cd,11,bc,32,07,01,c9,00`
* Using the old Amstrad Languages    * with the Firmware
* I also like to problem solve code in BASIC    * And type-in Type-Ins!

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

#### ZbyniuR

• 464 Plus
• Posts: 324
• Country:
• 6128 A1230 PSX Win7
• 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.

#### FloppySoftware

• CPC6128
• Posts: 243
• Country:
• The best team: Amstrad PCW, CP/M, and the Z80 cpu.
• 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

#### AMSDOS

• Supporter
• 6128 Plus
• Posts: 3.939
• Country:
• 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    * with the Firmware
* I also like to problem solve code in BASIC    * And type-in Type-Ins!

Home Computing Weekly Programs
Popular Computing Weekly Programs