AU2002301567B2 - A Method of Generating Clip Paths for Graphic Objects - Google Patents

Description

S&F Ref: 610827

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Actual Inventor(s): Address for Service: Invention Title: David Christopher Smith Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) A Method of Generating Clip Paths for Graphic Objects ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PR8388 [32] Application Date 19 Oct 2001 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c -1- A METHOD OF GENERATING CLIP PATHS FOR GRAPHICAL OBJECTS Technical Field of the Invention The present invention relates generally to image processing and, in particular, to a method of constructing clipping paths for graphical objects from a series of clipping rectangles. The invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for constructing clipping paths for graphical objects from a series of clipping rectangles.

Background Software application programs, such as word processors, are generally configured to create page-based documents where each page contains document data such as graphical objects text, images) represented by lines and fill regions. The position of document data on a page may be defined in a number of ways. Throughout the present description, the Cartesian co-ordinate system is used.

When representing the document data on a display device or a printing device, software application programs generally use graphics interface services of a host operating system to send commands describing the graphical objects to an output device.

Such graphics interface services are referred to herein as a 'graphics device interface layer' and are generally configured as an application software programming interface which provide a rich set of graphics features to all applications executing on the host operating system.

One role of the graphics device interface layer is to mediate between the application program and the output device, such that the graphics device interface layer requires one or more device layers. One such device layer is referred to herein as a 'device driver', and supports a relatively small set of functionality, such as drawing rectangular blocks of image data, and filling simple regions with flat colour. The graphics device interface layer generally provides graphical objects to the device driver in 610827.doc -2a format that the graphics device interface layer considers is the most efficient for the device driver, and at the resolution of the output device. For example, a square of ten units by ten units positioned at the top left of a page of size twenty units by twenty units, may be rendered by a software application onto an A4 page 210mm by 297mm) at 600 dpi, such that the graphical object given to the device driver is a 'path' of five points (2480,0),(2480,2480), 2480), where all of these points are pixel values.

The term "path" as used herein refers to a series of line segments, where each line segment consists of at least two points, such that each line segment traces the outline of a region a graphical object) on a page.

Another device layer which is often referred to as a 'graphics rendering system', renders graphical objects received from the graphics device interface layer by generating pixel values. The term 'rendering' as used herein refers to the process by which graphical objects received from the graphics device interface layer are converted to pixels by the graphics rendering system.

In some computer systems, rendering is a two-stage process where graphical objects are firstly conveited into an intermediate format before actual rendering can begin. In one such system, the first stage of the process is to convert each graphical object received from the graphics device interface layer into an intermediate edge-based object graphics format, such that all edges defining the outline of the graphical object are sorted into ascending y-value order, and then into ascending x-value order, assuming a raster scan order of rendering. The output from this first stage is a display list of edges and their associated fill and priority level (generally referred to as 'z-order'), along with other information such as whether a particular edge is a clipping edge or a filling edge.

The display list is generally referred to as a 'job' and contains all of the information needed to render a page. The z-order refers to the priority order in which a graphical object is to be rendered within the total set of graphical objects to be rendered 610827.doc -3for a page. A graphical object having a higher priority can obscure a graphical object having a lower priority. If the graphical object having the higher priority object is opaque, then the higher priority graphical object can totally obscure any object of lower priority and positioned beneath the higher priority object. If the higher priority graphical object is semi-transparent, then any graphical objects underneath the higher priority object can contribute colour to the higher priority graphical object.

The second stage of the rendering process consists of a rendering module 'parsing' the job and generating pixels associated with each scan-line of the page to be rendered. The term "parsing" refers to the process of analysing a string of input symbols in a line of a given format and determining the syntactic structure of the line as defined by the format.

In some computer systems, the graphics device interface layers can provide complex clipping regions to a graphics rendering system, in the form of a number of rectangles, that when combined define the actual clipping region. A complex clipping region is herein defined as a clipping region that requires four or more rectangular blocks of image data and at least one path to define the region. There are a number of alternative strategies that graphics rendering systems employ for dealing with complex clipping regions as will be described below.

One example of a complex clipping region will now be described with reference to Fig. 1, which shows a bitmap image 102 clipped by a five pointed star 100. Fig. 1 also shows an exploded view 110 of one portion (indicated by the circle) of the bitmap 102.

The star 100 is represented by a clipping region consisting of two paths. The first path defines the outline 101 of the star 100 and the second path defines a pentagon 103 wholly within the star 100. In this example, the clipping region of the star 100 can be represented by two hundred and eighty individual clipping rectangles 105). The graphics device 610827.doc -4interface layer of the host system provides these clipping rectangles 105) to the graphics rendering system.

Defining a clipping region in terms of rectangles provides a number of advantages when performing the rendering process. However, the advantages provided can be outweighed by several associated disadvantages.

The first advantage of defining a clipping region in terms of rectangles is that pixel accurate rendering on each scan-line of a page can be performed. For example, when drawing a line 107 from point A to point B on the star 100 as seen in Fig 1, for example, it can be difficult to determine exactly where the line 107 crosses each scanline. Further, different graphics device interface layers have different rules for determining scan-line crossings and when these rules differ from the host rendering system, inaccuracies can result. Secondly, rectangles are generally provided in scan-line order from the top-most rectangle in a clipping region to the bottom-most rectangle in the clipping region, which corresponds in general to the same direction that rendering occurs for printing and that display screens are refreshed for displaying.

A third advantage of defining a clipping region in terms of rectangles is that generally rectangles are a single scan-line high for complex clipping regions (although this depends on the clipping region itself). Therefore, each scan-line can be dealt with at once without requiring knowledge about subsequent scan-lines and without needing to keep a history of previous scan-lines.

Finally, providing clipping regions as rectangles is advantageous when the rendering process is a single stage process since graphical objects can be immediately rendered by the host graphics rendering system on receipt thereof.

However, in a graphics rendering system where the graphical objects are first converted into an intermediate edge-based graphics format, the region represented by the exploded view 110 of Fig. 1 would require many line segments 111, with each line 610827.doc segment consisting of two points. Thus, it is extremely inefficient for a graphics rendering system to deal with complex clipping regions as a series of clipping rectangles 105. Such a graphics rendering system would require a compiler stage to firstly convert each clipping rectangle 105 into a corresponding set of line segments in the intermediate graphics format. Then, once all of the graphical objects for a page have been received, the compiler stage would be required to sort each line segment into a display list in ascending scan-line y-value order, ascending pixel x-value order and ascending priority z-order. The rendering stage must then process each clipping rectangle as the display list is processed, generating pixels for each scan-line. Where a page has many graphical objects that have associated complex clipping regions, and printing is to be performed at a high resolution (eg 600dpi), the total number of clipping rectangles can be over ten thousand, which would incur a significant performance penalty for a two-stage rendering process.

Alternatively, the graphics device interface layer of a graphics rendering system can provide a function to represent a clipping region as a set of closed paths. Fig. 2 shows the star 100 of Fig. 1, represented as six line segments 201 to 206. When rendered, line segment 201 and line segment 202 would each consist of five points (not shown), the line segment 203 and line segment 204 would consist of three points and the line segment 205 and line segment 206 would consist of two points. In the example of Fig. 2, the star 100 can defined by two paths, as follows: Path 1 line segment 201, line segment 205, line segment 206, line segment 202; and Path 2 line segment 203, line segment 204.

Some graphics device interface layers such as those supporting PostScript

TM

always generate clipping paths, since this is the method preferred by PostScript

TM

However, a function representing a clipping region as a set of closed paths may not 610827.doc -6always be provided by a graphics device interface layer, or the function may not be available to the graphics rendering system. Further, many graphics rendering systems do not even support clipping functionality. Such systems leave clipping for the graphics device interface layer to implement, receiving only graphical objects that have already been clipped.

Summary of the Invention It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.

According to one aspect of the present invention there is provided a method of generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of nonoverlapping rectangles, said method comprising the steps of: generating a plurality of edge-lists for said rectangles, each of said edge-lists being associated with at least one said rectangle and including co-ordinate point values, said co-ordinate point values defining edges for one or more of said rectangles; ordering said edge-lists based on said co-ordinate point values to form a set of ordered edge-lists; traversing said set and selecting certain ones of said co-ordinate point values which define edges on a periphery of said clipping region; and generating said path using said selected co-ordinate point values.

