AU747017B2 - Overlapping edge blends and other texture mapped regions - Google Patents

Description

S&F Ref: 485131

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome Ohta-ku Tokyo Japan George Politis Spruson Ferguson St Martins Tower 31 Market Street Sydney NSW 2000 Overlapping Edge Blends and Other Texture Mapped Regions ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) [32] Application Date AU PP7717 14 Dec 1998 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c 27. FEB. 2002 18:16 SPRUSON FERGUSON 61 2 92615486 NO. 2788 P. 8/47 -1- OVERLAPPING EDGE BLENDS AND OTHER TEXTURE MAPPED REGIONS Field of the Invention The present invention relates to computer graphics and, in particular, to the generation of overlapping texture mapped regions, including parametrically defined colour blends.

Background The display of graphical objects involves considering many issues which influence various aspects of the image being displayed. Examples of such issues include S 10 the actual colour being displayed and the time taken to determine (render) the colour to be displayed. Where graphical objects are opaque, these issues are relatively simple.

However, transparent and partly transparent objects complicate issues, particularly where the colour and/or opacity of an object changes or varies within the object boundaries.

Specific problems arise where an object is self-overlapping and the displayed colour is a 00 15s textural blend of varying colours from the overlapping portions.

It is an object of the present invention to provide a manner in which such selfoverlapping regions may be faithfully rendered in a convenient fashion.

Summary of the Invention In accordance with one aspect of the present invention there is disclosed a S2 method of determining a displayable colour in a self-overlapping region of a variable colour object, said method comprising the steps of: determining, for each point in the region, the colour of each portion of the object present at that point; at each said point, averaging the colours present at that point; and outputting said averaged colours for reproductions within said region.

In accordance with another aspect of the present invention there is disclosed a method of determining a displayable colour in a self-overlapping region of a variable colour object characterised by the use of a commutative operator that mixes a plurality of S RA4/< solours in an order independent manner.

27. FEB. 2002 18:16 SPRUSON FERGUSON 61 292615486 NO. 2788 P. 9/47 -2- In accordance with another aspect of the present invention there is disclosed a commutative operator for mixing colours having opacity components, said operator being of the form: /nover o, ii 11oero SoI /n Zo.

where over o, I o, H os), and cj and oj are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object.

In accordance with another aspect of the present invention there is disclosed a method of rendering a graphical object, said method comprising steps of: accumulating edge transitions of said object in a scan line by scan line fashion using the non-zero winding fill rule to thereby determine a fill count for regions of the object defined by the edge transitions; :defining regions of said object having a fill count of at least 2 as self-overlapping 15 regions; :determining an output value of a pixel i said self overlapping regions according to a rule; and determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self-overlapping region.

20 In accordance with another aspect of the present invention there is disclosed a method for rendering in a scan-line manner an arbitrary object having at least one overlapping region, said method comprising the steps of: for each scan line of said object scan converting the object on said scan line determining the overlapping regions of said object within said scan line; 27. FEB. 2002 18:16 SPRUSON FERGUSON 61 292615486 NO, 2788 P. 10/47 initializing a overlap buffer for each said overlapping regions for each portion of the object on said scan line (da) determining if said portion is an overlapping region (daa) if so, accumulating the colour of pixels of said portion in the corresponding said overlap buffer; (dab) if not, outputting the colour of pixels of said portion; for each overlapping region, calculating an average colour from the corresponding accumulated value in said corresponding overlap buffer; and outputting the average colours.

accordance with another aspect of the present invention there is disclosed an apparatus for determining a displayable colour in a self-overlapping region of a variable colour object, said apparatus comprising: is clourcolour determination means for determining, for each point in the region, the clourof each portion of the object present at that point; averaging means, responsive to said colour determination means, adapted. to *average, at each said point, the colours present at that point; and output means coupled to said averaging means for outputting said averaged colours for reproductions within said region.

In accordance with another aspect of the present invention there is disclosed an apparatus for determining a displayable colour in a self-overlapping region of a variable colour object characterised by comprising a commutative operator means adapted to midx a plurality of colours in an order independent manner.

