Use of computer-based systems and methods has improved the production (including post production) of motion pictures, television programs and commercials, multimedia presentations, interactive games, internet content, CD-ROMs, DVDs, and simulation environments used for entertainment, training, education, marketing and visualization. Each of these applications may use multimedia data and image processing techniques to some degree to create and/or render a computer model of a scene in a real or synthetic world. The scene model not only describes buildings, parts, people, props, backgrounds, actors, and other objects in a scene, but also represents relationships between objects such as their movement, interactions, and other transformations over time.
Having a three-dimensional representation of the scene can be quite useful in most phases of multimedia production, including choreography, rendering and compositing. For example, consider a motion picture environment where computer-generated special effects are to appear in a scene with real world objects and actors. The producer may benefit greatly by creating a model from digitized motion picture film using automated image-interpretation techniques and then proceeding to combine computer-generated abstract elements with the elements derived from image-interpretation in a visually and aesthetically pleasing way.
Spatial two-dimensional (2-D) and three-dimensional (3-D) transforms such as translation, scaling, rotation, and other linear and non-linear transforms may also be applied in an orderly way. These transforms are often represented in conventional scene graphs that represent how objects have to obey certain constraints. Scene graphs are structures that arrange the logical and/or spatial representation of a graphical scene. They can be described as a collection of nodes in a graph (e.g., a Directed Acyclic Graph) or a tree structure. A node may have children, but often only one parent. The relationship between a parent and child may be referred to as an ‘edge’. A constraint applied to a parent is applied to all of its children. Such constraints an a-cyclic, and operate in one direction from parent to child, but do not also operate from child to parent. For example, a 3D game may define a logical relationship between two entities or objects like a cart and a horse so that the cart is considered an extension of the horse. A scene graph with these two entities would have a ‘horse’ node with a ‘cart’ node attached to it as a child. As the horse moves, so does the cart. But, the cart does not move the horse (e.g., backwards down a hill).
Dual constraint systems are similar to a-cyclic constraint systems because a child cannot affect a parent, and a relationship between children requires a linking parent node. Sometimes referred to as a ‘sibling’ relationship, a dual constraint affects each object as a member of the same group. However, in order to create a dual constraint between the siblings, a parent “dual” node must be created, thereby creating a hierarchical relationship between siblings and a single parent in the same manner as a typical hierarchical scene graph. Moreover, dual constraint systems may break other parent-child relations held by each sibling object and respective parent objects upon the formation of the parent “dual” node.
As described above, a common approach for organizing a scene-graph in user-interface frameworks is to specify a hierarchical parent-child relationship between elements/objects. This approach has a shortcoming in that constraints are only propagated in one direction, parent to child. If a particular animation requires a child object to move the parent, either the hierarchy needs to be modified, or a special case animation code must be implemented.
A scene graph has additional limitations in relation to defining multiple relationships between an object and multiple other objects. A scene graph is a static diagram of hierarchical relationships, and multiple static scene graphs are required to define multiple relationships between a single object and multiple other objects. When dealing with multiple relationships between an object and multiple other objects, scene graphs further fail in blending the effects of the multiple constraints from the multiple other objects that are simultaneously operating on the single object.
Accordingly, what is needed are systems and methods for creating bidirectional constraints between two or more objects without breaking hierarchical relationships between each those two objects and respective parent objects. What is also needed are systems and methods for creating bidirectional constraints between two or more objects without creating a hierarchical relationship between those two or more objects and a new parent node. What is further needed are systems and methods for blending multiple constraints operating on a single object.