US6487565B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Updating animated images represented by scene graphs
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-12-29
•
Granted: 2002-11-26
•
Expires: 2018-12-29
Abstract
Abstract Each frame in an animated graphics sequence has a hierarchical scene graph. Graph elements have creation timestamps that mark them as dirty, requiring rendering, or constant, not requiring rendering anew for the current frame. If an aggregate element is constant, it is rendered as a whole, without investigating its child elements. If dirty elements meet certain criteria, they are merged for rendering as a single unit. In this way, the scene areas to be rendered have variable positions and sizes.
Inventors
- 👤 Greg D. Schechter
- 👤 Chun-Fu R. Yeung
- 👤 Danny R. Dalal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 14:12
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/005; G06T15/00
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
173 words
A method for generating an updated frame from a previous frame of a sequence of frames of a graphical scene having multiple elements, the updated frame including elements from the previous frame that have been modified, each element from the previous frame having an old timestamp, the method comprising: affixing a new timestamp to each element that has been modified; constructing a hierarchical graph of the elements in the updated frame, the hierarchical graph having a number of subgraphs; while traversing the hierarchical graph, detecting that one of the elements has not been modified by comparing the old timestamp of the element to the new timestamp; skipping the traversal of a subgraph of the one element, and identifying at least some of the remaining elements as dirty elements by comparing the old timestamp of one of those remaining elements to the new timestamp; rendering only the dirty elements of the hierarchical graph; and combining the rendered elements with those elements that have not been modified to produce an image of the updated frame.
Claim 2
Independent Claim
173 words
A method for generating an updated frame from a previous frame of a sequence of frames of a graphical scene having multiple elements, the updated frame including elements from the previous frame that have been modified, each element from the previous frame having an old timestamp, the method comprising: affixing a new timestamp to each element that has been modified; constructing a hierarchical graph of the elements in the updated frame, the hierarchical graph having a number of subgraphs; while traversing the hierarchical graph, detecting that one of the elements has not been modified by comparing the old timestamp of the element to the new timestamp; skipping the traversal of a subgraph of the one element, and identifying at least some of the remaining elements as dirty elements by comparing the old timestamp of one of those remaining elements to the new timestamp; rendering only the dirty elements of the hierarchical graph; and combining the rendered elements with those elements that have not been modified to produce an image of the updated frame.
Claim 3
Dependent Claim
46 words
The method of claim 1 wherein the timestamp is selected from a group consisting of a timestamp that specifies the creation time of the element, a timestamp that specifies that the element never changes, and a timestamp that specifies that the element changes for every frame.
Claim 4
Dependent Claim
17 words
The method of claim 2 where the timestamps represent the relative creation times of their respective elements.
Claim 5
Dependent Claim
14 words
The method of claim 2 where modifying the some elements includes updating their timestamps.
Claim 6
Dependent Claim
16 words
The method of claim 1 where at least one of the elements is an overlay element.
Claim 7
Dependent Claim
44 words
The method of claim 5 further comprising, while traversing the graph, detecting that another of the elements has been modified and is not an overlay element, identifying the other element as a dirty element, and skipping traversal of the subgraph of the other element.
Claim 8
Dependent Claim
32 words
The method of claim 5 further comprising, while traversing the graph, detecting that another of the elements has been modified and is an overlay element, traversing the subgraph of the other element.
Claim 9
Dependent Claim
24 words
The method of claim 1 where certain elements represent images of the scene and have boundary boxes indicating their respective positions in the scene.
Claim 10
Dependent Claim
19 words
The method of claim 8 further comprising constructing images of the dirty elements that represent images in the scene.
Claim 11
Dependent Claim
12 words
The method of claim 9 where the constructed images are cropped images.
Claim 12
Dependent Claim
15 words
The method of claim 9 further comprising combining the constructed images into a composite image.
Claim 13
Dependent Claim
18 words
The method of claim 11 where rendering the dirty elements of the graph comprises rendering the composite image.
Claim 14
Dependent Claim
23 words
The method of claim 12 where combining the rendered elements with the unmodified elements comprises overlaying the rendered composite on the previous scene.
Claim 15
Dependent Claim
20 words
The method of claim 8 further comprising merging at least some of the dirty elements into a single merged element.
Claim 16
Dependent Claim
56 words
The method of claim 14 where merging the some dirty elements comprises: calculating a value of a parameter of the boundary boxes of individual ones of the some elements; and merging the some elements if the calculated value bears a predetermined relationship to the value of the parameter of a boundary box containing the some elements.
Claim 17
Dependent Claim
11 words
The method of claim 15 where the parameter is an area.
Claim 18
Dependent Claim
22 words
The method of claim 1 further comprising adding an element to the updated frame that was not present in the previous frame.
Claim 19
Dependent Claim
15 words
The method of claim 17 further comprising including the added element as a dirty element.
Claim 20
Independent Claim
180 words
A medium containing computer-readable instructions for executing a method for generating an updated frame from a previous frame of a sequence of frames of a graphical scene having multiple elements, the updated frame including elements from the previous frame that have been modified, each element from the previous frame having an old timestamp, the method comprising: affixing a new timestamp to each element that has been modified; constructing a hierarchical graph of the elements in the updated frame, the hierarchical graph having a number of subgraphs; while traversing the hierarchical graph, detecting that one of the elements has not been modified by comparing the old timestamp of the element to the new timestamp; skipping the traversal of a subgraph of the one element, and identifying at least some of the remaining elements as dirty elements by comparing the old timestamp of one of those remaining elements to the new timestamp; rendering only the dirty elements of the hierarchical graph; and combining the rendered elements with those elements that have not been modified to produce an image of the updated frame.
Claim 21
Independent Claim
180 words
A medium containing computer-readable instructions for executing a method for generating an updated frame from a previous frame of a sequence of frames of a graphical scene having multiple elements, the updated frame including elements from the previous frame that have been modified, each element from the previous frame having an old timestamp, the method comprising: affixing a new timestamp to each element that has been modified; constructing a hierarchical graph of the elements in the updated frame, the hierarchical graph having a number of subgraphs; while traversing the hierarchical graph, detecting that one of the elements has not been modified by comparing the old timestamp of the element to the new timestamp; skipping the traversal of a subgraph of the one element, and identifying at least some of the remaining elements as dirty elements by comparing the old timestamp of one of those remaining elements to the new timestamp; rendering only the dirty elements of the hierarchical graph; and combining the rendered elements with those elements that have not been modified to produce an image of the updated frame.
Claim 22
Dependent Claim
47 words
The medium of claim 19 where the method further comprises, while traversing the graph, detecting that another of the elements has been modified and is not an overlay element, identifying the other element as a dirty element, and skipping traversal of the subgraph of the other element.
Claim 23
Dependent Claim
45 words
The medium of claim 20 where the method further comprises: constructing images of the dirty elements that represent images in the scene; and combining the constructed images into a composite image, and where rendering to dirty elements of the graph comprises rendering the composite image.
Claim 24
Independent Claim
106 words
A method for rendering a current frame of an animation having a sequence of frames, each frame having a number of images that are represented by a number of elements, each element including a timestamp, the method comprising: replacing an old timestamp of an element with a new timestamp if the element will be modified by an operation; constructing a current scene graph for the current frame by executing one or more operations on one or more elements; and rendering the current scene graph to form a presentation suitable for a display, the act of rendering refraining from rendering an element that lacks a new timestamp.
Claim 25
Independent Claim
106 words
A method for rendering a current frame of an animation having a sequence of frames, each frame having a number of images that are represented by a number of elements, each element including a timestamp, the method comprising: replacing an old timestamp of an element with a new timestamp if the element will be modified by an operation; constructing a current scene graph for the current frame by executing one or more operations on one or more elements; and rendering the current scene graph to form a presentation suitable for a display, the act of rendering refraining from rendering an element that lacks a new timestamp.
Claim 26
Dependent Claim
14 words
The method of claim 22 , wherein each timestamp is a number in sequence.
Claim 27
Dependent Claim
72 words
The method of claim 22 , further comprising classifying each element as a constant image or as a dirty image, the act of classifying categorizing the element as a constant image if the timestamp of the element is an old timestamp and categorizing the element as a dirty image if the timestamp of the element is a new timestamp, wherein the act of rendering renders those elements that are classified as dirty.
Claim 28
Dependent Claim
96 words
The method of claim 24 , wherein constructing a current scene graph for the current frame includes constructing a current scene graph from a number of subgraphs prior to the execution of the act of rendering, each subgraph being formed by a top node and multiple nodes under the top node, each node representing an element, and wherein classifying each element as a constant image or a dirty image includes classifying the multiple nodes in the same category as the top node of a subgraph without categorizing each node of the multiple nodes in the subgraph.
Claim 29
Dependent Claim
44 words
The method of claim 25 , wherein each element is represented by a boundary box having coordinates, and further comprising consolidating a set of boundary boxes if the coordinates of each boundary box overlap with the coordinates of other boundary boxes in the set.
References Cited (Backward Citations)
US4599611A
Cited
US4857902A
Cited
US5189402A
Cited
US5883639A
Cited
US5574503A
Cited
US5708767A
Cited
US5764241A
Cited
US6154215A
Cited
US6100881A
Cited
US6072496A
Cited
US6243706B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-11-25 | 2006-05-27 | 2006-11-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-11-25 | 2010-05-27 | 2010-11-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-11-25 | 2014-05-27 | 2014-11-26 | $7700.00 | Window Closed / Lapsed |