Autumn 91 - CURVES AHEAD: WORKING WITH CURVES IN QUICKDRAW
CURVES AHEAD: WORKING WITH CURVES IN QUICKDRAW
MIKE REED AND KONSTANTIN OTHMER
Imagine being able to build into your application the capability to draw freehand
curves. Imagine being able to save these curves so that they can be loaded into other
programs like MacDraw or printed using the LaserWriter. And imagine being given the
key to an abundant supply of previously defined curves to play with. Imagine no more .
. . this article reveals all.
QuickDraw is a heck of a fine drawing engine for the Macintosh, but it does have its
limitations. In particular, it supports a limited set of geometric primitives for
drawing: lines, rectangles, rounded- corner rectangles, ovals, arcs, and polygons (see
Figure 1). If you want your application to provide the capability of drawing contours
consisting of curves and straight lines, you're out of luck.
Sure, you can use the arc primitive to draw a curve, but if you want to connect the
curve to anything, you've got a problem. An arc represents a segment of an ellipse and
is specified by a bounding rectangle (defining the ellipse) and start and stop angles
(see Figure 2). Because an arc is not specified by starting and ending points, it's hard
to know the exact points where QuickDraw will begin and end drawing the arc. Thus,
the arc does not lend itself to being combined with other arcs or lines.
A more useful curve primitive would be one that describes its start and end positions
as points. The quadratic BÉzier is just such a curve. Applications such as MacDraw®
use this type of curve to allow the drawing of freehand curves, and the Macintosh itself
uses this type of curve in an internal procedure to describe TrueType fonts.
In this article we give you the lowdown on the quadratic BÉzier. We show the coding
and the data structures used by programs like MacDraw to draw this kind of curve, and
we show how your application can interchange data about this kind of curve with
MacDraw and with devices equipped with a PostScript® interpreter. And since the
quadratic BÉzier happens to be the same curve that TrueType uses (in combination
with other shapes) to draw outline fonts, we show how to extract curve data from
TrueType fonts.
Figure 1 QuickDraw's Geometric Primitives
DRAWING CURVES AND PATHS
The quadratic BÉzier has a couple of properties that make it useful as a basis for
drawing curves in QuickDraw. First, it can be rotated easily by changing just the
starting, ending, and middle points and not the underlying equation itself. Second, it
can easily be subdivided into any number of shorter curves that become flatter and
flatter, until in effect it can be drawn with a series of straight lines. Indeed, the basic
technique for drawing a curve using the existing QuickDraw primitives is by
subdividing the curve into a series of line segments. If you're interested in the
mathematics behind this, see "Parametric Equations, Anyone?
This section begins by showing sample C code that implements the subdivision
algorithm that produces a curve. We then move on to consider how to produce a
combination of curves and straight lines, known in the lingo as apath . Then we talk
about how to combine paths to produce shapes. Note that for a curve, as for every
geometric primitive in QuickDraw, you always have two options: you can either frame
it or fill it. We show you how to do the framing; you can do the filling using the call
FillPoly or PaintPoly.
Figure 2 How an Arc Is Specified in QuickDraw
FRAMING A CURVE
The code that implements the subdivision algorithm to produce a curve takes a value
for the number of times the curve should be subdivided before it's drawn as straight
lines. This number can be dynamically computed based on the size of the curve and the
quality-versus-speed trade-off the application wants to make. The code uses
fixed-point coordinates to maintain high precision during the subdivisions.
To begin, let's define a few macros to help us use fixed-point coordinates in an
integer-based graphics system.
#define FR(x) ((x) + 0x8000 >> 16)
#define ff(x) ((long)(x) << 16)
#define fmoveto(x,y) MoveTo(FR(x), FR(y))
#define flineto(x,y) LineTo(FR(x), FR(y))
#define AVE(a,b) (((a) + (b)) / 2)
FR The same as FixRound: takes a Fixed and makes it a short.
ff The reverse of FixRound: takes a short and promotes it to a
Fixed.
fmoveto The same as MoveTo, but takes Fixed coordinates.
flineto The same as LineTo, but takes Fixed coordinates.
AVE Averages two numbers, either Fixed, short, or long.
To represent fixed-point coordinates, we define a struct called point. Note that this is
similar to QuickDraw's Point, but uses Fixed numbers instead of integers.
typedef struct {
Fixed x;
Fixed y;
} point;
To represent a curve, we need three points: a start point, a control point, and an
endpoint. (These correspond toa, b, and c in Figure 3.)
typedef struct {
point start;
point control;
point end;
} curve;
The function FrameCurve (below) draws a quadratic BÉzier using subdivision. If the
level for the FrameCurve routine is 0, a LineTo (using flineto) operation is
performed; otherwise, the curve is subdivided and FrameCurve is called recursively,
once for the left half of the curve and once for the right. FrameCurve assumes the
caller has already called fmoveto on the start point of the curve. The second routine,
ExampleCurve, calls FrameCurve requesting four levels of subdividing. Thus, the final
curve consists of 2^4, or 16, lines. It's shown in Figure 5.
Figure 5 The Curve Drawn by ExampleCurve
void FrameCurve(curve *cur, int level)
{
if (level)
{ curve left, right;
left.start = cur->start;
left.control.x = AVE(cur->start.x, cur->control.x);
left.control.y = AVE(cur->start.y, cur->control.y);
right.control.x = AVE(cur->control.x, cur->end.x);
right.control.y = AVE(cur->control.y, cur->end.y);
left.end.x = right.start.x = AVE(left.control.x,
right.control.x);
left.end.y = right.start.y = AVE(left.control.y,
right.control.y);
right.end = cur->end;
FrameCurve(&left, level-1);
FrameCurve(&right, level-1);
}
else
flineto(cur->end.x, cur->end.y);
}
void ExampleCurve()
{
static curve myCurve = {ff(0), ff(0), ff(100), ff(100), ff(100),
ff(0)};
fmoveto(myCurve.start.x, myCurve.start.y);
FrameCurve(&myCurve, 4);
}
FRAMING A PATH
Drawing contours such as font outlines requires drawing a combination of straight
lines and curves. Such a combination is known as apath . A path is defined by the
following data structure:
typedef struct {
long vectors; /* The number of points in the path. */
long controlBits[anyNumber];
point vector[anyNumber]; /* The points. */
} path;
A path is similar to a polygon except that it has a set of control bits that determine
whether each point is on or off the curve. There's one control bit for each point,
beginning with the most significant bit for point 0. If the bit is set, the corresponding
point is an off-curve point and therefore the control point for a curve. If the bit is
clear, the corresponding point is an on-curve point and therefore an endpoint for
either a line segment or a curve segment. Two consecutive on-curve points form a
straight line.
Here's a routine that takes an index and the control bits and returns TRUE (nonzero)
if the point is on the curve:
Boolean OnCurve(long *bits, long index)
{
bits += index >> 5; /* Skip to the appropriate long. */
index &= 31; /* Mask to get index into current long. */
return (*bits & (0x80000000 >> index)) == 0;
}
Two consecutive off-curve points imply an on-curve point at their midpoint, as
shown in Figure 6. This path consists of two curve segments. The first is defined bya,
b, (b + c ) / 2 and the second by (b + c ) / 2,c, d.
This ability to store a series of off-curve points allows a path to describe an
arbitrarily complex shape without having to store unneeded intermediate points.
However, this is just a storage nicety. When we draw the path, we need it broken down
into a series of line and curve segments. This is done with an iterator function called
NextPathSegment. It's called continuously, each time filling a record that is either a
line segment or a curve segment, until it returns FALSE.
Figure 6 On-Curve Point Implied by Two Off-Curve Points
typedef struct {
int isLine;
curve c;
/* Private. */
long index;
long ep;
long *bits;
point *p;
} pathWalker;
void InitPathWalker(pathWalker *w, path *aPath)
{
w->index = 0;
w->ep = aPath->vectors - 1;
w->bits = aPath->controlBits;
/* Skip past the control bits to point to the first point. */
w->p = (point *)(w->bits + (aPath->vectors + 31 >> 5));
}
int NextPathSegment(pathWalker *w)
{
long prevIndex, nextIndex;
if (w->index == 0) /* 0 means this is the first segment. */
{ if (OnCurve(w->bits, w->ep))
w->c.start = w->p[w->ep];
else
{ if (OnCurve(w->bits,0))
{ w->c.start = w->p[0];
w->index = 1;
}
else /* Start at an implied on-curve point. */
{ w->c.start.x = AVE(w->p[0].x, w->p[w->ep].x);
w->c.start.y = AVE(w->p[0].y, w->p[w->ep].y);
}
}
}
else /* Start where we previously left off. */
w->c.start = w->c.end;
NEXT_SEGMENT:
/* Compute the point index before and after the current one.
* This wraps around, since we assume the contour is closed. */
prevIndex = w->index == 0 ? w->ep : w->index - 1;
nextIndex = w->index == w->ep ? 0 : w->index + 1;
if (OnCurve(w->bits, w->index))
{ if (OnCurve(w->bits, prevIndex))
{ w->isLine = true; /* This means we have a line. */
w->c.end = w->p[w->index];
}
else if (w->index++ <= w->ep)
goto NEXT_SEGMENT;
}
else
{ w->isLine = false; /* This means we have a curve. */
w->c.control = w->p[w->index];
if (OnCurve(w->bits, nextIndex))
w->c.end = w->p[nextIndex];
else
{ w->c.end.x = AVE(w->p[w->index].x, w->p[nextIndex].x);
w->c.end.y = AVE(w->p[w->index].y, w->p[nextIndex].y);
}
}
return w->index++ <= w->ep;
/* Return TRUE if there are still more segments. */
}
The FramePath routine uses a pathWalker to traverse the path and draw it as it goes.
path *NextPath(path *aPath)
{
return (path *)((long *)aPath + 1 + (aPath->vectors + 31 >> 5) +
aPath->vectors * 2);
}