Method and apparatus for handling secondary dependencies

• US 6,756,994 B1
• Filed: 08/07/2000
• Issued: 06/29/2004
• Est. Priority Date: 08/07/2000
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Tlaskal, Martin Paul
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): RAHMJOO, MANUCHEHR
• Application Number:
  US09/633,886
• Time in Patent Office: 1,422 Days
• Field of Search: 345/440, 345/648, 345/619, 345/622, 345/672, 345/441
• US Class Current: 345/648
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing

Abstract

A method and apparatus for creating a series of images is disclosed. The method manages secondary dependencies of regions in a more efficient manner than the prior art. The present invention creates contents labels that represent either leaf node regions or the composition of two other contents labels, manages the reference counting of contents labels and provides a means for determining if there exists a contents label which represents the composition of two other contents labels. The present invention damages contents labels by preferably adding entries to a damage hash table. The present invention utilizes secondary dependency “Directed Acyclic Graphs” (herein referred to as “Dags”) (700) which are stored in every binary node and define the secondary dependency relationship between the contents label created in that node. Information is provided by the present invention as to whether a contents label which has the potential to come into existence is damaged in any way, via examination of secondary dependency Dags associated with the contents label. Information is also provided on whether rendering can be avoided by determining the properties of particular compositing operators involved in a rendering operation.

Claims

1. A method of creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects according to a compositing tree representing a compositing expression, said compositing tree including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said method comprising the steps of:

(a) for each said node, dividing a component image space in which said outlines are defined into one or more mutually exclusive regions, each said region being related to at least one graphical object and being substantially formed by one or more of said predetermined outlines, wherein each said node has at least one associated region;

(b) generating at least one directed acyclic graph for substantially each node of said compositing tree, said directed acyclic graph identifying, for at least one region associated with a particular node, those regions associated with any other nodes of said compositing tree that if changed can affect said at least one region;

(c) rendering a first image of said series by compositing any one or more of said regions substantially according to said compositing tree;

(d) in response to at least one change to at least one of said nodes of said compositing tree,

(i) examining the directed acyclic graph corresponding to said at least one node to identify those of said regions affected by said at least one change, wherein if at least one of said regions associated with said at least one node is indirectly affected by a change to at least one other of said regions associated with any other node of said compositing tree, said indirectly affected region is identified by inference through association with at least one other of said affected regions, said inference being determined through said examination of the directed acyclic graph corresponding to said at least one node,

(ii) for each node having affected regions, updating the corresponding identified regions and incorporating into said node those new regions arising from the change and/or removing any of said regions that are no longer relevant,

(iii) updating directed acyclic graphs corresponding to at least each node having affected regions to reflect changes to said compositing tree, and

(iv) rendering a further image of said series by compositing those regions affected by said at least one change; and

(e) repeating step (d) for further changes to at least one of said nodes of said compositing tree.

2. A method according to claim 1, further comprising the step of approximating each said predetermined outline on the outside and the inside to form an outline region.

3. A method according to claim 2, wherein each said outline region is approximated to a grid.

4. A method according to claim 1, wherein step (b) includes examining each said region to determine an opacity of each of said objects within said region.

5. A method according to claim 1, wherein a dependency information is created for each of said regions.

6. A method according to claim 1, wherein said directed acyclic graph includes:

a first dependency list identifying those regions directly affected by a change to a particular region; and

a second dependency list identifying those regions indirectly affected by a change to said particular region.

7. A method according to claim 6, wherein directly affected regions are those regions having content modified as a consequence of change.

8. A method according to claim 6, wherein indirectly affected regions are those regions which may include modified region outlines and/or content generation as a result of change.

9. A method according to claim 1, wherein at least one change includes changing the attributes of nodes of said compositing tree.

10. A method according to claim 1, wherein each of said mutually exclusive regions comprises a label.

11. A method according to claim 10, wherein said label is configured as a pointer to a properties structure.

12. A method according to claim 11, wherein said properties structure comprises data defining the properities of a region associated with said structure.

13. A method of creating a series of images, said images being formed by rendering a plurality of graphical objects to be composited according to a compositing tree, said compositing tree including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said method comprising the steps of:

(a) for each said node, dividing a space in which said outlines are defined into one or more mutually exclusive regions, wherein each said node has at least one associated region;

