Pushing the Envelope with FEZ

Frame Evading ZoomRects take the top prize at MacHack

By Doug McKenna, Chief Hierarchæologist, Mathemæsthetics, Inc.

About the Author

Doug McKenna is president of Mathemæsthetics, Inc. and author of Resorcerer®, the premiere and Eddy-award-winning Macintosh resource editor. Among his childhood hacks were a variety of ingeniously designed and less-than-benign mousetraps, as well as a private hand-built telephone line to a friend’s house. The line was eventually destroyed by lightning (fortunately the houses grounding either end weren’t). His first computer amusement was a canonical ASR-33 teletype paper-tape jingle bell hack. Although (or perhaps because) his parents let him play with matches at age six, fireworks at nine, and dynamite at twelve, his pyromaniacal tendencies have long since evolved into more constructive endeavors in the explosive virtual world of editing interfaces.

The Lessons Of Two Old Hacks

Back in the early 70’s, when I was more of an innocent lad than I am now, I had a summer job in the MIS department of a large industrial tool company where I got to hack out BASIC programs on a teletype-based system. One day, I came across a program called Screwball (author unknown), which provided me with the first and probably the most important lesson I’ve ever learned about user-interfaces.

Screwball was a typical practical joke hack. Some would say it had no social-redeeming value, or that it was a proto-virus. But I can still feel the utter amazement I had when I finally realized what it did. Or rather, what it’s author had done to my head. Upon running Screwball, I (the user) was presented with some silly question, the actual wording of which I no longer remember. Regardless of the answer typed back, the teletype responded with some equally silly or insulting (“screwbally”) answer, and then the program ostensibly exited back to BASIC’s command line shell. Except that it didn’t: if I recall correctly, Screwball used the then-relatively-new CHAIN command to secretly (or rather, silently) transfer control to another program whose entire user-interface was the same as BASIC’s interpreter, only things didn’t work quite right! The programs in the workspace directory wouldn’t run; strange error messages would arise under what used to be normal conditions; etc. When you tried to LIST SCREWBALL.BAS (or whatever), Screwball would list itself with a modification that excluded the final CHAIN instruction, so regaining your bearings in the face of this rogue program’s control over your perceptions was not a trivial task.

I’ve forgotten whether I figured out how Screwball worked, or whether Screwball itself was eventually forgiving enough to let me understand (that is, to truly exit after some not-too-secret incantation), but when I did figure it out I had a real epiphany: a computer program could be about more than just computing, it could be about controlling another person’s perceptions, which, for ill or for good, is the heart of what a user-interface is all about.

As an April Fool’s joke a few years later, I created my own version of Screwball, only this time it was for the entire DEC PDP-10 operating system’s command-line-interface and commonly-run system utilities, which included a variety of user-interfaces, including a full-screen source code text editor, all of which had to be cobbled together enough to fool and annoy an accomplished user for, say, a minimum of 5-10 minutes. Having nothing better to do, it took me two weeks of hacking 18/hours a day to create it in Fortran and assembly. What I learned from the hack was that it is always a lot easier creating an inconsistent interface than it is designing a consistent one. And also that the sleep researchers were right about the natural human sleep/wake cycles being longer than 24 hours in the absence of natural cues, of which most computer rooms of the time were devoid.

The lesson of both these hacks is that a user-interface can immerse the user in a metaphor at a different level than the underlying computation, and if the metaphor is appropriate and self-consistent then all is well and productive for the user. If not, the user will inevitably become frustrated, or will waste time thinking about the computer rather than the task at hand (or maybe will be the butt of a practical joke!). Screwball and its ilk were intentionally designed to be frustrating; our modern graphical user-interfaces are, with only partial success, designed not to be.

Which brings me to why I wrote my FEZ hack for the MacHack/MacHax conference/contest. It’s my little contribution to a more consistent graphical user interface on the Mac, and it partially solves a visual problem that has bothered me for a couple of years now. With machines being so much more powerful these days than ten years ago, doing the extra computation isn’t a problem. And it really looks way cool!

Standard ZoomRects

In the Mac Finder and other graphical desktop user-interfaces, icons represent documents, applications, folders, or other types of system objects. Internally, these are usually files that can be opened or closed, although the act of opening or closing the various classes of icons can mean different things. Usually, opening an icon means that another window gets created on the desktop. It is the Finder’s main purpose in life to support the graphical metaphor that the underlying hierarchical file system is a series of nested folders whose windows show the contents of the folders they represent.

When you double-click on a folder icon in a Finder window, the new window appears at its last position. From a visual logic point of view, this is fairly unambiguous, because you know which icon you just clicked on (and you don’t really care about it once the window is opened), and you know where the window that just opened is. However, in the opposite situation when you close a folder window on the desktop, it is not always easy to see which folder icon among the many icons in the underlying window is the representative icon for the window being closed. Thus was born the idea of zooming rectangles, which is a simple technique to provide animated visual feedback showing the link between a window and its icon elsewhere on the desktop.

The current zooming rectangles algorithm, usually known among Mac programmers as the ZoomRect routine (you have to roll your own; it’s not in the toolbox), takes as input the bounds of an icon, the bounds of a window frame, and the direction of the zoom. Because the animation in general takes place between windows on the desktop, all coordinates must be in global desktop coordinates and all drawing has to be in the global Window Manager port. This in turn means that all drawing must be non-destructive: if you muck with a pixel on the desktop, it is your responsibility to restore it to its old value as soon as possible, because pixels on the desktop (that is, in the Window Manager port) are shared among applications (processes). In the current cooperative multitasking environment, you can take control of the desktop pixels as long as you restore them prior to allowing the system control again. Drawing something twice in exclusive-OR mode is the easiest and fastest method of doing this. [NOTE: In the future, with pre-emptive multitasking, drawing to the desktop will of necessity be even more constrained since any one process may not have any knowledge of when other processes are also writing to the desktop.]

Figure 1: Standard zoom from a visible icon

The standard ZoomRect routine creates a series of rectangles, with each one being part of a simple linear interpolation in global screen coordinates between the two boundary rectangles. Most ZoomRect implementations interpolate between corresponding corners of the starting and ending rectangles; however, for my hack, I began by re-implementing the standard routine to perform the entirely equivalent interpolation between the centers of the two boundary rectangles, and to linearly interpolate between the two sizes. I also chose to avoid the Fixed point routines so I could keep my code simple:

