[Next] [Previous] [Top]

Zoomable Graphical Sketchpad

IMPLEMENTATION

Pad++ is implemented in C++ under various versions of the Unix operating system using the standard X graphics library system. It currently runs on SGIs, Suns, IBM RS-6000s, PCs running Linux, and should be trivially portable to other Unix systems. Pad++ is implemented as a widget in Tcl/Tk and thus allows applications to be written in the interpreted Tcl language. All Pad++ features are accessible through Tcl making it unnecessary to write any new C++ code.

Efficiency

In order to keep the animation frame-rate up as the dataspace size and complexity increases, we utilized several standard efficiency methods in our implementation, which taken together create a powerful system. We have successfully loaded over 600,000 objects (with the directory browser) and maintained interactive rates of about 10 frames per second. Even when objects are not visible, appropriate checks must be done each time there is movement to see if those objects should now be visible. The key is that the rendering system takes a time roughly proportional to the number of visible objects, independent of the number of objects in the database (on average).

Briefly, the efficiency methods we use in Pad++ include:

• Spatial Indexing: Objects are stored internally in a hierarchy based on bounding boxes which allow fast indexing to visible objects.
• Clustering: Pad++ automatically restructures the hierarchy of objects to maintain a balanced tree which is necessary for the fastest indexing.
• Refinement: Render fast while navigating by using lower resolution, and not drawing very small items. When the system is idle for a short time, the scene is successively refined, until it is drawn at maximum resolution.
• Level-Of-Detail: Render items differently depending on how large they appear on the screen. If they are small, render them with lower resolution.
• Region Management: Only update the portion of the screen that has been changed. Linked with refinement, this allows different areas of the screen to refine independently.
• Clipping: Only render the portions of large objects that are actually visible. This applies to images and text.
• Adjustable Frame Rate: Animations and zooming maintain constant perceptual flow, independent of processor speed, scene complexity, and window size. This is accomplished by rendering more or fewer frames, as time allows.
• Interruption: Slow tasks, such as animation and refinement, are interruptible by certain input events (such as key-presses and mouse-clicks). Animations are immediately brought to their end state and refinement is interrupted, immediately returning control to the user.
• Ephemeral Objects: Certain objects that represent large disk-based datasets (such as the directory browser) can be tagged ephemeral. They will automatically get removed when they have not been rendered for some time, and then will get reloaded when they become visible again.
• Optimized Image Rendering: The code to render zoomed images has been very carefully optimized and allows real-time zooming of high-resolution images.

Scripting Language Interface

An important consideration in the design and implementation of Pad++ is how to create a very fast and efficient graphics system, and yet still make it extensible. We wanted to make sure that we and others would be able to easily experiment with new interface mechanisms. Originally, Pad++ was implemented entirely in C++, making it very difficult for anyone but the authors to add new objects and interactions. Even for the authors, going through the compile and link cycle was very slow and tedious, making it difficult to do much experimentation.

We decided to create an interpreted scripting language interface to Pad++ to get around this problem. This approach is becoming quite common, and works well as long as the scripting language is at the right level. On one side, you want as much as possible to be in the scripting language so that the system is as easy to modify as possible. On the other side, it is critical that all speed-critical code be written as efficiently as possible. In a system like ours, there are three classes of code, each of which have different speed requirements:

• Create objects: Slow -- Scripting language is fine
• Handle events: Medium -- Small amount of scripting language is ok
• Render scene: Fast -- C++ or byte-compiled languages only

Rendering is done in C++ (for built-in Pad++ items) or in an efficient byte-compiled language such as KPL (for user defined widgets or animated items). This results in animation performance which is quite good, even on Linux based PC platforms.

We chose Tcl [25] as our primary scripting language, largely because it comes in combination with Tk, a Motif-like library for creating graphical user interfaces. Pad++ is built as a new widget in Tk. This allows it to be used in combination with standard non-zooming widgets such as menubars, buttons, sliders, etc. This lets us make complete applications while we build and debug widgets within Pad++. Just as importantly, it provides a mechanism to compare zoomable interfaces with traditional interface mechanisms in the same system.

The Tcl interface to Pad++ is designed to be very similar to the interface to the Tk Canvas widget (which provides a surface for drawing structured graphics). While Pad++ does not implement everything in the Tk Canvas yet, it adds many extra features. The Tcl interface to Pad++ is summarized here to give a feel for what it is like to program Pad++.

We are also experimenting with other scripting languages which are better suited to some tasks -- primarily those requiring higher speeds. As previously mentioned, we use KPL for high-speed animations. We also are considering incorporating an alternative language, such as Scheme, for more general programming which needs high speed interaction.

TCL Interface

There are many commands that create and manipulate objects, each referring to the object's unique integer id. Objects may be grouped by using tags, a mechanism for associating data with each object. Every command can be directed to either a specific object id or to a tag, in which case it will apply to all objects that share that tag. Each Pad++ widget has its own name, and all commands start with the name of that widget. In the examples that follow, the name of the widget is .pad.

Examples:

• A red rectangle with a black outline is created whose corners are at the points (0, 0) and (2, 1):

  .pad create rectangle 0 0 2 1 -fill red -pen black

   

• Put item number 5 at the point (3, 3), make the object twice as big, and make the object anchored at that point on its northwest corner:

  .pad itemconfig 5 -anchor nw -place "3 3 2"

   