(b) generating at least one directed acyclic graph for substantially each node of said compositing tree, said directed acyclic graph identifying, for at least one region associated with a particular node, those regions associated with any other nodes of said compositing tree that if changed can affect said at least one region;

(c) rendering a first image of said series utilising said compositing tree;

and then, in response to at least one change to at least one of said nodes,

(d) examining said directed acyclic graphs for substantially each node of said compositing tree,

(i) for a node with affected regions, updating the corresponding regions on the basis of said examination, wherein if at least one of said regions is indirectly affected by a change to at least one other of said regions, said indirectly affected region is identified by inference through association with at least one other of said affected regions, said inference being determined through said examination of the directed acyclic graph corresponding to said node with affected regions,

(ii) updating said directed acyclic graphs corresponding to at least each node having affected regions to reflect changes to said compositing tree, and

(iii) rendering a further image of said series by compositing those regions -affected by said at least one change; and

(e) repeating step (d) for further changes to at least one of said nodes of said compositing tree.

14. A method according to claim 13, further comprising the step of approximating each said predetermined outline on the outside and the inside to form an outline region.

15. A method according to claim 14, wherein each said outline region is approximated to a grid.

16. A method according to claim 13, wherein step (b) includes examining each said region to determine an opacity of each of said objects within said region.

17. A method according to claim 13, wherein a directed acyclic graph is created for each of said regions.

18. A method according to claim 13, wherein said directed acyclic graph includes:

a first dependency list identifying those regions directly affected by a change to a particular region; and

a second dependency list identifying those regions indirectly affected by a change in said particular region.

19. A method according to claim 18, wherein directly affected regions are those regions having content modified as a consequence of change.

20. A method according to claim 18, wherein indirectly affected regions are those regions which may include modified region outlines and/or content generation as a result of change.

21. A method according to claim 13, wherein at least one change includes changing the attributes of nodes in said compositing tree.

22. A method according to claim 13, wherein each of said mutually exclusive regions comprises a label.

23. A method according to claim 22, wherein said label is configured as a pointer to a properties structure.

24. A method according to claim 23, wherein said properties structure comprises data defining the properties of a region associated with said structure.

25. A method of creating a series of images, said images being formed by rendering at least a plurality of graphical objects to be composited according to a compositing tree, said compositing tree including a plurality of nodes each representing a component of at least one of said images, said method comprising the steps of:

(a) for each said node, dividing a component image space in which said graphical objects are defined into one or more regions, wherein each said node has at least one associated region;

(b) generating at least one directed acyclic graph for substantially each node of said compositing tree, said directed acyclic graph identifying, for at least one region associated with a particular node, those regions associated with any other nodes of said compositing tree that if changed can affect said at least one region;

(c) rendering a first image of said series utilising said compositing tree;

and then, in response to at least one change to at least one of said nodes,

(d) examining said directed acyclic graphs for substantially each node of said hierarchical structure, and

(i) for a node with affected regions, updating the corresponding directed acyclic graphs, wherein if at least one of said regions is indirectly affected by a change to at least one other of said regions, said indirectly affected region is identified by inference from being associated with at least one other of said affected regions, said inference being determined through said examination of the directed acyclic graph corresponding to said node with affected regions,

(ii) updating said directed acyclic graphs corresponding to at least each node having affected regions to reflect changes to said compositing tree, and

(iii) rendering a further image of said series; and

(e) repeating step (d) for further changes to at least one of said nodes of said compositing tree.

26. A method according to claim 25, further comprising the step of approximating each said predetermined outline on the outside and the inside to form an outline region.

27. A method according to claim 26, wherein each said outline region is approximated to a grid.

28. A method according to claim 25, wherein step (a) includes examining each said region to determine an opacity of each of said objects within said region.

29. A method according to claim 25, wherein said directed acyclic graph is created for each of said regions.

30. A method according to claim 25, wherein said directed acyclic graphs include:

a first dependency list identifying those regions directly affected by a change to said one region; and

a second dependency list identifying those regions indirectly affected by a change in said one region.

31. A method according to claim 30, wherein directly affected regions are those regions having content modified as a consequence of change.

