Rendering graphic object based images

• US 20020015039A1
• Filed: 04/18/2001
• Published: 02/07/2002
• Est. Priority Date: 04/18/2000
• Status: Active Grant

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Moore, Kevin John
• Granted Patent: US 7,277,102 B2
• Time in Patent Office: Days
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

Disclosed are methods, apparatus (1) and computer readable medium for generating instructions for a directed adjacency graph, such as an expression tree, into a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each scan line. The expression tree comprises one or more parent nodes and one or more leaf nodes. The parent nodes each representing an operator and each having branches to respective descendent nodes. The leaf nodes each representing a graphic object. The apparatus comprises means for scanning a plurality of pixel locations (300). The apparatus further comprising a module (504) for determining, for each of the scanned pixel locations, a portion of the expression tree in accordance with the activity of the operators, where the portion of the expression tree is that portion which passes data up the tree. The apparatus also comprises a Module (506) for generating instructions for the determined portion of the expression tree, wherein operator instructions are generated for those operators of the determined portion of the expression tree having active branches and wherein leaf instructions are generated for those graphic objects which are active at the scanned pixel location.

Claims

1. A method of generating instructions for a directed adjacency graph, said directed adjacency graph comprising one or more parent nodes and one or more leaf nodes, each of which said parent node representing an operator and having branches to respective descendent nodes, and each of which said leaf node representing a graphic object, said method comprising the steps of:

determining groups of one or more pixel locations;

determining, for each said group, a portion of said directed adjacency graph in accordance with activities of the operators, wherein the said portion of the directed adjacency graph is that portion which passes data up the directed adjacency graph; and

generating, for each said group, instructions for the determined portion of the directed adjacency graph, wherein operator instructions are generated for those operators of the determined portion of the directed adjacency graph having active branches and wherein leaf instructions are generated for those graphic objects which are active at said group of one or more pixel locations.

2. The method as claimed in claim 1, wherein said method comprises the step of generating a table for storing data concerning the activity of the operators and the activity of the branches of the parent nodes.

3. The method as claimed in claim 2, wherein said determining step comprises the sub-step of updating, for each said group, the said data stored in said table.

4. The method as claimed in claim 1, wherein said step of generating instructions comprises a sub-step of traversing said portion of the directed adjacency graph and generating instructions for the active operators and the leaf value instructions in said portion of the directed adjacency graph.

5. The method as claimed in claim 1, wherein said directed adjacency graph is an expression tree.

6. The method as claimed in claim 1, wherein said parent nodes represent binary operators.

7. A method of generating instructions for an expression tree, said expression tree having a plurality of nodes comprising one or more binary nodes and a plurality of leaf nodes, wherein each said binary node having a left branch to a descendent said node and a right branch to a descendent said node and representing a binary operation on said two descendant nodes, and wherein each said node represents a graphic object, with one or more said graphic objects overlapping, each said overlapping graphics objects comprising a left node region, a common region, and a right node region, said method comprising the steps of:

determining groups of one or more pixel locations;

determining, for each said group, whether the left and right branches of said one or more binary nodes are active or inactive;

traversing, for each said group, said expression tree, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said left node region is required for the binary operation of said previously traversed binary node and the left branch is active and the right branch is inactive of said previously traversed binary node, and wherein a right branch of any previously traversed binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said right node region is required for the binary operation of said previously traversed binary node and the right branch is active and the left branch is inactive of said previously traversed binary node; and

generating, for each said group, operator instructions for any said traversed binary node having active said right and left branches, and leaf value instructions for any traversed leaf node.

8. A method as claimed in claim 7, wherein said tranversing step traverses said expression tree, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the right branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the left branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node, and wherein the right branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the left branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the right branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node.

9. A method of rendering an expression tree into a raster pixel image having a plurality of scanlines and a plurality of pixel locations on each said scanline, said expression tree having a plurality of nodes comprising one or more binary nodes and a plurality of leaf nodes, wherein each said binary node having a left branch to a descendent said node and a right branch to a descendent said node and representing a binary operation on said two descendant nodes, and wherein each said node represents a graphic object, with one or more said graphic objects overlapping, each said overlapping graphics objects comprising a left node region, a common region, and a right node region, said method comprising the steps of:

generating a table representative of said expression tree, wherein said table comprises a plurality of records corresponding to associated said binary nodes and leaf nodes, and each said record of a said associated binary node comprises a first field indicating whether a said left region is required for operation of the operator of said associated binary node, a second field indicating whether a right region is required for operation of the operator of said associated binary node, a third field capable of indicating whether a said left branch of said associated binary node is active, and a fourth field capable of indicating whether a said right branch of said associated binary node is active;

determining groups of one or more pixel locations;

determining, for each said group, whether the left and right branches of said one or more binary nodes are active or inactive;

updating, for each said group, said third and fourth fields of said table for said determined active and inactive branches;

traversing, for each said group, said expression tree in accordance with said updated table wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said left node region is required for the binary operation of said previously traversed binary node and the left branch is active and the right branch is inactive of said previously traversed binary node, and wherein a right branch of any previously traversed binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said right node region is required for the binary operation of said previously traversed binary node and the right branch is active and the left branch is inactive of said previously traversed binary node;

generating, for each said group, operator instructions for any said traversed binary node having active said right and left branches, and leaf value instructions for any traversed leaf node; and

executing, for each said group, corresponding said generated instructions so as to render said image.

10. A method as claimed in claim 9, wherein said table further comprises for each said record of a said associated binary node a fifth field indicating whether the graphic object representing said descendent node on the right branch of said associated binary node obscures the graphic object representing said descendent node on the left branch of said associated binary node in the common region of the graphic objects representing said descendent nodes of said associated binary node, and a sixth field indicating whether the graphic object representing said descendent node on the left branch of said associated binary node obscures the graphic object representing said descendent node on the right branch of said associated binary node in the common region of the graphic objects representing said descendent nodes of said associated binary node;

and said tranversing step traverses said expression tree in accordance with said updated table, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the right branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the left branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node, and wherein the right branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the left branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the right branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node.

11. A method as claimed in claim 10, wherein said fifth and sixth fields are used to implement CLIP IN or a CLIP OUT operation.

13. Apparatus as claimed in claim 12, wherein said apparatus comprises means for generating a table for storing data concerning the activity of the operators and the activity of the branches of the parent nodes.

14. Apparatus as claimed in claim 13, wherein said determining means comprises means for updating, for each said group, the said data stored in said table.

15. Apparatus as claimed in claim 12, wherein said means for generating instructions comprises means for traversing said portion of the directed adjacency graph and means for generating instructions for active operators and leaf value instructions in said portion of the directed adjacency graph.

16. Apparatus as claimed in claim 12, wherein said directed adjacency graph is an expression tree.

17. Apparatus as claimed in claim 12, wherein said parent nodes represent binary operators.

19. Apparatus as claimed in claim 18, wherein said tranversing means traverses said expression tree, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the right branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the left branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node, and wherein the right branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the left branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the right branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node.

12. Apparatus for generating instructions for a directed adjacency graph, said directed adjacency graph comprising one or more parent nodes and one or more leaf nodes, each of which said parent node representing an operator and having branches to respective descendent nodes, and each of which said leaf node representing a graphic object, said apparatus comprising:

means for determining groups of one or more pixel locations;

means for determining, for each said group, a portion of said directed adjacency graph in accordance with activities of the operators, wherein the said portion of the directed adjacency graph is that portion which passes data up the directed adjacency graph; and

means for generating, for each said group, instructions for the determined portion of the directed adjacency graph, wherein operator instructions are generated for those operators of the determined portion of the directed adjacency graph having active branches and wherein leaf instructions are generated for those graphic objects which are active at said group of one or more pixel locations.

18. Apparatus for generating instructions for an expression tree, said expression tree having a plurality of nodes comprising one or more binary nodes and a plurality of leaf nodes, wherein each said binary node having a left branch to a descendent said node and a right branch to a descendent said node and representing a binary operation on said two descendant nodes, and wherein each said node represents a graphic object, with one or more said graphic objects overlapping, each said overlapping graphics objects comprising a left node region, a common region, and a right node region, said apparatus comprising:

means for determining groups of one or more pixel locations;

means for determining, for each said group, whether the left and right branches of said one or more binary nodes are active or inactive;

