TweetFollow Us on Twitter

From Algorithm to Animation: the Sequel

Volume Number: 19 (2003)
Issue Number: 7
Column Tag: QuickTime

From Algorithm to Animation: the Sequel

Making QuickTime movies which illustrate abstract processes

by Jay Martin Anderson

THE ORIGINAL

In the November 1993 issue of MacTech (volume 9, number 11), I described how I made a QuickTime movie of an algorithm from computational mathematics. In the intervening ten years, QuickTime has grown and matured, the Mac OS has crossed the divide between Classic and OS X, and several generations of IDEs have come and gone.

My interest in making QuickTime movies to illustrate algorithms from computer science and mathematics has not. Consequently, I wish to present an update of the technique used to make animations of algorithms, and apply it to a theorem from beginning calculus which my colleagues challenged me to illustrate this year.

THE PROBLEM

The Department of Mathematics at Franklin and Marshall College includes both mathematics and computer science and frequently enjoys sharing problems in one area with the other. In the spring of 2003, my mathematician colleagues challenged me to construct a way to depict the Mean Value Theorem (MVT) which states that, for a suitably "nice" function f(x) on a range a <= x <= b, somewhere (some x = c, a <= c <= b) the slope of the function, f'(c) is equal to the "rise over run" of the function, (f(b)-f(a))/(b-a).

I chose to take a particular function f(x) = x3 on the range -1 <= x <= 1, trace along the function showing a line tangent to the curve at each point, and stop when the tangent line had the same slope as the "rise over run," which is 1.

THE PARADIGM

At F&M we have developed a paradigm for constructing algorithm animations. We divide the moviemaking application into three parts: the model, the view, and the controller.

The model contains the algorithm to be visualized. In this example, it is the function and its derivative. The state of the model is the value of x, along with the value of f(x) and f'(x).

The view contains the graphical elements necessary to illustrate the model. It is in the view that a single picture of a single state of the model is developed. In our work beginning in 2003, the view is developed with OpenGL. In the view we will draw the graph of the function, the tangent line at every value of x, the line which represents the "rise over run," and any tangent line with the same slope as "rise over run."

The controller does all the initialization and cleanup necessary for the moviemaking application. In particular, it does all the work necessary to pass individual views to QuickTime for the formation of a movie. Most importantly, the controller contains the timing, which signals the model to change its state and the view to generate a new picture. The controller will continue to ask the model to change its state until the value of x has spanned the entire range of interest.

Many movies are divided into "acts" and "scenes," much like a real theater piece. This provides a simple way to modularize the model and the view, and is particularly useful if the animated view of the model is more complex than simply moving an object along a path. For this simple example, acts and scenes are not necessary.

Our movies are also annotated. A view of a state of the model is also accompanied by a few sentences of text which explain what the view shows. The resulting QuickTime movie has one video track, and one text track for each (natural) language necessary. The natural language feature of QuickTime makes it particularly easy to construct movies in English, German, Italian, etc. The text annotation in this movie gives numerical values for x and f'(x).

Beginning in 2003, our development platform for algorithm animation is Apple's Developer Tools, including Project Builder and Interface Builder. The application is developed in Objective-C, using Cocoa classes. The model is a subclass of NSObject; the view is a subclass of NSOpenGLView; and the controller is also a subclass of NSObject. Since the movie, and not the application which creates it, is the object of this exercise, the graphical user interface is kept as simple as possible, often including only a button "Make Movie" and perhaps some widgets to select among choices for the movie.

The connection between the strictly object-oriented Objective-C and Cocoa classes, and the older QuickTime API is not always elegant. Nonetheless, it is that connection which is perhaps the most significant contribution of this article. Almost every time the controller has to move information between the model or the view and QuickTime, some conversion is necessary.

Using Interface Builder

We begin with Project Builder and construct a new project, a Cocoa application. Interface Builder allows us easily to construct a window and view of appropriate size, place whatever GUI widgets we need in the window, construct the model and controller objects, and generate some source code for the model-view-controller system.

Launch Interface Builder by double-clicking the MainMenu.nib icon, which is found inside the Resources folder of the Files pane of the project. Make the window an appropriate size, and drag a Custom View onto the window. Make the Custom View be an appropriate size as well. Create a subclass of NSOpenGLView, such as MyOpenGLView, and make the Custom View be an instance of MyOpenGLView.

Drop whatever widgets you need into the window. In this example, we use only a button, labeled Make Movie.

Create a subclass of NSObject called MyController and a subclass of NSObject called MyModel. Within MyController, create an Action method, for example, createMovie. Also within MyController, create Outlets, which are instances of the classes MyModel and MyOpenGLView, respectively. Likewise, in the class MyOpenGLView, create an Outlet, which is an instance of the class MyModel.