ZoomCenterRect

This new routine does the same thing as a linear ZoomRect(), except that instead of interpolating between the four corners of the two limiting Rects, we interpolate along a line between the two limiting Rects’ centers, and between their two sizes. This sets us up to provide a more general routine that follows any path, instead of the implicit straight line that ZoomRect() would travel. This code doesn't care about the direction of the zoom, which is now implicit in the order of the two rectangular arguments; nor whether either of the Rect’s is empty. Both input Rect pointers must be non-NIL and in global coordinates. The thickness parameter should normally be 1 pixel, but was added during MacHack to enhance the demo by giving more visual weight to the zooming rectangles.

/* 1 */
void ZoomCenterRect(Rect *startRect, Rect *endRect, short thickness)
 {
 Point startCenter,endCenter,startSize,endSize;
 Rect r1,r2,r3,r4; short zoomSteps,x,y,w,h; long i;
 
 if (!InstallDesktop())   // Draw outside of all windows
 return;// or do nothing at all if problem

  // Get centers of the two limiting rectangles
   
 startCenter.h = (startRect->left + startRect->right) / 2;
 startCenter.v = (startRect->top + startRect->bottom) / 2;
 endCenter.h = (endRect->left + endRect->right) / 2;
 endCenter.v = (endRect->top + endRect->bottom) / 2;
 
 // And the starting and ending half sizes
 
 startSize.h = (startRect->right - startRect->left) / 2;
 startSize.v = (startRect->bottom - startRect->top) / 2;
 endSize.h = (endRect->right - endRect->left) / 2;
 endSize.v = (endRect->bottom - endRect->top) / 2;
 
 /* Fill the rectangle queue with empty rectangles so nothing gets drawn 
initially as the queue fills up.  The queue makes for a better zoom effect, 
since there will be more graphic weight to the zooming, and the amount 
of time any particular rectangle is displayed is will be longer. */
 
   SetRect(&r1,0,0,0,0);
 r2 = r1;
 r3 = r1;

 PenSize(thickness,thickness);// For demo only, usually it’s (1,1)
 
 zoomSteps = 16; // Can be set to any number here
 for (i=0; i<=zoomSteps; i++) {  // loops zoomSteps+1 times
 
 // The following arithmetic is susceptable to overflow for short
 // coordinates with large magnitudes (e.g. shorts greater than
 // (32K/zoomSteps), so we do our intermediate calculations in longs
 // by making i a long.  If zoomSteps is a power of 2, it is also a
 // lot faster to replace the divide-by-zoomSteps with a right-shift
 // by that power of 2.  Or you can go back and use the Fixed point
 // that some of the older ZoomRect implementations use.
 
 // Find the i'th intermediate position along line between centers
 x = ((zoomSteps-i)*startCenter.h + i*endCenter.h) 
 / zoomSteps;
 y = ((zoomSteps-i)*startCenter.v + i*endCenter.v) 
 / zoomSteps;

 // And i'th intermediate sizes (also interpolated linearly)
 w = ((zoomSteps-i)*startSize.h + i*endSize.h) 
 / zoomSteps;
 h = ((zoomSteps-i)*startSize.v + i*endSize.v) 
 / zoomSteps;

 // Build the next interpolated rectangle out from its center
 SetRect(&r4,x-w,y-h,x+w,y+h);
 // Draw the newest zooming rectangle into the queue
 FrameRect(&r4);
 // Erase (assuming xor mode) the i-3'rd previously drawn rectangle
 FrameRect(&r1);
 // Shift rectangle queue up by 1, leaving r4 ready to be redefined
 r1 = r2; r2 = r3; r3 = r4;
 
 // Use governor so processor speed doesn't affect zoom
 Wait(1);
 }
 
 // Erase last three zoomrects to empty the queue of drawn zoomrects
 // and to clean up any final desktop drawing
 
 FrameRect(&r1);
 FrameRect(&r2);
 FrameRect(&r3);
 
 ResetDesktop(); // Restore normal drawing environment
 }

The ZoomCenterRect routine in turn relies on some utility routines that will be useful in the coming FEZ enhancements. These routines manage the changing drawing environment:

/* 2 */
#include <LoMem.h>

#define MAXPORTSTACK 16
static GrafPtr portStack[MAXPORTSTACK];// Stack of saved GrafPtrs
static short sp = 0; // Stack entry index

static GrafPort deskPort;
static RgnHandle deskClip;

PushPort

Save the current port on the stack, and set the given port (if non-NIL)

/* 3 */
void PushPort(GrafPtr port)
 {
 if (sp < MAXPORTSTACK) {
 GetPort(&portStack[sp++]);
 if (port) SetPort(port);
 }
 }

PopPort

Restore the last saved port.

/* 4 */
void PopPort()
 {
 if (sp > 0)
 SetPort(portStack[--sp]);
 }

LocalToGlobalRect

Convert a rectangle in place from local coordinates to global ones with respect to the given port. If port is NIL, this will be the current port. This code is Mac specific in that it knows that a Rect structure is two Point structs next to each other.

/* 5 */
void LocalToGlobalRect(GrafPtr port, Rect *r)
 {
 PushPort(port);
 LocalToGlobal( (Point *)r ); // Top left
 LocalToGlobal( ((Point *)r) + 1 );// Bottom right
 PopPort();
 }

GlobalToLocalRect

Convert a rectangle in place from global to local coordinates with respect to the given port. If port is NIL, this will be the current port. This code is Mac specific like above.

/* 6 */
void GlobalToLocalRect(GrafPtr port, Rect *r)
 {
 PushPort(port);
 GlobalToLocal( (Point *)r ); // Top left
 GlobalToLocal( ((Point *)r) + 1 );// Bottom right
 PopPort();
 }

CenterRect

Deliver a rectangle, ans, that is the centered version of a given rectangle, r, within another given rectangle, inside.

/* 7 */
void CenterRect(Rect *r, Rect *inside, Rect *ans)
 {
 short rx,ry,ix,iy;

 // Use the difference between the rectangles' centers as an offset
 
 rx = (r->left + r->right) / 2;
 ry = (r->top + r->bottom) / 2;
 
 ix = (inside->right + inside->left) / 2;
 iy = (inside->bottom + inside->top) / 2;
 
 *ans = *r;
 OffsetRect(ans,ix-rx,iy-ry);
 }

