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