According to another aspect of the present invention there is provided a method of generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said method comprising the steps of: selecting a first rectangle from said plurality of rectangles; 610827.doc -7determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the following sub-steps for said right edgelist: (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; 610827.doc -8traversing said set of edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region; and generating said path using said selected co-ordinate point values.

According to still another aspect of the present invention there is provided a method of generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said method comprising the steps of: generating a plurality of edge-lists for each of said rectangles, said edge-lists including co-ordinate point values defining edges for one or more of said rectangles; and ordering said plurality of edge-lists based on said co-ordinate point values to provide a representation of said clipping region.

According to still another aspect of the present invention there is provided a method of generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said method comprising the steps of: selecting a first rectangle from said plurality of rectangles; determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; 610827.doc -9- (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the following sub-steps for said right edgelist: (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; repeating steps to (c4) for each of said plurality of rectangles.

According to still another aspect of the present invention there is provided an apparatus for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of nonoverlapping rectangles, said apparatus comprising: first generating means for generating a plurality of edge-lists for said rectangles, each of said edge-lists being associated with at least one said rectangle and including co-ordinate point values, said co-ordinate point values defining edges for one or more of said rectangles; 610827.doc ordering means for ordering said edge-lists based on said co-ordinate point values to form a set of ordered edge-lists; traversing means for traversing said set and selecting certain ones of said coordinate point values which define edges on a periphery of said clipping region; and second generating means for generating said path using said selected coordinate point values.

According to still another aspect of the present invention there is provided an apparatus for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said apparatus comprising: means for selecting a first rectangle from said plurality of rectangles; means for determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, wherein said means for determining a left edge-list comprises means for performing the following steps for said left edge-list: adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (ii) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; (iii) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (iv) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; 610827.doc -11means for determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, wherein said means for determining a right edge-list comprises means for performing the following steps for said right edge-list: adding points defining a right edge of said first rectangle to said right edge-list; (vi) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (vii) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (viii) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; means for traversing said set of edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region; and means for generating said path using said selected co-ordinate point values.

According to still another aspect of the present invention there is provided an apparatus for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said apparatus comprising: generation means for generating a plurality of edge-lists for each of said rectangles, said edge-lists including co-ordinate point values defining edges for one or more of said rectangles; and ordering means for ordering said plurality of edge-lists based on said coordinate point values to provide a representation of said clipping region.

610827.doc .1 -12- According to still another aspect of the present invention there is provided a computer program for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of non-overlapping rectangles, said program comprising: code for generating a plurality of edge-lists for said rectangles, each of said edge-lists being associated with at least one said rectangle and including co-ordinate point values, said co-ordinate point values defining edges for one or more of said rectangles; code for ordering said edge-lists based on said co-ordinate point values to form a set of ordered edge-lists; code for traversing said set and selecting certain ones of said co-ordinate point values which define edges on a periphery of said clipping region; and code for generating said path using said selected co-ordinate point values.

According to still another aspect of the present invention there is provided a computer program for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said program comprising code for performing the following steps: selecting a first rectangle from said plurality of rectangles; determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; 610827.doc -13- (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the following sub-steps for said right edgelist: (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; traversing said set of edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region; and generating said path using said selected co-ordinate point values.

According to still another aspect of the present invention there is provided a computer program for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said program comprising: 610827.doc -14code for generating a plurality of edge-lists for each of said rectangles, said edge-lists including co-ordinate point values defining edges for one or more of said rectangles; and code for ordering said plurality of edge-lists based on said co-ordinate point values to provide a representation of said clipping region.

According to still another aspect of the present invention there is provided a computer program for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said program comprising code for performing the following steps: selecting a first rectangle from said plurality of rectangles; determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and 610827.doc touching said first rectangle, and comprising the following sub-steps for said right edgelist: (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; repeating steps to (c4) for each of said plurality of rectangles.

According to still another aspect of the present invention there is provided an apparatus for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said apparatus comprising: means for selecting a first rectangle from said plurality of rectangles; means for determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and means for performing the following steps for said left edge-list: adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (ii) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; 610827.doc -16- (iii) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (iv) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; means for determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the means for performing the following steps for said right edge-list: adding points defining a right edge of said first rectangle to said right edge-list; (vi) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (vii) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (viii) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value.

Other aspects of the invention are also disclosed.

Brief Description of the Drawings One or more embodiments of the present invention will now be described with reference to the drawings, in which: Fig. 1 shows a bitmap image clipped by a five-pointed star and an exploded view of one part of the star; Fig. 2 shows the star of Fig. 1 represented as six edges; Fig. 3 shows a set of three joined rectangles; Fig. 4 shows two disjoint rectangles; 610827.doc -17- Fig. 5 shows a region described by four rectangles joined so as to form a hole region; Fig. 6 shows the relationship between an application, a graphics device interface layer, a graphics rendering system and a down-stream device.

Fig. 7 shows a set often rectangles; Fig. 8 is a table showing the co-ordinate positions of the rectangles of Fig. 7; Fig. 9 shows a rectangle and two edges which can be used to represent the rectangle; Fig. 10 shows a rectangle joined with two previously joined rectangles; Fig. 11 shows two disjoint rectangles before adding another rectangle which is shown in phantom lines; Fig. 1 l(b) shows two edge-lists which become joined after the addition of the rectangle shown in phantom lines to the two disjoint rectangles of Fig. 1 Fig. 12 shows a rectangle positioned to the right of another rectangle and which touches the rectangle last added to an edge-list; Fig. 13 shows a rectangle positioned to the right of another rectangle and which does not touch the rectangle last added to an edge-list; Fig. 14 shows a rectangle during the process of being added to four previously joined rectangles such that the added rectangle joins two of the previously joined rectangles; Fig. 15 shows the linked list of edge-lists and the path created after a fourth path traversal of the linked list of edge-lists of Fig. 32; Fig. 16 is a flow chart showing a method generating edge-lists representing the outline of a clipping region; Fig. 17 is a flow chart showing a method of determining the left-most edge-list touching a rectangle, as performed during the method of Fig. 16; 610827.doc -18- Fig. 18 is a flow chart showing a method of determining the right-most edge-list touching a rectangle, as performed during the method of Fig. 16; Fig. 19 is a schematic block diagram of a general-purpose computer upon which arrangements described can be practiced; Fig. 20 is a flow diagram showing a method of traversing the linked list of edgelists generated by the method of Fig. 16; Fig. 21 shows a first rectangle of the set of rectangles of Fig. 7 and the linked list of edge-lists after the rectangle has been processed.

Fig. 22 shows a further rectangle joined with the rectangle of Fig. 21 and the linked list of edge-lists after the rectangle has been processed; Fig. 23 shows the further rectangle of Fig. 22 joined with the rectangle of Fig. 21 and the linked list of edge-lists after the rectangle has been processed; Fig. 24 shows a still further rectangle added to the rectangles of Fig. 23 and the linked list of edge-lists after the rectangle has been added; Fig. 25 shows two still further rectangles added to the rectangles of Fig. 24 and the linked list of edge-lists after the rectangles have been added; Fig. 26 shows a still further rectangle added to the rectangles of Fig. 25 and the linked list of edge-lists while the rectangle is being added; Fig. 27 shows the still further rectangle of Fig. 26 and the edge-lists after the rectangle has been added to the rectangles of Fig. Fig. 28 shows a still further rectangle added to the rectangles of Fig. 27 and the linked list of edge-lists while the rectangle is being added; Fig. 29 shows the still further rectangle of Fig. 28 and the linked list of edge-lists after the rectangle has been added to the rectangles of Fig. 28; Fig. 30 shows a still further rectangle added to the rectangles of Fig. 29 and the linked list of edge-lists after the still further rectangle has been added; 610827.doc 19- Fig. 31 shows a still further rectangle added to the rectangles of Fig. 30 and the linked list of edge-lists after the still further rectangle has been added; Fig. 32 shows a still further rectangle added to the rectangles of Fig. 31 and the linked list of edge-lists after the still further rectangle has been added; Fig. 33 shows the linked list of edge-lists and a path created after a first path traversal of the linked list of edge-lists of Fig. 32; Fig. 34 shows the linked list of edge-lists and the path created after a second path traversal of the linked list of edge-lists of Fig. 32; and Fig. 35 shows the linked list of edge-lists and the path created after a third path traversal of the linked list of edge-lists of Fig. 32.

Detailed Description including Best Mode Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.

A method of generating a path representing a clipping region is described below.

The clipping region is provided by a graphics device interface layer as a series of rectangles as described above with reference to Fig. 1. The method generates edge-lists where each of the edge-lists is associated with at least one of the rectangles provided by the graphics device interface layer. An edge-list accumulates rectangle edges in order to describe one side of a complex clipping region, being either a left edge-list or a right edge-list. A left edge-list contains edges from the left of any rectangles. A right edge-list contains edges from the right of any rectangles. Edge-lists will be described in more detail below. The described method allows edge-lists to be traversed in less time and results in a substantial reduction in the number of discrete edges required to describe a 610827.doc 20 clipping region if such a clipping region were represented as a set of rectangles in the manner described above.

The method of generating a path representing a clipping region, is preferably practiced using a general-purpose computer system 1900, such as that shown in Fig. 19 wherein the described methods may be implemented as software, such as an application program executing within the computer system 1900. In particular, the steps of the described methods are effected by instructions in the software that are carried out by a processor 1905 of the computer system 1900. The instructions may be formed as one or more software code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part performs the described methods and a second part manages a user interface between the first part and the user. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for implementing the methods described herein.

The computer system 1900 comprises a computer module 1901, input devices such as a keyboard 1902 and mouse 1903, output devices including a printer 1915 and a display device 1914. A Modulator-Demodulator (Modem) transceiver device 1916 is used by the computer module 1901 for communicating to and from a communications network 1920, for example connectable via a telephone line 1921 or other functional medium. The modem 1916 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).

The computer module 1901 typically includes at least one processor unit 1905 as mentioned above, a memory unit 1906, for example formed from semiconductor random 610827.doc -21 access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 1907, and an I/O interface 1913 for the keyboard 1902 and mouse 1903 and optionally a joystick (not illustrated), and an interface 1908 for the modem 1916. A storage device 1909 is provided and typically includes a hard disk drive 1910 and a floppy disk drive 1911. A magnetic tape drive (not illustrated) may also be used. A CD-ROM drive 1912 is typically provided as a non-volatile source of data. The components 1905 to 1913 of the computer module 1901, typically communicate via an interconnected bus 1904 and in a manner which results in a conventional mode of operation of the computer system 1900 known to those in the relevant art. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

Typically, the application program is resident on the hard disk drive 1910 and read and controlled in its execution by the processor 1905. Intermediate storage of the program and any data fetched from the network 1920 may be accomplished using the semiconductor memory 1906, possibly in concert with the hard disk drive 1910. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 1912 or 1911, or alternatively may be read by the user from the network 1920 via the modem device 1916. Still further, the software can also be loaded into the computer system 1900 from other computer readable media. The term "computer readable medium" as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system 1900 for execution and/or processing. Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 1901. Examples of transmission media include radio or infra-red transmission channels 610827.doc t.

-22as well as a network connection to another computer or networked device, and the Internet or Intranets including email transmissions and information recorded on websites and the like.

The methods described herein may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of the methods. Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.

The method of generating a path representing a clipping region is preferably implemented as part of a graphics rendering system executing on the computer system 1900. Fig. 6 shows the relationship between an application program 601, a graphics device interface layer 602, a graphics rendering system 603 and a down-stream device 604. As seen in Fig. 6, one or more application programs 601 executing on the computer system 1900, may send graphics commands to a graphics device interface layer 602. The graphics device interface layer 602 subsequently sends graphical objects for a page, based on the commands received, to the graphics rendering system 603 which converts each graphical object to an intermediate edge-based format providing a job for the page. The job is rendered and the resulting pixels are output to a downstream device 604, such as the printer 1915 or a graphics card (not shown). The graphics device interface layer 602 preferably provides the graphics rendering system 603 with a complex clipping region, such as the region described in Fig. 1, as a series of rectangles.

Fig. 3 shows a region 30 described by a set of three rectangles R1, R2 and R3, which are joined. The region 30 described by the rectangles R1, R2, R3 can also be described by a path consisting of the line segments AB, BC, CD, DE, EF, FG, GH, HI, IJ, JK, KL, LA, or equally by the points A, B, C, D, E, F, G, H, I, J, K, L, as seen in Fig. 3.

A complex clipping region can contain disjoint areas, which means that separate paths are required to define each region. Fig. 4 shows a region 40 described by two 610827.doc -23 disjoint rectangles R5 and R6. The region 40 described by the rectangles R5 and R6 can also be described by two paths as follows: Path 1 consists of the line segments AB, BC, CD, DA and the points A, B, C, D; and (ii) Path 2 consists of the line segments EF, FG, GH, HE and the points E, F, G,

H.

A complex clipping region can contain holes and a path describing a hole is required to trace the outside of the clipping region and the inside of the clipping region.

Fig. 5 shows a region 51 described by four rectangles R7, R8, R9 and R10 joined so as to form a hole 53. The region 51 described by the rectangles R7, R8, R9, RO10 can also be described by two paths as follows: Path 1 consists of the line segments AB, BC, CD, DE, EF, FG, GH, HI, IJ, JK, KL, LA and the points A, B, C, D, E, F, G, H, I, J, K, L; and (ii) Path 2 consists of the line segments MN, NO, OP, PM and the points M, N,

O,P.

For ease of explanation, the steps of the methods described herein are described with reference to rectangles which are delivered in the order left-to-right, top-to-bottom raster scan order). However, it is not intended that the invention be limited to the described methods. For example, the invention may have application where rectangles are delivered to a graphics rendering system in any one of the following orders: right to left, top to bottom, (ii) right to left, bottom to top. and (iii) left to right, bottom to top.

In any of the above orders to (iii), the method of generating a path representing the outline of a clipping region described herein, assumes that no two rectangles overlap.

610827.doc -24- The method of generating a path representing a clipping region 150 will now be described with reference to a set of rectangles C1 to CIO as shown in Fig. 7, where the co-ordinate points representing the positions of the rectangles, C1 to CO10, are shown in the table 800 of Fig. 8. For example, rectangle Cl has a left edge 701 having a top left point 715 defined by the co-ordinates (23, 20) and a bottom right point 717 being defined by the co-ordinates (25, 21).

In the following description, a rectangle C1) is defined as consisting of four components left, top, right, and bottom). An individual component of the rectangle C1 will be herein notated with respect to C1 in the form 'Cl.component'. For example, Cl.left refers to the x-value of the left edge of the rectangle C1 and C1.CurrentY refers to the current y-value for the rectangle C1 when the rectangle C1 is being scanned by a graphics rendering system. Each of the rectangles C1 to CIO can be represented by two edges being the left edge and the right edge. The coordinate origin is herein defined as the top left of a page being rendered where Cl .left C 1.right and Cl .top C .bottom.

An edge-list as described herein has the following properties: the current x-value and current y-value of an edge-list represent the last point that was added to the edge-list; (ii) an edge-list remembers all four components of a rectangle whose edge was the most recently added; (iii) an edge-list has an array of points for storing accumulated points of each edge; (iv) an edge-list maintains a left pointer and a right pointer where the left pointer points to the edge-list graphically to the left of a particular edge-list and the right pointer points to the edge-list that is graphically to the right of this particular edge-list. The left and right pointers are maintained such that during traversal of the edge-lists, starting with any edge-list, the next edge-list is the edge-list pointed to by the right pointer, until the 610827.doc right-pointer is zero, in which case the left edge-list is chosen, until the next edge-list is the first edge-list. Thus, a clipping region is traversed in an anti-clockwise manner; no two edge-lists intersect; and (vi) the points of an edge-list do not back-track.

Edge-lists can be specified by a list of edge-lists a doubly linked list of edge-lists) and at any one time the linked list can be maintained by sorting the linked list in ascending current x-value order.

Fig. 16 is a flow diagram showing a method 1600 of generating edge-lists representing the outline of a clipping region. Typically, the method 1600 is implemented l0 as an application program where the application program is one software module of the graphics rendering system 603 for the host computer system 1900. The application program is preferably resident on the hard disk drive 1910 and is read and controlled in its execution by the processor 1905. The method 1600 generates a list (not shown) of edgelists associated with the rectangles C1 to C10 of Fig. 7 which are supplied to the graphics rendering system 603 by the graphics device interface layer 602 of the host computer system 1900. The rectangles C1 to C10 and the generated list of edge-lists are preferably stored in memory 1906. The method 1600 begins at step 1601 where the processor 1905 selects a rectangle from the set of rectangles C1 to C10 and the selected rectangle is assigned the reference C. Fig. 9 shows the rectangle C which consists of two edges 901, 902 where the left edge 901 is defined by the points (C.left, C.top) and (C.left, C.bottom), and the right edge 902 is defined by the points (C.right,C.top), (C.right, C.bottom), as seen in Fig. 9.

The method 1600 continues at the next step 1603, where the processor 1905 determines if all of the rectangles C1 to C10 have been processed and if this is the case then the method 1600 concludes. Otherwise, the method 1600 proceeds to step 1605, where the list of edge-lists stored in memory 1906 is searched to determine a left edge-list 610827.doc -26- L with the smallest value of current x-value satisfying a requirement that the rectangle most recently added to L is above and touching the rectangle C.

Fig. 17 is a flow chart showing a method 1700 of determining the left-most edgelist L touching the rectangle C, as performed in step 1605. The method 1700 is preferably implemented as an application program, which is resident on the hard disk drive 1910 and is read and controlled in its execution by the processor 1905. The method 1700 begins at the first step 1701, where the processor 1905 provides a pointer 'el' which is set to the first edge-list in the list of edge-lists. At the next step 1703, if all of the edge-lists for the rectangles C1 to CO10 have been processed then the method 1700 proceeds to step 1705, where 'none' is returned by the processor 1905 indicating that there are no more edgelists to be processed. Otherwise, the method 1700 proceeds to step 1707, where if the following conditions are satisfied: el.Side LEFT (ii) C.top el.CurrentY; (iii) C.right el.CurrentX; and (iv) C.left el.LastRectangleAdded.right, then the method 1700 proceeds to step 1707. Otherwise, the method 1700 proceeds to step 1711 where the processor 1905 sets the pointer el equal to the next edge-list which is indicated by a pointer el.Next. At the next step 1709, the edge-list pointed to by el is returned by the processor 1905, as the left-most edge-list touching the rectangle C. The method 1600 continues at the next step 1607, where if no rectangle satisfying the above conditions to (iv) is determined by the processor 1905, indicating that the rectangle C has no neighbouring rectangles touching it, then the method 1600 proceeds to step 1609.

Otherwise, if a left edge-list was found indicating that the rectangle C has a neighbouring rectangle above and touching the rectangle C, then the method 1600 proceeds to step 610827.doc -27- 1611. At step 1609, a new left edge-list L is created by the processor 1905 and the points of the left edge of the rectangle C are added to an array of points in the new edge-list L.

The current x-value and current y-value for the left edge-list L is set to the value of the point (C.left, C.bottom). The edge-list L is added to the list of edge-lists, stored in memory 1906, in order of ascending current x-value. Also at step 1609, a new right edgelist R is created by the processor 1905 and the points of the right edge of the rectangle C are added to an array of points in the right edge-list R. The current x-value and current yvalue of the right edge-list R are set to the value of the point (C.right, C.bottom). The edge-list R is added to the list of edge-lists, stored in memory 1906, in ascending current x-order. The left edge-list L, is graphically joined to the right edge-list R by setting a pointer 'L.Right' associated with the left edge-list L to point to the edge-list R. Similarly, the right edge-list R is graphically joined to the left edge-list L by setting a pointer 'R.Right' to the left edge-list L. After step 1609, the method 1600 returns to step 1601.

At step 1611, the processor 1905 adds the points of the left edge of rectangle C to an array of points in the left edge-list L stored in memory 1906. The current x-value and current y-value of the left edge-list L are set to (C.left,C.bottom) and the edge-list L is shifted in the list of edge-lists to ensure that the edge-lists are sorted in order of ascending current x-value. Also at step 1611, the processor 1905 determines a right edge-list R with the largest value of current x-value satisfying the requirement that the most recent rectangle added to the right edge-list R is above and touching the rectangle C. Therefore, at this stage, a left edge-list L exists and has been updated with the left edge of rectangle C, and a right edge-list R has been determined but has not yet been updated with the right edge of rectangle C.

Fig. 18 shows a method 1800 of determining the right-most edge-list R touching the rectangle C, as performed at step 1611. The method 1800 is preferably implemented as an application program, which is resident on the hard disk drive 1910 and is read and 610827.doc -28controlled in its execution by the processor 1905. The method 1800 begins at the first step 1801, where the processor 1905 sets a pointer 'el' to the first edge-list in the list of edge-lists stored in memory 1906. At the next step 1803, if all of the edge-lists have been processed then the method 1800 performed at step 1611, proceeds to step 1805, where 'none' is returned by the processor 1905 indicating there are no more edge-lists to be processed. Otherwise, the method 1800 proceeds to step 1807, where if the following conditions are satisfied: el.Side RIGHT; (vi) C.top el.CurrentY; (vii) C.right el.LastRectangleAdded.left; and (viii) C.left el.CurrentX, then the method 1800 proceeds to step 1809. Otherwise, the method 1800 proceeds to step 1811 where the processor 1905 sets the pointer el equal to the previous edge-list (i.e.

el.Prev). At step 1809, the edge-list pointed to by el is returned by the processor 1905 as the left-most edge-list touching the rectangle C.

The method 1600 continues at the next step 1613, where for each pair of edgelists, 1 and r, lying between the left edge-list L and the right edge-list R, but not inclusive of the left edge-list L and the right edge-list R, and with a current y-value equal to C.top the y-value for the top edge of the rectangle the method 1600 proceeds to step 1615, where the edge-list to the right of of the edge-list r indicated by the pointer r.Right) is set to zero, and the edge-list to the left of r indicated by the pointer r.Left) is set to 1, by the processor 1905. For example, with reference to Fig. 10, two edge-lists (not shown) for the edges and r have been joined from below by the addition of the rectangle C to form a region 1000 defined by the rectangles R1, R2, R3 and C. However, since the two edge-lists for the edges 1 and r are already joined by a previous rectangle 610827.doc -29- R1, the two edge-lists for the edges 1 and r now define a hole 1001 within the region 1000 defined by the rectangles R1, R2, R3 and C. The preferred method of traversal of a list of edge-lists is to proceed right and only proceed left when a right pointer associated with a traversed edge-list is equal to zero. Thus, setting a pointer r.Right to zero ensures the traversal will proceed left at the edge-list r. Alternatively, if two edge-lists are not joined, then the edge-lists belong to disjoint regions that will become joined on adding C. For example, Fig. 1 l(a) shows a region 1100 represented by two disjoint rectangles R1 and R2 before adding a rectangle C which is shown in phantom lines. In contrast, Fig. 1 shows the region 1100 where the edge-lists for the edges 1 and r are joined after the addition of the rectangle C. Therefore, setting the pointer r.Right to zero and the pointer r.Left to 1 ensures the integrity of an anti-clockwise traversal of the linked list of edgelists, as indicated by the arrow heads on the edges 1101) of the rectangles R1, R2 and C. Step 1613 is an optimisation step, since if the edge-list to the right of L, indicated by the pointer L.Right, is the edge-list R then there are no edge-lists to join.

