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

Opera 48.0.2685.50 - High-performance We...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
Tor Browser Bundle 7.0.7 - Anonymize Web...
The Tor Browser Bundle is an easy-to-use portable package of Tor, Vidalia, Torbutton, and a Firefox fork preconfigured to work together out of the box. It contains a modified copy of Firefox that... Read more
FotoMagico 5.5 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Adobe Audition CC 2018 11.0.0 - Professi...
Audition CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Audition customer). Adobe Audition CC 2018 empowers you to create and... Read more
Alfred 3.5.1 - Quick launcher for apps a...
Alfred is an award-winning productivity application for OS X. Alfred saves you time when you search for files online or on your Mac. Be more productive with hotkeys, keywords, and file actions at... Read more
AirRadar 4.0 - $9.95
With AirRadar, scanning for wireless networks is now easier and more personalized! It allows you to scan for open networks and tag them as favourites or filter them out. View detailed network... Read more
DEVONthink Pro 2.9.16 - Knowledge base,...
Save 10% with our exclusive coupon code: MACUPDATE10 DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research... Read more
ForkLift 3.0.8 Beta - Powerful file mana...
ForkLift is a powerful file manager and ferociously fast FTP client clothed in a clean and versatile UI that offers the combination of absolute simplicity and raw power expected from a well-executed... Read more
Data Rescue 5.0.1 - Powerful hard drive...
Data Rescue’s new and improved features let you scan, search, and recover your files faster than ever before. We have modernized the file-preview capabilities, added new files types to the recovery... Read more
Dropbox 37.4.29 - Cloud backup and synch...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keep them up-to-date between systems... Read more

Halcyon 6: Starbase Commander (Games)
Halcyon 6: Starbase Commander 1.4.2.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.4.2.0 (iTunes) Description: An epic space strategy RPG with base building, deep tactical combat, crew management, alien diplomacy,... | Read more »
Legacy of Discord celebrates its 1 year...
It’s been a thrilling first year for fans of Legacy of Discord, the stunning PvP dungeon-crawling ARPG from YOOZOO Games, and now it’s time to celebrate the game’s first anniversary. The developers are amping up the festivities with some exciting... | Read more »
3 reasons to play Thunder Armada - the n...
The bygone days of the Battleship board game might have past, but naval combat simulators still find an audience on mobile. Thunder Armada is Chinese developer Chyogames latest entry into the genre, drawing inspiration from the explosive exchanges... | Read more »
Experience a full 3D fantasy MMORPG, as...
Those hoping to sink their teeth into a meaty hack and slash RPG that encourages you to fight with others might want to check out EZFun’s new Eternity Guardians. Available to download for iOS and Android, Eternity Guardians is an MMORPG that lets... | Read more »
Warhammer Quest 2 (Games)
Warhammer Quest 2 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dungeon adventures in the Warhammer World are back! | Read more »
4 of the best Halloween updates for mobi...
Halloween is certainly one of our favorite times for mobile game updates. Many popular titles celebrate this spooky season with fun festivities that can stretch from one week to even the whole month. As we draw closer and closer to Halloween, we'... | Read more »
Fire Rides guide - how to swing to succe...
It's another day, which means another Voodoo game has come to glue our hands to our mobile phones. Yes, it's been an especially prolific month for this particular mobile publisher, but we're certainly not complaining. Fire Rides is yet another... | Read more »
Time Recoil (Games)
Time Recoil 1.0.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.1 (iTunes) Description: Time Recoil is a top-down shooter where you kill to slow time, dominate slow motion gunfights, and trigger devastating special... | Read more »
Campfire Cooking (Games)
Campfire Cooking 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Returner 77 (Games)
Returner 77 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Returner 77 is a cinematic space mystery puzzle game. You are in a giant alien spaceship hovering above Earth, after everything... | Read more »

Price Scanner via MacPrices.net

Apple restocks full line of refurbished 13″ M...
Apple has restocked a full line of Apple Certified Refurbished 2017 13″ MacBook Pros for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
13″ 3.1GHz/256GB MacBook Pro on sale for $167...
Amazon has the 2017 13″ 3.1GHz/256GB Space Gray MacBook Pro on sale today for $121 off MSRP including free shipping: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (MPXV2LL/A): $1678 $121 off MSRP Keep an... Read more
13″ MacBook Pros on sale for up to $120 off M...
B&H Photo has 2017 13″ MacBook Pros in stock today and on sale for up to $120 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook... Read more
15″ MacBook Pros on sale for up to $200 off M...
B&H Photo has 15″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2249, $150... Read more
Roundup of Apple Certified Refurbished iMacs,...
Apple has a full line of Certified Refurbished 2017 21″ and 27″ iMacs available starting at $1019 and ranging up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free... Read more
Sale! 27″ 3.8GHz 5K iMac for $2098, save $201...
Amazon has the 27″ 3.8GHz 5K iMac (MNED2LL/A) on sale today for $2098 including free shipping. Their price is $201 off MSRP, and it’s the lowest price available for this model (Apple’s $1949... Read more
Sale! 10″ Apple WiFi iPad Pros for up to $100...
B&H Photo has 10.5″ WiFi iPad Pros in stock today and on sale for $50-$100 off MSRP. Each iPad includes free shipping, and B&H charges sales tax in NY & NJ only: – 10.5″ 64GB iPad Pro: $... Read more
Apple iMacs on sale for up to $130 off MSRP w...
B&H Photo has 21-inch and 27-inch iMacs in stock and on sale for up to $130 off MSRP including free shipping. B&H charges sales tax in NY & NJ only: – 27″ 3.8GHz iMac (MNED2LL/A): $2179 $... Read more
2017 3.5GHz 6-Core Mac Pro on sale for $2799,...
B&H Photo has the 2017 3.5GHz 6-Core Mac Pro (MD878LL/A) on sale today for $2799 including free shipping plus NY & NJ sales tax only . Their price is $200 off MSRP. Read more
12″ 1.2GHz Space Gray MacBook on sale for $11...
Amazon has the 2017 12″ 1.2GHz Space Gray Retina MacBook on sale for $100 off MSRP. Shipping is free: 12″ 1.2GHz Space Gray MacBook: $1199.99 $100 off MSRP Read more

Jobs Board

Frameworks Engineer, *Apple* Watch - Apple...
Job Summary Join the team that is shaping the future of software development for Apple Watch! As a software engineer on the Apple Watch Frameworks team you will Read more
*Apple* News Product Marketing Mgr., Publish...
Job Summary The Apple News Product Marketing Manager will work closely with a cross-functional group to assist in defining and marketing new features and services. Read more
Fraud Analyst, *Apple* Advertising Platform...
Job Summary Apple Ad Platforms has an opportunity to redefine advertising on mobile devices. Apple reaches hundreds of millions of iPhone, iPod touch, and iPad Read more
*Apple* Information Security - Security Data...
Job Summary This role is responsible for helping to strengthen Apple 's information security posture through the identification and curation of security event data. Read more
Lead *Apple* Solution Consultant - Apple In...
…develop a team of diverse partner employees focusing on excellence to deliver the Apple story. Even when you're not present, you will maintain a consistent influence Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.