Patent Description:
The present disclosure relates to computer-generated animation and, more specifically, to optimizing the evaluation of a dependency graph for computer-generated animation.

Media productions typically use dependency graphs to render, animate, or otherwise describe a scene in an animation. The dependency graphs can include a system of interconnected nodes that perform computations on input data, such as input attributes, and produce output data, such as output attributes. A node may have multiple input attributes and multiple output attributes, as well as other attributes.

The following prior art discloses dependency gaphs, but not the combination of outputs of different nodes:.

As media productions create more realistic animations, the complexity and the number of nodes in the dependency graphs used to support these animations also increase. As a result, the time and computational resources required to evaluate these dependency graphs also typically increase. Accordingly, there is a need to optimize the evaluation of dependency graphs.

Systems and processes for performing graphics processing are in accordance with the claims.

The dependency graph may represent one or more three-dimensional objects.

Copies of this patent or patent application publication with color drawings will be provided by the office upon request and payment of the necessary fee.

The present application can be best understood by reference to the following description taken in conjunction with the accompanying drawing figures, in which like parts may be referred to by like numerals.

The following description is presented to enable a person of ordinary skill in the art to make and use the various embodiments. Descriptions of specific devices, techniques, and applications are provided only as examples. Various modifications to the examples described herein will be readily apparent to those of ordinary skill in the art, and the general principles defined herein may be applied to other examples and applications Thus, the disclosed technology is not intended to be limited to the examples described herein and shown, but is to be accorded the scope defined by the claims.

<FIG> illustrates exemplary images from an animation rendered using the process described in detail below. Each frame of the animation is rendered by evaluating a dependency graph that describes the character in the scene. For each frame, at least the value of the rotation input attribute of the transformation node of the character's neck has changed in the dependency graph, resulting in the movement of the character's neck. A transformation node may determine the scale, rotation, and location of an element, such as the character's neck, along the X, Y and Z axes.

Generally, attributes may refer to parameters of nodes that can be controlled through the system. Input attributes include attributes of a node that may be set by the system or that may be set by another node. In this example, the change in the value of the rotation input attribute of the transformation node of the character's neck results in a change to the value of the rotation_display output attribute of that transformation node. Output attributes include attributes of a node that may be read by the system or that may be accessed by another node. To determine the value of the rotation_display output attribute of the transformation node, the node may be evaluated. Evaluation may include, for example, computation, execution, or calculation. For example, the transformation node may determine the location of the character's neck using matrix multiplication. When the value of a specific output attribute of a node is requested, the system may evaluate the node to compute that specific output attribute. This may be referred to as evaluating the output attribute of the node. Alternatively, a node may be evaluated to compute all output attributes of the node.

The change in the value of the rotation_display output attribute of the transformation node of the character's neck may be propagated through the dependency graph when the dependency graph is evaluated. In this example, this may result in a change in the value of the character's output attributes, causing the appearance of the movement of the character's neck when the animation is rendered.

Referring to <FIG>, because the input attributes of the transformation node of the character's legs have not changed throughout these frames, the position of the character's legs have also not changed throughout the frames of the animation. Thus, once the output attributes of the transformation node of the character's legs have been evaluated for the first frame, the values may be cached for use in the subsequent frames. The values of the input attributes of the transformation node of the character's legs do not change, and thus the value of the output attributes of the transformation node of the character's legs do not change. Accordingly, the transformation node of the character's legs may not need to be reevaluated for each frame after being evaluated for the first frame.

<FIG> illustrates an exemplary process for evaluating a dependency graph that is configured to cache output attributes. The evaluation may be initiated by various triggers. For example, a request to display an image, a playback of an animation, a request for a value of an output attribute of a node, or the like, may initiate an evaluation.

Referring to block <NUM> of <FIG>, information in a dirty list specifying which cached output attributes are invalid and which cached output attributes are valid may be accessed. The dirty list may be generated by a system configured to store dirty information about the output attributes of a dependency graph in a dirty list. To track the validity of cached output attributes, the system may use the dirty list to identify an invalid output attribute as "dirty. " For example, a cached output attribute may be invalid, and thus dirty, when a value of an input attribute that affects the value of the output attribute changes. Thus, an input attribute affects an output attribute when the valid value of the output attribute depends on the value of the input attribute. The dirty list may be configured in many ways.

