Chaining actions for a directed graph

Details Chaining actions for a directed graph Chaining actions for a directed graph

2000-12-20

2004-05-18

Amsbury, Wayne (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06738777

ABSTRACT:

BACKGROUND OF INVENTION
1. Technical Field
The present invention relates to performing multiple actions with regard to a directed graph such as a directed acyclic graph. More specifically, the present invention relates to chaining such actions such that only a single traversal of the directed graph need be performed to perform such actions.
2. Background
A directed graph such as a directed acyclic graph may be employed by an application to represent a collection of data. For example, in at least some applications that are visually oriented, a “scene” that is to be rendered by the application is organized by the application in the form of such a directed graph example, if the scene includes a room with a person in the room, the directed may include a root node or container at a first level and a person description node and room description node at the second level. At the third level and directly below the person node may be a head node, body node, and limb nodes for the person, each of which variously further defines body parts of the person. Likewise, at the third level and directly below the room node may be a plurality of wall nodes, each of which variously further defines walls within the room. As may be appreciated, further levels of nodes may be provided to even further define elements of the in a progressively more detailed manner. It is not atypical, that a directed graph have on the order of thousands of nodes, for example.
Thus, the directed graph defines every element of the scene such that each element is available for rendering a particular view within the scene. Notably, a particular view need not necessarily include every element within the scene
ode within the directed graph. For example, in “looking” in a particular direction, one or more walls of the room of the scene may not be “visible”. Likewise, depending on granularity of the view, more finely detailed elements may or may not be For example, if the person is seen from afar in the view, the fingers of such person are not especially noticeable.
As may now be appreciated, then, to construct a view based on the directed graph, one or more actions are performed with regard to the directed graph to produce a cumulative effect. For example, one action may be to cull out nodes or containers of the graph that would not be visible based on the view looking in a particular direction. Another action may be to cull out nodes or containers of the graph that would not be visible based on being too finely detailed. A further action may be to actually draw the view based on the nodes or containers remaining after the culling action.
In general, to perform an action with regard to a directed graph, the directed graph is traversed and a method related to the action is applied to each node, the method applied is based on the type of node. Typically, the traversal begins at the first level of the directed graph, and all “children” of a node (i.e., (n)th level nodes depending from an (n−1)th level node) are dealt with prior to dealing with “siblings” of a node (i.e., nodes at the same (n)th level and all depending from an 1)th level node).
In the prior art, for each action to be taken with respect to a directed graph, a separate traversal of the graph was performed. However, and as should be appreciated, each traversal requires time and resources, especially for a directed graph having on the order of thousands of nodes. Moreover, each traversal may require creation of intermediate scene graphs to hold temporary results as the actions are applied.
As may also be appreciated, to construct a moving view based on the directed graph, a series of views must be constructed and sequentially displayed at a rate of 20 to 30 views per second. Accordingly, traversing the directed graph for each action for each view quickly becomes a considerable effort. Moreover, performing a traversal for each action for each view must now be performed within a set time in order to provide the views at the aforementioned display rate.
If a programmer desires to perform many operations at a node during a single traversal, such programmer can of course design a single highly specific action performs all of the operations. However, and importantly, there are so many operations that can be performed that it is impossible and/or impractical to write the single highly specific actions necessary to cover all possible combinations of operations. It is much more efficient to define each operation as a single action then to dynamically and flexibly chain the single actions together once the desired combination of operations is known.
Accordingly, a need exists for a method and mechanism for applying multiple actions to a directed graph in a single traversal of such directed graph. In a need exists for a method and mechanism for “chaining” the multiple actions such that all of the multiple actions are applied in sequence to each node in the directed graph before moving on to the next one. As may be appreciated, with such single traversal, the need for creating intermediate graphs is obviated. Further, a need exists for allowing chaining of actions in a flexible and dynamic manner such that the cumulative effect achieved by such chaining of actions is also flexible. Thus actions with very specific effects can be combined in arbitrary ways, and an application can then mix and match actions to suit particular needs.
SUMMARY OF THE INVENTION
The aforementioned need is satisfied by the present invention a method of applying a plurality of actions to a directed graph, where the directed graph having plurality of nodes branching out into multiple levels. In the method, a node in the directed graph is traversed to, and an action-specific method for each of the plurality of actions is performed on the traversed-to node. The traversing and performing are repeated until all nodes in the directed graph have been traversed Importantly, only a single traversal of the directed graph need be performed to all of the actions to the directed graph.
To effectuate such method, a chain comprising a plurality of the actions to be applied to the directed graph is constructed. Each action has a structure including state information comprising an action object pointer. The actions include a base action at a tail end of the chain and at least one chain action at a head end of the chain. The action object pointer of each chain action points to an immediately adjacent action toward the tail end of the chain, and the action object pointer of base action points to the chain action at the head end of the chain.


REFERENCES:
patent: 5524077 (1996-06-01), Faaland et al.
patent: 5751914 (1998-05-01), Coley et al.
patent: 5870545 (1999-02-01), Davis et al.
patent: 5873081 (1999-02-01), Harel
patent: 6292797 (2001-09-01), Tuzhilin et al.
patent: 6324550 (2001-11-01), Huetter
patent: 6341302 (2002-01-01), Celis
Press Release, “TGS Demonstrates HP's DirectModel Technology on SGI, Sun and Windows at SIGGRAPH '97; TGS to Deliver Toolkits and Applications,” SIGGRAPH '97, Los Angeles, CA, Aug. 4, 1997, 2 pages.
White Paper: Cripe, Brian E. and Gaskins, Thomas A., The Directmodel Toolkit: Meeting the 3D Graphics Needs of Technical Applications; Date unknown—please admit as prior art. [9 pages].

Affiliated with

Also associated with

Rating

Chaining actions for a directed graph does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Chaining actions for a directed graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chaining actions for a directed graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3261285