32. A method according to any one of claim 30 or 31, wherein indirectly affected regions are those regions which may include modified region outlines and/or content generation as a result of change.

33. A method according to any one of claim 25, wherein at least one change includes changing the attributes of nodes in said compositing tree.

34. An apparatus for creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects according to a compositing tree representing a compositing expression, said compositing tree including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said apparatus comprising:

division means for dividing a component image space in which said outlines are defined, corresponding to each said node of said compositing tree, into one or more mutually exclusive regions, each said region being related to at least one graphical object and being substantially formed by one or more of said predetermined outlines, wherein each node of said compositing tree has at least one associated region;

directed acyclic graph creation means for generating at least one directed acyclic graph for substantially each node of said hierarchical structure, said directed acyclic graph identifying, for at least one region associated with a particular node, those regions associated with any other nodes of said compositing tree that if changed can affect said at least one region;

render means for rendering a first image of said series by compositing any one or more of said regions substantially according to said compositing tree;

examination means for examining the directed acyclic graph corresponding to at least one of said nodes in response to at least one change to said at least one nodes, to identify those of said regions affected by said at least one change, wherein if at least one of said regions is indirectly affected by a change to at least one other of said regions associated with any other node of said compositing tree, said indirectly affected region is identified by inference through association with at least one other of said affected regions, said inference being determined through said examination of the directed acyclic graph corresponding to said at least one node, and wherein for each node with affected regions, the corresponding identified regions are updated by an updating means and those new regions arising from the change are incorporated into said node and/or any of said regions that are no longer relevant are removed, wherein the directed acyclic graphs corresponding to at least said nodes with affected regions are updated to reflect changes to said compositing tree, and wherein said render means renders a further image of said series by compositing those regions affected by said at least one change.

35. The apparatus according to claim 34, further comprising means for approximating each said predetermined outline on the outside and the inside to form an outline region.

36. The apparatus according to claim 35, wherein each said outline region is approximated to a grid.

37. The apparatus according to claim 34, wherein a directed acyclic graph is created for each of said regions.

38. The apparatus according to claim 34, wherein said directed acyclic graphs include:

a first dependency list identifying those regions directly affected by a change to a particular region; and

a second dependency list identifying those regions indirectly affected by a change in said particular region.

39. The apparatus according to claim 38, wherein directly affected regions are those regions having content modified as a consequence of change.

40. The apparatus according to claim 37, wherein indirectly affected regions are those regions which may include modified region outlines and/or content generation as a result of change.

41. The apparatus according to claim 34, wherein at least one change includes changing the attributes of nodes in said compositing tree.

42. The apparatus according to claim 34, wherein each of said mutually exclusive regions comprises a label.

43. The apparatus according to claim 42, wherein said label is configured as a pointer to a properties structure.

44. The apparatus according to claim 43, wherein said properties structure comprises data defining the properties of a region associated with said structure.

45. A computer readable medium for storing a program for apparatus which processes data, said processing comprising a process for creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects to be composited according to a compositing tree representing a compositing expression, said compositing tree including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said program comprising:

code for dividing a component image space in which said outlines are defined into one or more mutually exclusive regions, each said region being related to at least one graphical object and being formed by one or more of said predetermined outlines, wherein each node of said compositing tree has at least one associated region;

code for generating at least one directed acyclic graph for substantially each node of said compositing tree, said directed acyclic graph identifying, for at least one region associated with a particular node, those regions that if changed can affect said at least one region;

code for rendering a first image of said series by compositing any one or more of said regions substantially according to said compositing tree;

code for examining said directed acyclic graph corresponding to at least one of said nodes in response to at least one change to said at least one nodes, to identify those of said regions affected by said at least one change, wherein if at least one of said regions is indirectly affected by a change to at least one other of said regions associated with any other node of said compositing tree, said indirectly affected region is identified by inference through association with at least one other of said affected regions, said inference being determined through said examination of the directed acyclic graph corresponding to said at least one node;

code for updating the corresponding identified regions for each node with affected regions, and incorporating into said node those new regions arising from the change and/or removing any of said regions that are no longer relevant;

code for updating the directed acyclic graphs corresponding to at least said nodes with affected regions to reflect changes to said compositing tree; and

code for rendering a further image of said series by compositing those regions affected by said at least one change.