At step 1611, there may be further rectangles to the right of the rectangle C also touching the same rectangle as rectangle C. Therefore, if there are no edge-lists to join at step 1613, then the method 1600 proceeds to step 1617. At step 1617, if the value C.right associated with the rectangle C is less than the current x-value of the right edge-list R, then the method 1600 proceeds to step 1619, where a next rectangle from the set of rectangles, C1 to CO10, is selected and assigned the reference D by the processor 1905.

Otherwise, the method 1600 proceeds directly to step 1621. A software program listing showing one implementation of the process of updating an edge-list with a rectangle (C) as performed at steps 1611 and 1621, is shown below: SET el.LastRectangleAdded C IF el.Side LEFT SET el.CurrentX rect.left 610827.doc

ELSE

SET el.CurrentX rect.right

ENDIF

ADD point (el.CurrentX, rect.top) to el.Points ADD point (el.CurrentX, rect.bottom) to el.Points SORT el in the array of edge-lists, such that the edge-lists are maintained in ascending CurrentX order.

The rectangle D selected by the processor 1905 at step 1619, consists of two edges where the left edge is defined by the points (D.left, D.top), (D.left, D.bottom), and the right edge is defined by the points (D.right, D.top), (D.right, D.bottom). At the next step 1623 of the method 1600, if there are no rectangles left to process, then the method 1600 proceeds to step 1621. Otherwise the method 1600 proceeds to step 1625.