InstallDesktop

Create a new port the size of the current desktop, and initialize its drawing environment for drawing and erasing xor’ed zoomrects. Each successful call to InstallDesktop() must be matched by a call to RestoreDesktop() and unlike the above, they cannot be nested. This routine should deliver TRUE if all goes well, FALSE if memory or other problem.

/* 8 */
int InstallDesktop()
 {
 int installed = TRUE;

   PushPort(NIL);
   OpenPort(&deskPort);   // Sets the current port to deskPort
   CopyRgn(LMGetGrayRgn(),deskPort.visRgn);
 if (MemError())
 return(FALSE);
   deskPort.portRect = (*LMGetGrayRgn())->rgnBBox;
   
   PenPat(&qd.gray); // Set up gray, xor’ed rect framing
   PenMode(patXor);

 deskClip = NewRgn();// And save original clipping region
 if (deskClip)
 GetClip(deskClip);
  else
 installed = FALSE;

 return(installed);
 }

ResetDesktop

Restore the drawing environment in effect when InstallDesktop() was called and returned succesfully.

/* 9 */
void ResetDesktop()
 {
 SetClip(deskClip);
 DisposeRgn(deskClip);
 ClosePort(&deskPort);
 PopPort();
 }

Wait

Delay, on average, by (aBit - .5) ticks

/* 10 */
void Wait(short aBit)
 {
 long soon = TickCount() + aBit;
 
 while (TickCount() < soon) ;
 }

Mixing the Metaphor

One problem with doing a brute force linear interpolation between two global rectangles on the desktop is that the icon’s position may be partially or wholly outside the bounds of the window in which it is drawn. This usually doesn’t occur when you open an icon by double-clicking on it since, by definition, double-clicking on an icon means that it had to be at least partly visible. However, in the Finder it is possible to select an icon, decrease the size of the window it is in so that the icon is no longer visible, and then open the still-selected icon using a keyboard command. It is also possible for the Finder to open a selected but hidden icon via an AppleEvent.

Closing the hidden icon’s opened window poses the same problem, and a bad zoom is also easily seen when you Option-open a folder, which action closes the previous window after opening the folder on top of the window being closed. And the problem occurs in other contexts, such as in Resorcerer’s Dialog Editor, where dialog items can be placed both inside and outside the dialog window’s frame, and the editor supports opening any item into its own information window. Actually, it’s a bit worse in Resorcerer, because the editor also supports formally hiding dialog items (a la HideDItem), which means moving them 16K pixels (or about 19 feet) to the right, guaranteed to be off of even the most absurdly large desktop when converted to global coordinates. Interpolating (in 16 or fewer increments) a series of rectangles from so far away guarantees that nearly all of them will be uselessly offscreen.

Figure 2: Incorrect visual feedback with
standard zooms and hidden widgets

In these not-uncommon cases, the standard ZoomRect algorithm gets called by code that converts the bounds of icon (or item or widget) into global coordinates that are outside the bounds of its window, and ZoomRect zooms blindly to or from what is, as far as the user is concerned, essentially some random spot in a background window or the desktop. This provides erroneous visual feedback for the first part of the zoom (when opening) or the last part (when closing) and thus misinforms the user for no good reason.

So the hacker in me thought (to paraphrase one of the alltime great hackers, Conrad Cornelius O’Donald O’Dell), “Most people stop at Z[oomRect], but not me!”

Frame Evading ZoomRects (or FEZ)

From now on, I (and the source code) will refer to widgets instead of icons, since the problem applies to icons, dialog items, list items, or any other openable-from-within-a-window-into-its-own-window object. To solve the problem of zooming between a widget hidden within a window and a visible window on the desktop, I generalized the path between the centers of the boundary rectangles to be a curve instead of a line. Furthermore, the zoom has to be divided into two parts so that the curve passes through some point in the visible interior of the window whose frame hides the widget’s position. When travelling between this center point and the hidden widget, all zooming rectangles should be clipped to the interior of the window; for the other half of the zoom, clipping can be to the whole desktop (or as we’ll see later, some portion of it). The result is a much more visually pleasing and dynamic-looking zoom that enhances the careful 3D layered illusion of windows on the desktop. The zoom looks like it actually comes right out of the window at you, thereby living up to its name!

Figure 3: Opening a hidden widget with frame clipping

Even with this generalization, though, there are still going to be visual problems that ruin the metaphor of the graphically inviolable window. For instance, these days when opening a widget into a new window, it is no longer the case that the new window will be frontmost: there can be any number of floating palette windows in front of it that need to be zoomed under, not over. This can occur even if your own application has no floating palettes, because the system can put up things like balloons or text input windows for Kanji, etc. So we can no longer discard window information about either end of the zoom, which the standard ZoomRect does by expecting everything in preconverted global coordinates.

To be truly general as well as visually correct, though, you have to take into account the entire window list ordering, and analyze it completely before the zoom. This is because it is quite possible (in fact it frequently happens in the Finder) for there to be intervening windows between a window being closed and the window that holds the widget towards which the zooming rectangles are travelling. To create the illusion that windows are graphically inviolable and layered in a 3D way, you have to force the zoom to treat them in an ordered 3D manner so it can evade them, not travel right through them. With an infinitely visible desktop, a zoom could simply travel out to the side of the union of all windows, change direction, and sneak back into the window list looking for the final destination window. However, on a small desktop, the curved path of the zoom can be arbitrarily complex as it tries to find the best path to its destination while remaining on the visible screen(s).

Note that we are now in hacking-for-fun territory, not in designing-the-best-user-interface territory. There is a tradeoff between pure visual logic and not annoying the user with arbitrarily long animations not part of their immediate work needs. But not late at night at MacHack!

Bezier Splines

One of the easiest ways to create a general curved path without worrying about orientation or boundary conditions is to use a parameterized Bezier spline, which is a segment of a cubic polynomial that conforms to certain boundary conditions. Bezier curves are the basis of PostScript’s curveto operator, and a routine to compute a series of points along the path of a Bezier can prove useful in lots of other contexts. The one I’ve used for years is as follows:

/* 11 */
// Simple 2-D integer coordinates
// We use these instead of standard QuickDraw points because it makes
// 3D generalizations easy (for other uses than zooming rectangles!).
// Note: standard QuickDraw points have the x and y coordinates reversed.

