Circular Arc Subdivision

Ken Turkowski
Media Technologies: Computer Graphics
Advanced Technology Group
Apple Computer, Inc.


Abstract: A circular arc is converted into a series of straight line segments, by taking advantage of the property that when a circular arc is bisected, each half-arc has a chordal deviation one quarter that of the original arc.


3 October 1994


Apple Technical Report No. 97

Circular Arc Subdivision

Ken Turkowski
3 October 1994

Introduction
This gem presents an algebraic solution to the rendering problem of circular arcs. These forms commonly arise in graphic design. For instance, well-designed typefaces may apply a very slight curvature on a portion of a letterform</a> to produce a profound aesthetic effect.

A circular arc may be represented in terms of the center and radius of its parent circle, plus the starting and ending angles and . This suggests a first-principles solution which generates successive points on the arc by evaluating the sine and cosine of a series of intermediate angles.



Clearly, this approach is computationally intensive. Moreover, the method has numerical problems if the radius is large, the circle's center is remote or the values have limited precision (e.g., fixed-point or even single-precision floating point). All these undesirable conditions arise for any arc having a very small bend, as its radius of curvature rapidly grows to infinity.

An algebraic, vector-based approach instead subdivides the arc into two halves until the (inverse radius of) curvature goes to zero and a vector suffices. This suggests a recursive implementation which can also terminate when a sufficient number of intermediate vertices have been produced (i.e., the length of the intermediate vector is very small, independent of curvature). This approach avoids both trigonometric operations and ill-conditioned formulas. The method is derived from related work [Karow87] based upon a suggestion. Both the expressions and an error analysis are presented below.

Derivation

The circular arc is represented by its endpoints and the chordal deviation:

(x 0, y 0, x 1, y 1, d).

The sign of d is used to distinguish between the two arcs that lie on either side of the chord that joins the endpoints (In the figure below, d is positive).



The bisection point of each arc is used as an endpoint for each half arc:



where



is the length of the chord.

The chordal deviation d' , or sagitta , of the bisected arc can be approximated by:



In other words, when an arc is divided into congruent "sub-arc" halves, their chordal deviation is divided by about four.

By repeatedly bisecting the arc, the chordal deviation is reduced with quadratic convergence. The arc is then replaced with a series of chords that approximate the sub-arcs to within a given tolerance. This approximation works well for arcs subtending less than about 75 ; however, this depends upon the resolution and arc radius (estimated by d ).

Proof

The ratio between the two chordal deviations can be expressed as:

Where q is the angle subtended by the smaller arc.
Substituting the double-angle formula
br> yields


This is an exact representation. Expanding its reciprocal in a Taylor series around zero gives

,

the desired result.

The error in the approximation of d ' can be approximated well by retaining terms through the quadratic, q 2/64 . The exact error is

C Implementation

The algorithm is illustrated with a floating-point implementation in C.

1. define DMAX 0.5 /* max chordal deviation = 1/2 pixel */
   

1. include <math.h>
   
2. include <GraphicsGems.h>
   

/* Function prototype for externally defined functions */
void DrawLine(Point2 p0, Point2 p1);

void
DrawArc(Point2 p0, Point2 p1, double d)
{
if (fabs(d) <= DMAX) {
DrawLine(p0, p1);
}
else {
Vector2 v;
Point2 pm, pb;
double dSub;

v.x = p1.x - p0.x; /* vector from p0 to p1 */
v.y = p1.y - p0.y;

pm.x = p0.x + 0.5 * v.x; /* midpoint */
pm.y = p0.y + 0.5 * v.y;

dSub = d / 4;
V2Scale(&v, dSub); /* subdivided vector */

pb.x = pm.x - v.y; /* bisection point */
pb.y = pm.y + v.x;

DrawArc(p0, pb, dSub); /* first half arc */
DrawArc(pb, p1, dSub); /* second half arc */
}
}

Discussion

This method quickly produces a polyline that inscribes the circular arc, and should be faster than a previous gem [Musial91], which employs a secant-based root finder and trigonometric functions to maintain arc length while splitting errors between the outside and inside of the arc.

A variant method [Paeth88] uses a non-uniform chord subdivision to locate the point where the saggita has dropped to half its height. Given a chord of interval [ 1 +1] on the x -axis having saggita s , the points of half-saggita descent lie at . These converge to a constant offset for -- a parabola then approximates the circle). This formulation adds floating-point overhead to account for the non-uniform subdivision.

For IEEE-based (radix 2) floating-point representations, halving operations are almost free.

A fixed-point implementation of this uniform subdivision algorithm will be faster on many machines than a floating-point implementation. Multiplication by two and four can be accomplished by a right shift, and a fixed-point square root [Turkowski95] can be used to help rescale the vector.

Given dmax , the maximum chordal deviation allowed by approximating a circular arc by a series of line segments, the number of arc bisections can be computed as



where d 0 is the initial chordal deviation and is the ceiling function. This fact can be used to write a faster implementation that uses iteration instead of recursion, as advocated in another gem [Lindgren92] which also uses maximum chordal deviation as a subdivision criterion.

Bibliography

Karow87 Peter Karow, Digital Formats for Typefaces , 1987, URW Verlag, Hamburg, Germany, pp. 236-251.

Lindgren92 Terence Lindgren, Juan Sanchez and Jim Hall, Curve Tessellation criteria through sampling, in David Kirk, editor, Graphics Gems III , pages 262-265, Academic Press, Boston, 1992.

Musial91 Christopher Musial, A Good Straight-Line Approximation of a Circular Arc, In James Arvo, editor, Graphics Gems II , Academic Press, 1991, pp. 435-439.

Paeth88 Alan Paeth, Lemming Editor, IRIS Software Exchange , Summer 1988, 1(17).

Turkowski95 Ken Turkowski, Fixed Point Square Root, In Alan Paeth, editor, Graphics Gems V , Academic Press, 1995, pp. -.

See Also

• Apple Advanced Technology Group
• Apple Computer