Visual Value 3D - Efficient event propagation in scene graphs.

Scene graph based applications for 3D graphics normally supports event listeners in order to interact with displayed data. Events that eventually change data held in the scene graph need to be processed and handled in a robust manner. If a scene graph contains a complex structure with multiple dependencies between attributes, the event processing mechanism through the scene graph becomes a problem difficult to solve in an optimal way. Problems that seem to occur are multiple and partly inconsistent updates of scene graph data which in the end will affect the rendering performance.

The classic problem that any application using a graph as data maintainer can have is when paths between nodes are merged together as shown in the figure below.

Updating this graph can be done in two ways. Either you start at the root (node 1), update the node and make a recursive update call for each child. Or you start at the leaves (which in this case only is one node, node 5) make the update call recursively on each parent to make sure they are all updated and then update the node itself. By adding an “updated”-tag which will be set to true after a node has been updated a simple check of this flag can be made at the beginning of a node’s update call. If a node already is updated it can simply fall out silently from the update call and in that way break the recursion. This will guarantee that a node only will be updated once during an update session. The first method described above is called Forward Propagation and the second is called Backward Extraction.

Naive rendering software updates each node every time a new frame is to be rendered. More modern scene graph applications perform one update during initialization and reacts after that only to events that is changing the scene graph data. So how do we update the scene graph when an event occurs? Both of the two techniques mentioned above have benefits and drawbacks. Forward Propagation will start at a node and propagate down in the scene graph affecting all dependant nodes. The benefits are that all nodes that should be updated will be updated. The drawback is that if the scene graph looks like in the figure above and the updating starts at node 1, node 5 will be updated three times which is completely unnecessary. By using Backwards Extraction instead no nodes will be updated multiple times but there is no way of knowing which node that actually needs an update since the only way of knowing that would be to first update and then see if the node has been changed.

Most scene graph based applications existing today use Forward Propagation as updating technique and they use a tree as a scene graph. The tree structure is suitable together with Forward Propagation since merging node paths doesn’t exist, hence the problem described does not exist either. But it limits the dependencies in the scene graph to only be hierarchical. As an example; a scene graph like the one in the picture below cannot be created by using a tree since the top cylinder needs both base cylinders’ transforms in order to calculate its own transform.

If the two base cylinders’ transforms are animated or controlled by a user, the top cylinder’s transform should change dynamically. A tree cannot solve that kind of relationship, hence most scene graph applications does not support this kind of scene in a general way. There is however some frameworks that can handle it. X3D which is the iso-standard for expressing 3D graphics on the internet supports dynamic updates of nodes by using several inputs from any other node in the scene graph. The updating process is triggered by events which are passed between nodes. Events in X3D follows the Forward Propagation scheme that was described earlier, which means that if the scene with the cylinders is described with X3D we must define one event for each dependency which will be 6 events (both base cylinder’s translation, rotation and scaling). If all of this 6 change between each frame the top cylinder’s transform will be calculated 6 times and it won’t hold a correct value until the last time it was calculated.

Today’s existing scene graph application lacks a robust and thorough event handling system when scene graphs contain complex dependencies with merging node paths. Visual Value 3D is a framework that acts as a protecting layer between the event sources and the scene graph data. The foundation of Visual Value 3D is the ActiveValue which is a generic class that represents a value that dynamically knows how to calculate itself. An ActiveValue is typically a color or a transformation matrix and they it can be dependant on any other ActiveValue. Calculation is not performed until the value is invoked and each ActiveValue has an evaluated flag indicating if the value needs to recalculate itself or not. The calculation of an ActiveValue is handled by an evaluator class which executes a method which usually invokes other ActiveValues (the dependants) and returns the desired value. An overview of Visual Value 3D is shown below.

The scene graph nodes’ attributes is extracted from the Visual Value 3D framework and through there they can be dependant on any other attribute in the scene graph. Visual Value 3D uses the Forward Propagation technique to invalidate ActiveValues when events occur and the Backward Extraction technique to evaluate them. Invalidation of ActiveValues does nothing else than setting its evaluated flag to false which is a very cheap operation. Evaluation is then performed when someone asks for the ActiveValue. If it is already evaluated the current value is return without any recalculations. What is gained by combining these two methods in this way is that when events occur it performs a set on an ActiveValue which in turn starts an invalidation chain to make sure all dependant ActiveValues that they have been changed. Invalidation of an ActiveValues multiple times is so cheap that it does not affect the overall performance unless it is made a zillion times. When the rendering software asks for an ActiveValue it can, depending on if the ActiveValue is invalidated or not, start an evaluation chain of all ActiveValues that has been changed. This makes sure that the rendering software always receives a correct value with that only has been recalculated at most once. Visual Value 3D does not only provide a robust and reliable event processing mechanism but it also opens the door for “crazy” (or creative) dependencies in a scene graph. Changing color of an object depending on its rotation, making sure two objects always are a given distance away from each other (magnetism), changing resolution of objects depending on distance to the camera or just plain and simple animations are things easily made with Visual Value 3D. Visual Value 3D also works for a general purpose since all rules and dependencies are expressed outside the application in xml