2D REGION RENDERING

• US 20130027402A1
• Filed: 07/26/2012
• Published: 01/31/2013
• 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
• Granted Patent: US 9,710,943 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• 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 the steps of:

generating a region graph using at least a plurality of intersection points of the graphical objects, the intersection points identifying disjoint regions each representing a particular combination of the graphical objects, said region graph having at least one region graph link, said region graph link defining a relationship between the regions;

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

rendering 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.

2. A 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. A 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. A 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. A 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. A 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. A 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. A 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 the steps of:

generating a first region graph node 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 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;

associating a contributing level and an activating direction to the region graph link, said level and said activation direction defining an appearance of the region associated with the second region graph node; and

rendering the plurality of graphical objects using the assigned contributing level and activating direction of the region graph link 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.

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

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

11. A 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, by one of;

(A) generating a region graph using at least a plurality of intersection points of graphical objects in the portion, the intersection points identifying disjoint regions each representing a particular combination of the graphical objects, said region graph having at least one region graph link, said region graph link defining a relationship between the regions;

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

rendering 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;

or

(B) generating a first region graph node 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 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;

associating a contributing level and an activating direction to the region graph link, said level and said activation direction defining an appearance of the region associated with the second region graph node; and

rendering the plurality of graphical objects using the assigned contributing level and activating direction of the region graph link 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.

13. A 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. A method according to claim 13 wherein the portion comprises a band of the page.

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

16. A 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 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 using at least a plurality of intersection points of the graphical objects, the intersection points identifying disjoint regions each representing a particular combination of the graphical objects, said region graph having at least one region graph link, said region graph link defining a relationship between the regions;

code for assigning a contributing level and an activating direction to at least one of the region graph links, said level and said activation direction defining an appearance of the region associated with said region graph link; and

code for rendering 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.

18. A 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 first region graph node 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 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;

code for associating a contributing level and an activating direction to the region graph link, said level and said activation direction defining an appearance of the region associated with the second region graph node; and

code for rendering the plurality of graphical objects using the assigned contributing level and activating direction of the region graph link 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.

19. Computer apparatus comprising at least a processor and a memory coupled to the processor, the memory having at least one program recorded thereon, the at least one program being executable by the processor to adapted to render a plurality of graphical objects, wherein

(A) one said program comprises:

code for generating a region graph using at least a plurality of intersection points of the graphical objects, the intersection points identifying disjoint regions each representing a particular combination of the graphical objects, said region graph having at least one region graph link, said region graph link defining a relationship between the regions;

code for assigning a contributing level and an activating direction to at least one of the region graph links, said level and said activation direction defining an appearance of the region associated with said region graph link; and

code for rendering 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; and

(b) one other said program comprises;

code for generating a first region graph node 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 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;

code for associating a contributing level and an activating direction to the region graph link, said level and said activation direction defining an appearance of the region associated with the second region graph node; and

code for rendering the plurality of graphical objects using the assigned contributing level and activating direction of the region graph link 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.