In accordance with another aspect of the present invention there is disclosed a commutative operator means for mixing colours having opacity components, said operator means adapted to perform the operation: [Scioi /n n -La n over oi y- overoij Fo/n i =I Zoi i I 27. FEB. 2002 18:17 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 11/47 -4where over o, I o, TI (1 -ao), i=1 i=1 j=i+1 and ci and oi are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object.

In accordance with another aspect of the present invention there is disclosed an apparatus for rendering a graphical object, said apparatus comprising: means for accumulating edge transitions of said object in a scan line by scan line fashion using the non-zero winding fill rule to thereby determine a fill count for regions of the object defined by the edge transitions; means for defining regions of said object having a fill count of at least 2 as self- :0.:10 overlapping regions; means for determiing an output value of a pixel in said self overlapping regions according to a rule; and means for determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self-overlapping region.

In accordance with another aspect of the present invention there is disclosed a apparatus for rendering in a scan-line manner an arbitrary object having at least one overlapping region, said apparatus comprising: .~for each scan line of said object scan conversion means for scan converting the object on said scan O 20 line eec(b) overlapping region detection means for determining the overlapping regions of said object within said scan line; buffer initialization means for initializing an overlap buffer for each said overlapping regions overlapping region determination means, operative in respect of each portion of the object on said scan line (da) for determining if said portion is an overlapping region 27 FEB. 2002 18:17 SPRIJSON FERGUSON 612 92615486 NO. 2788 P. 12/47 (daa) and, if said portion is an overlapping region, adapted to accumulate the colour of pixels of said portion in the corresponding said overlap buffer; (dab) and, if said portion is not an overlapping region, adapted to output the colour of pixels of said portion; calculation means, operative in respect of each overlapping region, to calculate an average colour from the corresponding accumulated value in said corresponding overlap buffer; and (0outputting means for outputting the average colours.

In accordance with another aspect of the present invention there is disclose a computer program product including a computer readable medium incorporating a series of instructions configured to determine a displayable colour in a self-overlapping region *of a variable colour object, said instructions comprising: each determination steps for determining, for each point in the region, the colour of ac portion of the object present at that point; averaging steps for, at each said point, averaging the colours present at that point; and outputting steps for outputting said averaged colours for reproduction within said region.

In accordance with another aspect of the present invention there is disclosed a computer program product for determining a displayable colour in a self-overlapping region of a variable colour object characterised by comprising commutative operator steps adapted to mix a plurality of colours in an order independent manner.

In accordance with another aspect of the present invention there is disclosed a computer program product comprising commutative operator steps for mixing colours having opacity components, said operator steps adapted to perform the operation: (zcioi /n n s~j n over Oil E j ,over Oil E oi/n 'i=l K oi i=lI 27. FEB. 2002 18:17 SPRUSON FERGUSON 61 29215486 NO. 2788 P. 13/47 n n: n where over 1=So, HDir (l -o0), 1=1 i=1 j=i+1 and ci and oi are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object.

In accordance with another aspect of the present invention, there is provided computer program product including a computer readable medium having recorded thereon a computer program for directing a computer to render a graphical object, said program compnising: code for accumulating edge transitions of said object in a scan line by scan line fashion using the non-zero winding fill rule to thereby determine a fill count for regions of :00. i the object defined by the edge transitions; code for defining regions of said object having a fill count of at least 2 as selfoverlapping regions; gee: code for determining an output value of a pixel in said self overlapping regions according to a rule; and code for determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self-overlapping region.

n accordance with another aspect of the present invention, there is provided computer program for directing a computer to render a graphical object, said program comprising: code for accumulating edge transitions of said object in a scan line by scan line e~ee :fashion using the non-zero winding fill rule to thereby determine a fill count for regions of 27. FEB. 2002 18:17 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 14/47 6a the object defined by the edge transitions; code for defining regions of said object having a fill count of at least 2 as selfoverlapping regions; code for determining an output value of a pixel in said self overlapping regions according to a rule; and4 code for determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self-overlapping region.

In accordance with another aspect of the present invention, there is provided computer program product for rendering in a scan-line manner an arbitrary object having lo 1 at least one overlapping region, said program comprising: 6 so for each scan line of said object scan conversion steps for scan converting the object on said scan line overlapping region detection steps for determining the overlapping regions of said object within said scan line; buffer initialization steps for initializing a overlap buffer for each said overlapping regions overlapping region determination steps, operative in respect of each c. portion of the object on said scan line o 6 (da) for determining if said portion is an overlapping region 20 (daa) and, if said portion is an overlapping region, adapted *o to accumulatc the colour of pixels of said portion in the corresponding said overlap buffer; :so(dab) and, if said portion is not an overlapping region, adapted to output the colour of pixels of said portion; calculation steps, operative in respect of each overlapping region, to calculate an average colour from the corresponding accumrulated value in said corresponding overlap buffer; and outputting steps for outputting the average colours.

27. FEB. 2002 18:18 SPRIJSON FERGUSON 61 292515486 NO. 2788 P. 15/47 6b In accordance with another aspect of the present invention, there is provided method of rendering, in a scanline manner, a variable colour object having portions thereof forming at least one self-overlapping region, said method comprising, for a scanline that intersects said object, the steps of: 6 determining, for at least a first point along the scanline in said self-overlapping region 1 a colour of each portion of the object at said first point; averaging said colour of each said portion of the object at said first point to form a resultant colour at the first point; and outputting said resultant colour for the first point.

Brief Description of the Drawings A number of aspects of the prior art and a number of embodiments of the present invention will now be described with reference to the drawings in which:, ego: 0-e0 Figs. 1IA and lB depict prior art two-dimensional parameterized regions; 15 Figs. 2A and 2B depict a prior art distortion to an image; Figs, 3A and 3B depict a prior art mesh technique used to improve speed of rendering at the expense of quality; Fig. 4 depicts an overlapping ruled surface to which an embodiment of the e. present invention may be applied; :20 Fig. 5A depicts another ruled surface; go Figs. 5B and SC depict application of the embodiments to the regions of Fig. Figs. 6A to 6C depict how the non-zero winding rule may be applied to the regions of Fig. 4; Fig. 7 depicts application of the mesh techniques to the rendering of Fig. 4 and highlights mesh elements that are affected by self-overlap; Fig. 8 depicts a set of scan line runs generated using the winding counting fill rule and a generated array of transition points; Fig. 9 is a block diagram of a general purpose computer upon which the preferred embodiment of the present invention can be practiced; Fig. 10 depicts the method steps performed in one embodiment; and Fig. 11 depicts the method steps performed in a scan-line rendering embodiment.

Detailed Description Prior to discussing the present invention and its embodiments, it is appropriate to review current techniques for rendering texture mapped regions.

Given a region of space R over which a two-dimensional parameterization x(u,v) is defined, for example, a ruled surface as in Fig.

1A, or a Coons patch as in Fig. 1B, and (ii) some image, texture map, blend procedural texture or the like T(u,v) that yields colour (and/or opacity value) for given in suitable range, S. 20 it is possible to create an image distortion or curved colour blend or the like, by taking the colour T(u,v) at each value and drawing it at position as illustrated in Figs. 2A and 2B.

Conversely, it is possible to determine the value for each point x in the region R, look up the colour T(u,v) at and draw it at x. This presupposes that the mapping x(u,v) is invertible and can be inverted with sufficient ease.

An alternative approach that has been used is to provide an inverse 00 distortion and to derive the colour at each by first deriving then looking up then drawing the colour at x In this scheme, the region defined by u acts like a "cookie" section cutter on T, then distorts the cut (cookie) section into a CFP1541AU Open32 1:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc rectangle. This approach has the advantage that an easily invertible mapping is not required. However, it is not easy with this method to take a rectangular shape and distort it into a required irregular shape, as seen in Fig. 2B.

A common technique employed to improve the speed of such techniques is to divide the parameterized region R into a mesh of points at which the parameterization is calculated, an example of which is seen in Figs. 3A and 3B. The colour can be looked up in T at the mesh points and then linearly interpolated. The finer the mesh, the better the quality, but the slower the rendering. As shown in Fig. 3B, the mesh is often subdivided into triangles, which are the simplest polygon to render.

One difficulty with the first approach (where x(u,v) and T(u,v) are given) is that the region x(u,v) may self-overlap, as illustrated in Fig. 4. In this case, x(u,v) has no unique inverse within the overlapping region, with two competing choices for the correct colour.

Where the overlapping shape is a two-dimensional projection of a threedimensional object, each point will have a distance from the viewpoint. A variety of algorithms exist for determining which point in a region of overlap is the one closest to the viewpoint, and whose colour is thus typically chosen as the one to render at that point.

In situations where alpha-channel compositing is available, however, it is possible to define a sensible colour for the overlapping region. Suppose there are two 20 overlapping objects, one with colour cl, and opacity ol, and the other with colour c 2 and opacity 02. In practice, three colour channels, (R 1

,G

1 ,Bl) and (R 2

G

2

B

2 may be used. For simplicity, and without loss of generality, one channel will only be considered.

The colour and opacity can be stored together as a tuple It is customary in alphachannel compositing to store the colour and the opacity multiplied together, thus representing the two colours as (c l ol,ol) and (c20 2 (In mathematical expressions, angle brackets will be used here to notate these "premultiplied" colours).

"I A commonly used effect that simulates the superposition of one object on the other is provided by the "over" operator: (clo 1 ,o 1 over (c 2 0 2 ,o 2 (c 1 1 (1 Ol)c 2 0 2 01 02 0102).

CFP1541AU Open 32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc Note that this operator is not commutative, that is, in general, (cl 1 o,o 1 over (c 2 0 2 ,o 2 (c 2 o 2 ,o 2 over (clol,ol).

In other words, given a series of two or more objects, the order in which they are superposed is significant. However, it is worthwhile noting that the resulting opacity is independent of the order of the objects.

Returning to the difficulty of overlapping regions, at any point p where over parameterized region R overlaps itself such as seen in Fig. 4, there are two or more sets of parametric coordinates that map to p: p x(ul,vl) x(u 2

,V

2 It is possible to obtain, from these parametric coordinates, a set of competing colours that contribute to the net colour at p in some way: (cl 1 o,o 1 T(ul,vI), 2 ,o 2 T(u2,2), Combining these colours using the "over" operator may be unsuitable because it implies an ordering. Unless some specific application dictates an ordering, such as one based upon parameterization, in general none is imposed by the geometry or other intrinsic aspect of this process.

Addressing this issue, in accordance with the present invention, a number of 20 embodiments are proposed that permit calculation of the overlapping area to obtain a textured result.

9* A first embodiment presents the opacity-weighted average: 9.

E cioi oi n n (1) where n is the number of parametric coordinates (ui,vi) that map to the point p in question. Expression has the effect of mixing the contributing colours and averaging their opacities. An important advantage of averaging cio i rather than c i is that colours that are nearly transparent contribute only in a small way to the result, while nearly opaque colours contribute significantly. Thus, for example, while mixing 50% transparent red CFP1541AU Open 32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc and 50% transparent yellow should give orange, a nearly opaque red mixed with a barely visible yellow should yield a colour not far from red.

The simpler form cCi Zoi n n is possible if desired in some application.

Secondly, a more sophisticated approach is to mix the colour as in Expression but to simulate the effect of "over" in increasing the opacity as more and more contributing colours are superposed: I cioi/n n y cioi n /n over i over oi ioi/n Yi=l oi i=l (2) n n n where overo i X oi nF (1-oi), i= 1 1= j=i+l ie., the opacity of( x, o 1 over x, 02 over x, o n An advantage of this second, albeit more complicated method, is shown in Figs. 5A, 5B and Fig. 5A shows a ruled surface in which opacity o(u,v) v. Fig. 5B shows an 15 opacity profile along line L of Fig. 5A derived by averaging contributing opacities (as per 0:00 Expression Fig. 5C shows an opacity profile along line L of Fig. 5B derived by accumulating contributing opacities with "over" (as per Expression As can be seen, 0 Expression yields a result without the discontinuities of Fig. e* 0 A description of how such techniques can be implemented follows, with primary emphasis on scan line rendering. The methods described can be generalised easily to band or frame buffer rendering.

c The simplest approach is to store, for each pixel, running sums k C= E cio i i=l CFP1541AU Open32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc -11k A= X oi i=1 k, and, for the second method, k B over oi i=l Initially, for every pixel the values are set such that A B =C k 0.

As each pixel is rendered by whatever means, for example by dividing the region into a mesh and linearly interpolating intermediate colours, A, B and C are accumulated, and k is incremented. When rendering is finished, Expression or is calculated: ZCio i oi C C A n n \k k (3) or Cf C rcioi over f ,B ,A0 ,i oi A

E

oi A=0 (4) An inefficiency with this technique is that in regions where there is only one contributing colour, extra storage and complicated arithmetic are not needed for evaluation. If the regions where overlaps occur can be identified, it is then possible to limit the storage and calculation of running sums and final division to the pixels within those regions. Pixels outside can be written into a scan line (or frame, etc.) buffer Sdirectly.

One method for identifying those regions is to generate an outline for the region R and scan convert the region R using the non-zero winding method and maintaining a count of the number of contributing colours in a region. This will provide, for each scan line, information about which pixels have one contributing region, two contributing regions, and so on, as seen in Figs. 6A to 6C.

Fig. 6A shows a directed outline derived from the ruled surface R of Fig. 4.

Applying scan conversion using the non-zero winding method returns the number of CFP1541AU Open32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc -12portions of R that contribute to each pixel, as shown in Fig. 6B. On each scan line, as seen in Fig. 6B, non-zero winding scan conversion identifies a series of segments each having an associated count as seen in Fig. 6C.

In the case where the region R has been subdivided into a mesh and linear interpolation applied, care must be taken in cases where a sequence of linearly interpolated pixels cross a boundary of a segment returned by the "non-zero winding" method of scan conversion. Fig. 7 illustrates an example where this happens, with a triangular mesh derived from the ruled surface of Fig. 4. The shaded triangles span regions with different winding count, as seen from Fig. 6. In those cases, the linear interpolation must be broken into two (or more, as required) loops. The portions relating to winding count 1 are determined simply by writing the interpolated colours, while those with greater winding count are determined by accumulating partial sums (and later calculating the final colour and opacity).

Further details may now be discussed about how rendering would take place.

For each scan line, a set of runs is returned from the scan conversion of the outline of region R, as in Fig. 6C. These can be processed into a set of transition points where the fill count changes between less than 2 and 2 or more, with the transition points stored in an array, X, as shown in Fig. 8. It will be observed that regions with fill count of2 or more lie between points in array X indexed by even numbers and points indexed.

An additional final entry containing a very large number (denoted o• is required by the method described above.

A scan line without any occurrence of fill count 2 or more only has X[O] The next thing to do is to initialize buffers in regions where the fill count is 2 or more.

When rendering each triangle, the process described the following pseudocode may be implemented: Determine xstar t Xend, the range of pixels in the current scan line required to fill the triangle CFP1541AU Open32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc -13i -0 while Xstart X[i] do Increment i while Xend X[i] do begin if i is odd then Generate data for pixels Xstart to X[i] 1 and accumulate data in buffers, for example, sums A, B, C and k defined above.

else Generate data for pixels xstart to X[i] 1 and write data directly into output buffer.

Xstart X[i] Increment i end if i is odd then Generate data for pixels xstart to xend 1 and accumulate data in buffers, for example, sums A, B, C and k defined above.

else Generate data for pixels xstart to xend 1 and write data directly in output buffer.

After all triangles have been rendered, calculate output pixels can be determined for regions where the fill count is 2 or more, for example, by evaluating Expression (1) or using terms A, B, C and k.

n n over oi E o i 25 An alternative to i=1 for opacity is simply clamped at the I. maximum opacity, usually defined to be 1.

It will be apparent from the foregoing that a means for generating overlapping texture mapped regions and in particular overlapping parametrically defined colour blends is provided that affords practical results whilst keeping the amount of memory and processing comparable to prior art methods. The various alternatives for texture determination may be selected depending upon specific requirements of the desired result.

The preferred embodiment of the invention can be practised using a conventional general-purpose (host) computer system, such as the computer system 40 shown in Fig. 9, CFP1541AU Open 32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc -14wherein the various method steps performed are implemented as an application program software executed on the computer system 40. The computer system 40 comprises a computer module 41, input devices such as a keyboard 42 and mouse 43, output devices including a printer 13 and a display device 11. A Modulator-Demodulator (Modem) transceiver device 52 is used by the computer module 41 for communicating to and from a communications network, for example, connectable via a telephone line or other functional medium. The modem 52 can be used to obtain access to the Internet, and other network systems.

The computer module 41 typically includes at least one processor unit 45, a memory unit 46, for example, formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 47, and an I/O interface 48 for the keyboard 42, a mouse 43 and optionally a joystick (not illustrated). A storage device 49 is provided and typically includes a hard disk drive 53 and a floppy disk drive 54. A CD-ROM drive 55 is typically provided as a non-volatile source of data. The components 45 to 49 and 53 to 55 of the computer module 41, typically communicate via an interconnected bus 50 and in a manner which results in a conventional mode of operation of the computer system 40 known to those in the relevant art. Examples of computers on which the embodiments can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom. Typically, the application program of the preferred embodiment is resident on a hard disk drive 53 and read and controlled using the processor 45. Intermediate storage of the program and the print list and any data fetched from the network may be accomplished using the semiconductor memory 46, possibly in concert with the hard disk i drive 53. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk, or alternatively could be read by the user from the network via the modem device 52.

Fig. 10 indicates the various method steps 100 implemented in one embodiment.

The method 100 commences at step 102 where a graphic object forming part of the image to be rendered is examined to determined those regions of the object that are self- CFP1541AU Open32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc overlapping. As indicated above, this is preferably performed using the non-zero winding method. This is followed by step 104 where a determination is made as to whether any such regions require processing. If so, step 106 follows which examines if any portions of the region require processing. A single overlap provides two portions and a double overlap gives three, and so on. If so, the colour at each point (eg. pixel) within the position is examined at step 108 and at step 110 that colour is accumulated with colours at the same point locations from other portions in the region. After step 110, control returns to step 106. It will be apparent from this process that the averaging over the portions in a region can be performed progressively without a need to simultaneously store each pixel value for each location for each portion. When step 106 determines all portions in a region have been processed, the average colour for each point in the region is calculated at step 112. When there are no more regions, step 104 passes control to step 114 where pixel data for the object including all overlapping and non-overlapping regions are output.

The pixel data may be output for display by either the video display 11 or the printer 13.

Alternatively, the data may be stored in the memory 46 or using the devices 49. Further, the pixel data may be output to a computer network via the modem 52.

."'The graphical object being rendered is typically variable in colour and/or opacity.

For example the object may be formed of a distorted, tiled or texture-mapped pixel-based image, or any combination of such. The object may also be a spatially or parametrically defined blend of colour and/or opacity. The object may also be a spatially or .parametrically defined procedural texture.

Fig. 11 shows a method 200 for rendering an arbitrary object having overlapping .i regions in a scan-line manner. The method 200 commences with step 202 with an initialization for scan conversion of the scan line. Step 204 determines if there are lines remaining for scan conversion and, on a positive response (yes) step 206 scan converts the next scan line. Step 208 which follows determines the overlapping regions within the scan line, and step 210 initializes temporary buffers for the overlapping regions. Step 212 commences a loop which operates on each portion of the object on the current scan line.

Step 214 which follows determines if the current portion is an overlapping region CFP1541AU Open32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc -16determined from step 208. If so, step 216 follows which accumulates the colour of pixels of that portion in the temporary buffer for that overlapping region. Control then returns to step 214 to examine if there are any more portions on the current scan line. If, from step 214, the region is not an overlapping region, step 218 follows which writes the pixel colour values directly to an output buffer. When step 212 determines there are no more portions of the object on the current scan line, step 220 follows to calculate the average colour for each pixel in each overlapping region. Step 222 then writes the average colours to the output buffer and step 224 follows by sending the completed filled) output buffer to an output device, such as a printer or display, for reproduction. Control then returns to step 204 for consideration of the next scan line. When all scan lines have been converted, step 226 ceases scan conversion.

The foregoing describes only a number of embodiments of the present invention and modification may be made thereto without departing from the scope of the present invention.

For example, the weighted average opacity determined using Expression may not always be desired. In some instances an unweighted (direct) average may give a desired effect. Further, the colours at the overlap may be combined, in an alternative to average, by for example accumulating their values. Where appropriate, a predetermined i clamp level can be used to ensure at least a minimum level of translucency rather than allowing the texture to become wholly opaque.

r CFP1541AU Open 32 I:\ELEC\CISRA\OPEN\OPEN32\485131AU.doc

Claims (21)

1. 27. FEB. 2002 18:18 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 16/47 17- The claims defining the invention are as follows: 1 A method of determining a displayable colour in a self-overlapping region of a variable colour object, said method comprising the steps of; determining, for each point in the region, the colouir of each portion of the object present at that point; at each said point, averaging the colours present at that point; and outputting said averaged colours for -reproductions within said region. 2. A method according to claim 1, wherein each said colour includes an opacity io component and the average colour at each said point is calculated by weighting each colour by the corresponding opacity, and determining a resultant opacity. 4. I3 A method according to claim 2, wherein the resultant opacity is determnined by adding individual opacities together. 4. A method according to claim 3, wherein said added opacities are clamped to a *predetermined level when a sum exceeds said predetermined level. 6. A method according to claim 2, wherein the resultant opacity is determined by eauaing the over"t frmul ai ofrin()a.eendfnd 8 A method according to claim wherein the resultnt opaciuethis deteine b th idigfllrl*mto t eeriesid self-overlapping region.o cnieb cnmebss 27. FEB. 2002 18:18 SPRUSON FERGUSON 612 92615486 NO, 2788 P. 17/47 9. A method according to claim 8, wherein an array of transition points is used to store those pixels on a scan line that lie within said self-overlapping region. 10. A method according to any one of claims I to 9, wherein said variable colour object is a distorted and/or tiled and/or textured mapped pixel-based image. 11. A method according to any one of claims I to 9, wherein said variable colour object is a spatially or parametrically defined blend of colour and/or opacity. 0*0 A method according to any one of claims I to 9, wherein said variable colour object is a spatially or parametrically defined procedural texture. ~13. A method acodin ng toca displayabei colouromin atelf-oerapin rionsf vaialecoou ojet h oacerdb h s of av comuivoprtrhamiea plraiy f oous nn n ore ndeedn anr por14.nAo ethod afovrdin tof aim 13heenatlasjncadtoouscmpie 27. FEB. 2002 18:18 SPRUSON FERGUSON 61 292615486 NO. 2788 P. 18/47 -19- 16. A commutative operator for mixing colours having opacity components, said operator being of the form: Z ,o veron 1= 1 0 n Soi In ovr0 o oeo n2 n n where over S oi El (l -o 1 i'=l j=i+1 and ci and 01 are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object. 17. A method of determining a displayable colour in a self-overlapping region of a variable colour object substantially as described herein with reference to any one of the embodiments with reference to Figs. 5 to 8 of the drawings. B B@. B. B B B. B S* S S B B. 0 0 18. A method of rendering a graphical object, said method comprising steps of: accumulating edge transitions of said object in a scan line by scan line fashion is using the non-zero winding fill rule to thereby determine a fill count for regions of the *.:object defined by the edge transitions; defining regions of said object having a fill count of at least 2 as self-overlapping regions; *so e0~ *determining an output value of a pixel in said self overlapping regions according to a rule; and determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self-overlapping region. 19. A method according to claim 18, wherein: said rule is one of, 27. FEB. 2002 18:18 SPRUSON FERGUSON 61 292615486 NO, 2788 P. 19/47 application of a respective colour avenage and a respective opacity average to colours and opacities from the self-overlapping regions; application of an opacity-weighted average to colours and opacities from the self-overlapping regions; and application of an opacity-weighted average with simulated over to colours and opacities from the self-overlapping regions. A method for rendering in a scan-line manner an arbitrary object having at least one overlapping region, said method comprising the steps of: 10 for each scan line of said object scan converting the object on said scan line determining the overlapping regions of said object within said scan line; initializing an overlap buffer for each said overlapping regions 16 for each portion of the object on said scan line (da) determining if said portion is an overlapping region :(daa) if so, accumulating the colour of pixels of said portion in the corresponding said overlap buffer; (dab) if not, outputting the colour of pixels of said portion; for each overlapping region, calculating an average colour from the corresponding accumulated value in said corresponding overlap buffer; and go (0 outputting the average colours. 21. A method according to claim 20 wherein said output buffer comprises a line buffer. 22. An apparatus for determining a displayable colour in a self-overlapping region of variable colour object, said apparatus comprising: 27, FEB. 2002 18:19 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 20/47 -21 colour determination means for determining, for each point in the region, the colour of each portion of the object present at that point; averaging means, responsive to said colour determination means, adapted to average, at each said point, the colours present at that point; and output means coupled to said averaging means for outputting said averaged colours for reproductions within said region. 23, An apparatus according to claim 22, wherein each said colour includes an opacity component, and wherein said colour determination means further comprise opacity determnination means, and wherein said averaging means ffirther comprises opacity weighting means responsive to said determined colours and corresponding opacities, and the average colour at each said point is calculated by weighting each colour by the corresponding opacity, and determining a resultant opacity. is 24. An apparatus according to claim 23, said opacity weighting means further comprising adding means, wherein the resultant opacity is determined *by adding individual opacities together. An apparatus according to claim 24, said adding means further comprising clamping means, wherein said added opacities are clamped to a predetermined level when a sum exceeds said predetermined level. 26. An apparatus according to claim 23, wherein said opacity weighting means is adapted to determine the resultant opacity by averaging the opacity of each said colour. 27. FEBD. 2002 18: 19 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 21/47 -22
2. 28. An apparatus according to any one of the preceding claim numbers 22 to 27, characterised by winding fill rule means adapted to use the winding fill rule method to determine said self-overlapping region.
3. 29. An apparatus according to claim 28, wherein the winding fill rule means is further adapted to determine said self;overlapping region on a scanline by scanline basis. An apparatus according to claim 29, wherein the winding fill rule means are further adapted to use an array of transition points to store those pixels on a scan line that lie within said self-overlapping region. 0:09 31. An apparatus for determining a displayable colour in a self-overlapping region of 060 0:0* a variable colour object characterised by comprising a commutative operator means 15 adapted to mix a plurality of colours in an order independent maimer. 32, An apparatus according to claim 3 1, wherein at least one of said colours comprises an opacity component, wherein said commutative operator means is adapted to perform an operation: 9 ZCjoj /n nZ~o *0e over Oj =ver oi n n *where over I 0i [7I (i-o) i iljr2 ji+1 and ci and oi are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object.
4. 33. A commutative operator means for mixing colours having opacity components, said operator means adapted to perform the operation: 27. FEB. 2002 18:19 SPRUSON FERGUSON 612 92615486 NO. 2788 22/47 -23 ,over 0j ,over o lol/n i lj n ni n where over o, S o1 I i=l i=l j=i+l and cj and Oj are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object.
5. 34. An apparatus for determining a displayable colour in a self-overlapping region of a variable colour object substantially as described herein with reference to any one of the embodiments as that embodiment is described in the accompanying drawings. An apparatus for rendering a graphical object, said apparatus comprising: means for accumulating edge transitions of said object in a scan line by scan line fashion using the non-zero winding fill rule to thereby determ-ine a fill count for regions of the object defined by the edge transitions;, means for defining regions of said object having a fill count of at least 2 as self- overlapping regions; means for determining an output value of a pixel in said self overlapping regions according to a rule; and means for determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self- overlapping region.
6. 36. An apparatus according to claim 35, wherein: said means for determining the output value of a pixel in said self overlapping regions comprises one of: means for applying a respective colour average and a respective opacity average to colours and opacities from the self-overlapping regions; 27. FEB. 2082 18:19 SPRUSON FERGUSON 61 292615486 NO. 2788 P. 23/47 24 0: 0 0 00 means for applying an opacity-weighted average to colours and opacities from the self-overlapping regions; and means for applying an opacity-weighted average with simulated over to colours and opacities from the self-overlapping regions.
7. 37. An apparatus for rendering in a scan-line manner an arbitrary object having at least one overlapping region, said apparatus comprising: for each scan line of said object scan conversion means for scan converting the object on said scan line overlapping region detection means for detemiining the overlapping regions of said object within said scan line; buffer initialization means for initializing an overlap buffer far each said overlapping regions Is overlapping region determination means, operative in respect of each portion of the object on said scan line (da) for determining if said portion is an overlapping region (daa) and, if said portion is an overlapping region, adapted to accumulate the colour of pixels of said portion in the corresponding said overlap buffer; (dab) and, if said portion is not an overlapping region, adapted to output the colour of pixels of said portion; calculation means, operative in respect of each overlapping region, to calculate an average colour from the corresponding accumulated value in said corresponding overlap buffer; (0 outputting means for outputting the average colours.
8. 38. An apparatus according to claim 37 wherein said output buffer comprises a line Sbuffer. e5 S S. 00 on. 0 See. 0 0* e 6* S. C 00 0 eee 5* 0 00 00 27. FEB. 2002 18:20 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 24/47
9. 39. A computer program product including a computer readable medium incorporating a series of instructions configured to determine a displayable colour in a self-overlapping region of a variable colour object, said instructions comprising: s determination steps for determining, for each point in the region, the colour of each portion of the object present at that point; averaging steps for, at each said point, averaging the colours present at that point; and outputting steps for outputting said avenaged colours for reproduction within said i~e a region. A computer program product according to claim 39, wherein each said colour includes an opacity component, and wherein said colour determination steps fur-ther comprise opacity determnination steps, and wherein said averaging steps further comprise .15 opacity weighting steps responsive to said determined colours and corresponding opacities, and the average colour at each said point is calculated by weighting each colour by the corresponding opacity, and determining a resultant opacity. *41. A computer programn product according to claim 40, said opacity weighting steps e~20 further comprising adding steps, wherein the resultant opacity is determined by adding individual opacities together. 0 42. A computer program product according to claim 41, said adding steps further comprising clamping steps, wherein said added opacities are clamped to a predeternme level when a sum exceeds said predetermined level.
10. 43. A computer program product according to claim 40, wherein said opacity weighting steps are adapted to determine the resultant opacity by evaluating the "over"~ of Expression as herein defined. 27, FEB. 2002 18:20 SPRUSON FERGUSON 61 2 92615486 NO, 2788 P. 25/47 26
11. 44. A computer program product according to claim 40, wherein said opacity weighting steps are adapted to determine the resultant opacity by averaging the opacity of each said colour. A computer program product according to any one of claims 39 to 44, characterised by winding fill rule steps adapted to use the winding fill rule method to determine said self-overlapping region. '"1o 46. A computer program product according to claim 45, wherein the winding fill rule "steps are further adapted to determine said self-overlapping region on a scanline by scanline basis.
12. 47. A computer programa product according to claim 46, wherein the winding fill rule 5i steps are further adapted to use an array of transition points to store those pixels on a scan line that lie within said self-overlapping region.
13. 48. A computer program product for determining a displayable colour in a self- 0 overlapping region of a variable colour object characterised by comprising commutative @20 operator steps adapted to mix a plurality of colours in an order independent manner. 0 0 47. A computer program product according to claim 46, wherein tewinding fl rule colours comprises an opacity component, wherein said commutative operator steps are 0 0 S 1 daste ar t err aate oeana-a ftasto onstosoetoepxlnasa l t l is overing i o over O *0 U.4. Acmue rga routfrdtriigadspaal oori ef 0- 27. FEB. 2002 18:20 SPRUSON FERGUSON 61 2 92615486 NO. 2788 P. 26/47 27 n n n where over Z o, n i=l i=l ]=i41 and c i and o i are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object.
14. 50. A computer program product comprising commutative operator steps for mixing colours having opacity components, said operator steps adapted to perform the operation: over 0i OV 0ii Zoi/ n '1=1 Zoi i-1 O•n. Sn n where over Z o, TT (1-oi), i=1 ]=i+l 10 and c i and o i are the colour and opacity respectively at one pixel location within one portion of the self-overlap of said object.
15. 51. A computer program product for determining a displayable colour in a self- overlapping region of a variable colour object substantially as described herein with 15 reference to any one of the embodiments as that embodiment is described in the •e accompanying drawings. S 52. A computer program product including a computer readable medium having recorded thereon a computer program for directing a computer to render a graphical object, said program comprising: code for accumulating edge transitions of said object in a scan line by scan line fashion using the non-zero winding fill rule to thereby determine a fill count for regions of the object defined by the edge transitions; code for defining regions of said object having a fill count of at least 2 as self- overlapping regions; 27. FEB. 2002 18:20 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 27/47 28 code for determining an output value of a pixel in said self overlapping regions according to a rule; and code for determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self-overlapping region.
16. 53. A computer program product according to claim 52, wherein: said code for determining the output value of a pixel in said self overlapping regions comprises one of: code for applying a respective colour average and a respective opacity lo average to colours and opacities from the self-overlapping regions; code for applying an opacity-weighted average to colours and opacities from the self-overlapping regions; and code for applying an opacity-weighted average with simulated over to *040 colours and opacities from the self-overlapping regions, 0 0 a
17. 54. A computer program for directing a computer to render a graphical object, said *program comprising: code for accumulating edge transitions of said object in a scan line by scan line fashion using the non-zero winding fill rule to thereby determine a fill count for regions of the object defined by the edge transitions; code for defining regions of said object having a fill count of at least 2 as self- overlapping regions; code for determining an output value of a pixel in said self overlapping regions according to a rule; and code for determining an output value of a pixel in a non self-overlapping region according to the colour and opacity of said pixel in the non self-overlapping region. A computer program according to claim 54, wherein: K~tNT26 27. FEB. 2002 18:20 SPRUSON FERGUSON 612 92615486 NO. 2788 P. 28/47 29- said code for determining the output value of a pixel in said self overlapping regions comprises one of: code for applying a respective colour average and a respective opacity avenage to colours and opacities from the self-overlapping regions; code for applying an opacity-weighted avenage to colours and opacities from the self-overlapping regions; and code for applying an opacity-weighted average with simulated over to colours and opacities from the self-overlapping regions. 1 56. A computer program product for rendering in a scan-line manner an arbitrary object having at least one overlapping region, said programn comprising: so, for each scan line of said object scan conversion steps for scan converting the object on said scan line overlapping region detection steps for determining the overlapping 00 s1 regions of said objectvwithin said scan line; buffer initialization steps for initializing a overlap buffer for each said overlapping regions a* overlapping region determination steps, operative in respect of each 00000 portion of the object on said scan line 20 (ca) for determining if said portion is an overlapping region 0 0so(daa) and, if said portion is an overlapping region, adapted to accumulate the colour of pixels of said portion in the corresponding said overlap buffer; (dab) and, if said portion is not an overlapping region, 2a adapted to output the colour of pixels of said portion; calculation steps, operative in respect of each overlapping region, to calculate an average colour from the corresponding accumnulated value in said corresponding overlap buffer; outputting steps for outputting the average colours. C::D 6'29 27. FEB. 2002 18:21 SPRUSON FERGUSON 61 292615486 NO, 2788 P. 29/47 30
18. 57. A method of rendering, in a scanline manner, a variable colour object having portions thereof forming at least one self-overlapping region, said method comprising, for a scanline that intersects said object, the steps of: determining, for at least a first point along the scanline in said self-overlapping region, a colour of each portion of the object at said first point; averaging said colour of each said portion of the object at said first point to form a resultant colour at the first point; and outputting said resultant colour for the first point.
19. 58. A method according to claim 57, comprising further steps of: 0000determining, for at least a second point along the scanline in a non self- overlapping region, a colour of the object at said second point; and outputting said colour of the object at said second point. 900 gee* 59. A method according to claim 59, wherein teachesuadcluricdsa opacity i eenndb *0 0 A copo entadthe aveoraigt clurmateachwaidrint dadoaisalte byreightingeaho coou by. Ath d coresoding oai and determinin ah resultant opacity.i eemndb A method according to claim 59, wherein the resultant opacity is determined by o 20 eadding ndividalit oacsai ogethr 27. FEB. 2002 18:21 SPRUSON FERGUSON 61 2 92615486 NO, 2788 P, 30/47 -31
20. 64. A method according to any one of claims 59 to 63, characterised by using the winding fill rule method to determine said self-overlapping region. A method according to claim 64, wherein the winding fill rule method determines said self-overlapping region on a scanline by scanline basis.
21. 66. A method according to claim 65, wherein an array of transition points is used to store those pixels on a scan line that lie within said self-overlapping region. 10 67. A method according to any one of claims 59 to 66, wherein said variable colour se00 object is a distorted and/or tiled and/or textured mapped pixel-based image. 0 0000 0 0000 S 68. A method according to any one of claims 59 to 66, wherein said variable colour 0 object is a spatially or parametrically defined blend of colour and/or opacity. DATED this 2 7 t h Day of February, 2002 Canon Kabushiki Kaisha Patent Attorneys for the Applicant •SPRUSON FERGUSON 0 *0oo 0 O0 00 00* 0 0 *0