means for traversing, for each said group, said expression tree, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said left node region is required for the binary operation of said previously traversed binary node and the left branch is active and the right branch is inactive of said previously traversed binary node, and wherein a right branch of any previously traversed binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said right node region is required for the binary operation of said previously traversed binary node and the right branch is active and the left branch is inactive of said previously traversed binary node; and

means for generating, for each said group, operator instructions for any said traversed binary node having active said right and left branches, and leaf value instructions for any traversed leaf node.

20. Apparatus for rendering an expression tree into a raster pixel image having a plurality of scanlines and a plurality of pixel locations on each said scanline, said expression tree having a plurality of nodes comprising one or more binary nodes and a plurality of leaf nodes, wherein each said binary node having a left branch to a descendent said node and a right branch to a descendent said node and representing a binary operation on said two descendant nodes, and wherein each said node represents a graphic object, with one or more said graphic objects overlapping, each said overlapping graphics objects comprising a left node region, a common region, and a right node region, said apparatus comprising:

means for generating a table representative of said expression tree, wherein said table comprises a plurality of records corresponding to associated said binary nodes and leaf nodes, and each said record of a said associated binary node comprises a first field indicating whether a said left region is required for operation of the operator of said associated binary node, a second field indicating whether a right region is required for operation of the operator of said associated binary node, a third field capable of indicating whether a said left branch of said associated binary node is active, and a fourth field capable of indicating whether a said right branch of said associated binary node is active;

means for determining groups of one or more pixel locations;

means for determining, for each said group, whether the left and right branches of said one or more binary nodes are active or inactive;

means for updating, for each said group, said third and fourth fields of said table for said determined active and inactive branches;

means for traversing, for each said group, said expression tree in accordance with said updated table wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said left node region is required for the binary operation of said previously traversed binary node and the left branch is active and the right branch is inactive of said previously traversed binary node, and wherein a right branch of any previously traversed binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said right node region is required for the binary operation of said previously traversed binary node and the right branch is active and the left branch is inactive of said previously traversed binary node;

means for generating, for each said group, operator instructions for any said traversed binary node having active said right and left branches, and leaf value instructions for any traversed leaf node; and

means for executing, for each said group, corresponding said generated instructions so as to render said image.

21. Apparatus as claimed in claim 20, wherein said table further comprises for each said record of a said associated binary node a fifth field indicating whether the graphic object representing said descendent node on the right branch of said associated binary node obscures the graphic object representing said descendent node on the left branch of said associated binary node in the common region of the graphic objects representing said descendent nodes of said associated binary node, and a sixth field indicating whether the graphic object representing said descendent node on the left branch of said associated binary node obscures the graphic object representing said descendent node on the right branch of said associated binary node in the common region of the graphic objects representing said descendent nodes of said associated binary node;

and said tranversing means traverses said expression tree in accordance with said updated table, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the right branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the left branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node, and wherein the right branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the left branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the right branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node.

22. Apparatus as claimed in claim 21, wherein said fifth and sixth fields are used to implement CLIP IN or a CLIP OUT operation.

24. A computer readable medium as claimed in claim 23, wherein said computer program comprises code for generating a table for storing data concerning the activity of the operators and the activity of the branches of the parent nodes.

25. A computer readable medium as claimed in claim 24, wherein said determining code comprises code for updating, for each said group, the said data stored in said table.

26. A computer readable medium as claimed in claim 23, wherein said code for generating instructions comprises code for traversing said portion of the directed adjacency graph and code for generating instructions for active operators and leaf value instructions in said portion of the directed adjacency graph.

27. A computer readable medium as claimed in claim 23, wherein said directed adjacency graph is an expression tree.

28. A computer readable medium as claimed in claim 23, wherein said parent nodes represent binary operators.

30. A computer readable medium as claimed in claim 29, wherein said tranversing code traverses said expression tree, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the right branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the left branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node, and wherein the right branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the left branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the right branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node.

23. A computer readable medium comprising a computer program for generating instructions for a directed adjacency graph, said directed adjacency graph comprising one or more parent nodes and one or more leaf nodes, each of which said parent node representing an operator and having branches to respective descendent nodes, and each of which said leaf node representing a graphic object, said computer program comprising:

code for determining groups of one or more pixel locations;

code for determining, for each said group, a portion of said directed adjacency graph in accordance with activities of the operators, wherein the said portion of the directed adjacency graph is that portion which passes data up the directed adjacency graph; and

