Time inheritance scene graph for representation of media content

• US 6,266,053 B1
• Filed: 04/03/1998
• Issued: 07/24/2001
• Est. Priority Date: 04/03/1998
• Status: Expired due to Fees

• Current Assignee: Synapix Incorporated
• Original Assignee: Synapix Incorporated
• Inventors: French, Michael T., Robotham, John S.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Huynh, Cong-Lac
• Application Number:
  US09/054,603
• Time in Patent Office: 1,208 Days
• Field of Search: 345/302, 345/339, 345/440, 345/149, 707/501
• US Class Current: 715/255
• CPC Class Codes: A63F 2300/8082 Virtual reality
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

A technique for representing a visual scene as a directed acyclic graph of data and operators that generates a sequence of image frames over specified time intervals. The graph specifies temporal and spatial values for associated visual elements of the scene. Time is modeled in the inheritance properties explicitly defined within the scene graph hierarchy, by assigning temporal attributes to each media element. Branch nodes of the graph specify transforms for the temporal and spatial coordinate systems. To evaluate the appearance or behavior of the scene and in particular the global time values of particular elements at a given time instant, the graph is traversed in a direction from a root node down toward the leaf nodes, thereby causing temporal transformations specified along the branches of the graph to modify time parameters of the scene data at the nodes. Child nodes are preferably evaluated after being transformed, to determine the extent to which they contribute the data to the final scene. Temporal transformations may include translation operations that offset temporal event times; scaling operations that change the rate at which time passes; or clipping operations, that restrict the range of time parameters to exclude the evaluation of parts of the graph.

Claims

1. A method of specifying a choreographed media production as a graph of nodes and acyclic directed paths defining related sets of forward and reverse traversals comprising the steps of:

(b) adding to the graph a leaf node with a data-generation function that generates in a reverse traversal data related to the choreographed media production based on a temporal context;

(c) adding to the graph an intermediate node with a temporal transform that takes a temporal context as an input and derives a new temporal context as the output, during a forward traversal, and then restores the forward traversal'"'"'s input temporal context during the corresponding reverse traversal; and

(d) connecting the intermediate node into the graph with a directed path that defines both a forward traversal that carries a temporal context from the root node through the intermediate node to the leaf node and a symmetric reverse traversal that begins when the forward traversal is completed and ends at the root node;

wherein the root node defines both a spatial context and temporal context, the intermediate node includes the ability to apply a spatial transform during forward traversal and reverse this spatial transform during reverse traversal, and the leaf node bases its data-generation function on both the spatial context and temporal context.

2. A method as in claim 1 in which a traversal generates a sequence of pixel regions based on the time context.

3. A method as in claim 1 in which a traversal generates a sequence of pixel regions ans synchronized audio track based on the time context.

4. A method as in claim 1 in which the intermediate node also in the reverse traversal generates data related to the choreographed media production before restoring the forward traversal'"'"'s input temporal context.

5. A method as in claim 1 in which the spatial context is a two-dimensional context.

6. A method as in claim 1 in which the spatial context is a three-dimensional context.

7. A method as in claim 1 in which a segment of the graph represents a rendering process with a spatial transform that transforms a three-dimensional spatial context into a two-dimensional spatial context based on parameters for generating an image frame from a three-dimensional scene.

8. A method as in claim 1 in which a segment of the graph represents an image analysis process with a spatial transform that transforms a two-dimensional spatial context into a three-dimensional spatial context, based on parameters from the analysis of at least two image framed to recover three dimensional data from the visual scene represented by the images frames.

9. A method as in claim 1 in which a plurality of root nodes, a plurality of intermediate nodes and a plurality of leaf nodes are present in the graph and connected with acyclic directed paths, each directed path starting at one of the plurality of root nodes.

10. A method as in claim 1 in which a temporal transform within an intermediate node can terminate the forward traversal and initiate the reverse traversal based on transforming one of the parameters of the input time context to a null value.

11. A method as in claim 1 wherein the temporal transform within an intermediate node specifies a time scale for the input time context.

12. A method as in claim 1 wherein a set of operations and related connections contained in a portion of the graph is collapsed and represented as a single node with associated connections.

13. A method as in claim 1 wherein the data-generation function specifies how operations may be pipelined.

14. A method as in claim 1 wherein an advance traversal of multiple nodes provides parameters for set-up functions performed by nodes during this advance traversa.

15. A method as in claim 1 in which the graph structure is presented in a user interface as a schematic diagram with nodes represented as shapes and the paths connecting nodes represented as lines or arcs.

16. A method as in claim 1 in which a node is presented in a user interface as a track in a time line, an the result of applying the node'"'"'s time transform to a time context is presented as a time interval displayed with the associated track.

17. A method as in claim 16 in which user manipulation of the time interval alters at least one parameter of the time transform.

18. A method as in claim 1 wherein a forward traversal carries within the temporal context a constraint parameter that specifies modifications to processing performed during the reversal traversal.

19. A method as in claim 18 wherein the constraint is selected from the group consisting of image quality, sound quality, level of detail, processing time, and render functions.