Method of compiling compositing expressions for optimised rendering

• US 7,190,376 B1
• Filed: 03/14/2000
• Issued: 03/13/2007
• Est. Priority Date: 03/16/1999
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Tonisson, Alan
• Primary Examiner(s): Brier; Jeffery
• Assistant Examiner(s): AMINI, JAVID A
• Application Number:
  US09/524,698
• Time in Patent Office: 2,555 Days
• Field of Search: 345/619, 345/620, 345/629
• US Class Current: 345/629
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A method of creating an image utilizing a table of levels known as a “level activation table” (34) is disclosed. The method uses the level activation table to optimally evaluate a given compositing expression such that the number of pixel operations needed to evaluate the expression is minimized. The method determines the smallest regions in which compositing operations need to be performed and uses these regions to produce the level activation tables where clipping is applied to operations in order to avoid redundant and/or incorrect pixel operations. The method is preferably used in a compositing model in which objects are composited onto a page using a stack machine and an associated compositing stack (38). The stack 38 may be manipulated using standard stack operations such as push, pull and pop. Instructions for the stack machine are taken from the level activation table 34.

Claims

1. A method of creating a pixel image, the pixel image to be formed by rendering and compositing a plurality of graphical objects according to an expression tree representing a compositing expression for the image, at least one of said graphical objects being non-rectangular, the expression tree comprising a plurality of nodes arranged in a hierarchical structure, each of said nodes representing one of the objects or a compositing operation for combining graphical objects or results of other compositing operations, each of the graphical objects having a predetermined object outline forming a region comprising a plurality of pixels therein, said method comprising the steps of:

determining an active region for each of the graphical object nodes, the active region for each particular graphical object node being equal to the region inside the predetermined object outline for the graphical object represented by the particular graphical object node;

determining an active region for each of the compositing operation nodes, the active region for each particular compositing operation node being determined based on the active regions of each child node of the particular compositing operation node;

determining a clip region for each of the compositing operation nodes, the clip region for each particular compositing operation node being equal to the intersection of the active region of the particular compositing operation node and the clip region of a parent compositing operation node of the particular compositing operation node, at least one of the clip regions determined for one of the compositing operation nodes being smaller in area than the active region for said one compositing operation node;

determining an effective region for each of the compositing operation nodes, the effective region for each particular compositing operation node being equal to the intersection of the clip region of the particular compositing operation node and the active regions of the child nodes of the particular compositing operation node, at least one of said effective regions determined for one of said compositing operation nodes being smaller in area than the clip region for said one compositing operation node; and

applying the compositing operation represented by each operation node to the pixels falling wholly within the corresponding effective region for the operation node to create the image, wherein pixels falling outside the effective regions are disregarded in applying the compositing operations and the arrangement of nodes in the hierarchical structure remains stable during the creation of the image.

2. A method according to claim 1, wherein each clip region is dependent upon an active region of a child node of a particular compositing operation node.

3. A method according to claim 1, wherein a wholly opaque object in a particular region acts to eliminate one or more compositing operation nodes contributing to at least one other object constituting the particular region, wherein the at least one other object is obscured by the wholly opaque object in a space in which the outlines are defined.

4. A method of creating a pixel image, the pixel image to be formed by rendering and compositing a plurality of graphical objects according to an expression tree representing a compositing expression for the image, at least one of said graphical objects being non-rectangular, the expression tree comprising a plurality of nodes arranged in a hierarchical structure, each of said nodes representing one of the objects or a compositing operation for combining graphical objects or results of other compositing operations, each of the graphical objects having a predetermined object outline forming a region comprising a plurality of pixels therein, said method comprising the steps of:

determining an active region corresponding to each of the graphical object nodes, the active region for each particular graphical object node being equal to the region inside the predetermined object outline for the graphical object represented by the particular graphical object node;

determining an active region for each of the compositing operation nodes, the active region for each particular compositing operation node being determined based on the active regions of each child node of the particular compositing operation node;

determining a clip region for the compositing operation nodes, the clip region for each particular compositing operation node being equal to the intersection of the active region of the particular compositing operation node and the clip region of a parent compositing operation nodes of the particular compositing operation node, at least one of the clip regions determined for one of the compositing operation nodes being smaller in area than the active region for said one compositing operation node;