Make instances of these classes, and generate code for these classes.

Build connections as follows: from any widgets, such as the Make Movie button to the instance of MyController, with the target of the createMovie method; from the instance of MyController to the instance of MyModel; from the instance of MyController to MyOpenGLView; and finally from the instance of MyOpenGLView to the instance of MyModel. The connection from the button to the method means that the button sends the createMovie message to the controller. The connection from the controller to the model means that the controller can send messages (usually inquiries) to the model, and likewise to the view. The connection from the view to the model means that the view can send messages (again, usually inquiries) to the model.


Figure 1. Using Interface Builder. The window contains the view, a subclass of NSOpenGLView, and one button. The view is connected to the class MyModel, so that the view may inquire the state of the model.

This completes the work with interface builder; save the nib and continue with Project Builder.

The Code

The work of managing QuickTime is done with the createMovie method of the controller object. This also includes code to provide an interface, albeit awkward, between the Objective-C classes of Cocoa and the "legacy" code of QuickTime. Three points bear special mention.

First, OpenGL draws into a context, which is described by a pixel format. QuickTime accepts images from a pixMap, which is part of the GWorld data structure. The function CopyNSBitmapImageRepToGWorld accomplishes the task of copying pixels from the first to the second environment. It is based on the assumption of 32-bit pixels in each structure. Curiously, the copying of pixels requires an NSBitmapImageRep, which is four bytes wider than the context.

Second, QuickTime constructs a movie file using an FSSpec. The FSSpec must be derived from a path or file name in the "classic" Macintosh format, and it must appear as a Pascal string. The function QTUtils_ConvertCToPascalString serves to convert a C-string to a Pascal string.

Finally, the image drawn by OpenGL is inverted when it is copied to QuickTime. Given that the QuickTime movie is the object of this exercise, it seems simplest to construct the OpenGL drawings upside-down, and let the pixel copying to QuickTime invert them to the proper orientation.

The code for the class MyController, as well as for portions of the classes MyModel and MyOpenGLView, along with all header files, can be found on the website

http://eDisk.fandm.edu/~jay.anderson/mactech/example.html

The model is the simplest unit in this example. The methods f and ff serve to calculate the function and its derivative. The method changeState advances a point along the curve by equal increments in the x-direction, and computes the corresponding value of the function and its derivative. The method changeState also looks for matches between the slope of the curve and the "rise over run," and records the matches.

Listing 1: MyModel.m

MyModel

A portion of the class MyModel, which encapsulates the algorithm to be illustrated and its data 
structures.  Shown here are the method changeState, and the methods that evaluate the function and 
its derivative.  The remainder of the class, and the header file MyModel.h are found on the website.

