Inventor case study

Inventor is interesting in that it uses the Interpreter pattern in a non-linguistic domain. We will start with a toy example, regular expression parsing, to introduce virtually all of the concepts needed to understand Inventor's design.

Regular expression parsing

Design Patterns gives the example of parsing strings to match a regular expression, e.g.
raining & (dogs | cats)*
You can imagine writing a C procedure to do this: check if the first word is "raining", then loop, checking for the word "dogs" or "cats". The main disadvantage is that the meaning of the regular expression is mixed together with the procedural actions needed to parse it. Furthermore, if you wanted to perform another task with the same expression, e.g. compute the minimum length of a matching string (in this case, 7 characters), then the meaning of the expression would be again be replicated and mixed in with the procedural actions.

A better way, given in the book, is to implement parsing as the traversal of the abstract syntax tree for the regular expression. The tree has nodes for literals, repetition, and alternation. The above expression would be represented like this:

To parse a string, you call the parse method of the root of the tree, which calls the parse methods of its children, which call the parse methods of their children, etc. The current state of the parse, e.g. the current position in the input string, would be passed as argument and modified by these methods. So each node's code can be very simple and understandable, like matching a single literal, while their combined effect is complex.

You can store and transmit the parser in this abstract state (as a tree), so it is portable to different implementations of the nodes. You can also have regular expression plug-ins that you treat as black boxes and insert into another regular expression. For example, a component that looks for balanced parentheses. Anything that implements the parse method is fair game.

So now you want to compute the minimum length of a matching string. Supporting new tasks is easier now that the regular expression is abstracted, but has some caveats. Each task on the regular expression is represented as a method implemented by each node type and as traversal state to be modified by the method. So if you want to support a new task, you must provide an implementation of the traversal method for every node type. This is tricky in statically-typed, single-dispatch languages like C++ since you would need access to the source code of each node (the Visitor pattern (from Design Patterns) can help). This isn't possible for plug-ins since you're supposed to regard them as black boxes. What all this means is that new tasks should be rare and should have a graceful way of dealing with nodes which don't support them.

Computer Graphics

Inventor takes the same approach to graphics as we just took to regular expression parsing. Before Inventor, graphics were often done in a procedural way. For example, this is the GL code for drawing a multi-colored 3D box:
/* front face */
glColor3f(0.0, 0.7, 0.1);       /* green */
glVertex3f(-1.0, 1.0, 1.0);
glVertex3f(1.0, 1.0, 1.0);
glVertex3f(1.0, -1.0, 1.0);
glVertex3f(-1.0, -1.0, 1.0);
/* back face */
glColor3f(0.9, 1.0, 0.0);       /* yellow */
glVertex3f(-1.0, 1.0, -1.0);
glVertex3f(1.0, 1.0, -1.0);
glVertex3f(1.0, -1.0, -1.0);
glVertex3f(-1.0, -1.0, -1.0);
/* top side face */
glColor3f(0.2, 0.2, 1.0);       /* blue */
glVertex3f(-1.0, 1.0, 1.0);
glVertex3f(1.0, 1.0, 1.0);
glVertex3f(1.0, 1.0, -1.0);
glVertex3f(-1.0, 1.0, -1.0);
/* bottom side face */
glColor3f(0.7, 0.0, 0.1);       /* red */
glVertex3f(-1.0, -1.0, 1.0);
glVertex3f(1.0, -1.0, 1.0);
glVertex3f(1.0, -1.0, -1.0);
glVertex3f(-1.0, -1.0, -1.0);

As in the regular expression example, we see that the meaning of the scene is mixed together with the procedural actions needed to render it. If we wanted to perform another task with this box, e.g. compute its intersection with a line, then the meaning of the scene would be again be replicated and mixed in with the procedural actions.

Inventor instead implements rendering as the traversal of a tree, or scene graph. The tree has nodes for geometry, like cubes, cones, and spheres, as well as lights, color, orientation, and various other aspects that would normally be done procedurally.

For example, this scene:

corresponds to this scene graph:

To render a graph, you call the render method of the root node, which calls render on its children, and so on. The traversal state passed to each node is the current drawing state, e.g. the current color and position, which may be modified by the node, e.g. if the node is a translation node. ("Rendering" is thus interpreted as any action on the drawing state, like changing the current color or lighting model, not just putting figures on the screen.)

Using an explicit scene graph to drive the computation makes it easy to:

  • construct a scene, because of the higher abstraction level
  • modify the scene, e.g. for animation
  • define different actions on the scene, like finding where it intersects a line (a "ray pick" action) or obtaining a bounding box
  • store and transmit scenes, e.g. to be displayed using another render engine (or perhaps built!)
  • support plug-in nodes, like third-party nodes which make sounds when they are "rendered"


    Inventor uses five kinds of nodes:
    1. Group
    2. Shape
    3. Property
    4. Sensor
    5. Engine

    Group nodes are the intermediate nodes in the tree. Inventor's group nodes do things like:

    Shape nodes produce the actual graphics. There are nodes for common objects like cubes, cones, spheres, and text as well as nodes for custom polyhedrons, lines, and points.

    Property nodes only serve to modify the drawing state. This includes color, lights, orientation, texture, font, and scale.

    Sensor and engine nodes are used for Inventor's unique style of animation. Each node in the scene graph has fields which affect how it renders itself, e.g. the sphere node has a "radius" field. To animate the sphere, just change the radius between renders. Inventor keeps track of the nodes which have had their fields changed, so it knows when to redraw and more importantly who to redraw. (Inventor also remembers the effect each node had on the drawing state, so if a node's fields are the same and the drawing state is the same then Inventor uses this cached effect instead of calling the render method again. This can significantly speed up animation.)

    To change the field of a node, you can wire it to the output of a sensor or engine node. Inventor uses the Observer pattern to wire fields together. A sensor broadcasts notification of user input, or the time, or certain events in the scene like a collision between objects. A calculator engine simply outputs a constant value which is some deterministic function of its fields (usually the outputs of other sensors or engines). By wiring these together you can create a static scene graph description of a dynamic, animated figure. This is the power of the Interpreter pattern.

    Programming languages

    Programming languages use the Interpreter pattern to describe and perform arbitrary computations. This is particularly evident in Scheme interpreters like SCM, which literally traverse the abstract syntax tree of the program, using the current naming environment and data heap as traversal state. As before, the advantages of interpreting programs (as opposed to machine code) include readability, modification, porting to different hardware, and supporting different actions like type checking, compilation, and complexity measurement.

    It is interesting to consider the analogs of Inventor's scene graph actions on a program. Rendering, of course, corresponds to execution. Bounding box might correspond to estimating resource consumption. And ray pick? It could determine which part of the program was responsible for this part of the output.

    Thomas Minka
    Last modified: Mon Jan 13 21:18:07 EST 1997