determining an effective region for each of the compositing operation nodes, the effective region for each particular compositing operation node being equal to the intersection of the clip region of the particular compositing operation node and active regions of the child nodes of the particular compositing operation node, at least one of said effective regions determined for one of said compositing operation nodes being smaller in area than the clip region for said one compositing operation node;

mapping the effective regions and compositing operations associated with corresponding compositing operation nodes into a compositing table, comprising a plurality of levels, wherein each level of the compositing table represents one of the operators or an outline for clipping at least one other level; and

compositing the image using the compositing table, wherein pixels falling outside the effective regions are disregarded in applying the compositing operations and the arrangement of nodes in the hierarchical structure remains stable during the creation of the image.

5. A method according to claim 4, wherein each of the clip regions is dependent upon an active region of a child node of a particular compositing operation node.

6. A method according to claim 4, wherein a level comprising a push operation is added to the compositing table.

7. A method according to claim 4, wherein a corresponding compositing expression corresponding to an active region is complex.

8. A method according to claim 4, wherein a level comprising a clip operation is added to the compositing table.

9. A method according to claim 4, wherein an active region is determined on the basis that the corresponding compositing operation node has a complex left operand.

10. A method according to claim 9, wherein a level comprising a pop operation is added to the compositing table.

11. A method according to claim 10, wherein the pop operation will remove any unused pixel being outside an active region representing the complex left operand, during compositing of the complex left operand.

12. A method according to claim 11, wherein the active region is the active region of the complex left operand.

13. A method according to claim 11, wherein the active region is transformed to an effective region by the pop operation.

14. A method according to claim 13, wherein the effective region is the effective region of the complex left operand.

15. A method according to claim 13, wherein the effective region corresponds to a complex expression.

16. A method according to claim 15, wherein a level comprising a clip operation is added to the compositing table.

17. A method according to claim 4, wherein an active region is determined on the basis that the corresponding compositing operation has a primitive left operand.

18. A method according to claim 17, wherein a level comprising a push operation is added to the compositing table.

19. A method according to claim 17, wherein the active region corresponds to a complex expression.

20. A method according to claim 19, wherein a level comprising a clip operation is added to the compositing table.

21. A method according to claim 4, wherein a level comprising an operation and a data fill value of a particular object constituting an active region, is added to the compositing table.

22. A method according to claim 4, wherein the compositing table is optimised in regard to the number of pixel operations required to render the image.

23. A method according to claim 4, wherein a wholly opaque object in a particular region acts to eliminate one or more compositing operations contributing to at least one other object constituting the particular region, wherein the at least one other object is obscured by the wholly opaque object in a space in which the outlines are defined.

24. A method of creating a pixel image, the pixel image to be formed by rendering and compositing a plurality of graphical objects according to a hierarchically structured compositing expression, each of the graphical objects having a predetermined object outline forming a region comprising a plurality of pixels therein and at least one of said graphical objects being non-rectangular, such that an object region formed by each particular object outline of each particular graphical object is wholly within the particular graphical object and is formed wholly from the plurality of pixels, the hierarchically structured compositing expression comprising a plurality of nodes arranged in a hierarchical structure, each of the nodes representing one or more compositing operations, each compositing operation being defined by at least one compositing operator and one or more operands, each of the operands representing one of the graphical objects or a sub-expression representing the result of another of the compositing operations, said method comprising the steps of:

determining an active region for at least each sub-expression of the hierarchically structured compositing expression, each active region being determined based on the operators contained in the corresponding sub-expression, such that the active region of each particular graphical object represented by a corresponding one of said sub-expressions is equal to the region inside the predetermined object outline for the particular graphical object;

determining a clip region for the sub-expressions, the clip region for each particular sub-expression being equal to the intersection of the active region of the particular sub-expression and the clip region of a parent compositing operation of the particular sub-expression, at least one of the clip regions determined for one of the sub-expressions being smaller in area than the active region for said one sub-expression;

determining an effective region for each of the compositing operations of the hierarchically structured compositing expression, the effective region for each particular compositing operation being equal to the intersection of the clip region of the particular compositing operation and the active regions of the operands of the particular compositing operation, at least one of said effective regions determined for one of said compositing operations being smaller in area than the clip region for said one compositing operation;

