FASTARC: A Fast Arc Generator for the Apple II

FASTARC avoids calling the trig functions by using table lookup. This table consists 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. The entries are multiplied by Radius (and 'dx' entries by 1.1875 for aspect ratio correction) to create two single-byte increment tables ('dx' and 'dy') which are used to generate the points on the circumference by simple addition to Xcenter and Ycenter.

The FASTARC subroutine can be BLOADed at any address where at least 492 bytes are available. The program is self-relocating on first call, and it has two entry points: FASTARC, at its BLOAD address, and FASTCIRC, at the BLOAD address plus 14.

Generating Arcs

To use FASTARC from Applesoft, the parameters specifying the arc must be POKEd into low memory before CALLing FASTARC. 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
           Start          74       0..64  (or 128..192 if "clockwise")
           Length         75       0..64  (or 128..192 if "connected")

Note that Xcenter is a two-byte quantity, since values from 0..279 are within the screen area and that the Radius is limited to 214 pixels (to allow for a 19% horizontal expansion, discussed below). Start and Length are both specified in units of 360/16 degrees (5.625 degrees). The Start angle zero corresponds to the point (Xcenter + Radius, Ycenter), with increasing start angles corresponding to counterclockwise rotations. Adding 128 to Start specifies that the arc should be drawn clockwise from the Start point. Adding 128 to the Length parameter specifies that the Start point of the arc should be connected by a line to the last plotted point. Specifying a Length of zero causes only the starting point of the arc to be plotted, with or without any connecting line.

FASTARC's arcs are defined by 16 points per quadrant. The points are computed in order and the Applesoft ROM function HPLOT TO is used to draw a line between the previous point and the current point, creating a solid line for the arc. 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 FASTARC to work on the DHGR screen.)

Clipping

FASTARC clips parts of the arc 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 arc 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 very few pixels, but for larger radii the clipping anomaly can become quite visible. Of course, this effect does not occur at all for arcs entirely within the screen boundaries.

Generating Full Circles

To use the FASTCIRC entry point from Applesoft, the circle parameters must be POKEd into low memory before CALLing FASTCIRC. The Start and Length parameters are set internally to 0 and 64 respectively, so they need not be POKEd. 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).

As you might expect, small circles (radius less than 5 pixels) are less "circular", but larger circles are pretty good. The time required to draw the first circle of a new Radius is approximately 0.75*Radius + 28 milliseconds. Subsequent circles of the same Radius are drawn in 0.75*Radius + 23 milliseconds.

Aspect Ratio Correction

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. FASTARC 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, approximated in FASTARC by 1 + 1/8 + 1/16 = 1.1875 (the fractional part of this factor, $30, can be modified by POKEing load address + 72 to adjust for different aspect ratios--for example, POKE zero for the square pixels implemented by most emulators). At the default expansion, the maximum radius circle is 214 to prevent overflow with 8-bit arithmetic.

Downloads

In addition to the Merlin listing, Iíve included the FASTARC.PO disk image, which contains FASTARC, its Merlin source, several demo programs to illustrate its use, and this description as a TXT file.