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.
/* front face */ glBegin(GL_QUADS); 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); glEnd();
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:
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.
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.