In one example, the dirty list may be a list of only references to output attributes that are dirty. Thus, when an output attribute becomes dirty, it should be added to the list. When an output attribute is evaluated and is no longer dirty, it should be removed from the list. In another example, the dirty list may be a comprehensive list of all output attributes. Each output attribute identified in the comprehensive list may have a dirty flag or other dirty information associated with it to indicate whether the output attribute is dirty. In yet another example, the dirty list may contain a subset of the comprehensive list of output attributes. Each output attribute identified in the list may have a dirty flag or other dirty information associated with it to indicate whether the output attribute is dirty. In another example, the dirty list may be an array of "<NUM>"s and "<NUM>"s. A "<NUM>" at a particular location in the array may represent that an output attribute associated with that particular location is not dirty and a "<NUM>" at a particular location in the array may represent that an output attribute associated with that particular location is dirty. Such an array may be more conducive to bitwise operations, such as AND, OR, NOT, and XOR, than other types of lists.

Tracking the dirty status of output attributes in a dirty list may render tracking the dirty status of output attributes at the node level redundant. Instead, the dirty list may be stored external to the dependency graph.

<FIG> and <FIG> illustrate one example of a dirty list <NUM>. The dependency graph <NUM> of <FIG> includes five nodes: node_A <NUM>, node_B <NUM>, node_C <NUM>, node_D <NUM>, and node_E <NUM>. Dotted lines within a node indicate that an output attribute of the node is based on a connected input attribute of the node. For example, node_D <NUM> has three input attributes: input_1 <NUM>, input_2 <NUM>, and input_3 <NUM>. Node_D <NUM> also has three output attributes: output_1 <NUM>, output_2 <NUM>, and output_3 <NUM>. The dotted line <NUM> indicates that input_1 <NUM> of node_D <NUM> is used to compute output_1 <NUM> of node_D <NUM>. Similarly, dotted line <NUM> indicates that input_1 <NUM> of node_D <NUM> and input_2 <NUM> of node_D <NUM> are used to compute output_2 <NUM> of node_D <NUM>; dotted line <NUM> indicates that input_3 <NUM> of node_D <NUM> is used to compute output_3 <NUM> of node_D <NUM>. These relationships do not necessarily need to be displayed in the dependency graph, but are helpful for illustrating the concepts discussed.

Referring to <FIG>, the NODE. OUTPUT_ATTRIBUTE column <NUM> contains a comprehensive list of all output attributes of the dependency graph <NUM>. Each output attribute of the dependency graph is associated with a dirty flag in the DIRTY column <NUM>. In this example, a value of "<NUM>" for the dirty flag indicates the associated output attribute is not dirty. A value of "<NUM>" for the dirty flag indicates the associated output attribute is dirty. The naming scheme in this embodiment has been selected for illustrative purposes. The name node_A. output_1 <NUM> indicates the output attribute named "output_1" of the node named "node_A. " The "<NUM>" value <NUM> for the dirty flag associated with node_A. output_1 indicates that this output attribute is not dirty. Thus, the cached value at output_1 of node_A may be used without reevaluating node_A or reevaluating the output_1 output attribute of node_A. Similarly, node_A. output_2 <NUM> is associated with a "<NUM>" value <NUM> for its dirty flag. This indicates that output attribute output_2 of node_A is dirty and may need to be reevaluated. The remaining elements of <FIG> follow a similar syntax. Because this list indicates the current state of all output attributes, it may also be referred to as a current state cache.

<FIG> and <FIG> illustrate another example of a dirty list <NUM>. In this example, the dirty list <NUM> of <FIG> contains a list of all output attributes of dependency graph <NUM> that are dirty. Thus, when an output attribute is reevaluated and is no longer dirty, the reference to the output attribute should be removed from the dirty list <NUM>. Similarly, when an output attribute is determined to be dirty, the output attribute should be added to the dirty list <NUM>. Because this list indicates the current state of all output attributes, it may also be referred to as a current state cache.

