Explicit Dependency/Sharing Frameworks

The following brief breaks down into several sections:
1) References to frameworks for interactive modeling/animation.
2) Overview of how Apprentice accomplishes DAG traversal (should be similar to Inventor).
3) Presentation of alternative retained-mode designs.

An interactive modeling/animation framework embodies a system that manages and displays objects with attributes of shape and appearance over time. Although there are many existing frameworks in use, this brief does not attempt to describe or critique all or some of them. Rather, the purpose of this brief is to present a limited view of framework design based on an incomplete survey of interactive animation framework papers, experience from one prior work (Apprentice), and thoughts about improved designs intended to provide better performance through state optimizations using explicit dependencies.

_Section 1: References_

Although I have read a number of papers on animation frameworks, the two papers of interest to this brief present frameworks different from Inventor's scene DAG design. However, I would like to point readers to "An Object-Oriented 3D Graphics Toolkit", _Computer Graphics_, Vol. 26 No. 2, July 1992, pg. 341, in which Paul Strauss and Rikk Carey describe the framework that becomes/is Inventor.

The first paper is "An Object-Oriented Framework for the Integration of Interactive Animation Techniques", _Computer Graphics_, Vol. 25 No. 4, July 1991, pg. 105, in which a very pronounced group from Brown University (van Dam, Hughes, etc.) presents a framework for interactive modeling and animation.

In section 3, I would like to focus on two aspects of their framework:
a) Objects maintain a list of "messages" (attributes) that describe the object's time-varying "structure" (shape and appearance); and
b) Objects are related by delegation rather than inheritance.

The second paper is "Goal-Oriented Design and Correction of Articulated Figure Motion with the TRACK System", _Computers & Graphics_, Vol. 18 No. 4, 1994, pg. 443, in which Thalmann, et. al., propose a system for interactive articulated figure management.

In section 3, I would like to focus on several aspects of their framework:
a) Nodes retain geometry, topology and display information (shape and appearance); and
b) Nodes maintain direct and inverse transformation matrices for both object local and global coordinate systems.

I would also refer readers to the Talisman home page for hardware-based coherence optimization techniques:
http://www.research.microsoft.com/SIGGRAPH96/Talisman/

Readers will benefit from an understanding of Open Inventor, and I refer interested readers to the Open Inventor reference texts (_Inventor Mentor_, _Inventor Toolmaker_, _Open Inventor Reference_).

_Section 2: Apprentice_

Apprentice is a C++ scene-graph library based on the Strauss et. al. paper referenced above, the Open Inventor texts (_Mentor_, _Reference_, and _Toolmaker_), and the QvLib library for VRML.

Apprentice DAG traversal is invoked using actions. Actions traverse nodes of the DAG, collecting properties in elements of a state, later relying on elements for the shape and appearance of objects.

Two properties of the Inventor action mechanism that are possible performance issues:
a) Implicit dependencies between property and shape nodes require traversal to acquire attributes of objects; and
b) Application-defined scene graph layouts can potentially behave poorly, which has led to a number of optimization techniques external to the design of the framework.

In section 3, I would like to focus on alternative frameworks that overcome these issues.

In fact, these two issues are closely related.