At step 1621, the points of the right edge of rectangle C are added to the array of points in the right edge-list R by the processor 1905 and the y-value corresponding to the current x-value of the right edge-list R is set to the value represented by the point (C.right, C.bottom). Step 1621 ensures that the right edge-list R is in the list of edge-lists such that the list of edge-lists is sorted in order of ascending current x-value. Also at step 1621, the most recently determined left edge-list L, is graphically joined with the right edge-list R by setting the pointer L.Right to the right edge-list R. After step 1621, the method 1600 returns to step 1601, where the processor 1905 continues to process rectangles until all of the rectangles of the set, Cl to C10, have been processed.

In the steps 1629 to 1639 of the method 1600, any further rectangles starting on the same scan-line as rectangle C, to the right of rectangle C and touching the rectangle that was last added to edge-list R, will be processed by the processor 1905. For example, Fig. 12 shows a region 1200 where a rectangle D has been added to two previously joined rectangles R1 and C. Fig. 12 also shows graphically a left edge-list L 1201 and right edge-list R 1202, for the rectangle C. As seen in Fig. 12, the rectangle D is to the right of the rectangle C and touches the rectangle last added to the right edge-list R 1202 (i.e.

610827.doc -31 rectangle RI). In contrast, Fig. 13 shows a region 1300 where a rectangle D which does not touch a rectangle R1 last added to a right edge-list R 1302. Again, Fig. 13 graphically shows a left edge-list L 1301 and the right edge-list R 1302 for another rectangle C.

Continuing the description of the method 1600, at step 1625, if the processor 1905 determines that the rectangle D, has a top value D.top), which is not equal to the current y-value of the right edge-list R, or a left value D.left), greater than the current x-value of the right edge-list R the rectangle D is not touching the last rectangle added to the right edge-list then the method 1600 proceeds to step 1627.

Otherwise, the method 1600 proceeds to step 1629. A software program listing showing one implementation of the process of inserting a new edge-list from a rectangle as performed at steps 1609 and 1629, is shown below.

SET el NEW edge-list SET el.Side side SET el.Left 0 SET el.Right 0 CALL UpdateEdge-list(el, C) At step 1627, the rectangle D is placed back into the set of rectangles Cl to C10, stored in memory 1906, and the method 1600 proceeds to step 1621.

The method 1600 continues at the next step 1629, where a new right edge-list T is created by the processor 1905 and the points of the right edge of rectangle C are added to an array of points in the edge-list T. Also at step 1629, the y-value corresponding to the current x-value of the edge-list T is set to the value represented by the point (C.right, C.bottom) and the new right edge-list T is added to the list of edge-lists stored in memory 1906 such that the list of edge-lists is in order of ascending current x-value. Further, the most recently determined left edge-list L is joined with the right edge-list T, by setting the pointer associated with the left edge-list L indicated by the pointer L.Right) to the edge-list T. A new left edge-list L is created and the points of the left edge of rectangle D 610827.doc -32 are added to the array of points in the edge-list T by the processor 1905. The y-value corresponding to the current x-value of the edge-list T is set to the value represented by (D.left, D.bottom) and the edge-list L is added into the list of edge-lists stored in memory 1906, such that the list is sorted in order of ascending current x-value. The edge-list T is Sjoined with the edge-list L by setting the pointer T.Right to L. For example, Fig. 14 shows a rectangle D being added to previously joined rectangles C 1, C2, C3 and C such that the rectangle D joins the rectangles C2 and C3. Fig. 14 also graphically shows the edge-lists 1401, 1402 and 1403 which are a left edge-list L, a first right edge-list R1 and a second right edge-list R2, respectively. The edge-list T and the new edge-list L are also graphically shown in Fig. 14.