mapping each effective region and corresponding compositing operation into a compositing table, comprising a plurality of levels, wherein each level of the compositing table represents one of the operators or an outline for clipping at least one other level; and

evaluating the hierarchically structured compositing expression using the compositing table, wherein pixels falling outside the effective regions are disregarded in applying the compositing operations and the arrangement of nodes in the hierarchical structure remains stable during the creation of the image.

25. The method according to claim 24, wherein said active regions are determined during an upward traversal of the hierarchically structured compositing expression and the clip regions are determined in a downward traversal of the hierarchically structured compositing expression.

26. A method of creating a pixel image, the pixel image to be formed by compositing at least a plurality of graphical objects according to one or more compositing operations, each graphical object having a predetermined object outline forming a region comprising a plurality of pixels therein and at least one of said graphical objects being non-rectangular, the one or more compositing operations comprising a plurality of nodes arranged in a hierarchical structure, each of the nodes representing one or more compositing operations, each compositing operation being defined by at least one compositing operator and one or more operands, each of the operands representing one of the graphical objects or a result of another of the compositing operations, said method comprising the steps of:

determining an active region for each of the graphical object operands, such that the active region of each particular graphical object represented by a corresponding one of said operands is equal to the region inside the predetermined object outline for said particular graphical object;

determining an active region for each of the compositing operations, the active region for each particular compositing operation being determined based on the active regions associated with each operand of the particular compositing operation;

determining an effective region for each of the compositing operations, wherein the effective region for each particular compositing operation is equal to the intersection of a clip region of the particular compositing operation and one or more of the active regions of the operands of the particular compositing operation, the clip region for each particular compositing operation being equal to the intersection of the active region of the particular compositing operation and the clip region of a parent compositing operation of the particular compositing operation, at least one of the clip regions determined for one of the compositing operations being smaller in area than the active region for said one compositing operation, at least one of said effective regions determined for one of said one compositing operation being smaller in area than the clip region for said one compositing operation;

mapping the effective regions and corresponding compositing operations into a compositing table, comprising a plurality of levels, wherein each level of the compositing table represents one of the operators or an outline for clipping at least one other level; and

compositing the image using the compositing table, wherein pixels falling outside the effective regions are disregarded in applying the compositing operations and the arrangement of nodes in the hierarchical structure remains stable during the creation of the image.

27. A method according to claim 26, wherein each of the clip regions is dependent upon an active region of an operand of a particular compositing operation.

28. A method according to claim 26, wherein a level comprising a push operation is added to the compositing table.

29. A method according to claim 26, wherein a corresponding compositing expression corresponding to an active region is complex.

30. A method according to claim 26, wherein a level comprising a clip operation is added to the compositing table.

31. A method according to claim 26, wherein an active region is determined on the basis that the corresponding compositing operation has a complex left operand.

32. A method according to claim 31, wherein a level comprising a pop operation is added to the compositing table.

33. A method according to claim 32, wherein the pop operation will remove any unused pixel being outside an active region representing the complex left operand, during compositing of the complex left operand.

34. A method according to claim 33, wherein the active region is transformed to a still further region by the pop operation.

35. A method according to claim 34, wherein the effective region is the effective region of the complex left operand.

36. A method according to claim 35, wherein the effective region corresponds to a complex expression.

37. A method according to claim 36, wherein a level comprising a clip operation is added to the compositing table.

38. A method according to claim 33, wherein the active region is the active region of the complex left operand.

39. A method according to claim 26, wherein a further active region is determined on the basis that the corresponding compositing operation has a primitive left operand.

40. A method according to claim 39, wherein the active region corresponds to a complex expression.

41. A method according to claim 40, wherein a level comprising a clip operation is added to the compositing table.

42. A method according to claim 39, wherein a level comprising a push operation is added to the compositing table.

43. A method according to claim 26, wherein a level comprising an operation and a data fill value of a particular object constituting an active region, is added to the compositing table.

44. A method according to claim 26, wherein the compositing table is optimised in regard to the number of pixel operations required to render the image.

