The MatchTool
Oak and Maple Trees
Grammar to Build Tree
Fractal Snowflake Pattern
Golden Spiral Pattern
MatchTool Spiral
Overview

Graphical Search and Replace is the graphical analog to textual search and replace in text editors. It gives people the ability to find all objects in a graphical editor document that exhibit a set of graphical properties (including shape, object type, line color, fill color, line style, etc...), and change either those properties or a set of other properties.

In addition to making it very easy and fast to propagate many similar changes throughout a graphical document in the course of every day graphical editing, graphical search and replace can also be used to create shapes via graphical grammars, to find targets for graphical macros, and to create graphical templates.

Examples

The first panel on the left shows the MatchTool, our utility for Graphical Search and Replace. At the top are two search and replace panes (containing an oak and maple leaf in this example). The user specifies via a set of checkboxes which graphical properties are significant in the search and replace examples. This pattern was used to change the oak leaves to maple leaves in the pink panel below it.

Another way to create a maple tree is shown in the third panel. Initially we start with the search pattern on the left and replace a black line with a brown line and three black lines. This substitution is repeated until we have a brown tree with black lines instead of leaves. Finally we replace the black lines with leaves using the replacement pattern on the right. In effect, the tree was created using a graphical grammar.

The final three panels show other graphical grammars. In the first of these we create a triadic koch snowflake by starting with a triangle and repeatedly replacing all lines with set of 4 connected segments shown in the replace pane.

In the next panel we create a golden spiral by starting with a blue rectangle and repeatedly replacing blue rectangles of that shape (at any rotation and scale), with a blue square, white arc, and smaller blue rectangle as shown in the replace pane.

The final panel shows the "MatchTool Spiral", which we created by starting with a line, and repeatedly replacing it with the letters "MATCHTOOL" in a spiral arc, followed by another line. Since it would be difficult to position the letters in the Replace pane by hand, we used the MatchTool to actually create the Replace pane contents, in a manner we won't go into here.

Although the MatchTool is a fun and easy utility for creating shapes from graphical grammars, it is more frequently used to eliminate the drudgery of making repeated substitutions in a regular scene - as demonstrated in the first example where oak leaves were replaced by maple leaves.

History

David (DJ) Kurlander developed Graphical Search and Replace while a summer intern at Xerox PARC in 1987. Eric Bier suggested the idea, and DJ built the first version of the MatchTool for the Gargoyle graphical editor at PARC. Later, DJ and Eric wrote a patent application and SIGGRAPH paper on the topic. Back at Columbia, DJ implemented "MatchTool 2" for the Chimera graphical editor. MatchTool 2 was extended to support constraint-based search and replace and also became an iteration mechanism for executing graphical macros by example on all objects in a scene that match a graphical search description. Graphical search and replace became the third chapter in DJ's doctoral dissertation, Graphical Editing by Example.

Publications

David Kurlander and Eric Bier. Graphical Search and Replace. Computer Graphics, 22, 4 (August 1988). Proceedings of SIGGRAPH ‘88. pp. 113-120. August 1988. Atlanta, Georgia.

David Kurlander. Graphical Editing by Example. Doctoral Dissertation, Computer Science Department, Columbia University. July 1993.

Videos

Eric Bier and David Kurlander. The MatchTool: An Introduction to Graphical Search and Replace.  SIGGRAPH Video Review, issue 48. 1989.

David Kurlander. Graphical Editing by Example: A Demonstration. SIGGRAPH Video Review, issue 89. 1993. Extended abstract in INTERCHI ‘93 Proceedings, p. 529. Click here for the video, or here for the abstract.

Also See