` COMPUTE! ISSUE 38 / JULY 1983 / PAGE 165`

 CIRCLES Jeffrey S. McArthur Every Atari graphics programmer needs to draw circles. This tutorial will show you how to draw a circle – and draw one fast – without jumping through hoops. There are several drawing utilities here, from an elementary BASIC routine which takes 60 seconds to a machine language version that finishes in a fraction of a second. Even if you're not interested in the methodology, you can still use these subroutines in your graphics and games. Program 1 draws circles, but takes more than a minute to draw a circle, no matter how big or small it is. Reflections A circle is symmetrical, so why don't we take advantage of its symmetry? If we know the value of one point, we can reflect it across the X-axis or across the Y-axis. That is, if we know (X, Y) is a point on the circle, then so is (X,-Y). The same is true for (-X,Y) and (-X,-Y). So we have to do only a quarter of the work. Circles are also symmetrical along the X = Y line. If we know (X, Y) is on the circle, then so is (Y,X). Now we have to find only an eighth of the points. Program 2 uses that method. Unfortunately, even doing only one-eighth of the work, we still need more than ten seconds to draw the circle. Perhaps there is a better way. Instead of using sines and cosines, use the equation: ```X*X +Y*Y = R*R ``` That isn't very useful, but we can rearrange the equation and get: ```Y = SQRT(R*R-X*X) ``` So all we have to do is find Y for X = -R to R. However, since the square root function returns only the positive square root, we also have to plot the negative square root. Program 3 is an example of how to do that. This method is faster than using sines or cosines, but it still takes more than 16 seconds. So using Program 4, we reflect it, like we did in Program 2. Now we have a method that takes only five seconds on a large circle and is a lot faster on the smaller ones. If you take a close look at how Program 4 draws the circle, you see it draws lines of different lengths. This method works fine on a screen, but on a plotter the circle has flat spots. A Faster Circle The screen is made up of an array of points. Each point is addressed by two coordinates (X,Y). However, X and Y are always integers. In Atari BASIC you can PLOT 0.5, 0.5, but the points are rounded to integers. So if you are at one point on the circle and are trying to figure where the next point is, you can go in eight directions. If you divide the circle into quarters, then only three of those directions are valid. If you divide the circle into eight parts, you can go in only two directions. For example, if you are on the circle at (R, 0), the next point is either (R-1, 0) or (R-1, 1). This method is called a potential function. Since the screen cannot plot points except with integers, there is a small error that is not always equal to zero. We want to keep the error as small as possible. We also reflect it eight ways as before. That takes only three seconds, and we never have to draw any long lines. Program 5 uses this method. Notice also that you can achieve the entire result using only addition and subtraction. Such programs can be easily converted to machine language since we don't have to multiply or divide. Program 7 is a machine language program to draw a circle. Program 6 calls the machine language and takes less than two-tenths of a second to draw a circle. The machine language is called by a USR function. The parameters that are passed to it are, in order: the address of the code, the X coordinate of the center of the circle, the Y coordinate of the center of the circle, the radius, and the mode of drawing. The mode of drawing means ```0: turn point off 1: turn point on 2: invert point ``` The program can be converted to any 6502 machine. The only things that need to be changed are where the variables are stored and how to plot the points. The only problem with the machine language program is that it does no checking to see if the circle goes off screen. And no clipping is done. Therefore, if your circle goes off screen, you will write over other memory. Program 1: Sines And Cosines ```100 REM CIRCLE DEMONSTRATION 110 REM PROGRAM #1 140 REM THIS METHOD TAKES APPROXIMAT ELY 61 SECONDS 200 DEG 210 GRAPHICS 8 220 COLOR 1 230 SETCOLOR 2, 0, 0 240 A = 160 250 B = 80 260 R = 50 300 FOR ALPHA = 0 TO 360 310 X1 = INT(R * COS(ALPHA) + 0.5) 320 Y1 = INT(R * SIN(ALPHA) + 0.5) 330 PLOT A + X1, B + Y1 340 NEXT ALPHA ``` Program 2: Sines And Cosines Reflected ```100 REM CIRCLE DEMONSTRATION 110 REM PROGRAM #2 140 REM THIS METHOD TAKES APPROXIMAT ELY 11 SECONDS 200 DEG 210 GRAPHICS 8 220 COLOR 1 230 SETCOLOR 2, 0, 0 240 A = 160 250 B = 80 260 R = 50 270 PLOT A + R, B 300 FOR ALPHA = 0 TO 45 310 X1 = INT(R * COS (ALPHA) + 0.5) 320 Y1 = INT (R * SIN (ALPHA) + 0.5) 330 PLOT A + X1, B + Y1 340 PLOT A - X1, B + Y1 350 PLOT A + X1, B - Y1 360 PLOT A - X1, B - Y1 370 PLOT A + Y1, B + X1 380 PLOT A - Y1, B + X1 390 PLOT A + Y1, B - X1 400 PLOT A - Y1, B - X1 410 NEXT ALPHA ``` Program 3: Square Root ```100 REM CIRCLE DEMONSTRATION 110 REM PROGRAM #3 140 REM THIS METHOD TAKES APPROXIMAT ELY 17 SECONDS 210 GRAPHICS 8 220 COLOR 1 230 SETCOLOR 2, 0, 0 240 A = 160 250 B = 80 260 R = 50 270 X0 = -R : Y0 = 0 300 FOR Xl = -R TO R 310 Y1 = INT(0.5 + SQR(R * R - X1 * X 1)) 330 PLOT A + X0, B + Y0 : DRAWTO A + Xl, B + Yl 335 PLOT A + X0, B - Y0 : DRAWTO A + X1, B-Y1 336 X0 = X1 : Y0 = Y1 340 NEXT XI ``` Program 4: Square Roof Reflected ```100 REM CIRCLE DEMONSTRATION 110 REM PROGRAM #4 140 REM THIS METHOD TAKES APPROXIMAT ELY 5 SECONDS 210 GRAPHICS 8 220 COLOR 1 230 SETCOLOR 2, 0, 0 240 A = 160 250 B = 80 260 R = 50 270 X0 = -R : Y0 = 0 280 Xl = -R 290 Y1 = INT (0.5 + SQR(R * R - X1 * X1)) 300 PLOT A + X0, B + Y0 : DRAWTO A + X1, B + Y1 310 PLOT A - X0, B + Y0 : DRAWTO A - X1, B + Y1 320 PLOT A + X0, B - Y0 : DRAWTO A + Xl, B - Yl 330 PLOT A - X0, B - Y0 : DRAWTO A - X1, B - Y1 340 PLOT A + Y0, B + X0 : DRAWTO A + Yl, B + Xl 350 PLOT A - Y0, B + X0 : DRAWTO A - Y1, B + X1 360 PLOT A + Y0, B - X0 : DRAWTO A + Yl, B - Xl 370 PLOT A - Y0, B - X0 : DRAWTO A - Y1, B - X1 380 X0 = X1 : Y0 = Y1 390 IF - X1 > = Y1 THEN X1 = X1 + 1 : GOTO 290 ``` Program 5: Potential ```100 REM CIRCLE DEMONSTRATION 110 REM PROGRAM #5 140 REM THIS METHOD TAKES APPROXIMAT ELY 3 SECONDS 210 GRAPHICS 8 220 COLOR 1 230 SETCOLOR 2, 0, 0 240 A = 160 250 B = 80 260 R = 50 270 PHI = 0 280 Y1 = 0 290 X1 = R 300 PHIY = PHI + Y1 + Y1 + 1 310 PHIXY = PHIY -X 1 -X 1 + 1 400 PLOT A + Xl, B + Y1 410 PLOT A - Xl, B + Y1 420 PLOT A + Xl, B - Y1 430 PLOT A - Xl, B - Yl 440 PLOT A + Yl, B + X1 450 PLOT A - Yl, B + X1 460 PLOT A + Yl, B - X1 470 PLOT A - Yl, B-X1 500 PHI = PHIY 510 Y1 = Y1 + 1 520 IF ABS(PHIXY) = Y1 THEN 300 ``` Program 6: BASIC Call To Machine Language ```100 REM CIRCLE DEMONSTRATION 110 REM PROGRAM #6 140 REM THIS METHOD TAKES APPROXIMAT ELY 0.1833 SECONDS 210 GRAPHICS 8 220 COLOR 1 230 SETCOLOR 2, 0, 0 240 A = 160 250 B = 80 260 R = 50 270 P = 7* 1 6 * 16 * 16 300 I = USR(P, A, B, R, 1) ```