Techniques for rendering complex scenes

• US 7,532,212 B2
• Filed: 05/10/2004
• Issued: 05/12/2009
• 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): Sajous; Wesner
• Assistant Examiner(s): BROOME, SAID A
• Application Number:
  US10/842,962
• Publication Number:
  US 20050248563A1
• Time in Patent Office: 1,828 Days
• Field of Search: None
• US Class Current: 345/423
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

Techniques that facilitate rendering of a scene of arbitrary complexity without having to load all the models involved in the scene simultaneously in computer memory. A representation of the inputs and outputs of the various models involved in the scene and the dependencies between the inputs and the outputs is provided and used to facilitate the rendering process. A tessellator may tessellate the models without having to load information for all the models concurrently into computer memory. The tessellated scene may then be rendered without having to load all the models in the scene concurrently into computer memory.

Claims

1. A computer-implemented method of facilitating rendering of a scene comprising a plurality of models, the method comprising:

determining an ordered list of model references using a first representation, 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, each model reference identifying a model from the plurality of models, wherein determining the ordered list of model references comprises;

generating, based upon the first representation, an ordered list of inputs and outputs represented by the first representation;

determining one or more clusters in the ordered list of inputs and outputs, wherein each cluster comprises one or more inputs or outputs of the same model that are contiguous to each other in the ordered list of inputs and outputs;

generating a final ordered list of inputs and outputs by reordering the inputs and outputs in the ordered list of inputs and outputs to reduce the number of clusters comprising one or more inputs or outputs of a model;

ordering the clusters in the final ordered list of inputs and outputs; and

determining the ordered list of model references based upon the ordering of the clusters; and

processing the model references in order of their position in the ordered list, the processing for each model reference comprising;

loading a model corresponding to the model reference in computer memory, wherein the model is loaded a number of times equal to the number of clusters of the model, the inputs and outputs of one of the clusters being evaluated each time the model is loaded;

generating a result using the loaded model; and

storing the generated result; and

rendering the scene using the stored results, wherein the rendering is performed without loading all of the plurality of models concurrently in the computer memory.

2. The method of claim 1, wherein the first representation is a data structure comprising a plurality of nodes and directed links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the directed links represent the dependencies between the inputs and the outputs.

3. The method of claim 1, wherein rendering the scene comprises:

generating a tessellated representation for each model in the plurality of models using the stored results, wherein the tessellated representation for each model is generated without loading the plurality of models concurrently in the computer memory; and

rendering the scene using the tessellated representations of the plurality of model.

4. The method of claim 1, wherein generating a result using the loaded model for a model reference comprises using a previously stored result to generate the result.

5. A computer-readable medium encoded with a computer program for facilitating rendering of a scene comprising a plurality of models, the computer program comprising:

code for determining an ordered list of model references using a first representation, 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, each model reference identifying a model from the plurality of models, wherein the code for determining the ordered list of model references comprises;

code for generating, based upon the first representation, an ordered list of inputs and outputs represented by the first representation;

code for determining one or more clusters in the ordered list of inputs and outputs, wherein each cluster comprises one or more inputs or outputs of the same model that are contiguous to each other in the ordered list of inputs and outputs;

code for generating a final ordered list of inputs and outputs by reordering the inputs and outputs in the ordered list of inputs and outputs to reduce the number of clusters comprising one or more inputs or outputs of a model; and

code for ordering the clusters in the final ordered list of inputs and outputs; and

code for determining the ordered list of model references based upon the ordering of the clusters; and

code for processing the model references in order of their position in the ordered list, the processing for each model reference comprising;

loading a model corresponding to the model reference in computer memory, wherein the model is loaded a number of times equal to the number of clusters of the model, the inputs and outputs of one of the clusters being evaluated each time the model is loaded;

generating a result using the loaded model; and

storing the generated result; and

code for rendering the scene using the stored results, wherein the rendering is performed without loading all of the plurality of models concurrently in the computer memory.

6. The computer-readable medium of claim 5, wherein the first representation is a data structure comprising a plurality of nodes and directed links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the directed links represent the dependencies between the inputs and the outputs.

7. The computer-readable medium of claim 5, wherein the code for rendering the scene comprises:

code for generating a tessellated representation for each model in the plurality of models using the stored results, wherein the tessellated representation for each model is generated without loading the plurality of models concurrently in the computer memory; and

code for rendering the scene using the tessellated representations of the plurality of models.

8. The computer-readable medium of claim 5, wherein generating a result using the loaded model for a model reference comprises using a previously stored result to generate the result.

9. A system for facilitating rendering of a scene comprising a plurality of models, the system comprising:

a data processing system;

a renderer coupled to the data processing system;

wherein the data processing system is configured to;

determine an ordered list of model references using a first representation, 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, each model reference identifying a model from the plurality of models, wherein determining the ordered list of model references comprises;

generating, based upon the first representation, an ordered list of inputs and outputs represented by the first representation;

determining one or more clusters in the ordered list of inputs and outputs, wherein each cluster comprises one or more inputs or outputs of the same model that are contiguous to each other in the ordered list of inputs and outputs;

generating a final ordered list of inputs and outputs by reordering the inputs and outputs in the ordered list of inputs and outputs to reduce the number of clusters comprising one or more inputs or outputs of a model; and

ordering the clusters in the final ordered list of inputs and outputs; and

determining the ordered list of model references based upon the ordering of the clusters; and

process the model references in order of their position in the ordered list, the processing for each model reference comprising;

loading a model corresponding to the model reference in computer memory of the data processing system, wherein the model is loaded a number of times equal to the number of clusters of the model, the inputs and outputs of one of the clusters being evaluated each time the model is loaded;

generating a result using the loaded model; and

storing the generated result; and

wherein the renderer is configured to render the scene using the stored results, wherein the rendering is performed without loading all of the plurality of models concurrently in computer memory of the renderer.

10. The system of claim 9, wherein the first representation is a data structure comprising a plurality of nodes and directed links between the nodes, wherein the nodes represent the inputs and the outputs of the plurality of models and the directed links represent the dependencies between the inputs and the outputs.

11. The system of claim 9, further comprising a tessellator configured to generate a tessellated representation for each model in the plurality of models using the stored results, wherein the tessellated representation for each model is generated without loading the plurality of models concurrently in the computer memory;

and

wherein the renderer is configured to render the scene using the tessellated representations of the plurality of models.

12. The system of claim 9, wherein the data processing system is configured to generate a result for a model reference using a previously stored result.