At the next step 1631, if the processor 1905 determines that the value of right pointer, D.right, is greater than the current x-value of the right edge-list R (indicating that the rectangle D may have joined onto another rectangle), then the method 1600 proceeds to step 1633. In the example of Fig. 14, the rectangle D has joined the rectangles C2 and C3. Otherwise, the method 1600 proceeds to step 1635, where the rectangle D is assigned as the rectangle C and the method 1600 returns to step 1619. At step 1633, a new right edge-list R is determined, such that the new right edge-list R is the right edge-list with the largest current x-value satisfying the requirement that the most recent rectangle added to the edge-list R is above and touching the rectangle D. In the example of Fig 14, the most recent rectangle is rectangle C3 having an associated right edge-list R2. At the next step 1637, for each pair of edge-lists, I and r, lying between the left edge-list L and the right edge-list R but not inclusive of the edge-lists L and R, with a current y-value corresponding to the top of the rectangle D, the method 1600 proceeds to step 1639, where the edge-list to the right of the edge-list r indicated by the pointer r.Right) is set to zero by the processor 1905, and the edge-list to the left of r indicated by the pointer r.Left) is set to 1 by the processor 1905. Otherwise, if the processor 1905 610827.doc

I

-33 determines that there are no pairs of edge-lists, I and r, lying between the left edge-list L, and the right edge-list R with a current y-value corresponding to the top of the rectangle D, then the method 1600 proceeds directly to step 1635. Step 1637 is an optimisation step similar to step 1613. Once any edge-lists have been joined at step 1639, the method 1600 proceeds to step 1635 where the processor 1905 assigns the rectangle D to be the rectangle C and the method 1600 returns to step 1619. The method 1600 continues in a similar manner until the processor 1905 determines that either there are no more rectangles to process, or the condition for step 1625 fails. A software program listing showing one implementation of the process of joining intermediate edge-lists between L and R) as performed at steps 1639 and 1615 is shown below.

SET 1= R.Prev WHILE L WHILE 1 L AND l.CurrentY right.CurrentY SET 1 1.Prev

ENDWHILE

IF 1= L RETURN SET r 1.Prev WHILE r L AND r.CurrentY right.CurrentY SET r r.Prev

ENDWHILE

IF r L RETURN SET 1.Right 0 SET l.Left r SET 1 .Prev END WHILE At step 1621, the processor 1905 adds the points of the right edge of rectangle C to the array of points in the right edge-list R and the y-value corresponding to the current x-value of the right edge-list of R is set to the value represented by the point (C.right, C.bottom). Step 1621 ensures that the right edge-list R is in the list of edge-lists such that the list of edge-lists is sorted in order of ascending current x-value. Also at step 1621, the most recently determined left edge-list L, is graphically joined with the right edge-list R 610827.doc -34by setting the pointer L.Right to R. After step 1621, the method 1600 returns to step 1601, where the processor 1905 continues processing rectangles until all of the rectangles of the set, C1 to C10, stored in memory 1906 have been processed.

The edge-lists which have been generated using the method 1600 can be traversed in an anti-clockwise direction if a first edge-list in the list of edge-lists is a left edge-list. Otherwise, the edge-lists will be traversed in a clock-wise direction. Fig. 20 is a flow diagram showing a method 2000 of traversing the linked list of edge-lists generated by the method 1600. The method 2000 is implemented as an application program, which is resident on the hard disk drive 1910 and is read and controlled in its execution by the processor 1905. The method 2000 results in a path representing the clipping region described by the edge-lists. The method 2000 begins at step 2001, where the processor 1905 selects a first edge-list E from the list of edge-lists stored in memory 1906. At the next step 2003, if the processor 1905 determines that there are no edge-lists in the list, then the method 2000 concludes. Otherwise, the method 2000 continues at step 2005 where a target edge-list T is set to E by the processor 1905 and a path is created to hold the entire set of points from all of the edge-lists defining the outline of the path corresponding to the list of edge-lists stored in memory 1906. The path is preferably stored in memory 1906. At the next step 2007, for the next edge-list to be traversed, if the pointer E.Right associated with the edge-list E is zero, then the processor 1905 sets the next edge-list F to the value of E.Left at the next step 2009. Otherwise, the next edge-list F is set to the value of the pointer E.Right at the next step 2011.

The method 2000 continues at the next step 2013, where if the processor 1905 determines that the edge-list E is a left edge-list then the traversal of the list of edge-lists will proceed in an anti-clockwise direction and the method 1600 proceeds to step 2015.

Otherwise, the method 2000 proceeds to step 2017. At step 2015, the processor 1905 sets 610827.doc a flag labelled end to TOP, indicating that the points of the edge-list E will be traversed from top-to-bottom, and stores the flag end in memory 1906.

At step 2017, the processor sets the flag end to BOTTOM, indicating that the points of the edge-list E will be traversed from bottom-to-top, and stores the flag end in memory 1906. Once the direction for the first edge-list has been determined by the processor 1905, then subsequent edge-lists simply alternate between a top end and a bottom end as indicated by TOP and BOTTOM respectively.

The method 2000 continues at the next step 2019, where the processor 1905 adds the points of the edge-list E to the path proceeding from the determined end. The edgelist E is removed from the list of edge-lists stored in memory 1906 and the value of the flag end is set to the opposite end. For example, if end has been previously set to TOP then end is now set to BOTTOM. At the next step 2021, the processor 1905 sets the edge-list E to the edge-list F indicating the next edge-list to traverse to and the points of the edge-list E are added to the path from the determined end. Also at step 2021, the edge-list E is removed from the list of edge-lists by the processor 1905 and the value of the flag end is set to the opposite end. A software program listing showing one implementation for adding an edge-list to a path as performed at step 2021, is shown directly below.

IF end BOTTOM REVERSE order of points in edge-list points array.

ENDIF

APPEND points in edge-list to path.

Further, a software program listing showing one implementation for detaching an edgelist from the list of edge-lists as performed at step 2021, is shown below. For example, in a doubly linked list of edge-lists, detaching an edge-list can be achieved by: SET el.Prev.Next el.Next SET el.Next.Prev el.Prev 610827.doc -36- The method 2000 continues at the next step 2023, where if the processor 1905 determines that the value of the pointer E.Right associated with the edge-list E is equal to zero, then the next edge-list F is set to the value of the pointer E.Left at the next step 2025. Otherwise, the next edge-list F is set to the value of the pointer E.Right at step 2027. At the next step 2029, if the edge-list F is equal to the edge-list T the starting edge-list), then the method 2000 proceeds to step 2031 and processor 1905 closes the path. Otherwise the method 2000 returns to step 2021.

The method 1600 will now be explained by way of example using the rectangles C1 to C10, of Fig. 7. As discussed above, the rectangles C1 to C10 are provided by the graphics device interface layer 602 and are stored in memory 1906. Intermediate results for the example will be shown in Figs. 15 and Figs. 21 to The process of the present example begins at step 1601 where a current rectangle C1 is selected by the processor 1905 as the first rectangle in the set of rectangles C1 to CO10, as seen in Fig. 7. At next step 1603, the processor 1905 determines that the rectangle C1 is not empty so the process of the present example proceeds to step 1605.

There are currently no left edge-lists associated with the rectangles C1 to CO10, stored in memory 1906. Therefore, a new left edge-list L1, which is based on the points of the left edge 701 of the rectangle C1 is created and stored in memory 1906, at step 1609. If no left edge-list associated with the rectangles C1 to C10 was found then it is also true that no right edge-list will be found since the rectangle C1 is not touching any other rectangle.

A new right edge-list R1 is also created by the processor 1905 and inserted into the list of edge-lists stored in memory 1906 from the right edge 703 of the rectangle C1. The new left and right edge-lists L1 and R1 are joined such that the edge-list to the right of the edge-list L1 is set to R1, and the edge-list to the left of the edge-list R1 is set to L1, and the process returns to step 1601. Fig. 21 shows the rectangle C1 of the rectangles C 1 to 610827.doc -37- Fig. 21 also shows the edge-lists L1 and R1 both graphically as arrows 2101) on the rectangle C1 and as tables 2102 which are, stored in memory 1906, after step 1611 has been executed.

At step 1601, the process of the present example continues and the next rectangle returned from the set of rectangles C1 to C10 by the processor 1905 is the rectangle C2.

At step 1605, a left edge-list L1 is returned by the processor 1905, being a left edge-list whose last rectangle added is above and touching the rectangle C2. Subsequently, step 1611 is executed and the edge-list L1 is updated with the details of the left edge of rectangle C and a right edge-list R1 is returned, being a right edge-list whose last rectangle added is above and touching the rectangle C2. Fig. 22 shows the rectangle C2 joined with the rectangle C1 forming a region 2200. Fig. 22 also shows the edge-lists L1 and R1 both graphically as arrows 2201) on the rectangles C1 and C2 and as tables 2202 which are stored in memory 1906, after step 1611 has been executed.

The process of the present example continues at step 1613, where the pointer L1 .Right points to the edge-list RI, so there is no need to look for intermediate edge-lists.

At the following step 1617, the processor 1905 determines that the value C2.Right is greater than the value of R1.CurrentX 25), so there is no need to examine a next rectangle for being alongside the current rectangle C2 and touching the same rectangle as rectangle C2. In the following steps, the edge-list R1 is updated with the details of the right edge 704 of rectangle C2 by the processor 1905, the pointer L1.Right is set to R1, and the process returns to step 1601. Fig 23 shows the rectangle C2 joined with the rectangle C1 forming the region 2200. Fig. 23 also shows the edge-lists L1 and R1 both graphically as arrows 2301) on the rectangles C1 and C2 and as tables 2302 which are stored in memory 1906, after the rectangle C2 has been added to the region 2100.