typedef struct { short x; short y; } Point2D;

ComputeBezierSpline

Compute the path of a Bezier spline whose starting and ending knot points are p0 and p3, and whose control (tension) points are c1 and c2. The path should be stored in the array "path", which is expected to be able to hold (numPoints+1) elements, from 0 to numPoints, inclusive. numPoints should be a power of 2 between 2 and 32, inclusive. This routine can be easily generalized to 3D coordinates, and is optimized for fast computation in (long) integers. Since there are no divides, the routine does the right thing regardless of whether p0, c1, c2, or p3 are all different or coincident or whatever. For a derivation of this algorithm, see any textbook on graphics and Bezier splines. This routine assumes that a long is at least 32 bits, and that the magnitude of the size of the bounding box of the curve is not “too large”. On a PowerPC, you’d probably want to do this in straight floating point, without all the integer (fixed point) scaling.

/* 12 */
void ComputeBezierSpline(Point2D *p0, Point2D *c1, 
 Point2D *c2, Point2D *p3,
 Point2D *path, short numPoints)
 { 
 long i, ax,ay, bx,by, cx,cy, curx,cury;
 short s1,s2,s3;

 curx = p0->x; cury = p0->y;// Convert to longs

 //Compute the integer Bezier spline coefficients, a, b, and c

 cx = (c1->x - curx); cx += cx << 1; // c = 3 * (c1 - p0)
 cy = (c1->y - cury); cy += cy << 1;
 
 bx = (c2->x - c1->x); 
 bx += (bx << 1) - cx;  // b = 3 * (c2 - c1) - c
 by = (c2->y - c1->y); 
 by += (by << 1) - cy;
 
 ax = (p3->x - curx) - cx - bx;    // a = (p3 - p0) - c - b
 ay = (p3->y - cury) - cy - by;

 if (numPoints == 32) s1 = 5; // Scaling bit shifter
  else if (numPoints == 16) s1 = 4;
  else if (numPoints ==  8) s1 = 3;
  else if (numPoints ==  4) s1 = 2;
  else     s1 = 1;
 
 s2 = s1+s1; s3 = s2+s1;  // s2 = 2*s1; s3 = 3*s1;
 
 bx   <<= s1;   by <<= s1;// Scale operands up for later, according
 cx   <<= s2;   cy <<= s2;// to the degree in i in loop below
 curx <<= s3; cury <<= s3;// s3 is up to 15 bits worth of scaling

 // Get i’th path point along curve from p0 to p3
 // We already know the endpoints, so save 2 iterations through loop

 path[i] = *p0;
 for (i=1; i<numPoints; i++) {
 path[i].x = (i * (i * (i * ax + bx) + cx) + curx) >> s3;
 path[i].y = (i * (i * (i * ay + by) + cy) + cury) >> s3;
 }
 path[numPoints] = *p3;
  }

In order to create an arbitrarily complex curved path, you can tie a series of Bezier curves together, called a spline. This is why the segment endpoints are often called knots. As long as the closest control points on either side of a knot are colinear with the knot, then the pair of curve segments joined at the knot will be smoothly connected there (that is, the tangent at the knot will exist, and thus anything travelling along the curve won’t suddenly change direction at the knot).

Precomputing the ZoomFrame Array

The first thing I did was create a record called a ZoomFrame, which holds for each end of a zoom segment all the information needed to do the right thing for a single Bezier curve. To do the entire frame-evading zoom, we will have to create an array of ZoomFrames: one for the window being opened or closed, one for the widget, and one for every window between. The array will hold all information needed to animate the zoom. In particular, each ZoomFrame has a precomputed clipping region that must be installed as the zoom passes through the frame’s knot. The array will always have at least two entries. The Fez.h header file for this looks like:

/* 13 */
/*
 * FEZ.h
 *
 * Interface definitions for the FEZ routines.
 * Doug McKenna
 * © 1994 Mathemaesthetics, Inc.
 * All references to Moroccon hats, living or dead, are purely coincidental
 */

#include <math.h>

#define MAXPATH  32
#define SCROLLBARWIDTH    16

// Information about the start and end of a general zoom

typedef struct {

 /* Caller fills these in */
 Rect frame;// Global and/or local coordinates w/r/t its window
 WindowPtr win;  // Its window
 short thickness;// of rectangle lines, normally 1
 
 /* Fez routines use these internally */
 short opening;  // Same as “opening” in NewZoom (theWindow only)
 short isHidden; // Widget visibility flag: used for widget frame only
 RgnHandle clip; // Visible desktop in front of, including this window
 Point2D knot;   // Where zoom path should pass through zoom
 Point2D c0;// Control points for next segment of spline
 Point2D c1;
 
 } ZoomFrame, **ZoomFrameHandle;


/* FEZ Prototypes */

ZoomFrameHandle NewZoom(  ZoomFrame *theWidget, 
 ZoomFrame *theWindow,
 int opening);
void    FrameEvadingZoom(ZoomFrameHandle zoomArray);
void    DisposeZoom(ZoomFrameHandle zoomArray);
void    ZoomCenterRect( Rect *startRect, Rect *endRect, 
 short thick);
void    ComputeBezierPath(Point2D *p0, Point2D *c1,
 Point2D *c2, Point2D *p3,
 Point2D *path, short numPoints);

When opening a new window from a widget, the zoom must be performed prior to the window appearing, but the ZoomFrame array must be created after the window has been placed in its final position in the window list. When closing a window into a widget, the zoom must be performed after hiding the window being closed, but the array should be created before the window is hidden, since HideWindow changes the window list order.

Once the array of frames is created, you can perform the zoom by passing it to the routine FrameEvadingZoom. After the zoom, you must call DisposeZoom to return all the array’s storage back to the primordial memory soup whence it came.

Code for opening a widget might look like this:

