TweetFollow Us on Twitter

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

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

MacFamilyTree 7.3.3 - Create and explore...
MacFamilyTree gives genealogy a facelift: it's modern, interactive, incredibly fast, and easy to use. We're convinced that generations of chroniclers would have loved to trade in their genealogy... Read more
Skype 7.5.0.738 - Voice-over-internet ph...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
PushPal 3.0 - Mirror Android notificatio...
PushPal is a client for Pushbullet, which automatically shows you all of your phone's notifications right on your computer. This means you can see who's calling or read text messages even if your... Read more
Logic Pro X 10.1.1 - Music creation and...
Apple Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get... Read more
VLC Media Player 2.2.0 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Sound Studio 4.7.8 - Robust audio record...
Sound Studio lets you easily record and professionally edit audio on your Mac. Easily rip vinyls and digitize cassette tapes, or record lectures and voice memos. Prepare for live shows with live... Read more
LibreOffice 4.4.1.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
VueScan 9.5.03 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Freeway Pro 7.0.3 - Drag-and-drop Web de...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With its user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Cloud 3.3.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more

This Week at 148Apps: February 23-27, 20...
Final February Fun at 148Apps   How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you’re looking for. The ones we love become Editor’s Choice, standing out... | Read more »
GDC 2015 – Does Not Commute is Definitel...
GDC 2015 – Does Not Commute is Definitely a Game You Should Keep an Eye on Posted by Rob Rich on March 2nd, 2015 [ permalink ] We were teased about Mediocre Games’ (Smash Hit, | Read more »
F84 Games & POW! Announce Stan Lee V...
F84 Games has announced that it is working with legendary comic creator Stan Lee and POW! Entertainment to produce Stan Lee’s Hero Command. The game will be a action adventure of heroic proportions. | Read more »
Setlyst Keeps Your Set Straight So You C...
Setlyst Keeps Your Set Straight So You Can Focus On Rocking Out. Posted by Jessica Fisher on March 2nd, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Space is Vast, So Space Agency Has a Vas...
Space is Vast, So Space Agency Has a Vast New Update! Posted by Jessica Fisher on March 2nd, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Size DOES Matter Review
Size DOES Matter Review By Campbell Bird on March 2nd, 2015 Our Rating: :: HARD TO BEATUniversal App - Designed for iPhone and iPad This rhythm game has a unique control scheme and performance system that make it feel like a true... | Read more »
The first ever action 3D card battler Al...
On the other hand, you probably haven’t played an action 3D card battler – until now. Step forward, All Star Legion. All Star Legion is a 3D QTE-based action RPG card battler, but fear not – the game itself isn’t as convoluted as its description.... | Read more »
Travel Back to the 1980s With the Making...
Headup Games has released a hilarious making of video for its upcoming title, Pixel Heroes: Byte & Magic. The game is a RPG/Roguelike where you control three heroes set to save the township of Pixton from an evil cult called The Sons of Dawn.... | Read more »
Heavenstrike Rivals Review
Heavenstrike Rivals Review By Campbell Bird on March 2nd, 2015 Our Rating: :: HEAVENLY STRATEGICUniversal App - Designed for iPhone and iPad Despite a few flaws, this free-to-play strategy game is a fun mix of new and old strategy... | Read more »
Get The Whole Story – Lone Wolf Complete...
Get The Whole Story – Lone Wolf Complete is Now Available and On Sale Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

Sale! 15-inch 2.2GHz Retina MacBook Pro for $...
 Best Buy has the 15″ 2.2GHz Retina MacBook Pro on sale for $1774.99 $1799.99, or $225 off MSRP. Choose free home shipping or free local store pickup (if available). Price valid for online orders... Read more
27-inch 3.5GHz 5K iMac in stock today and on...
 B&H Photo has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available for... Read more
Apple Launches Free Web-Based Pages and Other...
Apple’s new Web-only access to iWork productivity apps is a free level of iCloud service available to anyone, including people who don’t own or use Apple devices. The service includes access to Apple... Read more
Survey Reveals Solid State Disk (SSD) Technol...
In a recent SSD technology use survey, Kroll Ontrack, a firm specializing in data recovery, found that while nearly 90 percent of respondents leverage the performance and reliability benefits of SSD... Read more
Save up to $600 with Apple refurbished Mac Pr...
The Apple Store is offering Apple Certified Refurbished Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
Apple CEO Tim Cook to Deliver 2015 George Was...
Apple CEO Tim Cook will deliver the George Washington University’s Commencement address to GWU grads on May 17, at which time he will also be awarded an honorary doctorate of public service from the... Read more
Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz... Read more
Save up to $50 on iPad Air 2s, NY tax only, f...
 B&H Photo has iPad Air 2s on sale for $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469.99 $30 off - 64GB iPad Air 2 WiFi: $549 $50 off - 128GB iPad Air 2... Read more
16GB iPad Air 2 on sale for $447, save $52
Walmart has the 16GB iPad Air 2 WiFi on sale for $446.99 on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale price for online orders only,... Read more

Jobs Board

*Apple* Pay Automation Engineer - iOS System...
**Job Summary** At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring passion and dedication to your job Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Event Director, *Apple* Retail Marketing -...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global engagement strategy and team. Delivering an overarching brand Read more
*Apple* Pay - Site Reliability Engineer - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.