Temporal dependencies in dependency graphs
Systems and processes are described below relating to evaluating a dependency graph having one or more temporally dependent variables. The temporally dependent variables may include variables that may be used to evaluate the dependency graph at a frame other than that at which the temporally dependent variable was evaluated. One example process may include tracking the temporal dirty state for each temporally dependent variable using a temporal dependency list. This list may be used to determine which frames, if any, should be reevaluated when a request to evaluate a dependency graph for a particular frame is received. This advantageously reduces the amount of time and computing resources needed to reevaluate a dependency graph.
1. A method for evaluating a dependency graph having a temporally dependent variable that is used to evaluate the dependency graph for a frame other than that at which the temporally dependent variable was evaluated, the method comprising:
receiving, by a processor, a request to evaluate the dependency graph for a requested frame of an animation;
identifying, based on a temporal dependency list, that a value of the temporally dependent variable is dirty for a first frame different from the requested frame, wherein a value of the temporally dependent variable for the first frame is to be used to evaluate the dependency graph for the requested frame, and wherein the temporal dependency list comprises a list of values of the temporally dependent variable determined by previous evaluations of the dependency graph;
in response to receiving the request to evaluate the dependency graph for the requested frame and in accordance with identifying that the value of the temporally dependent variable is dirty for the first frame, evaluating the temporally dependent variable for the first frame to generate a non-dirty value of the temporally dependent variable for the first frame;
updating the list of values of the temporal dependency list based on the non-dirty value of the temporally dependent variable for the first frame; and
evaluating at least a portion of the dependency graph at the requested frame based at least in part on the non-dirty value of the temporally dependent variable for the first frame from the updated list of values of the temporal dependency list.
2. The method of claim 1 , wherein the temporal dependency list comprises a temporal dirty flag for each value in the list of values.
3. The method of claim 2 , wherein identifying that the value of the temporally dependent variable is dirty comprises parsing the temporal dependency list to identify a set temporal dirty flag.
4. The method of claim 2 , wherein updating the list of values of the temporal dependency list comprises:
storing the non-dirty value of the temporally dependent variable for the first frame in the temporal dependency list; and
resetting a temporal dirty flag for the identified dirty value.
5. The method of claim 1 , wherein the temporally dependent variable is identified as being a temporally dependent variable by one or more nodes in the dependency graph.
6. The method of claim 1 , further comprising, before receiving the request to evaluate the dependency graph at the requested frame:
identifying the temporally dependent variable;
generating the temporal dependency list;
evaluating the dependency graph for one or more frames; and
storing values of the temporally dependent variable resulting from the evaluating of the dependency graph for one or more frames in the temporal dependency list.
7. The method of claim 1 , wherein evaluating at least the portion of the dependency graph at the requested frame is further based at least in part on a second non-dirty value of the temporally dependent variable for the requested frame.
8. A non-transitory computer-readable storage medium comprising computer-executable instructions for evaluating a dependency graph having a temporally dependent variable that is used to evaluate the dependency graph for a frame other than that at which the temporally dependent variable was evaluated, the computer-executable instructions comprising instructions for:
receiving, by a processor, a request to evaluate the dependency graph for a requested frame of an animation;
identifying, based on a temporal dependency list, that a value of the temporally dependent variable is dirty for a first frame different from the requested frame, wherein a value of the temporally dependent variable for the first frame is to be used to evaluate the dependency graph for the requested frame, and wherein the temporal dependency list comprises a list of values of the temporally dependent variable determined by previous evaluations of the dependency graph;
in response to receiving the request to evaluate the dependency graph for the requested frame and in accordance with identifying that the value of the temporally dependent variable is dirty for the first frame, evaluating the temporally dependent variable for the first frame to generate a non-dirty value of the temporally dependent variable for the first frame;
updating the list of values of the temporal dependency list based on the non-dirty value of the temporally dependent variable for the first frame; and
evaluating at least a portion of the dependency graph at the requested frame based at least in part on the non-dirty value of the temporally dependent variable for the first frame from the updated list of values of the temporal dependency list.
9. The non-transitory computer-readable storage medium of claim 8 , wherein the temporal dependency list comprises a temporal dirty flag for each value in the list of values.
10. The non-transitory computer-readable storage medium of claim 9 , wherein identifying that the value of the temporally dependent variable is dirty comprises parsing the temporal dependency list to identify a set temporal dirty flag.
11. The non-transitory computer-readable storage medium of claim 9 , wherein updating the list of values of the temporal dependency list comprises:
storing the non-dirty value of the temporally dependent variable for the first frame in the temporal dependency list; and
resetting a temporal dirty flag for the identified dirty value.
12. The non-transitory computer-readable storage medium of claim 8 , wherein the temporally dependent variable is identified as being a temporally dependent variable by one or more nodes in the dependency graph.
13. The non-transitory computer-readable storage medium of claim 8 , further comprising computer-executable instructions for:
identifying, before receiving the request to evaluate the dependency graph at the requested frame, the temporally dependent variable;
generating the temporal dependency list;
evaluating the dependency graph for one or more frames; and
storing values of the temporally dependent variable resulting from the evaluating of the dependency graph for the one or more frames in the temporal dependency list.
14. The non-transitory computer-readable storage medium of claim 8 , wherein evaluating at least the portion of the dependency graph at the requested frame is further based at least in part on a second non-dirty value of the temporally dependent variable for the requested frame.
15. An apparatus for evaluating a dependency graph having a temporally dependent variable that is used to evaluate the dependency graph for a frame other than that at which the temporally dependent variable was evaluated, the apparatus comprising:
a memory configured to store a temporal dependency list; and
a computer processor configured to:
receive a request to evaluate the dependency graph for a requested frame of an animation;
identify, based on a temporal dependency list, that a value of the temporally dependent variable is dirty for a first frame different from the requested frame, wherein a value of the temporally dependent variable for the first frame is to be used to evaluate the dependency graph for the requested frame, and wherein the temporal dependency list comprises a list of values of the temporally dependent variable determined by previous evaluations of the dependency graph;
in response to receiving the request to evaluate the dependency graph for the requested frame and in accordance with identifying that the value of the temporally dependent variable is dirty for the first frame, evaluate the temporally dependent variable for the first frame to generate a non-dirty value of the temporally dependent variable for the first frame;
update the list of values of the temporal dependency list based on the non-dirty value of the temporally dependent variable for the first frame; and
evaluate at least a portion of the dependency graph at the requested frame based at least in part on the non-dirty value of the temporally dependent variable for the first frame from the updated list of values of the temporal dependency list.
16. The apparatus of claim 15 , wherein the temporal dependency list comprises a temporal dirty flag for each value in the list of values.
17. The apparatus of claim 16 , wherein identifying that the value of the temporally dependent variable is dirty comprises parsing the temporal dependency list to identify a set temporal dirty flag.
18. The apparatus of claim 16 , wherein updating the list of values of the temporal dependency list comprises:
storing the non-dirty value of the temporally dependent variable for the first frame in the temporal dependency list; and
resetting a temporal dirty flag for the identified dirty value.
19. The apparatus of claim 15 , wherein the temporally dependent variable is identified as being a temporally dependent variable by one or more nodes in the dependency graph.
20. The apparatus of claim 15 , wherein the computer processor is further configured to:
identify, before receiving the request to evaluate the dependency graph at the requested frame, the temporally dependent variable;
generate the temporal dependency list;
evaluate the dependency graph for one or more frames; and
store values of the temporally dependent variable resulting from the evaluating of the dependency graph for one or more frames in the temporal dependency list.
21. The apparatus of claim 15 , wherein evaluating at least the portion of the dependency graph at the requested frame is further based at least in part on a second non-dirty value of the temporally dependent variable for the requested frame.