Tracking the validity of cache frames in digital movie editing

• US 7,103,839 B1
• Filed: 10/03/2000
• Issued: 09/05/2006
• Est. Priority Date: 10/03/2000
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Simons, David P., Natkin, Michael J.
• Primary Examiner(s): Lo, Weilun
• Assistant Examiner(s): Chuong, Truc T.
• Application Number:
  US09/680,155
• Time in Patent Office: 2,163 Days
• Field of Search: 345/660, 345/724, 345/418, 345/700, 345/565, 345/760, 345/769, 345723-725, 345/726, 345/731, 345/732, 348/135, 348/155, 715/719, 715/723, 715/726
• US Class Current: 715/723
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence

Abstract

Methods and apparatus, including computer program products, implementing and using techniques for determining validity of cached frames of a compositing hierarchy as a composition tree of a digital video composition is edited. The techniques use interval lists associated with nodes in a compositing tree to determine which cached frames of a composition hierarchy are guaranteed to be valid in the face of arbitrary edits to the hierarchy.

Claims

1. A computer program product, tangibly stored on a computer-readable medium, for calculating the validity of a cached frame of a movie in a movie compositing system, comprising instructions operable to cause a programmable processor to:

maintain a global editing timestamp that is updated with each editing operation performed by the system, the global editing timestamp representing an edit sequence position in a sequence of edits made to the movie;

establish an interval list for each node in a compositing tree defining a movie, each node having a timeline that maps to a master timeline of the movie, an interval list for a node including, for each interval in the node'"'"'s timeline, a single editing timestamp;

update the interval list for a node when the node is edited; and

use the interval list for a first node to evaluate the validity of a cached frame for a particular interval of the master timeline, the cached frame having been produced by compositing the first node in the compositing tree, the evaluation being performed by (a) comparing (i) an editing timestamp associated with the cached frame with (ii) the editing timestamps of intervals in the interval list that map to at least a portion of the interval of the master timeline, and (b) treating the cached frame as invalid if any of the intervals'"'"' editing timestamps is later than the editing timestamp associated with the cached frame.

2. The product of claim 1, further comprising instructions to:

use the interval lists of all nodes below the first node in the tree to evaluate the validity of the cached frame.

3. The product of claim 1, wherein:

updating the global timestamp comprises incrementing the global timestamp; and

the interval list is stored as a series of pairs (interval, timestamp), the series being sorted by the intervals.

4. The product of claim 3, wherein:

the series of (interval, timestamp) pairs are sorted in ascending order of intervals.

5. A computer program product, tangibly stored on a machine-readable medium, for displaying a frame of a movie composition, the product comprising instructions operable to cause a programmable processor to:

associate edit sequence information with an element of the movie composition, the edit sequence information specifying, for an interval of the element'"'"'s timeline, an edit sequence position representing the position in a sequence of edits made to the movie composition of a most recent edit made that affects the element during the interval, the interval being a portion of the timeline;

when caching a frame, associate with the cached frame an edit sequence position that represents a state of editing of the movie composition; and

when displaying the frame, compare the edit sequence position associated with the cached frame with edit sequence information associated with the element.

6. The product of claim 5, wherein:

the edit sequence position that represents a state of editing of the movie composition includes the edit sequence position of a most recent edit made to the movie composition.

7. The product of claim 5, further comprising instructions to:

in response to an edit made to the movie composition, update the edit sequence information.

8. The product of claim 7, wherein:

the instructions to compare include instructions to compare the sequence position associated with the cached frame with the updated sequence information.

9. The product of claim 5, further comprising instructions to:

for an edit made to the movie composition, identify an interval of the element'"'"'s corresponding timeline that may be affected by the edit.

10. The product of claim 9, wherein:

the identified interval is the maximum range during which the edit may affect the element.

11. The product of claim 5, further comprising instructions to:

for an edit made, identify an interval of the element'"'"'s corresponding timeline that is affected by the edit.

12. The product of claim 5, wherein instructions to compare include instructions to:

identify the edit sequence position of the most recent edit from the sequence information associated with the element; and

