FASTCIRC: A Fast Circle Generator for the Apple II

FASTCIRC avoids calling the trig functions by using the 16-byte COSTBL in the Applesoft ROM (at $F5BA). This is a table of sixteen single-byte values of the cosine function spanning the first quadrant (0..90 degrees), which by symmetry provides 64 sines and cosines for the entire 0..360 degree range. COSTBL entries are multiplied by the radius to create two 16-byte increment tables ('dx' and 'dy') which are used to generate the points on the circumference by simple addition to Xcenter and Ycenter. Since COSTBL entries are only 8 bits, the circles are not perfect, but they are good enough for most purposes.

The FASTCIRC program can be BLOADed at any address where at least 374 bytes are available. The program is self-relocating on first call, and its only entry point is its load address.

To use the circle generator from Applesoft, the circle parameters must be POKEd into low memory before CALLing the generator. The parameters and their locations are:

                Parameter   Location    Range
               ===========  ========   =======
                XcenterLo       6       0..255
                XcenterHi       7       0..1
                Ycenter         8       0..255
                radius          9       0..214
 

Note that Xcenter is a two-byte quantity, since values from 0..279 are within the screen area (and center coordinates may even be outside the screen) and that the radius is limited to 214 pixels (for reasons discussed below).

Since Applesoft's cosine table is only accurate to 8 bits, small circles (radius less than 5 pixels) are less "circular", but larger circles are pretty good. The time required to draw a circle is approximately 0.7*radius + 22 milliseconds.

FASTCIRC's circles are defined by 64 points on their circumference. The points are computed in clockwise order and the HPLOT TO Applesoft ROM function is used to draw a line from the previous point to the current point, creating a solid line for the circle. In fact, the radius-dependent time for the algorithm is entirely a result of the time that HPLOT TO requires to draw the dot-connecting line segments, so an optimized line-drawing function could speed things still more, and could handle precise clipping as well. This is also the way to extend FASTCIRC to work on the DHGR screen.

FASTCIRC clips parts of the circle that lie off the screen. It does this by not plotting any point or line segment that goes outside the screen boundaries, and, when a clipped part of the circle leaves or re-enters the boundaries of the screen, the in-bounds point is plotted without a connecting line to the off-screen point. This results in the clipping extending inside the screen area for a distance between zero and radius/10 pixels. This is not a practical problem for smaller radii, since the longest clipping anomaly is only a few pixels, but for larger radii the clipping anomaly can become quite visible. Of course, this effect does not occur at all for circles entirely within the screen boundaries.

Drawing on the Apple II screen is complicated by the fact that Apple II pixels are not square. There are almost 20% more X pixels per inch than Y pixels per inch. The result is that any drawing must be expanded in the X dimension if relative lengths are to be preserved, that is, if squares are to be square and circles are to be circular. FASTCIRC applies this scaling based on Jim Sather's aspect ratio analysis in "Understanding the Apple II" on page 8-28. Sather arrives at an X expansion ratio of 1.19:1. FASTCIRC approximates this by 1 + 1/8 + 1/16 = 1.1875 (the fractional part of this factor, $30, can be modified by POKEing load address + 47 to adjust for different aspect ratios--for example POKE zero for the square pixels implemented by many emulators). Because of the default expansion, the maximum radius is 214 to avoid overflow with 8-bit arithmetic.

In addition to the Merlin listing, Iíve included the FASTCIRC.PO disk image, which contains FASTCIRC, its Merlin source, and several demo programs to illustrate its use.