Techniques for animating complex scenes

• US 7,064,761 B2
• Filed: 05/10/2004
• Issued: 06/20/2006
• Est. Priority Date: 05/10/2004
• Status: Active Grant

• Current Assignee: Pixar (The Walt Disney Company)
• Original Assignee: Pixar (The Walt Disney Company)
• Inventors: da Silva, Marco Jorge, Grassia, Frank Sebastian, Demoreuille, Peter Bernard
• Primary Examiner(s): Chaule, U
• Assistant Examiner(s): PAPPAS, PETER
• Application Number:
  US10/843,224
• Publication Number:
  US 20050248564A1
• Time in Patent Office: 771 Days
• Field of Search: 345/419
• US Class Current: 345/473
• CPC Class Codes: G06T 13/00 Animation
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

Techniques that enable users (e.g., animators) to accurately animate models in a scene without having to load all the models involved in the scene concurrently in computer memory. For a particular model that a user wishes to animate, only a minimal set of models involved in the scene that are needed for the particular model to evaluate correctly are determined and loaded into computer memory. Additionally, if a particular model is to be unloaded from computer memory, then all models that depend, either directly or indirectly, on the particular model and that are loaded in memory are also unloaded from memory in order to avoid incorrect animation.

Claims

1. A computer-implemented method of facilitating animation of a scene comprising a plurality of objects, the plurality of objects represented by a plurality of models, the method comprising:

receiving information identifying a first model to be animated from the plurality of models;

using a first representation to determine a set of models from the plurality of models that are needed for evaluation of the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

loading the first model and the set of models in computer memory, wherein the plurality of models comprises at least one model that is not loaded into the computer memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.

2. The method of claim 1 wherein using the first representation to determine the set of models comprises:

for each input of the first model;

determining a first node in the graph representing the input;

traversing the graph from the firstnode using the links; and

including a model from the plurality of models in the set of models if at least one node of the model is encountered during the traversing.

3. The method of claim 2 wherein, for each input of the first model, traversing the graph from the first node using the links comprises determining a transitive closure set of all nodes in the graph that represent inputs or outputs of the plurality of models on which the input of the first model depends.

4. The method of claim 1 further comprising receiving information specifying animation for the first model.

5. The method of claim 1 wherein using the first representation to determine the set of models comprises determining a transitive closure set of one or more models from the plurality of models on which the first model depends.

6. A computer-implemented method of facilitating animation of a scene comprising a plurality of objects, the plurality of objects represented by a plurality of models, the method comprising:

receiving information identifying a first model from the plurality of models to be unloaded from computer memory;

using a first representation to determine a first set of models from the plurality of models that depend on the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

unloading, from the computer memory, the first model and one or more models from the first set of models that are loaded in the computer memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.

7. The method of claim 6 wherein using the first representation to determine the first set of models comprises:

for each output of the first model;

determining a first node in the graph representing the output;

traversing the graph from the first node using the links; and

including a model from the plurality of models in the first set of models if at least one node of the model is encountered during the traversing.

8. The method of claim 7 wherein, for each output of the first model, traversing the graph from the first node using the links comprises determining a transitive closure set of all nodes in the graph that represent inputs or outputs of the plurality of models that depend on the output of the first model.

9. The method of claim 6 wherein using the first representation to determine the first set of models comprises determining a transitive closure set of one or more models from the plurality of models that depend on the first model.

10. A computer program product stored on a computer-readable medium for facilitating animation of a scene comprising a plurality of objects, the plurality objects represented by a plurality of models, the computer program product comprising:

code for receiving information identifying a first model to be animated from the plurality of models;

code for using a first representation to determine a set of models from the plurality of models that are needed for evaluation of the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

code for loading the first model and the set of models in computer memory, wherein the plurality of models comprises at least one model that is not loaded into the computer memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.

11. The computer program product of claim 10 wherein the code for using the first representation to determine the set of models comprises:

for each input of the first model;

code for determining a first node in the graph representing the input;

code for traversing the graph from the first node using the links; and

code for including a model from the plurality of models in the set of models if at least one node of the model is encountered during the traversing.

12. The computer program product of claim 11 wherein, for each input of the first model, the code for traversing the directed graph from the first node using the directed links comprises code for determining a transitive closure set of all nodes in the directed graph that represent inputs or outputs of the plurality of models on which the input of the first model depends.

13. The computer program product of claim 10 further comprising code for receiving information specifying animation for the first model.