• Specify that item number 5 should be visible only when its largest dimension is greater than 20 pixels and less than 100 pixels.

  .pad itemconfig 5 -minsize 20 -maxsize 100

   

It is straightforward to make scripts get evaluated when specific events hit objects, or groups of objects. Simple macros get expanded within the event script to specify information specific to that event. Some examples follow:

• Make all items with tag foo turn blue when the left button of the mouse is pressed over any of those objects:

  .pad bind foo <ButtonPress-1> {

  .pad itemconfig foo -fill blue

  }

   

• This is a single event binding for a group of objects that affects just the object clicked on, using the macro '%O' to expand to the specific object:

  .pad bind foo <ButtonPress-1> {

  .pad itemconfig %O -fill blue

  }

   

Some basic navigation and searching mechanisms are provided by the Tcl interface. A few basic ones are:

• Smoothly go to the location (1, 0) with a magnification of 5, and take 1000 milliseconds for the animation:

  .pad moveto 1 0 5 1000

   

• Smoothly go to the location such that object number 37 is centered, and fills three quarters of the screen, and take 500 milliseconds for the animation:

  .pad center 37 500

   

• Return the list of object ids that contain the text "foo"

  .pad find withtext foo

Events

As briefly mentioned, it is possible to attach event handlers to items on the Pad++ surface so that when a specific event (such as ButtonPress, KeyPress, etc.) hits an item, the appropriate event handler is evaluated. This system operates much as it does with the Tk Canvas widget, but there are several significant additions:

• Modes

  Every event handler is defined for a specific mode. The mode is a simple text string and defaults to all if it is not specified. The Pad++ surface has a set of active event modes associated with it (that always includes the all mode). Only those event handlers whose mode is currently active will be fired. This allows the creation of many different event handlers that are selectable by setting the Pad++ mode.

• Event Searching Protocol

  When an event hits an item and there are no event handlers defined for that item, there is a well-defined event searching protocol that specifies which other items will be searched for event handlers. If the event went through a portal, then the portals are checked for event handlers. The portals are checked from the bottom up, that is, in the reverse order that event went through the portals. To summarize, the searching order is as follows:

 

1. Most specific object

2. Objects associated by tag ("all" being last)

3. Portals (and associated tag objects)

 

• PortalIntercept event

Portals can intercept events as the events pass through them with the PortalIntercept event. PortalIntercept is a new event sequence recognized by the Pad++ bind command. PortalIntercept event handlers get called for every event that passes through a portal in top down order. They do not replace other event handlers, but instead get called before those handlers. A PortalIntercept command may execute any code, and then it can return a special value that can modify the event. The modifications include killing the event, stopping the event at the portal rather than passing it through, changing the list of active modes on the surface the event hits for this event, and changing the coordinates of the event.

• Passing Events

When an event is fired, it is often useful for a handler to pass the event on to the next most general event handler. This is most commonly used to have a single event trigger the event handlers for specific items as well as classes of items.

Messages

Items can send arbitrary messages to other items or groups of items. This message sending facility is analogous to the Event mechanism, including the Searching Protocol and passing mechanism.

Callbacks

In addition to the event bindings that every item may have, every Pad++ item can define Tcl scripts associated with it which will get evaluated at special times. There are currently three types of these callbacks:

• Render Callbacks

  A render callback script gets evaluated every time the item is rendered. The script gets executed when the object normally would have been rendered. By default, the object will not get rendered, but the script may render the object at any time with the renderitem function. An example follows where item number 22 is modified to call the Tcl procedures beforeMethod and afterMethod surrounding the object's rendering.

  .pad itemconfig 22 -renderscript {

  beforeMethod

  .pad renderitem

  afterMethod

  }

   

  Instead of calling the renderitem command, an object can render itself. Several rendering routines are available to render scripts, making it possible to define an object that has any appearance whatsoever. Items which define a render script are called procedural objects and are used for creating animated objects (those that change the way they look on every render) and custom objects. They also can be used to implement semantically zoomable objects, since the size of an object is available within the callback.

• Timer Callbacks

  A timer callback script gets evaluated at regular intervals, independent of whether the item is being rendered, or receiving events.

• Zooming Callbacks

  Zooming callback scripts are evaluated when an item gets rendered at a different size than its previous render, crossing a pre-defined threshold. These are typically used for creating efficient semantically zoomable objects. Since many objects do not change the way they look except when crossing size borders, it is more efficient to avoid having scripts evaluated except for when those borders are crossed.

Extensions

Pad++ is extensible with Tcl scripts (i.e., no C/C++ code). This provides an easy to use mechanism to define new Pad++ commands as well as compound object types that are treated like first-class Pad++ objects. That is, they can be created, configured, saved, etc., with the same commands you use to interact with built-in objects, such as lines or text. These extensions are particularly well-suited for widgets, but can be used for anything.

Extensions are defined by creating Tcl commands with specific prefixes. Each extension is defined by three commands which allow creation, configuration, and invocation of the extension, respectively. Defining the procedures makes them automatically available to Pad++. No specific registration is necessary. All three procedure definitions are necessary for creation of new Pad++ object types, but it is possible to define just the command procedure for defining new commands without defining new object types.

Efficiency

 

Scripting Language Interface

 

TCL Interface

 

Events

 

Messages

 

Callbacks

 

Extensions

[Next] [Previous] [Top] [Contents] [Index]

Copyright Computer Science Department, The University of New Mexico

Web Accessibility