compare the edit sequence position associated with the cached frame with the identified edit sequence position.

13. The product of claim 5, wherein the sequence information associated with the element is placed into groups, the product further comprising instructions to:

identify the most recent edit sequence information for each group.

14. The product of claim 5, wherein:

the edit sequence information includes an interval list, the interval list specifying, for each interval of the element'"'"'s timeline, the edit sequence position representing a position in a sequence of edits made to the composition of a most recent edit made that affects the element during the interval.

15. The product of claim 14, wherein:

each interval of the interval list includes a start time; and

except for the last listed interval of the interval list, each interval of the interval list is delimited by its start time and the start time of the subsequent interval.

16. The product of claim 15, wherein:

the movie composition has a master timeline to which the element'"'"'s timeline maps, the master time line including a start time and a stop time;

the first interval listed in the element'"'"'s interval list has a start time that precedes the start time of the composition'"'"'s master timeline; and

the last interval listed in the element'"'"'s interval list extends beyond the stop time of the composition'"'"'s master timeline.

17. The product of claim 15, further comprising instructions to:

for an edit, determine the start time and duration of an interval when the edit may affect the element, and define new intervals in the interval list if the interval list does not include an interval having the start time and duration of the determined interval, the new intervals being defined based on the start time and the duration of the determined interval.

18. The product of claim 17, wherein:

the instructions to define new intervals include instructions to define new intervals such that the intervals in the interval list do not overlap.

19. The product of claim 17, further comprising:

associate the edit sequence position of the edit with the determined interval.

20. The product of claim 15, wherein:

the edit sequence position is represented by an integer.

21. The product of claim 20, wherein:

the interval list of an element includes a first array and a second array that is parallel to the first array, the first array including start times and the second array including integers representing edit sequence positions.

22. The product of claim 14, further comprising instructions to:

when displaying the frame, identify the interval of the interval list that affects the frame and compare the edit sequence position associated with the cached frame with the edit sequence position listed in the interval list for the identified interval.

23. The product of claim 14, further comprising instructions to:

maintain a first interval list for a first type of type of edits and a second interval list for a second type of edits.

24. The product of claim 23, further comprising instructions to:

in response to an edit to the composition, identify one or more interval lists to update; and

update the identified interval lists.

25. The product of claim 5, wherein:

the element is a first element and the movie composition includes multiple elements; and

the elements of the movie composition are nodes in a compositing tree, a parent node in the compositing tree being affected by changes to a child node in the compositing tree, the product further comprising instructions to;

when displaying the frame, identify one or more elements that are child nodes of the first element, the instructions to compare including instructions to compare the edit sequence position associated with the cached frame with the edit sequence information associated with the one or more elements identified as child nodes of the first element.

26. The product of claim 5, wherein:

the element is a first element and the movie composition includes multiple elements; and

the first element collaterally depends and one or more other elements in the movie composition, an element that is collaterally dependent on another element being affected by the other element, the product further comprising instructions to;

when displaying the frame, identify one or more elements on which the first element collaterally depends, the instructions to compare includes instructions to compare the edit sequence position associated with the cached frame to the edit sequence information associated with the one or more identified elements.

27. The product of claim 5, further comprising instructions to:

validate the cached frame when the edit sequence position associated with the cached frame specifies an edit that is as or more recent than an edit specified by the current edit sequence position specified recent as by the edit sequence information for the interval of the element'"'"'s timeline.

28. A method for displaying a frame of a movie composition, the method comprising:

associating edit sequence information with an element of the movie composition, the edit sequence information specifying, for an interval of the element'"'"'s timeline, an edit sequence position representing the position in a sequence of edits made to the movie composition of a most recent edit made that affects the element during the interval, the interval being a portion of the timeline;

when caching a frame, associating with the cached frame an edit sequence position that represents a state of editing of the movie composition; and

when displaying the frame, comparing the edit sequence position associated with the cached frame with edit sequence information associated with the element.

29. The method of claim 28, wherein:

the edit sequence position that represents a state of editing of the movie composition includes the edit sequence position of a most recent edit made to the movie composition.