Implicit dependencies are implemented in Inventor so that during traversal, properties are associated with elements in the traversal state, then elements in the traversal state are associated with shapes. The indirect relationship between properties and shapes is defined by the traversal order of the scene DAG. Typically, traversal happens from the top of the scene DAG to the bottom, and from left to right. (I guess you could think of this as preorder traversal, where the current node is the root, the left subtree is represented by the first node in the ordered list of children, and the right subtree is represented by the next sibling in the parent's child list.)

The indirect relationship that elements provide is really at the core of both how the Inventor DAG system intends to minimize state changes and how the OpenGL state machine is defined. Elements in Inventor have an almost one-to-one correspondence to the OpenGL state.

The implicit relationship between properties and shapes, however, has the disadvantage that neither the rendering library nor the application can acquire attributes of objects without traversal (assuming that the relationship between properties and shapes remains implicit).

Thalmann et. al. comment on this aspect of Inventor:

"Even a more recent approach like INVENTOR, which manages a powerful Direct Acyclic Graph (DAG), does not meet our needs. This is mainly because the information is organized in a procedural display list fashion that requires some traversal to get global information about any component of interest."

I believe that some modeling, animation, and data visualization techniques may be difficult or impractical to implement without defining explicit relationships between properties and shapes.

In addition, the application, rather than the Inventor framework, is given the task of organizing the DAG for performance. Poor performance from bad scene DAG layouts has spawned an SGI document on the topic. (see http://www.sgi.com/Technology/Inventor, Documents, Optimizing...) "Good" scene DAGs have consolidated and non-redundant properties like condensed face sets, intelligent use of separators, etc.

But even the best scene DAG layout on one system may not necessarily perform well on other systems. A scene DAG designed for a system with plentiful texture memory will have a serious performance problem if it performs a lot of texture swapping on a system with limited texture memory.

I beg the question, then, why are implicit dependencies used in Inventor and other systems?

I would suggest several reasons, although there may be more:
1. Intuitive for state machines. The implicit dependency in Inventor scene DAGs is an intuitive system to use for state machines, like OpenGL. The structure of the scene DAG has a direct correspondence with state changes in OpenGL, and when properly organized by applications, can result in optimized performance with typical rendering engines.
2. Memory optimization. For M shapes that all share N properties, an Inventor scene DAG will have N+M-1 pointers to associate them. Explicit dependencies could potentially define 2N*M pointers for a mutual association between M shapes and N properties.
3. Ease-of-use. The hierarchical nature of the scene DAG is easy to understand.

In the next section, I will propose that explicit dependencies may also share these properties in a well designed framework.

_Section 3: Alternative Designs_

My intention with this brief was to describe what I learned from the implementation of Apprentice, what I perceive to be its strengths and weaknesses, so that, hopefully, the next generation of general-purpose frameworks (OpenGL++/OpenGLPlus) will be an improvement upon rather than a standardization of existing systems.

When I look at how to approach problems like API design, I think the number one consideration is to require the least amount of effort from the application programmer. After all, APIs are meant to make our jobs easier.

With retained-mode scene graph APIs specifically, I believe the best design would be one in which the library/driver rather than the application decides how best to optimize the input data, and I believe that this can be accomplished with good framework design. OpenGL clearly demonstrates this concept, allowing the underlying driver to choose how best to batch and process requests. I believe OpenGL++ (OpenGLPlus) should follow in its footsteps.

I would like to present a design different from Inventor, one that uses explicit rather than implicit dependencies to relate attributes with shape and appearance. I am not, by any means, trying to introduce this as a novel concept... there are certainly implementations out there that explicitly relate attributes with shapes. I would like to show that a framework with explicit dependencies is relatively equivalent to a framework with implicit dependencies, that many of the characteristics of one may be applied to both if designed properly.

I would also like to show how explicit dependencies may solve the performance issues inherent in implicit dependencies, mainly that traversal will be minimized when acquiring attributes of objects. For application programmers, this results in possibly better performance when acquiring many fine-grained attributes. For library/driver designers, this results in possibly better performance by allowing the library/driver to optimize the traversal order of the scene graph based on any arbitrary set of conditions. For instance, an example I presented earlier used a scene DAG with a lot of texture swapping. A library/driver given mutually-associated explicit dependencies between texture nodes and shape nodes could traverse shape nodes based on their association with texture nodes, rendering all shape nodes associated with the first texture node, then rendering all shape nodes associated with the second texture node, etc. Another driver with plentiful texture memory could choose to traverse based on some other criteria, say an algorithm that on-the-fly determines an approximated best traversal pattern for a given scene graph.

Allow me, then, to set up some requirements. A framework using explicit dependencies must:
1. Have structure characteristics similar to its implicit counterpart ( in this case, the Inventor scene DAG ). This allows direct translation between the two frameworks. In fact, it might be reasonable to maintain an explicit dependency framework _inside_ the API as part of a caching/optimization mechanism, with direct associations between objects of the internal explicit framework and objects from the implicit, application-defined scene DAG. Hmmm...
2. Have a memory footprint similar to its implicit counterpart.
3. Be easy to learn. This may require a shift in perspective about how scenes are defined.
4. Provide better performance for acquiring fine-grained attributes of objects.
5. Provide the library/drivers with a system for optimizing the scene graph.

1. Have structure characteristics similar to its implicit counterpart ( in this case, the Inventor scene DAG ).The first requirement is actually quite easy to demonstrate and will probably illustrate for readers the direct association between the two systems. Apprentice tracks nodes that set attributes in the traversal state. When a property node sets the value of an element in the state, the pointer to that node is stored with that element (for the purpose of cache validation, not implemented in Apprentice). Further down the scene DAG, a shape reads the element value and uses it as one attribute of its shape or appearance. The pointer to the node that set the element is still valid and an association may be established between the shape node and the property nodes it depends upon.

If one were to write an action that traversed the scene DAG in order, storing pointers to property nodes (indirectly obtained through elements) in a member list of shape nodes, one would have an explicit dependency graph between a shape node and all of the property nodes upon which it depends. (Note: accumulated elements would require a slightly more complicated association from successor to predecessor.) One could literally throw away the implicit scene DAG after executing this action, relying on the explicit dependency graph defined in the member list of each shape node for subsequent actions.

Now we've created a whole bucket of problems, haven't we... our memory requirement just shot up to "M shapes * N properties" number of pointers, and worse yet, each node has its own set of properties that need to be set into the state, making the number of state changes M*N. "What happened to your second requirement?"

2. Have a memory footprint similar to its implicit counterpart.Fain, dear Hamlet, all is well.

Traversal of the Inventor scene DAG results in properties being set into the state, then retrieved from the state by shapes. In effect, each step in the traversal process results in an inheritance of the state from the previous step, aggregated with the property change of the current step. If you step through N properties then you would have accumulated N state changes. If you then step through M shapes, the accumulated N state changes are implicitly applied to the shapes.

With regard to the example in part C, rather than storing the pointers to all N properties in all M shapes, you can group pointers to the N properties into one "composite" object, then point all M shapes to that composite object.

N + M pointers!

(Because we eventually want mutual association for acquiring attributes, we may eventually need 2(N+M) pointers.)

In fact, many of the techniques that are described in books like Design Patterns can be used in an explicit dependency framework to handle these types of situations.

[Digression: It has occured to me that translating an Inventor scene DAG to an explicit dependency framework, then optimizing it based on certain conditions and translating it back to Inventor may be one method for automatically removing some of the bottlenecks described in the Optimizing Open Inventor document and for optimizing an implicit scene DAG for a specific system.]

There are more complex scenarios that may have behaviors different from this example, but I think this is enough to illustrate the kind of organization that would reduce the memory footprint of an explicit framework.

3. Be easy to learn. This may require a shift in perspective about how scenes are defined.The Inventor file format is very, very easy to learn. It certainly is appropriate for VRML and other applications.

The difficulty with moving to explicit frameworks is that its native representation in a file format may rely heavily on object-oriented concepts, whereas the Inventor file model more closely resembles collections of discrete structures (there's no real concept of inheritance in the file format).

I believe, however, that common user interface models can appropriately represent the explicit framework. Essentially, when users select an object in their scene, then select a color for that object from a palette, the user is associating the color property with the object's appearance. This association is represented directly using explicit dependencies by associating the shape object with the color object in the shape object's dependency list.

This is a very subjective requirement, however, and I don't believe it will be answered unless we have concrete instances of explicit frameworks.

4. Provide better performance for acquiring fine-grained attributes of objects.Given that a shape object has mutual associations with all of its attributes, either through delegation, association, or proxy, acquiring attributes requires nothing more than finding the appropriate attribute in the dependency list (and possibly traversing up the dependency hierarchy for accumulated attributes, such as the model matrix, assuming the cache is invalid for the bottom-most attribute in the hierarchy.)

For some objects, acquiring attributes may simply be retrieving a value referenced through a member pointer to the attribute node. For instance, either directly or indirectly, a cone shape points to all of its attributes, color, texture, material, lighting, matrix, etc. If an application wants to retrieve the color of the cone, it searches the dependency list for the color node, retrieves the pointer, then calls get(). If members of the cone frequently refer to the color, a pointer to the color could be stored as a member variable for fast response, eliminating the need to search the dependency list.

The TRACK system from Thalmann, et. al., maintains both direct and inverse transformation matrices for both object local and global world coordinate systems, such that:

"...a modification of the motion root, inducing a different motion propagation flow, can be managed efficiently without changing the topology of the hierarchy."

I believe this characteristic is equally applicable to an explicitly defined matrix hierarchy. The model matrix associated with an arbitrary object in an explicit framework may be easily coupled/decoupled with any other matrix.

This is not a characteristic of an implicit framework. If you move an object out of one context and into another, you must recreate the attributes of the object from its previous context.

(The fifth requirement is one of the most important, IMHO, so I'm going to take some time to explain it thoroughly.)

[Note: Finally, the end. This evening while browsing a book store, I discovered a paper from the Springer-Verlag book Object Oriented Programming for Graphics, 1995? (I don't remember the names of the editors) The paper was from the Third Eurographics Conference on Object Oriented Graphics and the authors were Conner and van Dam (I don't remember the name of the paper). The paper covers subject areas that overlap this brief significantly (delegation systems, implicit/explicit sharing between objects), and anyone interested in this brief should seek out and read that paper. Some of the terminology in the paper is different from the terminology I have been using. The most important difference in terminology is "dependency" vs. "sharing". I would define dependency as unidirectional sharing. The Springer-Verlag book is ~$75.]

5. Provide the library/drivers with a system for optimizing the scene graph.A shift of responsibility for optimizing scene graphs from the application to the library has several implications. Applications may be better suited to understand the structure of their data while libraries better understand the performance issues of the underlying rendering engine. I believe that several performance optimization issues may be affirmed without in-depth analysis, for the purpose of this brief:
a) Implicit frameworks prevent or discourage libraries from restructuring the scene DAG for optimal performance.
b) Techniques to optimize implicitly defined scene DAGs at the application or user level may not guarantee optimal relative performance across a wide range of software and hardware platforms.
c) Diverse rendering engines (both hardware and software) available now, and especially in the future as the market expands, will have different requirements for achieving optimal performance.

If you are a vendor writing drivers for a retained-mode library, you are seriously going to want to consider how your system will perform with a variety of scene DAGs. If the library uses an implicit framework, an explicit dependency representation may allow you to optimize performance for your system.

This is what I'm going to explore in this subsection, how explicit dependencies allow performance optimization of a scene DAG. For the sake of simplicity, this subsection will not consider a framework with mutual association for acquiring attributes. In addition, composite attribute nodes cause multiple levels of indirection from shape nodes to attributes, and for the purpose of explaining these fundamental concepts, I'm going to leave composites out of the examples.

(Hmmm... if I dig the hole deeper, maybe I'll hit a spring that will fill the hole with water and carry me out.)

More specifically, I'm going to use two hypothetical systems, one system that greatly benefits from front-to-back ordering during rasterization and has virtually unlimited texture memory, and another system with object linear rasterization performance but limited texture memory. (I'm not sure if these are good real-world examples, but they expand upon earlier examples and adequately demonstrate the concepts explained in this subsection.)

The scene DAG we input to both of these hypothetical systems is the same. It consists of many shapes, each bound to one of a limited set of textures, each with a list of vertices, and each with a unique transformation that scatters them around the scene. The dependencies for each shape include a reference to a transformation, a reference to a list of vertices, and a reference to a texture.

The first hypothetical system achieves optimal performance when the traversal order is sorted by z-depth front-to-back. This requires some criteria for determining the z-depth of objects; we will simply use a dumb method based on the z component of the first transformed vertex in the object. In addition, sorting by depth requires that the library maintain a list of all shapes to be sorted. To assist with state validity, the library also maintains a state list of pointers for each property node type, such that the pointer to the most recent property node selected into the state (and its attribute(s) set into the state machine) is maintained in the list.

The first task of a rendering action in this system is to sort the shapes. The library starts with an unsorted list of shapes to traverse. For each shape, the library finds the transformation reference and vertex list reference in the shape node's dependency list, gets the first vertex from the vertex list and transforms it with the transformation. Given the transformed vertices from each shape, the library sorts the list by z-depth (using ).

Given the sorted z-depth list, the library can now traverse the list of shapes in front-to-back order. For each shape, the library checks the shape's dependency list against the list of valid pointers in the state list, setting attributes that don't match the state. The scene DAG we defined earlier may cause mismatches for textures and would definitely cause mismatches for transformations; each shape node has a unique transformation that would need selecting into the state; most likely, the texture would change repeatedly and would need selecting into the state. Finally, the library renders the shape.

It is important to note here that if the library wants front-to-back traversal, the library gets front-to-back traversal, no matter what the impact is on other aspects of the state. This is inherent in the method the library chooses to decide the traversal order. It's a feature!

If a library knows the impact of state changes on performance, it can gauge the type of traversal algorithm that will provide optimal performance.

The second hypothetical system wants the traversal order sorted by texture. This requires that the library maintain an unsorted list of all textures. This also requires that texture nodes have a reference list of pointers to all associated shape nodes. Again the library maintains a state validity list.

No sorting is necessary, the library is able to immediately jump into traversal using the list of texture nodes. For each texture node, the library traverses the dependency list that points to shape nodes. For each shape node in the texture node's list, the library checks the shape's dependency list against the list of valid pointers in the state list, setting attributes that don't match the state. The scene DAG we defined earlier will cause a texture mismatch on the first shape node of each texture node. Subsequent shape nodes that share a texture node will not cause a mismatch. Again, because each shape node has a unique transformation, it will cause a mismatch. Finally the library renders the shape.

Again, the library wanted traversal based on minimizing texture cache misses and that is exactly what it got, possibly to the dismay of other state changes.

_Section 4: Conclusion_

I believe this brief may have created a lot more questions in your mind than answers. In history, the uprooting of conventional thought has caused many a revolution. As Asimov surmises in "Nightfall", the realization of man that he is not alone in the universe could cause the fall of civilization. This brief should simply shift the perspective in your mind of how you could look at scene graph representations.

Eric Powers