Time inheritance scene graph for representation of media content

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.

What is claimed is:  
     
         1 . A data structure for representing a time-based visual scene as a directed acyclic graph of operators and paths that generate a sequence of image frames over a specified time-interval in the scene comprising: 
 (a) a plurality of nodes, wherein each node in the graph represents an operator;    (b) a plurality of data paths, wherein a directed data path in the graph represents the flow of data from the output data port of one operator to the input data port of another operator;    (c) a plurality of directed control paths, wherein a directed control path in the graph represents the flow of a control signal with associated parameters from the output control port of one operator to the input control port of another operator;    (d) a time-source operator having an output control port that generates a control signal with the specified time-interval parameter and an input data port to accept data that represents the sequence of image frames; and    (e) a time-aware operator having an input control port which can accept a time-interval parameter and an output data port to generate data that represents a sequence of image frames for the time-interval.    
     
     
         2 . A data structure as in  claim 1  wherein: 
 (a) the time-source operator has an input status port to receive a signal that data is ready on an associated input data port; and  
 (b) the time-aware operator has an output status port to send a signal that data is ready on an associated output data port; and  
 (c) the status ports of the time-source and time-aware operators are connected with a directed path representing the flow of a status signal with associated parameters.  
 
     
     
         3 . A data structure as in  claim 1  with at least two time-aware operators wherein: 
 (a) one operator has an output control port that propagates the control signal with associated time-interval parameter from the time-source operator; and  
 (b) the input control port of the second time-aware operator is connected with a directed path to the output control port of the first time-aware operator.  
 
     
     
         4 . A data structure as in  claim 1  with at least two time-aware operators wherein: 
 (a) one operator has an output control port that propagates the control signal from the time-source operator with a modified time-interval parameter; and  
 (b) the input control port of the second time-aware operator is connected with a directed path to the output control port of the first time-aware operator.  
 
     
     
         5 . A data structure as in  claim 1  with at least two time-aware operator nodes wherein: 
 (a) one operator transforms three dimensional data into two-dimensional pixel image data;  
 (b) a second operator transforms two-dimensional pixel image data into three-dimensional data; and  
 (c) the second operator is connected through the graph structure of control paths to the first operator, such that the control output of the first operator is propagated to the control input of the second operator.  
 
     
     
         6 . A data structure as in  claim 1  with at least two time-aware operator nodes where: 
 (a) one operator transforms three-dimensional data into two-dimensional pixel image data; and  
 (b) a second operator uses at least two sources of two-dimensional pixel image data to generate at least one frame of a time-based sequence of visual images.  
 
     
     
         7 . A data structure as in  claim 1  where the time-aware operator generates both a time-based sequence of visual images and a synchronized audio track.  
     
     
         8 . A data structure as in  claim 1  where at least one operator: 
 (a) has an input data path to specify a level-of-detail for an output data path; and  
 (b) produces an output data element at more than one level-of-detail.  
 
     
     
         9 . A data structure as in  claim 1  where at least one operator: 
 (a) maintains a cache of output data elements and the corresponding input control parameters; and  
 (b) substitutes cached output data elements for reprocessing when subsequent processing requests specify similar input control parameters.  
 
     
     
         10 . A data structure as in  claim 1  where an operator in a graph can represent an entire sub-graph of operators with their connecting input and output paths.  
     
     
         11 . A data structure as in  claim 10  where the sub-graph of operators and connections is transformed into an equivalent set of operations in a pipelined data-flow configuration where the data outputs within the original sub-graph are segmented into data-flow streams appropriate for optimizing the throughput of the pipelined implementation.  
     
     
         12 . A data structure as in  claim 1  where the modification to the time-interval is from the set of: 
 (a) a truncated sub-set of the original time-interval; and  
 (b) a linear transform applied to the original time-interval; and  
 (c) a non-linear transform applied to the original time-interval; and  
 (d) the substitution of a time-interval unrelated to the original time-interval.  
 
     
     
         13 . A data structure as in  claim 1  wherein the topology of the scene graph is such that: 
 (a) each path is a directed arc between operators;  
 (b) all data paths have the same direction in the graph;  
 (c) all control paths have the same direction in the graph (opposite from the data paths); and  
 (d) all status paths have the same direction in the graph (same as the data paths).  
 
     
     
         14 . A scene graph for use in animation, rendering and compositing applications wherein the concept of time-intervals are integrated into a data-flow oriented graph control structure, such during evaluation of the scene, time data flows in one direction with control data, while data representing the time interval flows back in the reverse direction.