Referring to block <NUM> of <FIG>, the system may detect a change in the value of an input attribute of the dependency graph. Frequently in animation, the same dependency graph must be repeatedly evaluated while the value of the same input attribute is changed for each evaluation. Each time an input attribute is changed, the system may need to determine which output attributes are affected, and thus should be marked as dirty. To reduce the computational resources required, the system may be configured to access an input change list to determine if the input change list contains information associating the changed input attribute with the output attributes that it affects. This input change list may be stored external to the dependency graph.

If the system determines in block <NUM> that the association information is available in the input change list, in block <NUM> the system may use the association information to quickly determine which output attributes should be marked as dirty in response to detecting the change in the value of the input attribute. However, if the system determines that the association information for the changed input attribute is not available in the input change list, in block <NUM> the system may walk the graph to determine which output attributes are affected by the changed input attribute.

The dependency graph <NUM> of <FIG> and the input change list <NUM> of <FIG> illustrate this concept. Consider the example when a user or the system modifies the value of input attribute node_A. input_1 <NUM>, as illustrated in dependency graph <NUM>. When the system detects that node_A. input_1 <NUM> has changed, the system may check the stored input change list <NUM> to determine if it includes information associating the changed input attribute node_A. input_1 <NUM> with the output attributes that it affects. In this example, input change list <NUM> only indicates an association between node_C. input_2 and the outputs that it affects. Thus, the system will determine that the association information for the changed input attribute is not available in the input change list.

Referring to block <NUM>, when the association information is not available for the changed input attribute, as is the case for the input change list <NUM> and changed input attribute node_A. input_1 <NUM>, the system may determine which output attributes are affected by the changed input attribute by "walking the dependency graph. " Walking the dependency graph-walking the graph or traversing the dependency graph - is a process whereby the system follows the effects of an attribute, such as an input attribute, through the dependency graph to determine the attributes, such as the output attributes, that are affected by the input attribute. Thus, the system may walk or traverse the dependency graph starting at the location where an input attribute has changed to determine each output attribute that is affected by the changed input attribute. This may be called walking the graph downstream - or traversing the graph downstream - because it follows the flow of information.

Thus, when the system detects that node_A. input_1 <NUM> has changed and determines that association information is not available in the input change list <NUM>, the system may walk the graph to determine which outputs should be marked as dirty. The system may determine that node_A. output_1 <NUM> is not affected by the change, but that node_A. output_2 <NUM> should be identified as dirty. The system will continue to walk the graph and determine that the input attribute node_B. input_2 <NUM> is connected to the dirty output attribute node_A. output_2 <NUM>. In turn, node_B. output_1 <NUM> is affected by the change at node_B. input_2 <NUM>. Thus, output attribute node_B. output_1 <NUM> should also be identified as dirty. The system next determines that input attributes node_D. input_1 <NUM> and node_E. input_1 <NUM> are connected to node_B. output_1 <NUM>. The system determines that output attribute node_D. output_1 <NUM> and output attribute node_D. output_2 <NUM> should be identified as dirty because they are computed based on node_D. input_1 <NUM>. The system also determines that output attribute node_E. output_1 <NUM> should be identified as dirty because it is computed based on node_E. input_1 <NUM>. Thus, after walking the graph the system has selected the following output attributes to identify as dirty as a result of the changed input attribute node_A. input_1 <NUM>: node_A. output_2 <NUM>, node_B. output_1 <NUM>, node_D. output_1 <NUM>, node_D. output_2 <NUM>, and node_E. output_1 <NUM>. The system may then update the input change list <NUM> to add the new association. An exemplary updated input change list <NUM> is illustrated in <FIG>. The system may also update the dirty list to identify these output attributes as dirty.

<FIG> depicts input change list <NUM> after it has been updated. INPUT_ATTRIBUTE column <NUM> contains a list of all, or some, input attributes that have been changed and which have resulted in the system walking the dependency graph to determine the output attributes that are affected. For each input attribute listed in the NODE. INPUT_ATTRIBUTE column <NUM>, the input change list also contains a list of each output attribute that is affected by the input attribute in the AFFECTED NODE. OUTPUT_ATTRIBUTES column <NUM>. For example, after walking the graph to determine the affected output attributes when the input attribute node_A. input_1 <NUM> of dependency graph <NUM> changes, the system has stored the list of affected output attributes in the input change list <NUM> and associated them with node_A. input_1 <NUM>.

