Please consider a donation to the Higher Intellect project. See https://preterhuman.net/donate.php or the Donate to Higher Intellect page for more info.

Circular Arc Subdivision

From Higher Intellect Vintage Wiki
Revision as of 19:29, 23 September 2020 by Netfreak (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 TR97.gif1.gif and TR97.gif2.gif. 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.

TR97.gif3.gif

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).

TR97.gif4.gif

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

TR97.gif5.gif

where

TR97.gif6.gif

is the length of the chord.

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

TR97.gif7.gif

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:
TR97.gif8.gif
Where q is the angle subtended by the smaller arc.
Substituting the double-angle formula
TR97.gif9.gifbr> yields
TR97.gif10.gif

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

TR97.gif11.gif,

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

TR97.gif12.gif

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 TR97.gif13.gif. These converge to a constant offset for TR97.gif14.gif -- 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

TR97.gif15.gif

where d 0 is the initial chordal deviation and TR97.gif16.gif 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