Returning to step 1601, the process of the example continues with the selection of rectangle C3 from the rectangles C1 to C10. In the followings steps, no left edge-list is 610827.doc -38found, by the processor 1905, where the last rectangle added is above and touching the rectangle C3. Thus, a new left edge-list L2, based on the points of the left edge 705 of the rectangle C3 is created and inserted into the list of edge-lists stored in memory 1906. A new right edge-list R2, is created and inserted into the list of edge-lists from the right edge 706 of the rectangle C3. Edge-lists L2 and R2 are joined such that the edge-list to the right of the edge-list L2 is set to R2 by the processor 1905, the edge-list to the left of edge-list R2 is set to L2, and the process returns to step 1601. Fig. 24 shows the rectangles C3, C1 and C2 forming a region 2400. Fig. 24 also shows the edge-lists L1, R1, L2 and R2 both graphically as arrows 2401) on the rectangles C1, C2 and C3, and as tables 2402 which are stored in memory 1906, after the rectangle C3 has been added to the region 2200 to form the region 2400.

The process of the present example continues at step 1601, where rectangle C4 is returned from the set of rectangles C1 to CO10 by the processor 1905. At the next step 1605, edge-list L1 is returned. Then at step 1611, the processor 1905 updates the edgelist L1 with the left edge 707 of rectangle C4 and the edge-list R1 is returned. The process continues at the next step 1613, where the pointer L1.Right already equals R1. At the next step 1617, the value of the pointer C4.right 22) is determined to be less than the value of R1.CurrentX 28) by the processor 1905, so the process proceeds to step 1619. In the following steps, a next rectangle C5 is assigned as the rectangle D. The process continues at the next step 1625, where the value of D.top 22) is equal to the value of R1.CurrentY 22) and the value of D.left 20) is less than or equal to R1.CurrentX 28). Subsequently, step 1629 is executed by the processor 1905 and a new right edge-list R3 is created, based on the right edge 1002 of rectangle C4, and the new right edge-list R3 is inserted into the list of edge-lists in order of ascending CurrentX. The pointer L1.Right is set to R3 by the processor 1905 and a new left edgelist L3 is created, based on the points of the left edge of C5, and the new left edge-list L3 610827.doc -39is inserted into the list of edge-lists stored in memory 1906 in order of ascending CurrentX representing the current x-values. Also, the pointer R3.Right is set to L3.

Fig. 25 shows the rectangles C4 and C5 joined with the rectangles C1, C2 and C3 to form the region 2500. Fig. 25 also shows the edge-lists L1, R3, L3, R1, L2 and R2, both graphically as arrows 2501) on the rectangles C1 to C5 and as tables 2502 which are stored in memory 1906, after the rectangles C4 and C5 have been added to the region 2400 to form the region 2500. At step 1631, the new rectangle C5 (assigned as D) is checked by the processor 1905 for a right edge that is greater than the value of R1.CurrentX 28). Since this is not the case, step 1635 is executed by the processor 1905 and the process returns to step 1619.

A next rectangle C6 is assigned as rectangle D by the processor 1905 at step 1619. The test at step 1625 is performed and since the value of D.top 22) is equal to the value of R1.CurrentY 22) and the value of D.left 27) is less than or equal to the value of R1.CurrentX 28), step 1629 is executed by the processor 1905. At step 1629, a new right edge-list R4 is created by the processor 1905, based on the points of the right edge of rectangle C5, and the new right edge-list R4 is inserted into the linked list of edge-lists stored in memory 1906, in order of ascending CurrentX current x-values).

Also at step 1629, the right edge-list pointer of edge-list L3 is set to point to the edge-list R4 by the processor 1905 and a new left edge-list L4 is created, based on the points of the left edge 711 of rectangle C6. The new left edge-list L4 is inserted into the linked list of edge-lists stored in memory 1906. Further, the edge-list to the right of edge-list R4 (i.e.

indicated by the pointer R4.Right) is set to the edge-list L4. Fig. 26 shows the rectangle C6 joined with the rectangles C1 to C5 to form a region 2600 and the edge-lists L1, R3, L3, R4, L4, R1, L2 and R2 both graphically as arrows 2601) on the rectangles CI to C6 and as tables 2602 which are stored in memory 1906, while the rectangle C6 is being added to the region 2500 to form the region 2600.

610827.doc Step 1633 is executed by the processor 1905 since the new rectangle C6 (assigned as D) has a value of D.right 33) which is greater than R1.CurrentX 28) indicating that D.right may have joined onto a new rectangle that is above and touching rectangle D. The edge-list R2 is returned by the processor 1905 as being the right edgelist having a last rectangle added which is above and touching the rectangle D. At the next step 1637, the edge-list indicated by the pointer L4.Right is examined by the processor 1905 and found to be not equal to the edge-list R2. In this case step 1639 is executed by the processor 1905 and each of the intermediate edges between the edge-list L4 and the edge-list R2 are joined. During the process of step 1639, for the edge-list indicated by the pointer L4.Right, a left edge-list L2 and a right edge-list R1 are found.

The edge-list to the right of the edge-list L2 indicated by the pointer L2.Right) is set to 0, and the edge-list to the left of the edge-list L2 indicated by the pointer L2.Left) is set to R1. The process continues at the next step 1635, where the rectangle C is assigned as the rectangle D by the processor 1905 and the process returns to step 1619.

Fig. 27 shows the region 2600 and the edge-lists L1, R3, L3, R4, L4, R1, L2 and R2, as arrows 2701) on the rectangles C1 to C6, after the rectangle C6 has been added to the region 2500 to form the region 2600.

A next rectangle C7 is assigned as D by the processor 1905, at step 1619 and the test at step 1625 is performed. Since the value of the point D.top 22) is equal to the value of R2.CurrentY(i.e. 22) and the value of the point D.left 34) is less than or equal to the value of R2.CurrentX 35), step 1629 is executed by the processor 1905.

A new right edge-list R5 is created, based on the points of the right edge 709 of the rectangle C6, and the new right edge-list R5 is inserted into the linked list of edge-lists stored in memory 1906. Further, the edge-list indicated by the pointer L4.Right is set to point to the edge-list R5 and a new left edge-list L5 is created, based on the points of the left edge 713 of the rectangle C7, and the new left edge-list L5 is inserted into the list of 610827.doc -41edge-lists stored in memory 1906. Also, the edge-list indicated by the pointer R5.Right is set to the edge-list L5. Fig. 28 shows the rectangle C7 joined with the rectangles C1 to C6 to form a region 2800. Fig. 28 also shows the edge-lists L1, R3, L3, R4, L4, R1, L2, L5 and R2, both graphically as arrows 2801) on the rectangles C1 to C7 and as tables 2802 which are stored in memory 1906, during the rectangle C7 being added to the region 2600.

Continuing the present example, the new rectangle C7 indicated by the pointer C7.right 37) is greater than the value of R2.CurrentX 35) and therefore, the rectangle C7 may have joined onto a rectangle other than the rectangle C3 that is above and touching the rectangle C7. In this case the processor 1905 executes the step 1633 and the edge-list R2 is returned as being the right edge-list having a last rectangle added which is above and touching the rectangle C7. At the next step 1637, the edge-list indicated by the pointer L5.Right is examined by the processor 1905 and found to be not equal to the edge-list R2. At the next step 1639, the process of joining all intermediate edges (as shown be the software code above) between the edge-list L5 and the edge-list R2 is performed by the processor 1905. In this case, no intermediate edge-lists are found and the process of the present example resumes at step 1635, where the rectangle C is assigned as D and the process returns to step 1619. Fig. 29 shows the rectangle C7 joined with the rectangles C1 to C6 to form the region 2900. Fig. 29 also shows the edge-lists L1, R3, L3, R4, L4, R1, L2, R5, L5 and R2, both graphically as arrows 2901) on the rectangles C1 to C7 and as tables 2902 which are stored in memory 1906, after the rectangle C7 has been added.

The process continues at the next step 1619, where a next rectangle C8 is assigned as D by the processor 1905. The test at step 1625 is performed and since the value of the point D.top 23) is not equal to the value of R2.CurrentY 22), the rectangle C8 is returned to the pool of rectangles stored in memory 1906 at step 1627, and 610827.doc -42the process returns to step 1621. At step 1621, the processor 1905 updates the edge-list R2 with the details of the right edge of the rectangle C7, the edge-list indicated by the pointer L5.Right is set to R2 and the process returns to step 1601.

The process of the present example continues at step 1601, where the next rectangle returned by the processor 1905 from the set of rectangles, C1 to C10, stored in memory 1906, is the rectangle C8. At step 1605, a left edge-list L1 is returned by the processor 1905 since the edge-list L1 is a left edge-list having a last rectangle added which is above and touching the rectangle C8. The process of the present example continues at step 1611, where the left edge-list L1 is updated with the details of the left edge of the rectangle C8. A right edge-list R3 is returned, the edge-list R3 being a right edge-list having a last rectangle added which is above and touching the rectangle C8. At the next step 1613, the edge-list to the right of the edge-list L1 indicated by the pointer L1.Right) is already the right edge-list R3. Therefore, the process proceeds to step 1617, where the value C8.right is equal to the value of R3.CurrentX and the process proceeds to step 1621. The right edge-list R3 is updated by the processor 1905 with the details of the right edge of the rectangle C8, at step 1621, and the edge-list L1.Right is set to the right edge-list R3 before the process returns to step 1601. Fig. 30 shows the rectangle C8 joined with the rectangles C1 to C7 to form a region 3000. Fig. 30 also shows the edge-lists L1, R3, L3, R4, L4, Ri, L2, R5, L5 and R2, both graphically as arrows 3001) on the rectangles C1 to C8 and as tables 3002 which are stored in memory 1906, after the rectangle C8 has been added.