Referring to block <NUM>, the next time the system detects a change in the input attribute node_A. input_1 <NUM>, the system may use input change list <NUM> to determine which output attributes will be affected without having to walk the graph. Specifically, the system can quickly determine that node_A. input_1 affects the output attributes <NUM>. The dirty list may be updated to identify these affected output attributes as dirty in the dirty list.

Thus, when the system detects a change in the value of an input attribute, the system may access the input change list to determine whether information has already been compiled associating the changed input attribute with the output attributes it affects. If the input change list contains information specifying the relationship, there is no need to walk the graph to determine which output attributes are affected. Instead, the system may use the information stored in the input change list to update the dirty list.

It is desirable to reduce the number of times the system walks a graph because walking a graph is computationally resource intensive and time consuming. For example, multiple pointers of multiple nodes may need to be dereferenced each time the graph is walked, and these pointers may point to memory locations distributed at different locations in memory, in different physical memory chips or drives, or even in memory located across different computing systems. Accordingly, the system may save computational resources by reducing the number of times the graph is walked. This is especially true when the same attribute is repeatedly changed for multiple frames, multiple times, multiple intervals, multiple evaluations, or multiple other markers.

An input change list may be populated in several ways. As described above, the system may be configured to add an association to the input change list when the system detects a change in the value of an input attribute and the system determines that the input change list does not contain association information for the changed input attribute. In another example, the user may provide the associations that are stored in the list. In another example, the system may be configured to populate one or more associations before any evaluations take place, before any evaluation requests are received, or before the system detects any changes in the value of any input attributes. An input change list may also be generated or updated when the structure or dependencies of the dependency graph changes. For example, the input change list may be updated to reflect new dependencies if a new node is added to the dependency graph.

As an alternative to generating and updating the input change list as changes to input attributes are detected, the system may generate a complete or partial list of each attribute of a dependency graph, such as each input attribute, and the output attributes that it affects prior to the system requiring the information. If this is done, the system may not need to walk the graph the first time an attribute is changed.

<FIG> illustrates an example of an input change list that associates a set of input attributes with the output attributes they affect. For example, input change list <NUM> illustrates an association between input attributes node_A. input_1, node_C. input_1, and node_C. input_2 and output attributes node_A. output_2, node_B. output_1, node_C. output_1, node_C. output_2, node_D. output_1, node_D. output_2, node_D. output_3, and node_E. Storing this type of information may be helpful when a set of input attributes typically changes together, rather than independently.

In another example, the system may maintain a separate list for each of a plurality of input attributes that associate the input attributes with the attributes they affect. The list may be a comprehensive list of all attributes, a comprehensive list of all output attributes, a partial list of attributes, or a partial list of output attributes. For example, the input change list may be an array of "<NUM>"s and "<NUM>"s. A "<NUM>" at a particular location in the array may represent that an output attribute associated with that particular location is affected by the input attribute associated with the array and a "<NUM>" at a particular location in the array may represent that an output attribute associated with that particular location is not affected. Such an array may be more conducive to bitwise operations, such as AND, OR, NOT, and XOR, than other types of lists.

In order to preserve memory and other computational resources, restrictions may be placed on the input change list. One restriction may limit storage of association information between an input attribute and the output attributes it affects to n-number of input attributes. In one example, the last n-number of association information may be maintained, using a first-in-first-out system. Thus, the least-recently accessed, least-recently updated, or the oldest-added associations may be removed when a new association is added. In another example, the system may only store association information after a determined or calculated number of changes to the value of an attribute. This may prevent less-frequently-changed attributes from pushing out more-frequently-changed attributes from the input dependency list.

Referring to block <NUM> of <FIG>, once the system has determined the output attributes that are affected by the changed input attribute, the system may update the dirty list to mark the affected output attributes as dirty. The dirty list may be updated based on the association information in the input change list.

In one example, the system may perform a bitwise OR operation on the contents of the dirty list and the list of output attributes affected by the changed input. The dirty list may be updated to mark any output attribute dirty if it is either marked as dirty in the dirty list or marked as affected by the changed input attribute in the input change list.

