2D region rendering

• US 9,710,943 B2
• Filed: 07/26/2012
• Issued: 07/18/2017
• Est. Priority Date: 07/29/2011
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Iskenderian, Edward James, Morrison, Paul William
• Primary Examiner(s): He, Yingchun
• Assistant Examiner(s): Gillespie, Nicole
• Application Number:
  US13/559,427
• Publication Number:
  US 20130027402A1
• Time in Patent Office: 1,818 Days
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

Abstract

Disclosed is a method of rendering a plurality of graphical objects. The method generates a region graph using at least a plurality of intersection points of the graphical objects. The intersection points identify disjoint regions each representing a particular combination of the graphical objects, in which the region graph has at least one region graph link, and defines a relationship between the regions. A contributing level and an activating direction are assigned to at least one of the region graph links, the level and the activation direction defining an appearance of the region associated with said region graph link. The method then renders the plurality of graphical objects using the assigned contributing level and activating direction of the region graph links by traversing the region graph to determine at least one contributing level for each region in the region graph using the assigned contributing level and the activating direction.

Claims

1. A method of rendering a plurality of graphical objects, said method comprising:

generating a region graph having a plurality of nodes, one for each disjoint region identified using at least a plurality of intersection points of the graphical objects, each disjoint region representing a particular combination of the graphical objects, wherein the plurality of nodes are linked by at least one region graph link that encodes a change in an active level list when traversing between neighboring nodes;

assigning an object level of an associated object and an activating direction to the at least one region graph link, the object level and the activation direction defining an appearance of the region associated with the at least one region graph link;

determining a plurality of region graph links joining a selected node with further nodes;

determining a contributing level for the selected node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the region including color of pixels represented by the region; and

rendering the plurality of graphical objects using at least the determined contributing level for a disjoint region corresponding to the selected node.

2. The method according to claim 1, wherein the rendering step comprises the steps of:

rendering each region to pixels using the contributing level associated with the region.

3. The method according to claim 1, wherein the step of the generating the region graph comprises:

generating a plurality of nodes for an edge graph based on the plurality of intersection points of the graphical objects; and

generating the region graph from the edge graph.

4. The method according to claim 3, wherein the generating of the region graph from the edge graph comprises generating a dual for the edge graph to form the region graph.

5. The method according to claim 4, wherein the dual of the edge graph is the region graph which has:

(a) a node for each plane region of the edge graph, and

(b) at least a region graph link joining two neighbourhood regions of the edge graph.

6. The method according to claim 5, wherein the dual is determined by:

sorting the edge graph edges dividing neighbourhood regions of the edge graph in a predetermined direction from a current edge;

determining a next edge in the predetermined direction at an edge graph node where the current edge and the next edge meet;

adding a node of the region graph to a region, said region having an appearance determined by the next edge; and

assigning a contributing level and an activating direction to a region graph link ending at the added node, the level and the activation direction defining the appearance of the region.

7. The method according to claim 3, wherein the contributing level associated with a region graph link is associated with an edge of the edge graph that the region graph link crosses.

8. The method according to claim 1, wherein the activating direction of a region graph link is the direction towards a node of the region graph to which the contributing level of the region graph link is assigned.

9. A method of rendering a plurality of graphical objects, said method comprising:

generating a first region graph node associated with a first disjoint region for an object edge pair in a current scan line;

sorting the object edge pair in a subsequent scan line;

determining a crossing of said object edge pair in the subsequent scan line;

generating a second region graph node associated with a second disjoint region as a result of the crossing of said object edge pair;

joining the first region graph node and the second region graph node to form a region graph link of a region graph, the region graph link encoding a change in an active level list when traversing between the first and second region graph nodes;

associating an object level of an associated object and an activating direction to the region graph link, said object level and said activation direction defining an appearance of the second disjoint region;

determining a plurality of region graph links linking the second region graph node with further region graph nodes;

determining a contributing level for the second region graph node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the second disjoint region including color of pixels represented by the second disjoint region; and

rendering the plurality of graphical objects using at least the determined contributing level for the second disjoint region corresponding to the second region graph node.

10. The method according to claim 9, wherein the rendering step comprises:

rendering each region to pixels using the contributing level associated with the region.

11. The method according to claim 9, wherein the activating direction of a region graph link is the direction towards a node of the region graph to which the contributing level of the region graph link is assigned.

12. A method of rendering a page comprising a plurality of graphical objects, said method comprising:

determining a rendering complexity associated with at least a portion of the page and graphical objects of that portion;

comparing the determined complexity with a threshold value; and

region rendering the portion, where the determined complexity is less than the threshold value, by one of;

(A) generating a region graph having a plurality of nodes, one for each disjoint region identified using at least a plurality of intersection points of graphical objects in the portion, each disjoint region representing a particular combination of the graphical objects, wherein the plurality of nodes are linked by at least one region graph link;

assigning an object level of an associated object and an activating direction to the at least one region graph link, the object level and the activation direction defining an appearance of the region associated with the at least one region graph link, the at least one region graph link encoding a change in an active level list when traversing between neighboring nodes;

determining a plurality of region graph links joining a selected node with further nodes;

determining a contributing level for the selected node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the region including color of pixels represented by the region; and

rendering the plurality of graphical objects using at least the determined contributing level for a disjoint region corresponding to the selected node;

or

(B) generating a first region graph node associated with a first disjoint region for an object edge pair of a plurality of graphical objects in a current scan line of the portion;

sorting the object edge pair in a subsequent scan line of the portion;

determining a crossing of said object edge pair in the subsequent scan line;

generating a second region graph node associated with a second disjoint region as a result of the crossing of said object edge pair;

