September 96 - Graphical Truffles: A Library for Traversing Paths
Graphical Truffles: A Library for Traversing Paths
Daniel I. Lipton
The QuickDraw GX graphics system is based on shape objects that are used by
reference. An application creates a shape object such as a path or a polygon by
passing in data that represents the geometric points of the shape to be drawn
or otherwise manipulated. The QuickDraw GX graphics system then stores this
information in its internal database and returns to the application a reference
to the shape object. This reference is then passed to the various QuickDraw GX
routines that perform operations on the shape.
Since the QuickDraw GX graphics system is maintaining the original data in its
database, the application often won't keep this data around. Also, an
application may not even have created the geometric points in the first place,
as in the case of converting text into a path.
It's often desirable, for a variety of purposes, for an application to retrieve
the geometric information from a shape object. Given the richness of geometric
information that these objects can contain, it can be a nontrivial task to read
back the information. This column describes a C library that any application
can incorporate for the purpose of traversing the geometric information in
QuickDraw GX paths.
WHAT'S IN A QUICKDRAW GX PATH OBJECT
The QuickDraw GX graphics system provides several types of graphics primitives
with which to create visual content: lines, curves, polygons, paths,
typography, and bitmaps. In this system, curves are quadratic Béziers
that can be defined by three control points, the middle point being off the
curve and the other two being on. Figure 1 depicts a single quadratic curve
segment.
Figure 1. A QuickDraw GX quadratic curve segment
A QuickDraw GX path object is just a conglomeration of curve and line segments,
resulting from an array of points. The object can contain multiple contours,
each contour being a group of connected segments.
The question arises, if we look at a specific point in a path structure,
whether the point is part of a line segment or part of a curve segment. The
answer is that in addition to the points themselves, a path contains an array
of flags, one for each point, indicating whether the point is on or off the
path. To represent a single contour for a path object, QuickDraw GX uses the
gxPath data structure:
struct gxPath {
long vectors;
long controlBits[1];
struct gxPoint vector[1];
};
typedef struct gxPath gxPath;
The
vectors field is an integer that specifies the number of points in the contour,
the controlBits field is a bit array representing the on-curve/off-curve flags,
and the vector field is an array of points for the contour.
To represent a path object, QuickDraw GX uses the gxPaths data structure:
struct gxPaths {
long contours;
struct gxPath contour[1];
};
typedef struct gxPaths gxPaths;
The
contours field is an integer specifying the number of contours, and the contour
field is an array of gxPath structures, one for each contour.
Hence we have enough information to figure out what the points mean. If we see
two on-path points in a row, we know that represents a line. If we see an
on-path point followed by an off-path point followed by an on-path point, we
know that's a quadratic curve segment.
So to read the QuickDraw GX path object to determine the actual shape, all we
have to do is get a point and then get the next point. According to the
previous description, it would be safe to assume that the very first point in a
contour is an on-path point. Then, if the next one were also on the path, we'd
have a line; if it were off, we'd know that we'd have to read a third one
(which by definition would have to be on) and we'd have a curve.
The only trouble is that those assumptions aren't necessarily true. The design
of QuickDraw GX could have restricted applications to using only those patterns
of on-path/off-path points, disallowing two consecutive off-path points and
requiring the first point and the last point in a contour to be on the path;
however, it didn't.
In the interest of saving memory, QuickDraw GX allows two consecutive off-path
points to imply a middle on-path point -- known as an implicit point -- exactly
halfway between the off-path points. An example of this is shown in Figure 2.
Figure 2. A QuickDraw GX quadratic path
For each implicit point there's a memory savings of 8 bytes in QuickDraw GX.
This allows us to define geometries in less space than would be required in
other popular graphics models that use cubic Bézier curves without
implicit points, but it does complicate traversing the path.
QuickDraw GX also allows the first or the last point of a contour to be off the
curve, in the case where the contour is closed. This further complicates path
traversal.
THE SHAPEWALKER LIBRARY
You can use the ShapeWalker library (which is included on this issue's CD) to
avoid having to write a huge blob of code to deal with all those points and
flags discussed above. It allows an application to pass in a QuickDraw GX shape
object and be sent back (via callbacks) each line and curve segment in the
shape. All implicit points are resolved by the library, so the client sees only
complete line or curve segments.
The header file to be used with the library defines types for four callbacks
and a prototype for the ShapeWalker function:
// Function is called to move to a new point
// (start new contour).
typedef Boolean (*TpwMovetoProc)(gxPoint *p,
void* refcon);
// Function is called to draw a line from
// current point to p.
typedef Boolean (*TpwLinetoProc)(gxPoint *p,
void* refcon);
// Function is called to draw a curve from
// current point (which will be p[0]) through
// p[1] to p[2].
typedef Boolean (*TpwCurvetoProc)(gxPoint p[3],
void* refcon);
// Function is called to close a contour.
typedef Boolean (*TpwClosepathProc)
(void* refcon);
// Return result will be true if path walking
// was terminated by one of the callbacks.
Boolean ShapeWalker(gxShape theShape,
TpwMovetoProc DoMoveto,
TpwLinetoProc DoLineto,
TpwCurvetoProc DoCurveto,
TpwClosepathProc DoClosepath,
void* refcon);
When
using the library, you provide four callbacks and a refcon. Each callback will
get passed the refcon and possibly point information. It's suggested that the
client maintain whatever state information is necessary for the purpose at
hand. The refcon can be a pointer to a structure containing the state
information. One typical component of such information that most clients would
need is the notion of the current point. The current point is the piece of the
path we've looked at most recently, representative of the state of processing
the shape. This current point should be updated as segments come through the
callbacks. (We'll see this in a moment in our sample application.)
Each callback must also return a result of type Boolean, giving the client a
mechanism for causing the library to terminate traversal of the shape before
completion. Return false and the shape walker will continue on to the next
segment; return true and it will terminate early. This can be used to catch
errors in processing the points, or to terminate processing if you've finished
with the shape before the last point is reached.
The four callbacks are as follows:
- DoMoveto -- This procedure is called at the start of each new contour in
the shape. It gets passed a single point and the refcon. The point identifies
the location of the beginning of the contour. If the client is maintaining a
current point via the refcon, it should be updated to the point passed in.
- DoLineto -- This procedure is called for each line segment in the
contour. It gets passed a single point and the refcon. The point represents the
end point of the line segment. The start point of the line segment is whatever
point we last saw; that will be the current point if one is being maintained.
If the client is maintaining a current point via the refcon, it should be
updated to the point passed in.
- DoCurveto -- This procedure is called for each quadratic curve segment
in the contour. It gets passed an array of three points and the refcon. The
three points correspond to the control points of the curve. The first point in
the array will be the current point if one is being maintained. The current
point should then be updated to reflect the third point in the array.
- DoClosepath -- This procedure is called at the end of every contour if
the QuickDraw GX shape is closed (has the gxClosedFrameFill shape fill
attribute). Closing a contour implies connecting the last point in the contour
(whatever the current point is when this function is called) with the first
point in the contour (the point passed into the DoMoveto function).
The
code shown in Listing 1 is a sample application (SamplePathWalker.c) that
converts a piece of text to a path and then uses the ShapeWalker library to
read the points from the result. In this example the callback procedures are
used only to print out the points in the segments, but of course they can be
used to do a lot of other things as well.
Listing 1. Sample application using the ShapeWalker library
// The following structure is used to maintain a state while
// walking a shape.
typedef struct {
gxPoint currentPoint; // current point
gxPoint firstPoint; // first point in contour
} TestWalkRec;
#define fix2float(x) ((double)x / 65536.0)
Boolean TestMoveto(gxPoint *p, TestWalkRec* pWalk);
Boolean TestMoveto(gxPoint *p, TestWalkRec* pWalk)
{
printf("Begin new contour: %f, %f\r\n", fix2float(p->x),
fix2float(p->y));
pWalk->currentPoint.x = p->x;
pWalk->currentPoint.y = p->y;
pWalk->firstPoint.x = p->x;
pWalk->firstPoint.y = p->y;
return (false);
}
Boolean TestLineto(gxPoint *p, TestWalkRec* pWalk);
Boolean TestLineto(gxPoint *p, TestWalkRec* pWalk)
{
printf("Line from %f, %f to %f, %f\r\n",
fix2float(pWalk->currentPoint.x),
fix2float(pWalk->currentPoint.y),
fix2float(p->x), fix2float(p->y));
pWalk->currentPoint.x = p->x;
pWalk->currentPoint.y = p->y;
return (false);
}
Boolean TestCurveto(gxPoint p[3], TestWalkRec* pWalk);
Boolean TestCurveto(gxPoint p[3], TestWalkRec* pWalk)
{
printf("Curve from %f, %f through %f, %f, to %f, %f\r\n",
fix2float(p[0].x), fix2float(p[0].y),
fix2float(p[1].x), fix2float(p[1].y),
fix2float(p[2].x), fix2float(p[2].y));
pWalk->currentPoint.x = p[2].x;
pWalk->currentPoint.y = p[2].y;
return (false);
}
Boolean TestClosepath(TestWalkRec* pWalk);
Boolean TestClosepath(TestWalkRec* pWalk)
{
printf("Closing the contour\r\n\r\n");
pWalk->currentPoint.x = pWalk->firstPoint.x;
pWalk->currentPoint.y = pWalk->firstPoint.y;
return (false);
}
main()
{
gxShape theShape;
gxPoint location = {ff(100), ff(100)};
TestWalkRec walker;
Boolean result;
theShape = GXNewText(5, "Hello", &location);
GXSetShapeTextSize(theShape, ff(50));
GXSetShapeType(theShape, gxPathType);
GXSetShapeFill(theShape, gxClosedFrameFill);
result = ShapeWalker(theShape, TestMoveto, TestLineto,
TestCurveto, TestClosepath, &walker);
GXDisposeShape(theShape);
}
WALKING THE PATH
The files PathWalking.h and PathWalking.c are all that are required to use the
ShapeWalker library in your application (for the sake of brevity, PathWalking.c
isn't shown in this column). This library should make it easy for your
application to process QuickDraw GX path objects. For completeness, the library
will also process curve objects, line objects, rectangle objects, and polygon
objects in a similar manner. All other shape types will result in the posting
of the "illegal_type_for_shape" graphics error. (Graphics errors can be polled
with the GXGetGraphicsError function.)
The ShapeWalker library is actually based on the same code used by QuickDraw GX
in its built-in GX-to-PostScript translator for printing. The library's
versatility means that its uses in your application are limited only by your
imagination, so get creative and try it out!
DANIEL I. LIPTON (daniel_lipton@powertalk.apple.com) has worked at Apple for
seven years and is one of the original QuickDraw GX team members. In his spare
time, Dan runs a small business repairing perpetual motion machines.*
Thanks to Dave Hersey, Ingrid Kelly, and Dave Polaschek for reviewing this
column.*