/* 14 */
void OpenWidgetWindow(WindowPtr parentWindow)
{
 Rect bounds,rect; Point pt;
 WindowPtr w; WidgetHandle item;
 ZoomFrame start,end; ZoomFrameHandle zoomArray;
 
 // Check first for window whose widget is already in this window
 item = (WidgetHandle)GetWRefCon(parentWindow);
 if ((*item)->openWindow)
 SelectWindow((*item)->openWindow);
  else {
 // Widget not yet opened: open an invisible window for it
 w = AddWidgetWindow(item,&bounds);
 // Deliver its final global position
 if (w) {
 (*item)->openWindow = w; // Attach new window to widget
 rect = (*item)->position;// Get local position of widget
 
 // Precompute the zoom information before showing window
 start.frame = rect; start.win = parentWindow;
 end.frame = bounds; end.win = w;
 end.thickness = start.thickness = 1;
 zoomArray = NewZoom(&start,&end,TRUE);
 if (zoomArray)
 FrameEvadingZoom(zoomArray);
 else {
 // Memory or other problem: do an old-style zoom
 LocalToGlobalRect(parentWindow,&rect);
 ZoomCenterRect(&rect,&bounds,1);
 }

 ShowWindow(w);
 DisposeZoom(zoomArray);
 }
 }
}

Code to close a window back to the widget in another window might look like this:

/* 15 */
void CloseWidgetWindow(WindowPtr w, WindowPtr parentWindow)
 {
 Rect startBox,endBox; WidgetHandle item;
 ZoomFrame start,end; ZoomFrameHandle zoomArray;
 
 item = (WidgetHandle)GetWRefCon(parentWindow)
 // Detach item from its window, which is about to close
 (*item)->openWindow = NIL;

 startBox = (*((WindowPeek)w)->strucRgn)->rgnBBox;
 // Global coords
 endBox = (*item)->position;// Local coords
 // Precalculate the multi-window zoom information before hiding window
 start.frame = startBox; start.win = w;
 end.frame = endBox; end.win = parentWindow;
 start.thickness = end.thickness = 1;
 zoomArray = NewZoom(&end,&start,FALSE);
 
 HideWindow(w);
 
 // Make widget visible if it's behind closed window and needs updating
 // Otherwise, zoom destination may not be obvious.  Updates for other
 // windows can wait.  If updates are time-consuming, this can wait too.
 DoUpdate(parentWindow);

 if (zoomArray)
 FrameEvadingZoom(zoomArray);
  else {
 // No memory or other problem: do an old-style zoom
 LocalToGlobalRect(parentWindow,&endBox);
 ZoomCenterRect(&startBox,&endBox,lineThick);
 }
 
 DisposeZoom(zoomArray);
 }

Figure 4 shows all of the zoom rectangles created after closing the window “Fez 1”, which belongs to the icon in the background window “Fez 0”. The zoom travels underneath the two intermediate windows, “Fez 2” and “Fez 3”.

Figure 4: Closing “Fez 1” creates a zoom that evades intermediate windows “Fez 2” and “Fez 3”

Finally, the workhorse FEZ routines NewZoom, FrameEvadingZoom, and DisposeZoom are:

NewZoom

/* 16 */
FEZ.c
Frame Evading ZoomRects
by Doug McKenna
(c) 1994 Mathemaesthetics, Inc.
This function precomputes an array of ZoomFrames for doing various types 
of zooms on the desktop between theWidget and theWindow frames.  The 
delivered array will have at least 2 entries, with the first and last 
entries the same as the arguments.  When opening is non-zero (TRUE), 
then the zoom travels from theWidget to theWindow; otherwise, the zoom 
travels from theWindow to theWidget.  The delivered array must be passed 
to FrameEvadingZoom() to perform the actual zoom drawing later.

The caller must fill in the initial .win, .frame, and .thickness fields 
of both ZoomFrame arguments before passing them into this routine.  The 
frame rectangle for theWidget should be in LOCAL coordinates with respect 
to theWidget->win.  The frame rectangle for theWindow should be in GLOBAL 
screen coordinates.  In either case, theWindow->win should be in its 
final or current position in the Window List.  If opening, you will want 
to show the window after doing the zoom; if closing, you will want to 
hide the window before doing the zoom.

The ZoomArray is allocated as a relocatable block on the heap and the 
caller must dispose of it with DisposeZoom.

Delivers NIL if not enough memory or other problem.