code for generating, for each said group, instructions for the determined portion of the directed adjacency graph, wherein operator instructions are generated for those operators of the determined portion of the directed adjacency graph having active branches and wherein leaf instructions are generated for those graphic objects which are active at said group of one or more pixel locations.

29. A computer readable medium comprising a computer program for generating instructions for an expression tree, said expression tree having a plurality of nodes comprising one or more binary nodes and a plurality of leaf nodes, wherein each said binary node having a left branch to a descendent said node and a right branch to a descendent said node and representing a binary operation on said two descendant nodes, and wherein each said node represents a graphic object, with one or more said graphic objects overlapping, each said overlapping graphics objects comprising a left node region, a common region, and a right node region, said computer program comprising:

code for determining groups of one or more pixel locations;

code for determining, for each said group, whether the left and right branches of said one or more binary nodes are active or inactive;

code for traversing, for each said group, said expression tree, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said left node region is required for the binary operation of said previously traversed binary node and the left branch is active and the right branch is inactive of said previously traversed binary node, and wherein a right branch of any previously traversed binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said right node region is required for the binary operation of said previously traversed binary node and the right branch is active and the left branch is inactive of said previously traversed binary node; and

code for generating, for each said group, operator instructions for any said traversed binary node having active said right and left branches, and leaf value instructions for any traversed leaf node.

31. A computer readable medium comprising a computer program for rendering an expression tree into a raster pixel image having a plurality of scanlines and a plurality of pixel locations on each said scanline, said expression tree having a plurality of nodes comprising one or more binary nodes and a plurality of leaf nodes, wherein each said binary node having a left branch to a descendent said node and a right branch to a descendent said node and representing a binary operation on said two descendant nodes, and wherein each said node represents a graphic object, with one or more said graphic objects overlapping, each said overlapping graphics objects comprising a left node region, a common region, and a right node region, said computer program comprising:

code for generating a table representative of said expression tree, wherein said table comprises a plurality of records corresponding to associated said binary nodes and leaf nodes, and each said record of a said associated binary node comprises a first field indicating whether a said left region is required for operation of the operator of said associated binary node, a second field indicating whether a right region is required for operation of the operator of said associated binary node, a third field capable of indicating whether a said left branch of said associated binary node is active, and a fourth field capable of indicating whether a said right branch of said associated binary node is active;

code for determining groups of one or more pixel locations;

code for determining, for each said group, whether the left and right branches of said one or more binary nodes are active or inactive;

code for updating, for each said group, said third and fourth fields of said table for said determined active and inactive branches;

code for traversing, for each said group, said expression tree in accordance with said updated table wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said left node region is required for the binary operation of said previously traversed binary node and the left branch is active and the right branch is inactive of said previously traversed binary node, and wherein a right branch of any previously traversed binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active or if a said right node region is required for the binary operation of said previously traversed binary node and the right branch is active and the left branch is inactive of said previously traversed binary node;

code for generating, for each said group, operator instructions for any said traversed binary node having active said right and left branches, and leaf value instructions for any traversed leaf node; and

code for executing, for each said group, corresponding said generated instructions so as to render said image.

32. A computer readable medium as claimed in claim 31, wherein said table further comprises for each said record of a said associated binary node a fifth field indicating whether the graphic object representing said descendent node on the right branch of said associated binary node obscures the graphic object representing said descendent node on the left branch of said associated binary node in the common region of the graphic objects representing said descendent nodes of said associated binary node, and a sixth field indicating whether the graphic object representing said descendent node on the left branch of said associated binary node obscures the graphic object representing said descendent node on the right branch of said associated binary node in the common region of the graphic objects representing said descendent nodes of said associated binary node;

and said tranversing means traverses said expression tree in accordance with said updated table, wherein the left branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the right branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the left branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node, and wherein the right branch of any previously traversed said binary node is traversed to its said descendent node if the right and left branches of said previously traversed binary node are active and if the graphic object representing said descendent node on the left branch of said previously traversed binary node does not obscure the graphic object representing said descendent node on the right branch of said previously traversed binary node in the common region of the graphic objects representing said descendent nodes of said previously traversed binary node.

33. A computer program as claimed in claim 32, wherein said fifth and sixth fields are used to implement CLIP IN or a CLIP OUT operation.