The present example continues at the next step 1601, where the next rectangle returned by the processor 1905, from the set of rectangles, C 1 to C 10, is rectangle C9. At the next step 1605, a left edge-list L3 is returned, the left edge-list L3 being a left most left edge-list having a last rectangle added which is above and touching the rectangle C9.

At the next step 1611, the processor 1905 updates the left edge-list L3 with the details of 610827.doc -43the left edge of rectangle C9. A right edge-list R2 is returned, the right edge-list R2 being a right most right edge-list having a last rectangle added which is above and touching the rectangle C9. The process continues at the next step 1613, where the processor 1905 finds the edge-list indicated by the pointer L3.Right to be not equal to the right edge-list R2 and the process proceeds to step 1615. During the process of step 1615, a left edgelist L5 and a right edge-list R5 are found. The edge-list to the right of the edge-list indicated by the pointer L5.Right) is set to 0, and the edge-list to the left of L5 (i.e.

indicated by the pointer L5.Left) is set to R5. Then, a left edge-list L4 and a right edgelist R4 are found. The edge-list to the right of L4 indicated by the pointer L4.Right) is set to 0, and the edge-list to the left of L4 indicated by the pointer L4.Left) is set to R4. The process continues at step 1617, where since the value C9.right 35) is less than the value of R2.CurrentX 37), step 1619 is executed by the processor 1905 and D is assigned to rectangle At the next step 1625, the value of D.top 24) is not equal to the value of R2.CurrentY 23), so the rectangle D is returned by the processor 1905 to the pool of rectangles stored in memory 1906 and execution resumes at step 1621, where the right edge-list R2 is updated with the details of the right edge of rectangle C9 and the pointer L3.Right is set to the right edge-list R2. After step 1621, the process returns to step 1601.

Fig. 31 shows the rectangle C9 joined with the rectangles C1 to C8 to form a region 3100.

Fig. 31 also shows the edge-lists L1, R3, L3, R4, L4, R1, L2, R5, L5 and R2, both graphically as arrows 3101) on the rectangles C1 to C9 and as tables 3102 which are stored in memory 1906, after the rectangle C9 has been added.

The process of the present example continues at the next step 1601, where the next rectangle returned by the processor 1905 from the set of rectangles, C1 to stored in memory 1906, is rectangle CO10. At the next step 1605, a left edge-list L1 is returned, the edge-list L1 being a left edge-list having a last rectangle added which is 610827.doc -44above and touching the rectangle C 10. Then, at step 1611, the processor 1905 updates the edge-list LI with the details of the left edge of rectangle CO10 and a right edge-list R2 is returned, where the right edge-list R2 is a right-most right edge-list having a last rectangle added which is above and touching the rectangle C10. At the next step 1613, the edge-list to the right of the edge-list L1 indicated by the pointer L1.Right) is not equal to the right edge-list R2 and the process proceeds to step 1615. During the process of step 1615, a left edge-list L3 and a right edge-list R3 are found. The edge-list to the right of L3 (i.e.

indicated by the pointer L3.Right) is set to 0, and the edge-list to the left of L3 (i.e.

indicated by the pointer L3.Left) is set to R3. After step 1615, the process continues at step 1617, where since the value of ClO.right 26) is less than the value R2.CurrentX 35) the process proceeds to step 1619. At the next step 1623, the processor 1905 finds that D is empty so the process proceeds to step 1621. At step 1621, the edge-list R2 is updated by the processor 1905 with the details of the right edge of rectangle CIO, the pointer L1.Right is set to R2 and the process returns to step 1601. Fig. 32 shows the rectangle CO10 joined with the rectangles C1 to C9 to form a region 3200. Fig. 32 also shows the edge-lists L1, R3, L3, R4, L4, R1, L2, R5, L5 and R2, both graphically as arrows 3201) on the rectangles C1 to CO10 and as tables 3202 which are stored in memory 1906, after the rectangle C10 has been added. The process of the present example concludes at step 1601 where an empty rectangle is returned.

The traversal of the edge-lists L1, R3, L3, R4, L4, R1, L2, R5, L5 and R2 stored in memory 1906 will now be explained with reference to the method 2000 of Fig. 20. As seen in Fig. 32, the first edge-list selected in the list of edge-lists (as at step 2001) is the left edge-list L1. At the next step 2005, a variable T is set to the left edge-list L1 and a new path, Path 1, is created, as seen in Fig. 33. The edge-list F is set to L1.Right R2), as at step 2011. Then at step 2013, since the edge-list LI is a left edge-list, the flag end is set equal to TOP. The traversal process continues at the next step 2019, where the 610827.doc processor 1905 adds points in the left edge-list L1 to the path, Path 1, starting from point 0 and the left edge-list L1 is removed from the list of edge-lists and the flag end is set to BOTTOM. At the next step 2021, the processor 1905 adds the points in the right edgelist R2 from point 7, backwards to point 0, to the path P1 and the right edge-list R2 is removed from the linked list of edge-lists seen in Fig. 32. Further, the flag end is set to

TOP.

The traversal of the edge-lists L1, R3, L3, R4, L4, R1, L2, R5 and L5, stored in memory 1906, continues at the next step 2023, where the next edge-list F after the edgelist R2 is selected to be the edge-list L2, since the value of the pointer R2.Right is 0. At the next step 2029, the left edge-list L1 is not equal to the left edge-list L2 and the process returns to step 2021. Traversal of the edge-lists L1, R3, L3, R4, L4, R1, L2, R5 and by the processor 1905 continues in this manner by processing the next edge-list R1, until the next edge-list R1 is determined to be the edge-list L1 in step 2029. At this point step 2031 is executed by the processor 1905 and a path, Pathl, has been generated as seen in Fig. 33.

The traversal of the edge-lists L1, R3, L3, R4, L4, R1, L2, R5 and L5 continues at the next step 2001, where the first edge-list in the linked list of edge-lists stored in memory 1906 is the right edge-list R3. Processing continues in a similar manner to above from the right edge-list R3 to the left edge-list L3 then back to the right edge-list R3 and a second path, Path 2, is constructed as seen in Fig 34.

The third path traversal begins at step 2001, where the first edge-list in the list is the edge-list R4. Processing continues in a similar manner as explained above from the right edge-list R4 to the left edge-list L4 then back to the ight edge-list R4 and a third path, Path 3, is constructed, as seen in Fig. 35. Finally the fourth path traversal begins at step 2001, where the first edge-list in the linked list of edge-lists is the right edge-list Again, processing continues in a manner as explained above, from the right edge-list 610827.doc -46to the left edge-list L5 then back to the right edge-list R5 and a fourth path, Path 4, is constructed as in seen in Fig. The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.

In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

610827.doc

Claims (4)