ZoomFrameHandle  NewZoom( ZoomFrame *theWidget, 
 ZoomFrame *theWindow, int opening)
 {
 RgnHandle clipRgn,tmpRgn; ZoomFrame *zf;
 short numFrames,w,h,width,height,x,y,k,i;
 WindowPeek wp; Rect ans,*bounds,*bbox;
 ZoomFrameHandle zoomArray = NIL;
 int okay = FALSE;
 
 // Reality checks
 if (theWidget==NIL || theWindow==NIL ||
 theWidget->win==NIL || theWindow->win==NIL ||
 theWidget->win==theWindow->win)
 return(NIL);
 
 // Install parameters in theWindow's private fields to pass to FEZ
 theWindow->opening = opening;
 
 // Start with entire visible desktop as clipping region for theWindow
 clipRgn = NewRgn();
 if (clipRgn == NIL) goto cleanup; 
 CopyRgn(LMGetGrayRgn(),clipRgn);
 if (MemError()) goto cleanup;
 
 // Subtract out all visible windows that are in front of theWindow.
 // These are typically floating palettes (or text input windows or
 // balloons).
 
 // For each visible window from front, up to theWindow’s...
 wp = (WindowPeek)LMGetWindowList();
 while (wp!=(WindowPeek)theWindow->win && wp!=NIL) {
 if (wp->visible) {
 // Cut out its structure region
 DiffRgn(clipRgn,wp->strucRgn,clipRgn);
 if (MemError()) goto cleanup;
 }
 wp = wp->nextWindow;
 }
 if (wp == NIL) goto cleanup; // Reality check: should never happen

 // clipRgn now contains all pixels on desktop except those that belong
 // to windows in front of theWindow's.
 
 // Get maximum number of windows for which we might have to
 // create array entries
 
 numFrames = opening ? 2 : 1; // theWindow is invisible when opening
 wp = (WindowPeek)theWindow->win;
 while (wp!=(WindowPeek)theWidget->win && wp!=NIL) {
 if (wp->visible) numFrames++;
 wp = wp->nextWindow;
 }
 if (wp == NIL) {
 // Uh, ohh...theWidget->win is in front of theWindow->win (or
 // not in the window list).  This requires reversing various
 // orders in things, so we’ll punt for now, since this is a
 // rare case (although it’s more likely to happen when closing
 // than when opening).  We deliver NIL to do nothing.
 goto cleanup;
 }
 if (numFrames < 2) {
 // when closing, theWidget->win was found, but was invisible
 goto cleanup;
 }
 
 // Determine whether the widget is wholly visible in its window or not.
 // theWidget's frame is expected to already be in local coordinates.
 
 theWidget->isHidden = TRUE;
 if (SectRect(&theWidget->win->portRect,&theWidget->frame,&ans))
 if (EqualRect(&ans,&theWidget->frame))
 theWidget->isHidden = FALSE;
 
 // Create maximum array storage for entries, initialized to 0.
 zoomArray = (ZoomFrameHandle) NewHandleClear(
 numFrames * sizeof(ZoomFrame));
 if (zoomArray == NIL) goto cleanup;
 
 // Place theWindow at start of array, regardless of zoom direction
 zf = *zoomArray;
 *zf = *theWindow;
 zf->clip = clipRgn; clipRgn = NIL;// Pass off clipRgn to first entry
 
 // Traverse down the window list until we hit the widget's window
 numFrames = 1;
 wp = (WindowPeek)theWindow->win;
 if (wp) wp = wp->nextWindow; // Skip first, we just did it above
 while (wp != (WindowPeek)theWidget->win) {
 if (wp->visible) {
 
 // This is a good place to do any checks to cull windows that
 // pose no threat to the zoom path.  This is a pretty hard
 // problem, but at the very least, we can ignore windows
 // that do not cover the widget's window's content region,
 // to which we will eventually be clipping.
 bounds = &(*wp->strucRgn)->rgnBBox;
 bbox = &(*((WindowPeek)theWidget->win)->contRgn)->rgnBBox;
 if (SectRect(bbox,bounds,&ans)) {
 
 // Need another knot in spline and intermediate ZF
 // Initialize the next ZoomFrame's clipping
 // region as whatever we've got before, minus
 // its window's structure.
 
 tmpRgn = NewRgn();// Use tmp before dereference
 (*zoomArray)[numFrames].clip = tmpRgn;
 if (tmpRgn) {
 DiffRgn((*zoomArray)[numFrames-1].clip,
 wp->strucRgn,tmpRgn);
 if (MemError()) goto cleanup;
 }
  else
 goto cleanup;
 
 // Tell it which window it is evading, and keep same line width
 zf = (*zoomArray) + numFrames;
 zf->win = (WindowPtr)wp;
 zf->thickness = theWindow->thickness;
 
 // We will add information to the array after it has been
 // created, since in theory you may need to do some kind of
 // global search on the entire set of frames to find the best
 // spline path.  In the meantime, we record the window's
 // structure region's bounds to be used in the next stage.
 
 zf->frame = (*wp->strucRgn)->rgnBBox;
 // Global coordinates
 numFrames++;
 }
 }
 wp = wp->nextWindow;
 }
 
 // Set the last zoom to the ending ZoomFrame for widget, and cut the
 // array down to its final size, since we allocated a maximum number
 // of entries above but may have culled some windows above.
 
 (*zoomArray)[numFrames] = *theWidget;
 tmpRgn = NewRgn();
 (*zoomArray)[numFrames].clip = tmpRgn;
 if (tmpRgn)
 CopyRgn((*zoomArray)[numFrames-1].clip,tmpRgn);
  else
 goto cleanup;
 
 // Cut the thing down to size
 numFrames++;
 SetHandleSize((Handle)zoomArray,numFrames*sizeof(ZoomFrame));
 HLock((Handle)zoomArray);
 // Convert theWidget's frame to global coordinates like all
 // the other entries will be.
 zf = (*zoomArray) + numFrames - 1;
 LocalToGlobalRect(zf->win,&zf->frame);
 
 // Got our zoom array, now all we have left to do is compute the
 // frame positions next to the windows, and the knots and Bezier
 // control points within them.  In order to evade each window frame,
 // the zoom has to find its way around the window, either above or
 // below or to the right or to the left (or we could use octants
 // for complete generality).
 
 zf = *zoomArray;
 for (i=0; i<numFrames; i++,zf++) {// For each ZoomFrame...
 
 // For all the internal frames, change the frame position.
 // The end frames are already in their final positions.
 if (i>0 && i<(numFrames-1)) {
 
 // Get width and height of window structure
 width = w = (zf->frame.right - zf->frame.left);
 height = h = (zf->frame.bottom - zf->frame.top);
 
 // For maximum amusement, we set the midway zooms to be
 // on various sides of the window frames, half size.
 // Basically, rotate our zoom around each successive window
 // This maximizes slinkyness and is very silly, but good for
 // demo purposes.  This is the spot in the routine where it
 // would be appropriate to analyze the window pattern as a
 // whole to try to optimize a simple path that evades the
 // group as a whole to get to the destination frame.  For
 // a small number of windows, you could even do a complete
 // backtrack search to find the shortest path, but I'll
 // leave that for another day.
 
 // Turn w and h into an offset to one side of window
 
 k = i & 3; // Cycle every four frames
 switch(k) {
 case 0: w = 0; h = -(h+16); break;// 16 pixels above
 case 1: w =  (w+16); h = 0; break;// 16 pixels to right
 case 2: w = 0; h =  (h+16); break;// 16 pixels below
 case 3: w = -(w+16); h = 0; break;// 16 pixels to left
 }
 
 OffsetRect(&zf->frame,w,h);// Move it outside window
 // Make the thing smaller than entire window bounds
 InsetRect(&zf->frame,width/4,height/4);
 }
 
 // Set knot to the center of its zoom rect frame for all frames
 zf->knot.x = (zf->frame.left + zf->frame.right) / 2;
 zf->knot.y = (zf->frame.top + zf->frame.bottom) / 2;
 }

 // Finally, traverse the array, using line segments between knots to
 // choose spline control points that form a "smooth" path.
 // If the two control points on either side of a Bezier spline knot
 // are colinear, then the spline is continuous through the knot.
 // This means the zoom won't too suddenly change direction as at passes
 // each individual ZoomFrame entry in the zoomArray.  The hard part
 // is figuring out how to set the line that the two control points
 // have to be on so that the path isn't too crazy.  Note that if we
 // have only 2 entries in the array, we don't have any intermediate
 // knots to worry about.
 //
 // Naturally, this code would need to be sped up for older 68K macs,
 // especially since the first time it's called it'll have to load
 // the SANE package, but it seems to work reasonably fast on my
 // PowerBook 180c (68030).
 
 zf = *zoomArray;// It's still locked
 zf->c0 = zf->knot;
 
 for (zf++,k=1; k<(numFrames-1); k++,zf++) {
 
 double theta,dot,cross,sn,cs; Point2D pt;
 long dx0,dy0,dx1,dy1,len0,len1;
 
 // Vector from last knot to this one
 dx0 = zf->knot.x - (zf-1)->knot.x;
 dy0 = zf->knot.y - (zf-1)->knot.y;
 // Vector from this knot to next one
 dx1 = (zf+1)->knot.x - zf->knot.x;
 dy1 = (zf+1)->knot.y - zf->knot.y;
 
 // Get the angle between the two vectors, (dx0,dy0) --> (dx1,dy1)
 dot = dx0*dx1 + dy0+dy1;//Dot product = len0*len1 * cos(theta)
 cross=dx0*dy1-dx1*dy0;  //Cross product = len0*len1 * sin(theta)
 theta = atan2(cross,dot);
 
 // Get the sin and cosine of half the angle
 theta = theta / 2.0;
 sn = sin(theta);
 cs = cos(theta);
 
 // Rotate our initial vector by half the angle, and shrink
 // it to a third its size (purely a heuristic: the larger
 // this vector is, the more boisterous (wider) the Bezier
 // turn will be.  The result will be the vector between control
 // points (through the knot) for this frame.
 x = (cs*dx0 - sn*dy0) / 3.0;
 y = sn*dx0 + cs*dy0 / 3.0;
 
 // Set the two colinear control points for the next knot
 (zf-1)->c1.x = zf->knot.x - x;
 (zf-1)->c1.y = zf->knot.y - y;
 zf->c0.x = zf->knot.x + x;
 zf->c0.y = zf->knot.y + y;
 }
 
 zf->c1 = zf->knot;
 
 HUnlock((Handle)zoomArray);
 okay = TRUE;    // Tell cleanup not to throw zoomArray away

cleanup:
 if (clipRgn) DisposeRgn(clipRgn);
 if (!okay) {
 DisposeZoom(zoomArray);
 zoomArray = NIL;
 }
 
 return(zoomArray);
 }