In block <NUM>, the system may receive a request to evaluate an output attribute. When a request is received to evaluate a dependency graph, or part of a dependency graph, the system may save time and computing resources by only reevaluating those output attributes that have both been marked as dirty and that affect the evaluation. This may be referred to as a "lazy evaluation. " In order to use lazy evaluation, the system may determine which output attributes affect the requested output attribute and which of the affecting output attributes are dirty. Any cached values of output attributes that affect the evaluation, but have not been marked as dirty, may be used without being reevaluated.

For example, the dirty output attributes of nodes that only relate to an object that is not visible in a part of a scene may not need to be evaluated for those portions of the scene because they do not affect the scene. Similarly, dirty output attributes may not need to be evaluated when a user has specified that the user is not interested in the effect the output attributes will have on an evaluation. Accordingly, every dirty output attribute of a dependency graph does not need to be evaluated at each time, frame, interval, evaluation, or other marker when lazy evaluation is used.

Using the input change list and the dirty list, the system may determine which output attributes are dirty. To determine which output attributes affect a requested output attribute, the system may be configured to access an output dependency list. The output dependency list may comprise an association between a requested output attribute and one or more output attributes that affect the requested output attribute. This output dependency list may be stored external to the dependency graph.

In block <NUM>, if the system determines that association information for a requested output attribute is available in the output dependency list, the system may use the association information to quickly determine which output attributes may need to be reevaluated for the requested output, if they are dirty. However, if the system determines that association information for the requested output attribute is not available in the output dependency list, the system may need to walk the graph to determine which output attributes affect the requested output attribute.

In block <NUM>, when the association information is not available for the requested output attribute, the system may walk the graph upstream (e.g., follow the graph in the direction opposite that of the flow of information) starting at the requested output attribute to determine which output attributes affect the requested output attribute. The system may generate or update the output dependency list by storing association information gathered while walking the graph upstream from the requested output attribute. By storing this association information, the system may not need to walk the graph for subsequent evaluations to determine which output attributes affect a requested output attribute. Further, the output dependency list may store multiple requested output attributes, each requested output attributed associated with all or some of the output attributes that respectively affect it.

The dependency graph <NUM> of <FIG> and the illustrative output dependency list <NUM> of <FIG> illustrate this concept. OUTPUT_ATTRIBUTE column <NUM> of output dependency list <NUM> contains an output attribute <NUM>. The output dependency list <NUM> associates the output attribute <NUM> and a list of each output attribute <NUM> that affects it. The AFFECTING NODE. OUTPUT_ATTRIBUTES column <NUM> contains the list of affecting output attributes <NUM>.

Consider the example when a user or the system requests the value of output attribute node_D. output_1 <NUM>. The system may first look to the output dependency list <NUM> to determine if it includes an association between the requested output attribute and the output attributes that affect it. In this case, output dependency list <NUM> does not contain an association between node_D. output_1 <NUM> and the output attributes that affect it. Instead, output dependency list <NUM> contains an association between node_D. output_2 and the outputs that affect it. Thus, the system may walk the graph upstream on the dependency graph <NUM> to determine which output attributes affect the requested output attribute node_D. output_1 <NUM>. For example, the system may determine that node_B. output_1 <NUM> affects node_D. output_1 <NUM>. However, node_B. output_1 <NUM> is affected by node_A. output_1 <NUM> and node_A. output_2 <NUM>. Thus, the system determines that output attributes node_B. output_1 <NUM>, node_A. output_1 <NUM>, and node_A. output_2 <NUM> affect node_D. output_1 <NUM>. The system may update output dependency list <NUM> to store information associating the requested output attribute node_D. output_1 <NUM> with the output attributes that affect it.

<FIG> illustrates an updated output dependency list <NUM> that includes this association information. The next time a user or the system requests an evaluation of output attribute node_D. output_1 <NUM>, the system will not need to walk the graph to determine which output attributes affect it. Instead, the information will be available in the output dependency list <NUM>. Specifically, the system can look to the NODE. OUTPUT_ATTRIBUTE column <NUM> and the AFFECTING NODE. OUTPUT_ATTRIBUTES column <NUM> to determine that node_D. output_1 is affected by node_A. output_1, node_A. output_2, and node_B.

In block <NUM> of <FIG>, when the association information is available for the requested output attribute, the system may not need to walk the graph. Instead, the system can quickly determine which output attributes affect the requested output attribute based on the output dependency list.