joining the first region graph node and the second region graph node to form a region graph link of a region graph, the region graph link encoding a change in an active level list when traversing between the first and second region graph nodes;

associating an object level of an associated object and an activating direction to the region graph link, the object level and the activation direction defining an appearance of the second disjoint region;

determining a plurality of region graph links linking the second region graph node with further region graph nodes;

determining a contributing level for the second region graph node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the second disjoint region including color of pixels represented by the second disjoint region; and

rendering the plurality of graphical objects using at least the determined contributing level for the second disjoint region corresponding to the second region graph node.

13. The method according to claim 12 further comprising:

scan rendering the portion, where the determined complexity is greater than the threshold, according to a scan-line rendering technique.

14. The method according to claim 13 wherein the portion comprises a band of the page.

15. The method according to claim 13 wherein the portion comprises a tile of the page.

16. The method according to claim 15 further comprising:

identifying at least one said graphical object which spans a first tile to be scan rendered and a second tile to be region rendered;

dividing said one graphical object into a first part within the first tile and a second part with the second tile;

scan rendering the first tile including the first part; and

region rendering the second tile including the second part.

17. A non-transitory computer readable storage medium, having a computer program recorded thereon, the program being executable by computer apparatus to render a plurality of graphical objects, said program comprising:

code for generating a region graph having a plurality of nodes, one for each disjoint region identified using at least a plurality of intersection points of the graphical objects, each disjoint region representing a particular combination of the graphical objects, wherein the plurality of nodes are linked by at least one region graph link;

code for assigning an object level of an associated object and an activating direction to the at least one region graph link, the object level and the activation direction defining an appearance of the region associated with the at least one region graph link the at least one region graph link encoding a change in an active level list when traversing between neighboring nodes;

code for determining a plurality of region graph links joining a selected node with further nodes;

code for determining a contributing level for the selected node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the region including color of pixels represented by the region; and

code for rendering the plurality of graphical objects using at least the determined contributing level for a disjoint region corresponding to the selected node.

18. A non-transitory computer readable storage medium, having a computer program recorded thereon, the program being executable by computer apparatus to render a plurality of graphical objects, the program comprising:

code for generating a first region graph node associated with a first disjoint region for an object edge pair in a current scan line;

code for sorting the object edge pair in a subsequent scan line;

code for determining a crossing of said object edge pair in the subsequent scan line;

code for generating a second region graph node associated with a second disjoint region as a result of the crossing of said object edge pair;

code for joining the first region graph node and the second region graph node to form a region graph link of a region graph, the region graph link encoding a change in an active level list when traversing between the first and second region graph nodes;

code for associating an object level of an associated object and an activating direction to the region graph link, the object level and the activation direction defining an appearance of the second disjoint region;

code for determining a plurality of region graph links linking the second region graph node with further region graph nodes;

code for determining a contributing level for the second region graph node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the second disjoint region including color of pixels represented by the second disjoint region; and

code for rendering the plurality of graphical objects using at least the determined contributing level for the second disjoint region corresponding to the second region graph node.

19. An apparatus comprising at least a processor and a memory coupled to the processor, the memory having at least first and second programs recorded thereon, the at least first and second programs being executable by the processor to adapted to render a plurality of graphical objects, wherein

(A) the first program comprises:

code for generating a region graph having a plurality of nodes, one for each disjoint region identified using at least a plurality of intersection points of the graphical objects, each disjoint region representing a particular combination of the graphical objects, wherein the plurality of nodes are linked by at least one region graph link;

code for assigning an object level of an associated object and an activating direction to the at least one region graph link, the object level and the activation direction defining an appearance of the region associated with the at least one region graph link, the at least one region graph link encoding a change in an active level list when traversing between neighboring nodes;

code for determining a plurality of region graph links joining a selected node with further nodes;

code for determining a contributing level for the selected node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the region including color of pixels represented by the region; and

code for rendering the plurality of graphical objects using at least the determined contributing level for a disjoint region corresponding to the selected node; and

(B) the second program comprises;

code for generating a first region graph node associated with a first disjoint region for an object edge pair in a current scan line;

code for sorting the object edge pair in a subsequent scan line;

code for determining a crossing of said object edge pair in the subsequent scan line;

code for generating a second region graph node associated with a second disjoint region as a result of the crossing of said object edge pair;

code for joining the first region graph node and the second region graph node to form a region graph link of a region graph, the region graph link encoding a change in an active level list when traversing between the first and second region graph nodes;

code for associating an object level of an associated object and an activating direction to the region graph link, said object level and said activation direction defining an appearance of the second disjoint region;

code for determining a plurality of region graph links linking the second region graph node with further region graph nodes;

code for determining a contributing level for the second region graph node using object levels and activating directions assigned to the determined plurality of region graph links, the contributing level contributing to the appearance of the second disjoint region including color of pixels represented by the second disjoint region; and

code for rendering the plurality of graphical objects using at least the determined contributing level for the second disjoint region corresponding to the second region graph node.

20. A method of rendering a plurality of graphical objects, said method comprising:

determining a plurality of disjoint regions by identifying intersection points of the received objects, each of disjoint regions representing a particular combination of the graphical objects;

generating a region graph having a plurality of nodes, one for each disjoint region, the nodes being linked by region graph links, wherein each region graph link is assigned an object level of an associated object and an activating direction and encodes a change in an active level list when traversing between the neighboring nodes;

identifying a plurality of region graph links joining a selected node with further nodes to determine a contributing level for the selected node, the contributing level contributing to the appearance of the each disjoint region, corresponding to the selected node, including color of pixels represented by the second disjoint region; and

rendering the plurality of graphical objects using at least the determined contributing level for a disjoint region corresponding to the selected node.