@implementation MyModel
- (void)changeState:(int)frNo
{
   if (frNo == 0)
   {
      // beginning frame is blank, with only an annotation
      strcpy(annotation, "MEAN VALUE THEOREM.  Compare
 rise/run to slope of graph.");
   }
   else
   {
      // as frame number goes from 0 to 200, x goes from -1.0 to 1.0 in 200 steps
      x = -1.0 + frNo/100.0;
      y = [self f:x];
      slope = [self ff:x];
      sprintf(annotation, "x = %5.2f, y = %5.2f, slope =
 %5.2f", x, y, slope);
      if (fabs(slope - ror) < 0.01) 
      {
         // slope matches rise/run; record this position, append extra annotation
         match = 1;
         xMatch[nMatches++] = x;
         strcat(annotation, "\rSlope matches rise/run: mean
 value theorem!");  
      }
      else                          
         match = 0;
   }
}
- (float)f:(float)z
{ return z*z*z; }
- (float)ff:(float)z
{ return 3*z*z; }
@end

The view is responsible for drawing the curve, the "rise over run" line, a point and tangent line which moves along the curve as the state of the model changes, and any matches between the slope of the curve and the rise-over-run line. These are simple OpenGL primitives: point, line and line-strip. Colors, the point size and the line width are chosen for viewing ease.

Listing 2: MyOpenGLView.m

MyOpenGLView

The method drawRect from the class MyOpenGLView; the remainder of the class and the header file 
MyOpenGLView.h are found on the website.  This method is invoked when the display message is sent 
to the view.  It draws each frame of the movie.  

@implementation MyOpenGLView
- (void)drawRect:(NSRect)rect
{
   float x, y, slope;
   short match;
    
   glClear(GL_COLOR_BUFFER_BIT);   // clear the screen
   x = model->x;
   y = model->y;
   slope = model->slope;
   match = model->match;
   
   /* Draw the components of the frame:  the graph of the function, the rise/run line,
      the point at (x, y), and the slope of the graph at that point.
   */
   [self drawGraph];                  
   [self drawRR];
   [self drawPoint:x:y];
   [self drawSlope:x:y:slope];
 
   /* Draw a tangent line at each place where the slope of the function matches the
      rise/run line.
   */   
   if (model->nMatches > 0)
   {
      int i;
      for (i = 0; i < model->nMatches; i++)
         [self drawMatch:i];
   }
   // show it!
   glFlush();
}
@end

The text annotations are developed within the model, and left in a string. In the controller, this string is copied to the text handler, just as the image is copied to an image compressor. Color, font, and size of text can be chosen when the text handler is constructed.

Lights! CAMERA!  ACTION!

The controller runs a simple loop to construct successive frames of the movie. In particular, the controller sends the changeState message to the model, and then the display message to the view. This image is then copied to QuickTime and compressed. In addition, the controller sends a getText message to the model to acquire the annotation to be placed into the text track.

Results

The model-view-controller paradigm has been implemented for making QuickTime movies that illustrate algorithms in Java and in Cocoa/Objective-C. The Cocoa/Objective-C implementation allows the use of OpenGL with QuickTime in a workable, if awkward, marriage of Objective-C classes with "legacy" QuickTime APIs. This opens up abstract moviemaking to the standard of OpenGL, including three-dimensional graphics. The Java implementation, which is not described here, does not require the awkward connection between software components, but does not provide easy access to OpenGL.


Figure 2. One frame of the Mean Value Theorem movie. The test point has moved from x = -1.00 to x = -0.32, and has found one spot where the slope of the curve matches the rise/run line. The text track is shown in white on blue beneath the video track.

Besides the sample movie described here, our work in 2003 and beyond includes constructing animations of algorithms from computational geometry, such as the triangulation of a polygon, constructing and searching in kd-trees and range trees, and more. Our recent work includes animations of algorithms for computing the convex hull, for the intersection of many line segments and for recognizing the polygon in which a point lies. Sample movies are posted on our web site (begin at http://eDisk.fandm.edu/~jay.anderson) as they become available.

ACKNOWLEDGMENTS

Significant assistance has come from Apple Computer, from whom code to construct QuickTime movies, media, and tracks has been borrowed; and from Big Nerd Ranch and Aaron Hillegass, whose Cocoa programming book, course and advice were enormously useful.


Jay Martin Anderson is the Richard S. and Ann B. Barshinger Professor of Computer Science at Franklin and Marshall College in Lancaster, Pennsylvania. Once a physical chemist, he has been teaching computer science since 1978 and making QuickTime movies since 1992. His interests include many aspects of computer graphics, including cartography and computational geometry; opera, theatre, and bicycling. He can be reached at jay.anderson@fandm.edu.

 
AAPL
$112.65
Apple Inc.
+3.24
MSFT
$47.52
Microsoft Corpora
+1.78
GOOG
$511.10
Google Inc.
+6.21

MacTech Search:
Community Search:

Software Updates via MacUpdate

BBEdit 11.0.2 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
ExpanDrive 4.2.1 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Adobe After Effects CC 2014 13.2 - Creat...
After Effects CC 2014 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous After Effects customer). After Effects CS6 is still available... Read more
Command-C 1.1.7 - Clipboard sharing tool...
Command-C is a revolutionary app which makes easy to share your clipboard between iOS and OS X using your local WiFi network, even if the app is not currently opened. Copy anything (text, pictures,... Read more
Tidy Up 4.0.2 - Find duplicate files and...
Tidy Up is a complete duplicate finder and disk-tidiness utility. With Tidy Up you can search for duplicate files and packages by the owner application, content, type, creator, extension, time... Read more
Typinator 6.3 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
GraphicConverter 9.5 - Graphics editor w...
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
Toast Titanium 12.0.1 - The ultimate med...
Toast Titanium goes way beyond the very basic burning in the Mac OS and iLife software, and sets the standard for burning CDs, DVDs, and now Blu-ray discs on the Mac. Create superior sounding audio... Read more
QuickBooks 2015 16.0.2.1422 R3 - Financi...
Save 20% on QuickBooks Pro for Mac today through this special discount link QuickBooks Pro 2013 helps you manage your business easily and efficiently. Organize your finances all in one place, track... Read more
Remotix 3.0.6 - Access all your computer...
Remotix is a fast and powerful application to easily access multiple Macs (and PCs) from your own Mac. Features: Complete Apple Screen Sharing support - including Mac OS X login, clipboard... Read more

Latest Forum Discussions

See All

Shift - Photo Filters Designed By You (...
Shift - Photo Filters Designed By You 1.0 Device: iOS Universal Category: Photography Price: $.99, Version: 1.0 (iTunes) Description: | Read more »
Elastic Drums (Music)
Elastic Drums 1.0 Device: iOS iPhone Category: Music Price: $3.99, Version: 1.0 (iTunes) Description: *** Introduction price 3,99$ instead of 7,99$ *** Elastic Drums is a music app with 6 channels of synthesized drum sounds, a step... | Read more »
Fireworks Simulator (Games)
Fireworks Simulator 1.0.8 Device: iOS Universal Category: Games Price: $.99, Version: 1.0.8 (iTunes) Description: *** 50% discount – For a short time only *** You can play Fireworks Simulator on these devices: - iPhone 5, 5s, 5c, 6,... | Read more »
The Hit List — Simply Powerful Tasks, To...
The Hit List — Simply Powerful Tasks, To-Dos, Projects, & Reminders 2.0 Device: iOS iPhone Category: Productivity Price: $9.99, Version: 2.0 (iTunes) Description: >> LAUNCH SPECIAL: The Hit List 2 for iPhone is ONLY $9.99... | Read more »
Mahjong Journey Review
Mahjong Journey Review By Jennifer Allen on December 18th, 2014 Our Rating: :: STEADY MATCHINGiPad Only App - Designed for the iPad Aimed at the more laid back gamer, Mahjong Journey isn’t for everyone, but those looking for some... | Read more »
Emoji Type - custom keyboard with predic...
Emoji Type - custom keyboard with predictive emojis 0.4.0 Device: iOS iPhone Category: Utilities Price: $.99, Version: 0.4.0 (iTunes) Description: Emoji Type is custom keyboard for iOS 8 that auto suggests emojis as you type. ABOUT... | Read more »
Game of the Year 2014 – 148Apps Staff Pi...
The end of 2014 is almost here, which can only mean one thing. Okay it can mean a lot of things, but in this specific context it means Game of the Year lists! Which is why the 148Apps staff have all picked their favorites from the past year. And why... | Read more »
UponPixels Review
UponPixels Review By Jennifer Allen on December 18th, 2014 Our Rating: :: CREATIVE TYPOGRAPHYUniversal App - Designed for iPhone and iPad Add cool typography and objects to your photos with the easy to use UponPixels.   | Read more »
The Vikings are Coming! CastleStorm’s Ne...
The Vikings are Coming! CastleStorm’s New Update Adds a Survival Mode Posted by Jessica Fisher on December 18th, 2014 [ permalink ] | Read more »
Duet Display (Productivity)
Duet Display 0.3.3 Device: iOS Universal Category: Productivity Price: $9.99, Version: 0.3.3 (iTunes) Description: Duet Display allows you to use your iPad or iPhone as an extra display. Developed by a team of ex-Apple engineers,... | Read more »

Price Scanner via MacPrices.net

Save up to $400 on MacBooks with Apple Certif...
The Apple Store has Apple Certified Refurbished 2014 MacBook Pros and MacBook Airs available for up to $400 off the cost of new models. An Apple one-year warranty is included with each model, and... Read more
Save up to $300 on Macs, $30 on iPads with Ap...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
iOS and Android OS Targeted by Man-in-the-Mid...
Cloud services security provider Akamai Technologies, Inc. has released, through the company’s Prolexic Security Engineering & Research Team (PLXsert), a new cybersecurity threat advisory. The... Read more
KMI MIDI K-Board Great Gift for Amateur &...
The K-Board is a MIDI Nano keyboard for music creation for iPad, Android, And computers; the easiest way to make music with iPads & Android tablets, and Mac, Windows, or Linux computers. Ultra-... Read more
Amazon offers 15-inch 2.2GHz Retina MacBook P...
 Amazon.com has the 15″ 2.2GHz Retina MacBook Pro on sale for $1699 including free shipping. Their price is $300 off MSRP. Stock is limited, so act now if you’re interested. Read more
Holiday sales continue: MacBook Pros for up t...
 B&H Photo has new MacBook Pros on sale for up to $300 off MSRP as part of their Holiday pricing. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1699... Read more
Holiday sale: Mac minis available for up to $...
 B&H Photo has new 2014 Mac minis on sale for up to $80 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 1.4GHz Mac mini: $459 $40 off MSRP - 2.6GHz Mac mini: $629 $70 off... Read more
Google Search App For iOS Gets A Major Makeov...
Google has given iOS users an early Christmas present with a substantial update of it’s not-very-often-upgraded Google Search app. Google Search has been my go-to tool for Web searches since it was... Read more
ShopKeep Apple Pay And Chip Card Reader Avail...
ShopKeep, a cloud-based technology provider to more than 10,000 small business owners to manage retail shops and restaurants with iPads, has released its new Apple Pay and chip card reader. This... Read more
Holiday sale! 27-inch 5K iMac for $2299, save...
 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

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.