In one example, the output dependency list may comprise multiple associations where an output attribute is associated with the output attributes that affect it. In another example, the output dependency list may comprise multiple associations where an output attribute is associated with all, or some, outputs of the dependency graph and each associated output attribute is flagged as "affecting" or "not affecting. " This may be done by marking an "affecting" flag as "<NUM>" for output attributes that affect the requested output attribute or "<NUM>" for output attributes that do not affect the requested output attribute.

In order to preserve memory and other computational resources, restrictions may be placed on the output dependency list. One restriction may limit storage of association information between a desired or requested output attribute and the output attributes affecting the desired output to n-number of desired or requested output attributes. In one example, the last n-number of association information data may be maintained, using a first-in-first-out system. Thus, the least-recently-accessed, least-recently-updated, or the oldest-added associations may be removed when a new association is added. In another example, the system may only store association information after a determined or calculated number of requests for a specific output attribute. This prevents less frequently requested output attributes from pushing out more frequently requested output attributes from the output dependency list.

In one example, the system may maintain a separate list for each of a plurality of output attributes that associate the output attributes with the attributes they affect. The list may be a comprehensive list of all attributes, a comprehensive list of all output attributes, a partial list of attributes, or a partial list of output attributes. For example, the output dependency list may be an array of "<NUM>"s and "<NUM>"s. A "<NUM>" at a particular location in the array may represent that an attribute associated with that particular location affects the requested attribute and a "<NUM>" at a particular location in the array may represent that an attribute associated with that particular location does not affect the requested attribute. Such an array may be more conducive to bitwise operations, such as AND, OR, NOT, XOR, than other types of lists.

In block <NUM>, the system may evaluate the requested output attribute. Once the system determines which output attributes affect the requested output attribute and which output attributes of the dependency graph are dirty, the system may determine which output attributes should be evaluated based on lazy evaluation.

In one example, the list of output attributes to be evaluated for a requested output attribute may be determined by a bitwise AND operation on the dirty list and the output attributes affecting the requested output attributed, as stored in the output dependency list. After evaluating an output attribute, the system may update the status of the output attribute in the dirty list to indicate that the output attribute is no longer dirty. This status may be changed before, during, or after the output attribute (or the node associated with the output attribute) has been evaluated.

Thus, when a changed input attribute is contained in the input change list, the system can update the dirty list with the affected output attributes without walking the graph. Then, when a requested output attribute is already in the output dependency list, the system can determine which outputs affect the requested output attribute without walking the graph. The dirty list and the output dependency list for the requested output attribute may now be compared to determine which output attributes are dirty and affect the requested output attribute. Thus, evaluation of these dirty output attributes can begin without walking the graph. As a result, the requested output attribute may be properly evaluated. The dirty list may also be updated to reflect that the evaluated output attributes are no longer dirty.

In certain examples, blocks <NUM> through <NUM> may occur independently from blocks <NUM> to <NUM>.

<FIG> illustrates an exemplary animation system <NUM> that may be used to implement the dependency graph evaluation process discussed above. The process may be implemented, for example, in either hardware or in software stored on a non-transitory computer-readable storage medium. The system may be configured to evaluate a dependency graph, a node within a dependency graph, or an output attribute of a dependency graph. The system may be further configured to receive input from a user and to display graphics, an image, or scene of an animation based on the evaluation.

The animation system <NUM> may be configured to receive user input from an input device <NUM>. The input device <NUM> may be any device that receives input from the user and transmits it to the animation system <NUM>. For example, the input device may be a keyboard, a mouse, a tablet, a stylus, or the like. Those skilled in the art will recognize that other types of input devices may also be used.

The animation system <NUM> may be configured to output graphics, images, or animation to a display device <NUM>. The display device <NUM> may be any device that receives data from the animation system and presents it to the user. For example, the display device may be a liquid crystal display, a set of light emitting diodes, a projector, or the like. Those skilled in the art will recognize that other types of output devices may also be used.