DisposeZoom

/* 17 */
/*
 * Throw away the given zoomArray (if it's non-NIL) and throw away all
 * internal clipping regions (and whatever else) as well.
 */

void DisposeZoom(ZoomFrameHandle zoomArray)
 {
 if (zoomArray) {
 long numZooms = GetHandleSize((Handle)zoomArray) 
 / sizeof(ZoomFrame);
 while (numZooms-- > 0) {
 RgnHandle clip = (*zoomArray)[numZooms].clip;
 if (clip) DisposeRgn(clip);
 }
 }
 }

FrameEvadingZoom

/* 18 */
/*
 * Given an array of ZoomFrames, as previously created by NewZoom, animate
 * the zoom on the desktop.  The array is always in canonical order from
 * theWindow to theWidget, so if we are opening (as found in theWindow)
 * we have to traverse the array backwards.
 */

void FrameEvadingZoom(ZoomFrameHandle zoomArray)
 {
 Point midCenter,startSize,midSize,endSize,pt;
 Rect r1,r2,r3,r4,ans,midway,clip,content,widgetBounds;
 short zoomSteps,zoomSteps2,
 x,y,w,h,dx,dy,n,numPairs,numFrames,zfInc;
 long i,j; Point2D p0,c1,c2,p3,path[MAXPATH+1]; 
 int    useDive;
 WindowPeek wp,*list; 
 ZoomFrame*start,*end,*theWindow,*theWidget;
 RgnHandleclip1=NIL,clip2=NIL,clip3=NIL,clip4=NIL,
 tmpClip;
 
 // Reality check, since NewZoom can deliver NIL for strange situations
 if (zoomArray == NIL)
 return;
 
 // Draw outside of all windows; deskPort becomes current port
 if (!InstallDesktop())
 return;
 // From now on, always return via cleanup so port gets restored
 
 // Fill the clipped rectangle queue with empty rectangles
 // so nothing gets drawn as the queue fills up.  The queue makes
 // for a better zoom effect, since there will be more graphic
 // weight to the zooming, and the amount of time any particular
 // zoomrect is displayed is much longer.
 
   SetRect(&r1,0,0,0,0);
 r2 = r1;
 r3 = r1;
 // Queued clipping regions 1 through 4 are allocated empty
 clip1 = NewRgn(); clip2 = NewRgn();
 clip3 = NewRgn(); clip4 = NewRgn();
 if (clip4 == NIL) goto cleanup;
 
 // Now do a zoom between each pair of adjacent ZoomRects in the
 // array, in which there is always at least one pair (2 entries).
 
 HLock((Handle)zoomArray);
 numFrames = GetHandleSize((Handle)zoomArray) 
 / sizeof(ZoomFrame);
 numPairs = numFrames - 1;
 
 theWindow = (*zoomArray) + 0;
 theWidget = (*zoomArray) + (numFrames-1);
 
 // Each iteration slides [start,end] up or down by one in the array
 
 if (theWindow->opening) {
 start = theWidget;
 zfInc = -1;// Down
 }
  else {
 start = theWindow;
 zfInc = 1; // Up
 }
 end = start + zfInc;// end is always adjacent to start
 
 for (n=0; n<numPairs; n++,start+=zfInc,end+=zfInc) {
 
 // Get the starting and ending half sizes
 
 startSize.h = (start->frame.right - start->frame.left) / 2;
 startSize.v = (start->frame.bottom - start->frame.top) / 2;
 endSize.h = (end->frame.right - end->frame.left) / 2;
 endSize.v = (end->frame.bottom - end->frame.top) / 2;
 
 // Knots are the same regardless of opening or closing
 p0 = start->knot;
 p3 = end->knot;
 
 if ((theWindow->opening && start==theWidget) ||
 (!theWindow->opening && end==theWidget)) {
 
 // Get content area minus the scroll bar and grow icon areas
 // This assumes window has both right and bottom scroll bars
 // To be truly general, we should be using a content region.
 content = theWidget->win->portRect;
 content.right -= SCROLLBARWIDTH;
 content.bottom -= SCROLLBARWIDTH;
 
 // Find a rectangle within the window to serve as an intermediate
 // destination for the zoom that is completely contained in the
 // visible area of the destination zoom window.  When the zoom
 // reaches midway, we'll change the clipping region.
 midway.left = content.left;
 midway.top = content.top;
 midway.right = (content.right +
 (theWidget->frame.right-theWidget->frame.left))/2;
 midway.bottom = (content.bottom +
 (theWidget->frame.bottom-theWidget->frame.top))/2;
 CenterRect(&midway,&content,&midway);
 
 // If midway is larger than window, use inset window content
 if (midway.left<content.left || 
 midway.top<content.top ||
   midway.right>content.right || 
 midway.bottom>content.bottom) {
 midway = content;
 InsetRect(&midway,8,8);
 }
 
 // Convert to global coords and get center and half-sizes

 LocalToGlobalRect(theWidget->win,&midway);
 midSize.h = (midway.right - midway.left) / 2;
 midSize.v = (midway.bottom - midway.top) / 2;
 midCenter.h = (midway.right + midway.left) / 2;
 midCenter.v = (midway.bottom + midway.top) / 2;
 
 // Get window content as clipping rectangle in global coords
 clip = content;
 LocalToGlobalRect(theWidget->win,&clip);
 
 // But have to take intersection of it with the
 // final window clipping region
 tmpClip = NewRgn();
 if (tmpClip) {
 RectRgn(tmpClip,&clip);
 SectRgn(theWidget->clip,tmpClip,theWidget->clip);
 DisposeRgn(tmpClip);
 }
 
 // Set control (tension) points to other side of
 // window (in global coordinates)
 pt.h = (content.left + content.right) / 2;
 pt.v = (content.top + content.bottom) / 2;

 if (theWidget->frame.bottom > midway.bottom)
 pt.v = content.top + CONTROLINSET;
 if (theWidget->frame.top < midway.top)
 pt.v = content.bottom - CONTROLINSET;
 if (theWidget->frame.right > midway.right)
 pt.h = content.left + CONTROLINSET;
 if (theWidget->frame.left < midway.left)
 pt.h = content.right - CONTROLINSET;

 PushPort(theWidget->win);
 LocalToGlobal(&pt);
 PopPort();
 
 c1.x = c2.x = pt.h;
 c1.y = c2.y = pt.v;
 useDive = TRUE;
 }
  else {
 // Not final widget window: still evading window frames
 useDive = FALSE;
 // Since the control points for the segment between each pair are
 // stored in only one ZoomFrame, we have to use the fact that
 // we're opening or not to get the right ones.
 if (theWindow->opening) {
 c1 = end->c1;   // Traversing array backwards
 c2 = end->c0;
 }
  else {
 c1 = start->c0; // Traversing it forwards
 c2 = start->c1;
 }
 }
 
 // Precompute the spline's path, including both endpoints
 
 ComputeBezierPath(&p0,&c1,&c2,&p3,path,MAXPATH);
 
 // You could interpolate among bounding pen sizes if you wanted
 // to give more of a depth effect, but this would probably only
 // be worth doing in a higher resolution world.
 PenSize(start->thickness,start->thickness);
 
 zoomSteps = MAXPATH;// Must be power of 2
 zoomSteps2 = zoomSteps/2;// Halfway point
 
 for (i=0; i<=zoomSteps; i++) {    // loops zoomSteps+1 times
 
 x = path[i].x;
 y = path[i].y;
 
 if (useDive) {
 // If opening, start is theWidget and end is before it in
 // the array. If closing, end is theWidget and start is
 // after it in the array.  In either case, we have to change
 // the clipping region half way through the zoom, when it
 // reaches midway.  This is another heuristic that looks
 // pretty good most of the time, although occasionally the
 // clipping changes to early or late.  Ideally we should
 // be using two Bezier segments to guarantee that the zoom
 // rect being at midway happens at a known time.
 if (i <= zoomSteps2) {
 // First half of zoom
 w = ((zoomSteps2-i)*startSize.h + i*midSize.h) 
 / zoomSteps2;
 h = ((zoomSteps2-i)*startSize.v + i*midSize.v)
 / zoomSteps2;
 SetClip(start->clip);
 }
  else {
   // Second half of zoom: interpolate from midway to
 // end within window
   j = i - zoomSteps2;
 w = ((zoomSteps2-j)*midSize.h + j*endSize.h) 
 / zoomSteps2;
 h = ((zoomSteps2-j)*midSize.v + j*endSize.v)
 / zoomSteps2;
 SetClip(end->clip);
 }
 }
  else {
 // Get i'th intermediate size (interpolated linearly) for whole zoom
 w = ((zoomSteps-i)*startSize.h + i*endSize.h) 
 / zoomSteps;
 h = ((zoomSteps-i)*startSize.v + i*endSize.v) 
 / zoomSteps;
 // Set clipping to exclude all higher windows
 if (theWindow->opening) SetClip(end->clip);
  else     SetClip(start->clip);
 }
 
 // Build the next interpolated rectangle in queue and draw it
 GetClip(clip4);
 SetRect(&r4,x-w,y-h,x+w,y+h);
 FrameRect(&r4);
 
 // Erase (assuming xor mode) the i-3'rd previously drawn rectangle
 SetClip(clip1);
 FrameRect(&r1);
 
 // Shift clipped rectangle queue up by 1, leaving r4
 // ready to be redefined
 r1 = r2; r2 = r3; r3 = r4;
 tmpClip = clip1;
 clip1=clip2;clip2=clip3;clip3=clip4;clip4=tmpClip;
 
 // Use governor so processor speed doesn't affect zoom.  Because
 // of the computation involved, this isn’t really needed on the
 // slower machines.
 Wait(1);
 }
 }
 
 HUnlock((Handle)zoomArray);
 
 // Erase last three zoomrects to empty the queue of drawn zoomrects
 
 SetClip(clip1); FrameRect(&r1);
 SetClip(clip2); FrameRect(&r2);
 SetClip(clip3); FrameRect(&r3);
 
cleanup:
 if (clip4) DisposeRgn(clip4);
 if (clip3) DisposeRgn(clip3);
 if (clip2) DisposeRgn(clip2);
 if (clip1) DisposeRgn(clip1);
 
 ResetDesktop(); // Restore normal drawing environment
 }

That’s it - “Sheik Yerbouti”, as FZ (Frank Zappa) once said.