30. The method of claim 28, further comprising:

in response to an edit made to the movie composition, updating the edit sequence information.

31. The method of claim 30, wherein:

the instructions to compare include instructions to compare the sequence position associated with the cached frame with the updated sequence information.

32. The method of claim 28, further comprising:

for an edit made to the movie composition, identifying an interval of the element'"'"'s corresponding timeline that may be affected by the edit.

33. The method of claim 32, wherein:

the identified interval is the maximum range during which the edit may affect the element.

34. The method of claim 28, further comprising:

for an edit made, identifying an interval of the element'"'"'s corresponding timeline that is affected by the edit.

35. The method of claim 28, wherein comparing includes:

identifying the edit sequence position of the most recent edit from the sequence information associated with the element; and

comparing the edit sequence position associated with the cached frame with the identified edit sequence position.

36. The method of claim 28, wherein the sequence information associated with the element is placed into groups, the method further comprising:

identifying the most recent edit sequence information for each group.

37. The method of claim 28, wherein:

the edit sequence information includes an interval list, the interval list specifying, for each interval of the element'"'"'s timeline, the edit sequence position representing a position in a sequence of edits made to the composition of a most recent edit made that affects the element during the interval.

38. The method of claim 37, wherein:

each interval of the interval list includes a start time; and

except for the last listed interval of the interval list, each interval of the interval list is delimited by its start time and the start time of the subsequent interval.

39. The method of claim 38, wherein:

the movie composition has a master timeline to which the element'"'"'s timeline maps, the master time line including a start time and a stop time;

the first interval listed in the element'"'"'s interval list has a start time that precedes the start time of the composition'"'"'s master timeline; and

the last interval listed in the element'"'"'s interval list extends beyond the stop time of the composition'"'"'s master timeline.

40. The method of claim 38, further comprising:

for an edit, determining the start time and duration of an interval when the edit may affect the element, and define new intervals in the interval list if the interval list does not include an interval having the start time and duration of the determined interval, the new intervals being defined based on the start time and the duration of the determined interval.

41. The method of claim 40, wherein:

defining new intervals include defining new intervals such that the intervals in the interval list do not overlap.

42. The method of claim 40, further comprising:

associating the edit sequence position of the edit with the determined interval.

43. The method of claim 38, wherein:

the edit sequence position is represented by an integer.

44. The method of claim 43, wherein:

the interval list of an element includes a first array and a second array that is parallel to the first array, the first array including start times and the second array including integers representing edit sequence positions.

45. The method of claim 37, further comprising:

when displaying the frame, identifying the interval of the interval list that affects the frame and compare the edit sequence position associated with the cached frame with the edit sequence position listed in the interval list for the identified interval.

46. The method of claim 37, further comprising:

maintaining a first interval list for a first type of type of edits and a second interval list for a second type of edits.

47. The method of claim 46, further comprising:

in response to an edit to the composition, identifying one or more interval lists to update; and

update the identified interval lists.

48. The method of claim 28, wherein:

the element is a first element and the movie composition includes multiple elements; and

the elements of the movie composition are nodes in a compositing tree, a parent node in the compositing tree being affected by changes to a child node in the compositing tree, the method further comprising;

when displaying the frame, identifying one or more elements that are child nodes of the first element, the step of comparing including comparing the edit sequence position associated with the cached frame with the edit sequence information associated with the one or more elements identified as child nodes of the first element.

49. The method of claim 28, wherein:

the element is a first element and the movie composition includes multiple elements; and

the first element collaterally depends and one or more other elements in the movie composition, an element that is collaterally dependent on another element being affected by the other element, the method further comprising;

when displaying the frame, identifying one or more elements on which the first element collaterally depends, the step of comparing includes comparing the edit sequence position associated with the cached frame to the edit sequence information associated with the one or more identified elements.

50. The method of claim 28, further comprising:

validating the cached frame when the edit sequence position associated with the cached frame specifies an edit that is as or more recent than an edit specified by the current edit sequence position specified recent as by the edit sequence information for the interval of the element'"'"'s timeline.