The animation system <NUM> may comprise a central processing unit <NUM>. The central processing unit may comprise one or more processing cores. The central processing unit <NUM> may be coupled to and able to communicate with the input device <NUM>. Although the animation system <NUM> is illustrated with one central processing unit <NUM>, the animation system <NUM> may have multiple processing units. The animation system <NUM> may also comprise a graphics processing unit <NUM>. The graphics processing unit <NUM> may be dedicated to processing graphics related data. The graphics processing unit <NUM> may comprise a single processing core or multiple processing cores. Although the animation system <NUM> is illustrated with one graphics processing unit <NUM>, the animation system <NUM> may have a plurality of graphics processing units. The central processing unit <NUM> and/or the graphics processing unit <NUM> may be coupled to and able to communicate data to the output device <NUM>.

In one example, the animation system <NUM> may comprise one or more processors and instructions stored in a non-transitory computer readable storage medium, such as a memory or storage device, that when executed by the one or more processors, perform the processes for evaluating an output attribute of a dependency graph as described above. In the context of the embodiments described herein, a "non-transitory computer readable storage medium" can be any medium that can contain or store the program for use by or in connection with the instruction execution system, apparatus, or device. The non-transitory computer readable storage medium can include, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus or device, a portable computer diskette (magnetic), a random access memory (RAM) (magnetic), a read-only memory (ROM) (magnetic), an erasable programmable read-only memory (EPROM) (magnetic), a portable optical disc such a CD, CD-R, CD-RW, DVD, DVD-R, or DVD-RW, or flash memory such as compact flash cards, secured digital cards, USB memory devices, memory sticks, and the like.

The animation system <NUM> may comprise volatile memory <NUM>, which is a non-transitory computer readable storage medium, in communication with the central processing unit <NUM>. The volatile memory <NUM> may be, for example, random access memory, such as dynamic random access memory or static random access memory, or any other type of volatile memory. The volatile memory <NUM> may be used to store data or instructions during the operation of the animation system <NUM>. Those skilled in the art will recognize that other types of volatile memory may also be used.

The animation system <NUM> may also comprise non-volatile memory <NUM>, which is a non-transitory computer readable storage medium, in communication with the central processing unit <NUM>. The non-volatile memory <NUM> may include flash memory, hard disks, magnetic storage devices, read-only memory, or the like. The non-volatile memory <NUM> may be used to store animation data, dependency graph data, computer instructions, or any other information. Those skilled in the art will recognize that other types of non-volatile memory may also be used.

The animation system <NUM> is not limited to the devices, configurations, and functionalities described above. For example, although a single volatile memory <NUM>, non-volatile memory <NUM>, central processing unit <NUM>, graphics processing unit <NUM>, input device <NUM>, and output device <NUM> are illustrated, a plurality of any of these devices may be implemented internal or external to the animation system <NUM>. In addition, the animation system <NUM> may comprise a network access device for accessing information on a network, such as an internal network or the Internet. Those skilled in the art will recognize other configurations of the animation system <NUM> may be used.

Various exemplary embodiments are described herein. Reference is made to these examples in a non-limiting sense. They are provided to illustrate more broadly applicable aspects of the disclosed technology. Various changes may be made and equivalents may be substituted within the scope of the claims. In addition, many modifications may be made to adapt a particular situation, material, composition of matter, process, process act(s) or step(s) within the scope of the claims.

Claim 1:
A method for performing graphics processing, the method comprising:
accessing a dependency graph, the dependency graph comprising a plurality of interconnected nodes, each node having one or more output attributes, wherein the dependency graph receives one or more input attributes;
accessing a first list, wherein the first list includes a dirty status for each output attribute of the dependency graph that is invalid due to a change of a value of an input attribute that affect the value of the output attribute;
accessing a input change list, wherein the input change list associates at least one of the one or more input attributes with output attributes that are affected by the at least one of the one or more input attributes;
accessing an output dependency list, wherein:
the output dependency list identifies at least one output attribute of a first node of the output attributes and identifies output attributes that affect the at least one output attribute of the first node of the output attributes, the output attributes that affect the at least one output attribute including an output attribute of a second node that is different from the first node; and
the output dependency list associates the at least one output attribute of the first node of the output attributes with output attributes that affect the at least one output attribute of the first node of the output attributes;
receiving an evaluation request for a requested output attribute; and
evaluating, using a processor, a set of output attributes, the set of output attributes selected for evaluation based on the set of output attributes being specified in the first list as dirty and the set of output attributes being specified in the output dependency list as associated with the requested output attribute;
rendering a frame of an animation using the evaluated set of output attributes of the dependency graph