Make your own free website on Tripod.com

Drawing Circles using Bresenham's Circle Algorithm





update dec 2006

bresenham arc, line drawing, and scan conversion working
now!  Thanks to Andy McFadden and Nick Westgate...

here is dsk image:
 zipped disk image



I posted to Comp.sys.apple2.programmer newsgroup, 
asking how to quickly compute an arc + area of 
circle.
  
Andy McFadden  replied with : this post  , which pointed to:

this page,   and this page. 


I had been doing the the following 
to compute circles:

*********************************************

     10 gosub 1000: rem draw screen 
     20 END 

     1010 REM draw screen 
     1020 GR: COLOR = 7 
     1050 color = 3:plot 19,19 : rem center 
     1060 color = 4 

     1070 CX = 19:CY = 19 : rem center coordinates of circle 
     1100 r1=19 : rem radius of circle 
     1110 for a = 0 to 360:rem angle 
     1120 gosub 8000: rem compute x,y offset 
     1130 plot CX + x1 , CY + y1 : rem plot point 
     1140 next a 
     1150 return 


     8000 rem calc pt in circle 
     8010 ar = a * (3.14/180) 
     8020 x1 = r1 * cos (AR) 
     8030 y1=-r1 * sin (ar) 
     8040 return 

*********************************************



This took 30 seconds in an emulator, running at 
"real machine" speed.

Using the information contained in the articles 
that Andy gave me links to, I was able to speed
this up to about 1 second execution time! :


*********************************************

      500 radius = 19
      510 CX = 19: cy = 19 : REM center coordinates

     1000 D = 3 - (2*radius) 
     1010 X = 0 
     1020 Y = radius  :rem (when x=0, Y = radius!) 


     2000"loop": 
     2010 if d < 0 then d = d + ( 4 * x ) + 6 
             :goto 3000: rem "D isn't < 0"  
     2020 if d > = 0 then d = d + 4 * ( x - y ) + 10
             : y = y - 1 


     3000 rem "D isn't <0" 
     3010 gosub 4000: rem "plot" 
     3020 if x=y then GOTO 3500 
     3030 x=x+1:goto 2000 : rem "loop" 
     3040 END 

     3500 rem done with circle
     3510 print "done"
     3520 END

     4000 rem "plot" 
     4010 plot cx+x, cy+y 
     4020 plot cx+x, cy-y 
     4030 plot cx-x,cy+y 
     4040 plot cx-x,cy-y 
     4050 plot cx+y,cy+x 
     4060 plot cx+y,cy-x 
     4070 plot cx-y,cy+x 
     4080 plot cx-y,cy-x 
     4090 return 

*********************************************



this graphic shows the order that the points
are plotted in.  Point 1 refers to line 4010
plot.  point 2 refers to line 4020 plot, etc:

___________________
| number  |   line |
|_________|________|
| pt1:    | 4010   |
| pt2:    | 4020   |
| pt3:    | 4030   |
| pt4:    | 4040   |
| pt5:    | 4050   |
| pt6:    | 4060   |
| pt7:    | 4070   |
| pt8:    | 4080   |
|_________|________|




The graphic above shows what I want to figure
out next.  I want to calculate a 45 degree 
slice of the circle, and fill this area
(I actually want coordinates of all the points,
but if I can fill it, I know the points!)



The 45 degree slice that I want to compute
coordinates for can be *any* 45 degree slice.

As INPUT to the routine, I have the angle
of a line running through the center of 
the 45 degree slice:




In the above example, the slice is centered
on 42 degree line.  In my program I want
the 42 degrees to be variable, but always
compute a 45 degree segment of the circle.




more progress

the above graphic shows which plots (in the code) refer to which angle in the circle. 0 degrees on the circle is "up", or "north". 180 is "down" or "south" ________________________ |number | degrees | |_________|_____________| 1 | # 2 | 0 - 45 | 2 | # 6 | 45 - 90 | 3 | # 5 | 90 - 135 | 4 | # 1 | 135 - 180 | 5 | # 3 | 180 - 225 | 6 | # 7 | 225 - 270 | 7 | # 8 | 270 - 315 | 8 | # 4 | 315 - 0 | ------------------------- Since I only want a 45 degree segment of the circle, I will only be using 2 of the lines in the PLOT routine each time I do a calculation. I need to determine WHICH of these plots to use based on the input angle of the routine. I also have to skip drawing points that are out of range. DSK image of what I have so far