1. 2. The method according to claim 1, wherein said edge-lists including said selected co-ordinate point values are removed from said set of ordered edge-lists.
2. 3. The method according to claim 1, wherein said set is ordered based on a magnitude of said co-ordinate point values.
3. 4. The method according to claim 1, comprising the further step of comparing at least two co-ordinate point values to determine an order of said edge-lists. The method according to claim 4, wherein said selected co-ordinate point values are selected based on said comparison.
4. 610827.doc -48- 6. The method according to claim 1, comprising the further step of adding co- ordinate point values to each of said edge-lists. 7. The method according to claim 6, wherein if a next co-ordinate point value to be added to an edge-list equals a previously added co-ordinate point value, then said next co-ordinate point value is not added to said edge-list. 8. The method according to claim 6, wherein if a next co-ordinate point value to be added to an edge-list is on an edge defined by at least two previously added co- ordinate point values then said next co-ordinate point value is not added to said edge-list. 9. The method according to claim 1, wherein each of said rectangles is represented by a left and a right edge-list. 10. The method according to claim 1, wherein said edge-lists are ordered based on ascending x-coordinate point values. 11. The method according to claim 1, wherein said rectangles are provided in scan- line order. 12. The method according to claim 1, wherein said co-ordinate point values represent pixel values. 13. The method according to claim 1, wherein each of said edge-lists includes a pointer to at least one other of said edge-lists. 610827.doc -49- 14. The method according to claim 13, wherein said pointer indicates an order of said edge-lists. A method of generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said method comprising the steps of: selecting a first rectangle from said plurality of rectangles; determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the following sub-steps for said right edge- list: 610827.doc (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; traversing said set of edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region; and generating said path using said selected co-ordinate point values. 16. The method according to claim 15, wherein any edge-lists of said set including said selected co-ordinate point values are removed from said set of edge-lists. 17. The method according to claim 15, said method comprising the further step of joining said left edge-list with said right edge-list. 18. The method according to claim 15, wherein for each pair of edge-lists lying between said left edge-list and said right edge-list, and having a current y-value equal to a point on a top edge of said first rectangle, said method comprising the following further sub-steps of: setting an edge-list to the right of said pair of edge-lists to zero; and setting an edge-list to the left said pair of edge-lists to one. 610827.doc -51 19. The method according to claim 15, said method comprising the further step of selecting a second rectangle, wherein if said second rectangle has a point on a top edge not equal to a current y-value of said right edge-list, or a point on a left edge greater than said current x-value of said right edge-list, then said second rectangle is returned to said plurality of rectangles, otherwise steps and are repeated for said second rectangle. The method according to claim 15, wherein said rectangles are non-overlapping. 21. A method of generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said method comprising the steps of: generating a plurality of edge-lists for each of said rectangles, said edge-lists including co-ordinate point values defining edges for one or more of said rectangles; and ordering said plurality of edge-lists based on said co-ordinate point values to provide a representation of said clipping region. 22. The method according to claim 21, comprising the further steps of traversing said ordered edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region. 23. The method according to claim 22, comprising the further step of removing any of said edge-lists including said selected co-ordinate point values from said ordered edge- lists. 610827.doc -52- 24. The method according to claim 23, comprising the further step of generating a path using said selected co-ordinate point values. A method of generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said method comprising the steps of: selecting a first rectangle from said plurality of rectangles; determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the following sub-steps for said right edge- list: 610827.doc -53 (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; repeating steps to (c4) for each of said plurality of rectangles. 26. The method according to claim 25, comprising the further steps of traversing said list of edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region 27. The method according to claim 26, wherein any edge-lists of said set including said selected co-ordinate point values are removed from said set of edge-lists. 24. 28. The method according to claim 26, comprising the further step of generating a path using said selected co-ordinate point values. 29. An apparatus for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of non-overlapping rectangles, said apparatus comprising: first generating means for generating a plurality of edge-lists for said rectangles, each of said edge-lists being associated with at least one said rectangle and 610827.doc -54- including co-ordinate point values, said co-ordinate point values defining edges for one or more of said rectangles; ordering means for ordering said edge-lists based on said co-ordinate point values to form a set of ordered edge-lists; traversing means for traversing said set and selecting certain ones of said co- ordinate point values which define edges on a periphery of said clipping region; and second generating means for generating said path using said selected co- ordinate point values. 30. The apparatus according to claim 29, wherein said edge-lists including said selected co-ordinate point values are removed from said set of ordered edge-lists. 31. The apparatus according to claim 29, wherein said set is ordered based on a magnitude of said co-ordinate point values. 32. The apparatus according to claim 29, further comprising comparing means for comparing at least two co-ordinate point values to determine an order of said edgelists. 33. The apparatus according to claim 32, wherein said selected co-ordinate point values are selected based on said comparison. 34. The apparatus according to claim 29, further comprising adding means for adding co-ordinate point values to each of said edge-lists. 610827.doc The apparatus according to claim 34, wherein if a next co-ordinate point value to be added to an edge-list equals a previously added co-ordinate point value, then said next co-ordinate point value is not added to said edge-list. 36. The apparatus according to claim 34, wherein if a next co-ordinate point value to be added to an edge-list is on an edge defined by at least two previously added co- ordinate point values then said next co-ordinate point value is not added to said edge-list. 37. The apparatus according to claim 29, wherein each of said rectangles is represented by a left and a right edge-list. 38. The apparatus according to claim 29, wherein said edge-lists are ordered based on ascending x-coordinate point values. 39. The apparatus according to claim 29, wherein said rectangles are provided in scan-line order. The apparatus according to claim 29, wherein said co-ordinate point values represent pixel values. 41. The apparatus according to claim 29, wherein each of said edge-lists includes a pointer to at least one other of said edge-lists. 42. The apparatus according to claim 41, wherein said pointer indicates an order of said edge-lists. 610827.doc -56- 43. An apparatus for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said apparatus comprising: means for selecting a first rectangle from said plurality of rectangles; means for determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, wherein said means for determining a left edge-list comprises means for performing the following steps for said left edge-list: adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (ii) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; (iii) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (iv) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; means for determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, wherein said means for determining a right edge-list comprises means for performing the following steps for said right edge-list: adding points defining a right edge of said first rectangle to said right edge-list; 610827.doc -57- (vi) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (vii) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (viii) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; means for traversing said set of edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region; and means for generating said path using said selected co-ordinate point values. 44. The apparatus according to claim 43, wherein any edge-lists of said set including said selected co-ordinate point values are removed from said set of edge-lists. The apparatus according to claim 43, further comprising means for joining said left edge-list with said right edge-list. 46. The apparatus according to claim 43, said apparatus further comprising: means for setting to zero an edge-list to the right of each pair of edge-lists lying between said left edge-list and said right edge-list, and having a current y-value equal to a point on a top edge of said first rectangle; and means for setting an edge-list to the left said pair of edge-lists to one. 47. The apparatus according to claim 43, further comprising means for selecting a second rectangle, wherein if said second rectangle has a point on a top edge not equal to a current y-value of said right edge-list, or a point on a left edge greater than said current x- 610827.doc -58- value of said right edge-list, then said second rectangle is returned to said plurality of rectangles. 48. The apparatus according to claim 43, wherein said rectangles are non- overlapping. 49. An apparatus for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said apparatus comprising: generation means for generating a plurality of edge-lists for each of said rectangles, said edge-lists including co-ordinate point values defining edges for one or more of said rectangles; and ordering means for ordering said plurality of edge-lists based on said co- ordinate point values to provide a representation of said clipping region. The apparatus according to claim 49, further comprising traversal means for traversing said ordered edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region. 51. The apparatus according to claim 50, further comprising removal means for removing any of said edge-lists including said selected co-ordinate point values from said ordered edge-lists. 52. The apparatus according to claim 51, further comprising path generating means for generating a path using said selected co-ordinate point values. 610827.doc -59- 53. A computer program for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of non-overlapping rectangles, said program comprising: code for generating a plurality of edge-lists for said rectangles, each of said edge-lists being associated with at least one said rectangle and including co-ordinate point values, said co-ordinate point values defining edges for one or more of said rectangles; code for ordering said edge-lists based on said co-ordinate point values to form a set of ordered edge-lists; code for traversing said set and selecting certain ones of said co-ordinate point values which define edges on a periphery of said clipping region; and code for generating said path using said selected co-ordinate point values. 54. A computer program for generating a path representing the outline of a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said program comprising code for performing the following steps: selecting a first rectangle from said plurality of rectangles; determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; 610827.doc (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the following sub-steps for said right edge- list: (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; traversing said set of edge-lists and selecting co-ordinate point values which define edges on a periphery of said clipping region; and generating said path using said selected co-ordinate point values. A computer program for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said program comprising: 610827.doc -61 code for generating a plurality of edge-lists for each of said rectangles, said edge-lists including co-ordinate point values defining edges for one or more of said rectangles; and code for ordering said plurality of edge-lists based on said co-ordinate point values to provide a representation of said clipping region. 56. A computer program for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said program comprising code for performing the following steps: selecting a first rectangle from said plurality of rectangles; determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and performing the following sub-steps for said left edge-list: (bl) adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (b2) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; (b3) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (b4) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and 610827.doc -62- touching said first rectangle, and comprising the following sub-steps for said right edge- list: (cl) adding points defining a right edge of said first rectangle to said right edge-list; (c2) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (c3) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (c4) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; repeating steps to (c4) for each of said plurality of rectangles. 57. An apparatus for generating edge-lists representing a clipping region, said clipping region describing a portion of a graphical image and being provided as a plurality of rectangles, said apparatus comprising: means for selecting a first rectangle from said plurality of rectangles; means for determining a left edge-list for said first rectangle, said left edge-list comprising coordinate point values defining edges for at least said first rectangle and a smallest current x-coordinate point value, as herein defined, wherein a most recent rectangle added to said left edge-list is above and touching said first rectangle, and means for performing the following steps for said left edge-list: adding co-ordinate point values defining a left edge of said first rectangle to said left edge-list; (ii) setting said current x-value of said left edge-list to a value corresponding to a point on said left edge; 610827.doc -63- (iii) setting a current y-value, as herein defined, of said left edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (iv) adding said left edge-list to a set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value; means for determining a right edge-list having a largest current x-value, said right edge-list comprising coordinate point values defining edges for at least said first rectangle, wherein a most recent rectangle added to said right edge-list is above and touching said first rectangle, and comprising the means for performing the following steps for said right edge-list: adding points defining a right edge of said first rectangle to said right edge-list; (vi) setting a current x-value of said right edge-list to a value corresponding to a point on said right edge; (vii) setting a current y-value of said right edge-list to a value corresponding to a point on a bottom edge of said first rectangle; and (viii) adding said right edge-list to said set of edge-lists, wherein said set of edge-lists is sorted in order of ascending current x-value. 58. A method of generating a path representing the outline of a clipping region, said method being substantially as herein before described with reference to any one of the embodiments as shown in Figs. 3 to 59. An apparatus for generating a path representing the outline of a clipping region, said apparatus being substantially as herein before described with reference to any one of the embodiments as shown in Figs. 3 to 610827.doc -64- A computer program for generating a path representing the outline of a clipping region, said program being substantially as herein before described with reference to any one of the embodiments as shown in Figs. 3 to DATED this Sixteenth Day of October 2002 CANON KABUSHIKI KAISHA Patent Attorneys for the Applicant SPRUSON&FERGUSON 610827.doc