14. The computer program product of claim 10 wherein the code for using the first representation to determine the set of models comprises code for determining a transitive closure set of one or more models from the plurality of models on which the first model depends.

15. A computer program product stored on a computer-readable medium for facilitating animation of a scene comprising a plurality of objects, the plurality of objects represented by a plurality of models, the computer program product comprising:

code for receiving information identifying a first model from the plurality of models to be unloaded from computer memory;

code for using a first representation to determine a first set of models from the plurality of models that depend on the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

code for unloading, from the computer memory, the first model and one or more models from the first set of models that are loaded in the computer memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.

16. The computer program product of claim 15 wherein the code for using the first representation to determine the first set of models comprises:

for each output of the first model;

code for determining a first node in the graph representing the output;

code for traversing the graph from the first node using the links; and

code for including a model from the plurality of models in the first set of models if at least one node of the model is encountered during the traversing.

17. The computer program product of claim 16 wherein, for each output of the first model, the code for traversing the graph from the first node using the links comprises code for determining a transitive closure set of all nodes in the graph that represent inputs or outputs of the plurality of models that depend on the output of the first model.

18. The computer program product of claim 15 wherein the code for using the first representation to determine the first set of models comprises code for determining a transitive closure set of one or more models from the plurality of models that depend on the first model.

19. A system for facilitating animation of a scene comprising a plurality of objects, the plurality of objects represented by a plurality of models, the system comprising:

a processor;

a volatile memory coupled to the processor;

a storage subsystem coupled to the processor, the storage subsystem is configured to store instructions that when executed by the processor cause the processor to;

receive information identifying a first model to be animated from the plurality of models;

use a first representation to determine a set of models from the plurality of models that are needed for evaluation of the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

load the first model and the set of models in volatile memory, wherein the plurality of models comprises at least one model that is not loaded into the computer memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.

20. The system of claim 19 wherein:

the storage subsystem is configured to store instructions that when executed by the processor cause the processor to

determine, from the graph, a transitive closure set of all inputs and outputs of the plurality of models on which the one or more inputs of the first model depend, and

include a model from the plurality of models in the set of models if an input or output of the model is included in the transitive closure set.

21. The system of claim 19 wherein the storage subsystem is configured to store instructions that when executed by the processor cause the processor to determine a transitive closure set of one or more models from the plurality of models on which the first model depends.

22. A system for facilitating animation of a scene comprising a plurality of objects, the plurality of objects represented by a plurality of models, the system comprising:

a processor;

a volatile memory coupled to the processor;

a storage subsystem coupled to the processor, the storage subsystem is configured to store instructions that when executed by the processor cause the processor to;

receive information identifying a first model from the plurality of models to be unloaded from computer memory;

use a first representation to determine a first set of models from the plurality of models that depend on the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

unload, from the volatile memory, the first model and one or more models from the first set of models that are loaded in the volatile memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.

23. The system of claim 22 wherein:

the storage subsystem is configured to store instructions that when executed by the processor cause the processor to

determine, from the graph, a transitive closure set of all inputs and outputs of the plurality of models that depend on the one or more outputs of the first model, and

include a model from the plurality of models in the first set of models if an input or output of the model is included in the transitive closure set.

24. The system of claim 22 wherein the storage subsystem is configured to store instructions that when executed by the processor cause the processor to determine a transitive closure set of one or more models from the plurality of models that depend on the first model.

25. An apparatus for facilitating animation of a scene comprising a plurality of objects, the plurality of objects represented by a plurality of models, the apparatus comprising:

means for receiving information identifying a first model to be animated from the plurality of models;

means for using a first representation to determine a set of models from the plurality of models that are needed for evaluation of the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

means for loading the first model and the set of models in computer memory, wherein the plurality of models comprises at least one model that is not loaded into the computer memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.

26. An apparatus for facilitating animation of a scene comprising a plurality of objects, the plurality of objects represented by a plurality of models, the apparatus comprising:

means for receiving information identifying a first model from the plurality of models to be unloaded from computer memory;

means for using a first representation to determine a first set of models from the plurality of models that depend on the first model, the first representation comprising information identifying one or more inputs and outputs of the models in the plurality of models and identifying dependencies between the one or more inputs and outputs; and

means for unloading, from the computer memory, the first model and one or more models from the first set of models that are loaded in the computer memory;

wherein the first representation is a graph comprising a plurality of nodes and links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the links represent the dependencies between the inputs and the outputs.