45. A method according to claim 26, wherein a wholly opaque object in a particular region acts to eliminate one or more compositing operations contributing to at least one other object constituting the particular region, wherein the at least one other object is obscured by the wholly opaque object in a space in which the outlines are defined.

46. A method of creating a pixel image, the pixel image to be formed by rendering and compositing a plurality of graphical objects according to a hierarchical structure representing a compositing expression for the image, at least one of said graphical objects being non-rectangular, the hierarchical structure including a plurality of nodes, each node being associated with either a compositing operator or an operand of the compositing expression, each operand representing one of the graphical objects or a result of a sub-expression of the compositing expression, each of the graphical objects having a predetermined object outline forming a region comprising a plurality of pixels therein, said method comprising the steps of:

determining an active region for at least each sub-expression of the compositing expression, such that the active region of each particular graphical object represented by a corresponding one of said sub-expression is equal to the region inside the predetermined object outline for the particular graphical object and the active region for each particular sub-expression being determined based on the active regions associated with further sub-expressions containing the particular sub-expression;

determining a clip region for the sub-expression, the clip region for each particular sub-expression being equal to the intersection of the active region of the particular sub-expression and the clip region of a parent compositing operation of the particular sub-expression, at least one of the clip regions determined for one of the sub-expressions being smaller in area than the active region for said one sub-expression;

determining an effective region for each of the nodes, each of the effective regions having a corresponding compositing operation, the effective region for each particular node being equal to the intersection of the clip region and the active regions associated with the child nodes of the particular node, at least one of said effective regions determined for one of said nodes being smaller in area than the clip region for said one node; and

applying the corresponding compositing operations substantially to the effective regions to create the image, wherein pixels falling outside the effective regions are disregarded in applying the compositing operations and the arrangement of nodes in the hierarchical structure remains stable during the creation of the image.

47. The method according to claim 46, said method further including the steps of:

mapping the effective regions and the compositing operations into a compositing table comprising a plurality of levels, wherein each level represents at least one compositing operation for rendering an object or parts thereof or represents an outline for clipping at least one other level; and

compositing the image using the compositing table.

48. The method according to claim 46, wherein the compositing operations include compositing and stack operations.

49. A computer readable medium storing a program for an apparatus which processes graphical objects intended to form a raster pixel image, the processing comprising a method of creating a pixel image, the pixel image to be formed by rendering at least a plurality of graphical objects to be composited according to a hierarchical structure representing a compositing expression for the image, at least one of said graphical objects being non-rectangular, the hierarchical structure including a plurality of nodes, each node being associated with either a compositing operator or an operand of the compositing expression, each of the operands representing one of the graphical objects or a result of a sub-expression of the compositing expression, each of the graphical objects having a predetermined object outline forming a region comprising a plurality of pixels therein, said program comprising:

code for determining an active region for at least each sub-expression of the compositing expression, such that the active region of each particular graphical object represented by a corresponding one of said sub-expression is equal to the region inside the predetermined object outline for the particular graphical object and the active region for a particular sub-expression determined based on the active regions associated with further sub-expressions containing the particular sub-expression;

code for determining a clip region for the sub-expressions, the clip region for each particular sub-expression being equal to the intersection of the active region of the particular sub-expression and the clip region of a parent compositing operation of the particular sub-expression, at least one of the clip regions determined for one of the sub-expressions being smaller in area than the active region for said one sub-expression;

code for determining an effective region for each of the nodes, each of the effective regions having a corresponding compositing operation, the effective region for each particular node being equal to the intersection of the clip region and the active regions associated with the child nodes of the particular node, at least one of said effective regions determined for one of said nodes being smaller in area than the clip region for said one node; and

code for applying the corresponding compositing operations substantially to the effective regions to create the image, wherein pixels falling outside the effective regions are disregarded in applying the compositing operations and the arrangement of nodes in the hierarchical structure remains stable during the creation of the image.

50. The computer readable medium according to claim 49, said medium further storing:

code for mapping the effective regions and the compositing operations into a compositing table comprising a plurality of levels, wherein each level represents at least one compositing operation for rendering an object or parts thereof or represents an outline for clipping at least one other level; and

code for compositing the image using the compositing table.

51. The computer readable medium according to claim 49, wherein the compositing operations include compositing and stack operations.