Generating one or more linear blends

A method (1005) generates one or more linear blends. Initially, the method has a list of already received one or more fill-paths defining a current linear blend, and a newly received fill-path, where the fill-paths each comprise a single colored parallelogram (eg. 700). The method adds (1090) the new fill-path to the list to become the last fill-path in the list, if the difference (1230) in color between the new fill-path and the last fill-path in the list is no greater, in each color channel, than a predetermined threshold value multiplied by the difference in color between the last and second-last fill-paths in the list. The predetermined threshold value is preset to such a value so that the new fill-path will not be added to the list if the new fill-path does not visually form part of the current linear blend. The method repeats this step for each new fill-path received until the aforementioned condition is not satisfied. Then, the method generates (1040) one or more linear blends from the first fill-path in the list to the last fill-path in the list.

FIELD OF THE INVENTION

The present invention relates to electronic image generation and control and, in particular, relates to generating one or more linear blends.

BACKGROUND

Traditionally, software applications such as word processors, create page-based documents where each page contains graphic objects such as text, lines, fill regions and image data. When representing the document data on a display device or a printing device, such software applications typically send commands defined in terms of the graphics interface services of a native operating system within which the software application operates. The graphics interface services of the native operating system are typically known as the graphics device interface (GDI) layer. The GDI layer is generally an application programming interface (API) providing a rich set of graphics features to all applications. Typically, a graphics rendering system renders the graphics objects received from the GDI layer, generating pixels, which are then sent to the output device. Rendering is the process by which the graphics objects received from the GDI layer are converted to pixels by the graphics rendering system, which are then sent to the output device for storage, display, or printing.

Turning toFIG. 1there is shown a traditional relationship between a prior art software application110, a graphics device interface layer120, a graphics rendering system130, and an output device140. The application110passes each page of a document as a series of commands defined in terms of the graphic interfaces services which describe the graphic objects of the page. The GDI layer120mediates between the application program110and the output device140, such that the GDI layer120enables the graphics rendering system130to support a much smaller set of functionality, such as drawing rectangular blocks of image data, and filling simple regions with flat color. The GDI layer120also provides graphics objects to the graphics rendering system130in a format that the GDI layer120determines that the rendering system130would process most efficiently, and at a resolution of the output device140. The graphics rendering system130then renders the graphics objects received from the GDI layer120, generating pixels, which are then sent to the output device140.

In some known graphic rendering systems, rendering is a two-stage process. In these rendering systems, graphics objects are first converted into an intermediate language before the rendering process begins. In one such system, the first stage of the process converts each graphic object received from the GDI layer into some intermediate edge-based object graphics format, such that all edges are sorted in ascending y, then ascending x, these corresponding respectively to the scan lines and pixel locations on such scan lines in a rasterized display. The output from this stage is typically a display list of edges and their associated fill priority (z-order), along with other information such as if this edge is a clipping edge or a filling edge. This is sometimes called a job. The job contains all the information needed by the second stage to render the page. The second stage of the process involves a rendering module parsing the job and generating the pixels for the output device for each scanline down the page.

In some GDI layers, a graphics object filled with a smooth blend of color is represented by the GDI layer as a series of adjacent single-colored parallelograms, each differing in color by some small offset from the previous, and which is clipped over the area of the graphics object. The parallelograms may proceed left to right, top to bottom or diagonally across the page.

Some applications refer to this type of fill as a gradient fill (Microsoft Word) or a fountain fill (Corel Draw). For sake of clarity, this type of fill is referred for the purposes of this description as a gradient fill. An example of a graphic object210filled with a diagonal gradient fill as produced by a typical prior art application is shown inFIG. 2A. The method of filling an object with a gradient fill is dependent on the application. However, in its simplest form, such a method typically consists of specifying a start color and an end color at each end of a bounding box of the graphic object being filled.FIGS. 2A,2B,2C illustrate how a diagonal gradient fill is typically passed by the application to the GDI layer to the graphics rendering system.

Some graphics rendering systems typically support a simple form of the gradient fill effect called a linear ramp or a linear blend. This can be represented by a starting reference point on the page, with an associated starting color, accompanied by a constant gradient change per color channel per pixel, on a line parallel to the gradient of the blend.

However, applications are generally not restricted to outputting a blend comprising a purely linear gradient fill effect. In fact, color changes in gradient fill effects produced by some applications can be parabolic or even sinusoidal. An example of an object300having a sinusoidal gradient fill produced by a prior art application is shown inFIG. 3.

Typically, the GDI layer reduces the gradient fill to a set of single-colored parallelograms, referred to here as fill-paths, with an accompanying clipping object. For example,FIG. 2B, shows the fill-paths and clipping object passed to the graphics rendering system by a typical prior art GDI layer, which were produced from the example gradient fill as shown inFIG. 2A. The GDI layer reduces the gradient fill to a set of single colored fill-paths250and a clip object220. For sake of clarity,FIG. 2Bshows only two exaggerated fill-paths250. The entire set of the fill-paths230covers a rectangular area260, with each fill-path250parallel to and adjoining its adjacent fill-path(s). The length of the sides of these fill-paths250depends on the resolution at which rendering occurs. For example, at 600 dpi, each fill-path250is typically no greater than 100 pixels high, but each can vary in width by several pixels. Also, each fill-path250has a slightly different interior color from the previous fill-path250. This produces a smooth blend of colors associated with the gradient fill when the object is rendered. Turning now toFIG. 2C, there is shown the result of the rendering of the example shown inFIG. 2Bby a typical prior art graphics rendering system. In the latter case, the rendering system has clipped the bounding box260comprising the fill-paths250with the clipping object220resulting in the object210. InFIG. 2C, the result after rendering is the same asFIG. 2A.

There are a number of conventional methods for rendering such a representation of a gradient fill effect.

One conventional method is to simply render each fill-path. Many graphics rendering systems use a Painters algorithm style of rendering where each object is drawn onto a frame buffer as it arrives. A 2-stage object-graphics rendering system that firstly converts all incoming objects into some intermediate format for the page, and then renders each scanline, is at a disadvantage in rendering each fill-path. For the gradient fill shown inFIG. 2A, the GDI layer generates 128 fill-paths at 600 dpi. It can be seen that in the case of the blend proceeding top to bottom or bottom to top, then on any scanline, only one fill-path is active. But in the worst case of the blend proceeding left to right or right to left, all 128 fill-paths are active on a scanline, equating to 256 edges per scanline. Hence for an object-based rendering system, such a method of rendering is considerably inefficient. Also, each flat fill must be stored in the intermediate object-graphics format, and accessed for each fill-path for each scanline. This method consists of large amounts of memory accesses and can also consume large amounts of fill resources when the number of fill-paths is in the order of thousands. This occurs frequently when printing to pages larger than A3at high-resolutions.

On an aesthetic level, another disadvantage of simply rendering each fill-path is that although the intended effect is clearly a smooth blend, an artifact called Mach Banding can occur. Since the eye is more sensitive to edges than it is to smooth changes in color, the eye can often see the division of rectangles when a gradient fill effect is rendered this way. The divisions become even clearer at some parts of the color gamut. Also, if the entire image is enlarged, then each fill-path is also enlarged and Mach Banding becomes highly visible.

At the application-level, another conventional method for dealing with gradient fill effects is to simply render the fill effect onto a bitmap and send this to the GDI layer. This method is effective for small fill regions, but has the disadvantage of being slower to draw and cumbersome to render since every pixel of an image has to be dealt with by the graphic rendering system. This method also does not scale well when the object is enlarged (duplication of pixels) or reduced (loss of pixels).

Another conventional method is to test each incoming fill-path for linearity and when the next fill-path is no longer linear within some error, then to create an equivalent linear blend up to this fill-path. Tracking for linearity then starts again from this next fill-path. This method can dramatically reduce the number of graphic objects needing to be rendered. In the best case scenario the entire graphic object can be described by a single linear blend. For the diagonal gradient fill as shown inFIG. 2A, this would represent a 1/128threduction of the number of edges per scanline than if this were drawn with multiple fill-paths.

However, this method has its disadvantages. As described above, an application may provide gradient fill effects more advanced than a simple linear blend. Such effects may consist of several color changes throughout the object being filled (eg. sinusoidal as inFIG. 3), or they may follow some non-linear curve as inFIGS. 4Aor4B. Similarly, the lengths of the sides of consecutive fill-paths are not necessarily constant. In either case, the resulting set of fill-paths describing the object does not necessarily consist of a constant change in color for each fill-path even though the desired overall effect in each case is a smooth blend of color across the graphic object.

In this method an error factor is applied to determine the linearity of the next fill-path in a series of fill-paths. If the next fill-path is different to the previous fill-path by a constant difference plus or minus some error, then it is merged into the linear blend being tracked. If this error factor is too small, then it results in many linear blends, defeating the purpose of this method. If this error factor is too large, then it results in color shifting such that the output would not correctly represent the input. For example, turning toFIG. 4Athere is shown a non-linear blend varying from black in the top-left corner to white in the bottom right corner, where the midpoint color between black and white is located at 25% of the distance between the top-left and bottom right corners. Also,FIG. 4Bshows a similar non-linear blend, but where the midpoint color is located at 75% of the distance between the top-left and bottom right corners. If the non-linear fill-paths shown inFIGS. 4Aor4B were tracked using a large enough such error factor, then the result would be a pure linear blend from black in the top-left corner to white in the bottom-right corner as shownFIG. 4C. The result is clearly not what the user of the application intended.

Also, when the fill-paths are combined into multiple linear blends, then Mach Banding tends to become noticeable between adjacent linear blends. This banding is highly visible because the linear blends are split at their greatest error, delineating the adjacent linear blends more markedly than if individual fill-paths were rendered.

SUMMARY

According to a first aspect of the present disclosure, there is provided a method of generating one or more linear blends, wherein the method initially comprises a list of already received one or more fill-paths defining a current linear blend, and a newly received fill-path, where the fill-paths each comprise a single colored parallelogram, the method comprising the steps of: (a) adding the new fill-path to the list to become the last fill-path in the list, if a number of conditions are met, otherwise proceeding to step (c), wherein one of the number of conditions is based on the color of the new fill-path and the last fill-path and a threshold value, and the threshold value is preset to such a value so that the new fill-path will not be added to the list if the new fill-path does not visually form part of the current linear blend; (b) repeating step (a) for each new fill-path received; and (c) generating one or more linear blends from the first fill-path in the list to the last fill-path in the list.

According to a second aspect of the present disclosure, there is provided a method of generating one or more linear blends from a list of one or more fill-paths defining a current linear blend, and at least one new fill-path, where the fill-paths each comprise a single colored parallelogram, the method comprising the steps of:

(a) adding one said new fill-path to said list to become a last fill-path in said list, if each condition of a set thereof is met, otherwise proceeding to step (c), said set comprising at least one condition, said one condition being based on the color of the new fill-path and the last fill-path and a threshold value, and said threshold value is preset to such a value so that the new fill-path will not be added to the list if the new fill-path does not visually form part of the current linear blend;

(b) repeating said step (a) for each remaining said new fill-path; and

(c) generating one or more linear blends from the first fill-path in said list to the last fill-path in said list.

Preferably, the set of conditions further comprises conditions selected from the group consisting of:

a (second) condition that the new fill-path is physically contiguous with the last fill-path in the list;

a (third) condition that a height of the new fill-path is no greater than two times a height of the most recently added fill-path in the list, the height being measured in a direction determined by physical positions of the fill-paths of the list;

a (fourth) condition that the number of fill-paths in the current linear blend is greater than 1;

a (fifth) condition that a sum of the accumulated height of the fill-paths in the linear blend and a rectangle-height of the new fill-path is less than a predefined maximum;

a (sixth) condition that a raster operation for the currently received fill-path does not use a destination, and is the same as a raster operation for the current linear blend; and

a (seventh) condition that the currently received fill-path has the same clip as the current linear blend.

Other aspects of the invention, including apparatus, computer programs and computer media arranged to perform the methods, are also disclosed.

DETAILED DESCRIPTION INCLUDING BEST MODE

A method for generating linear blends is preferably implemented as a software module for running on a processor of a general-purpose computer. A typical general-purpose computer for executing such a software module is described below with reference toFIG. 17. The software module is preferably a part of a first stage of a graphics rendering system that interfaces to a graphics device interface (GDI) layer and receives graphics objects for a page, converting each graphics object to an intermediate edge-based format. In the second stage of the graphics rendering system, the job is rendered and the resulting pixels are output to a downstream device, such as a printer or graphics card. Preferably, both stages of the graphics rendering system are implemented as modules in a graphics software application. Alternatively, the first stage is implemented as a software application, which interfaces with the second stage, which is implemented as a hardware device coupled to a bus for communicating with the first stage operating on the processor.

The GDI layer is preferably an application-programming interface (API) and provides the graphics rendering system with a gradient fill as a series of fill-paths.

Although the following method describes the case of a non-orthogonal gradient fill effect, and specifically where the fill-paths arrive in the order top-left to bottom-right with vertical sides, it can be easily modified to handle the cases where the fill-paths proceed in any orthogonal or non-orthogonal direction.

Before proceeding with the detailed description, a brief review of terminology is discussed.

A fill-path is defined as a single-colored (or flat-colored) parallelogram. The term parallelogram is also taken to include a rectangle or a square. Where a gradient fill proceeds exactly horizontally or vertically, the fill-path is generally rectangular in shape. For gradient fills proceeding diagonally across the page, the fill-path is a parallelogram.

The direction in which a non-orthogonal gradient fill travels can be any one of 8 directions. These directions are partitioned into gradient fills that use horizontal fill-paths and gradient fills that use vertical fill-paths and are defined as follows:Horizontal Gradient Fills:Horizontal Down Left, HDOWNLEFT.Horizontal Up Left, HUPLEFT.Horizontal Down Right, HDOWNRIGHT.Horizontal Up Right, HUPRIGHT.Horizontal Left, LEFTHorizontal Right, RIGHTVertical Gradient FillsVertical Down Left, VDOWNLEFT.Vertical Up Left, VUPLEFT.Vertical Down Right, VDOWNRIGHT.Vertical Up Right, VUPRIGHT.Vertical Down, DOWNVertical Up, UP

FIGS. 5A to 5Dand6A to6D illustrate the aforementioned definitions of the direction in which a diagonal gradient fill may travel.FIGS. 5A to 5Dillustrate vertical gradient fills whereasFIGS. 6A to 6Dillustrate horizontal gradient fills

FIG. 5Ashows a clipping object600, which is in the form of a banner, and its bounding box620, and fill-paths610. A number of fill-paths610proceed in a vertical direction from the top left corner towards the bottom right corner of the bounding box620, and are defined as Vertical Down Right. Also shown are vertical fill-paths630, and are defined as Down.

FIG. 5Bshows the same clipping object600and bounding box620, and fill-paths640. The fill-paths640proceed in a vertical direction from the top right corner towards the bottom left corner of the bounding box620, and are defined as Vertical Down Left. Also shown are vertical fill-paths630, and are defined as Down.

FIG. 5Cshows the same clipping object600and bounding box620. The fill-paths660proceed in a vertical direction from the bottom right corner towards to the top left corner of the bounding box620, and are defined as Vertical Up Left. Also shown are vertical fill-paths650, and are defined as Up.

FIG. 5Dshows the same clipping object600and bounding box620. The fill-paths670proceed in a vertical direction from the bottom left corner towards to the top right corner of the bounding box620, and are defined as Vertical Up Right. Also shown are vertical fill-paths650, and are defined as Up.

FIG. 6Ashows the clipping object600, and its bounding box605, and fill-paths625. The fill-paths625proceed in a horizontal direction from the top left corner towards the bottom right corner of the bounding box620, and are defined as Horizontal Down Right. Also shown are horizontal fill-paths615, and are defined as Right.

On the other hand, the fill-paths635ofFIG. 6Bproceed in a horizontal direction from the bottom left to the top right of the bounding box and are defined as Horizontal Up Right. Again the horizontal fill-paths615, and are defined as Right.

FIG. 6Cshows the clipping object600, and its bounding box605, and fill-paths655. The fill-paths655proceed in a horizontal direction from the bottom right corner towards the top left corner of the bounding box605, and are defined as Horizontal Up Left. Also shown are horizontal fill-paths645, and are defined as Left.

On the other hand, the fill-paths665ofFIG. 6Dproceed in a horizontal direction from the top right to the bottom left of the bounding box and are defined as Horizontal Down Left. Again, the horizontal fill-paths645, and are defined as Left.

However, if a fill-path is deemed not aligned with an adjacent fill-path then no (ie. a NULL) direction is assigned. Having no direction means that a gradient fill will not be created, or the new fill-path will not be accepted as part of the current fill.

There are two different types of height that are referred to in the present description, those being rectangle-height and total-height. Depending on how the currently stored gradient fill is oriented the heights are defined differently.FIGS. 7A and 7Billustrate the definitions of these different heights and how they differ depending on the orientation of a gradient fill.FIG. 7Ashows fill-paths700in the form of parallelograms proceeding in a vertical direction and a bounding box705of a clipping object (not shown). In the case of vertical fill-paths (eg.FIG. 7A), the rectangle-height of a fill-path is defined as the length of the side of the parallelogram constituting the fill-path, in the y co-ordinate direction. In the case of vertical fill-paths (eg.FIG. 7A), the total-height at an n-th fill-path is defined as the sum of the rectangle-heights of the n-th fill-paths in the y co-ordinate direction. In the case of horizontal fill-paths (eg.7B), a similar definition applies, however the lengths are measured in the x co-ordinate direction. Also, as will become apparent, the rectangle-height may differ from fill-path to fill-path.

When defining a linear gradient fill from individual fill-paths, the intermediate edge format accepts the color values and positions of two reference points on a line parallel to the gradient of the blend to define the gradient fill.FIGS. 8A and 8Bshows the equations used to find the second reference point (Q,P), which is used in defining the gradient fill. The first reference point (“fill-path point1” as illustrated) is already known.FIG. 8Adepicts the vertical angles associated with collected fill-paths inclined at an angle (θ) and which transverse length (X). The angle (θ) is determined from:

θ=arctan⁡(YX)
where X and Y are coordinates along the fill-path. Where the height (Height) of the fill-path is known, a width (Z) of the fill-path maybe calculated from:
Z=Height.cos(θ).
The width (Z) establishes a point (P, Q) on a fill-path where the distances from the fill-path point1can be determined as:
P=Z.cos(θ)
Q=Z.sin(θ)
By substitution, these distances can be determined in terms of the angle (θ):

Similarly, for the horizontal angles shown inFIG. 8B. the following equations also may be derived:

FIG. 22shows the two reference points, Point1and Point2(Q, P) and the lines used in the calculation of the two reference points for an alternate method. The first point, Point1, is simply the first point described in the direction of the fill. The second point, (Q, P) is determined from the intersection of line B and line C. Line C is the line that runs coincidently over the length of the far end of the last fill-path in the gradient fill. Line B is the line 90 degrees to line A that runs through point1of the gradient fill.

The direction in which a gradient fill travels can be described by any one of four directions. These directions are named after the alignment of the points that make up the fill-paths within a gradient fill. The four directions are defined as follows:DIR_01(or DIR_32)DIR_10(or DIR_23)DIR_12(or DIR_03)DIR_21(or DIR_30)

FIGS. 23A to 23Drespectively illustrate the aforementioned definitions of the direction in which a diagonal gradient fill may travel. Each direction has an alternative name, that can be used interchangeably. If a fill-path is deemed not aligned with an adjacent fill-path then no (ie. a NULL) direction is assigned. Having no direction means that gradient fill will not be created, or the new fill-path will not be accepted as part of the current gradient fill.

There are two different types of height that are referred to in the description, rectangle-height (or the height of a fill-path) and total-height. The total-height is defined as the sum of the individual rectangle heights of each of the fill-paths in the currently stored list of fill-paths. The side of the fill-path that defines the rectangle-height of a gradient fill is dependent on which direction the gradient fill is travelling.FIGS. 23A to 23Dshow that for a direction of DIR_01the rectangle-height is defined as the length of the line between point0and point1of a fill-path. For a direction of DIR_10the rectangle-height is defined as the length of the line between point1and point0. For a direction of DIR_12the rectangle-height is defined as the length of the line between point1and point2. For a direction of DIR_21, the rectangle-height is defined as the length of the line between point2and point1. Also, it will become apparent that the fill-path heights may differ from fill-path to fill-path. The widths of each of the fill-paths is also shown inFIGS. 23A to 23D.

The term “stored color gradient” is defined as the color gradient between the most recently added fill-path and the second most recently added fill-path in the currently stored gradient fill. The value of this color gradient is stored so that any new fill-paths can be checked to ensure that its color gradient is within a reasonable limit of the stored color gradient.

The currently stored gradient fill is a dynamic list of fill-paths. For each of the fill-paths added to the currently stored gradient fill, 3 arrays are defined by the method as follows:1. A color array holds the values of each color of the fill-path, where color[n]=the color of fill-path(n);2. A heights array holds the values of the accumulated heights of the fill-paths, where heights[n]=the sum of the values of rectangle-heights of fill-paths(1) to fill-paths(n). This is also the current value of total-height at fill-path(n); and3. A points array holds the values of the points of the individual fill-paths, where points[n]=the 4 points in x,y co-ordinates of the parallelogram defining the boundary of fill-path(n).

The phrase “stored gradient fill” refers to the variables necessary for describing the gradient fill currently being tracked. This includes the aforementioned color array, point array and heights array, the number of fills in the gradient fill, the direction of the gradient fill, and the color gradient between the first two colors in the gradient fill.

The method receives in turn the fill-paths from the GDI layer and adds those paths to the currently stored gradient fill depending upon certain criteria being met. Initially, the method checks whether the difference in color between a newly received fill-path and the fill-path that was most recently added to the currently stored gradient fill is greater than a reasonably large error factor. Preferably, this error factor is 2 times the difference in color between the 2 most recently added fill-paths of the currently stored gradient fill. Specifically, the method checks, for each color channel (e.g. RGB) of the image being generated, whether a color channel value Cnof the newly received fill-path satisfies one of the following formulae:
0<Cn−Cn−1≦2(Cn−1−Cn−2) if Cn>Cn−1
−2(Cn−1−Cn−2)≦Cn−Cn−1≦0 ifCn≦Cn−1Equation (1)where Cn−1and Cn−2are the corresponding color channel values of the 2 most recently added fill-paths of the currently stored gradient fill.

If the check returns true for each color channel, the method adds the newly received fill-path to the currently stored gradient fill and repeats these operations for the next received fill-path. Otherwise, if the check returns false for any one of the color channels, then the method undertakes to generate one or more linear blends from the color and position of the first fill-path of the currently stored gradient fill to the color and position of the most recently added fill-path of the currently stored gradient fill. In other words, the method continues adding fill-paths to the currently stored gradient fill until a fill-path is reached that no longer satisfies the aforementioned criteria. This occurs when one of the color channels for the next fill-path causes a significant change in direction for the current color channel's gradient. For example, this will occur when the direction of the color gradient changes sign.

As mentioned previously, if the check returns false, the method undertakes to generate one or more linear blends from the fill-paths already added to the currently stored gradient fill Specifically, the method determines an optimal set of linear blends fitting the set of fill-paths in the currently stored gradient fill. The method achieves this in the following manner.

Firstly, for the purposes of explanation, it is assumed that the currently stored gradient fill contains n fill-paths denoted as fill-path[1] through to fill-path[n], where fill-path[1] is the first fill-path added to the currently stored gradient fill and fill-path[n] is the last fill-path added to the currently stored gradient fill.

The method generates the set of linear blends fitting the fill-paths of currently stored gradient fill by first testing whether the color gradients between fill-path[1] and fill-path[n] are not equal to the corresponding color gradients between fill-path[1] and mid-point fill-path[n/2] (within some acceptable error). If the test returns true, that is, if it is not equal, then the method then partitions the set of fill-paths into 2 sets, one for the first half of the fill-paths (fill-path[1] . . . fill-path[n/2]) and one for the second half of the fill-paths (fill-path[n/2] . . . fill-path[n]) and repeats the test for each of these new sets of fill-paths. On the other hand, if the test returns false, that is the color gradients between fill-path[1] and fill-path[n] are equal (within some acceptable error) to the corresponding color gradients between fill-path[1] and fill-path[n/2] for some set of fill-paths[1. . . n], then the method outputs a linear ramp call to the graphics rendering system for this set of fill-paths[1. . . n], using the colors array to define the start and end colors of the linear ramp, and the points array to define the area to be filled. This step can be implemented as a software module, which can-be defined recursively as:

Hn, Hn/2are the values of the accumulated rectangle-heights of fillpaths1to n and1to n/2 respectively,

Cnis the value of the color channel of the n-th fill-path,

E0is a threshold constant, preferably 0.1, and

As can be seen, the method when partitioning the set of fill-paths, preferably uses the fill-path at the midpoint as both the end point of the first ramp and the start point of the second ramp. This ensures a smooth blend between adjacent linear ramps and eliminates Mach Banding when compared to previous implementations. Alternatively, traditional partitioning based upon (n/2) and (n/2)+1 may be used.

Turning now toFIGS. 9A to 9C, there is shown the values of a color channel of an exemplary set of fill-paths added to the currently stored gradient fill for the purposes of illustrating the method of generating one or more linear blends.FIGS. 9A to 9Cillustrate the color values in the y co-ordinate direction of the fill-paths1to11, which are depicted in the x co-ordinate direction. The symbol C represents the value of the color channel of a fill-path, whereas the symbol H represents the value of the accumulated height, e.g total-height, of all the stored fillpaths. For simplicity, there is assumed to be only one color channel. As will be apparent, the fill-paths1. . .10are added to the currently stored gradient fill in turn, until the fill-path11is received from the GDI layer. As can be seen this fill-path11fails the criteria set out in Equation (1), and is not added to the currently stored gradient fill. The method then generates one or more linear blends from the fill-paths1. . .10already stored in the currently stored gradient fill in the following manner.

The preferred method compares the color gradient between fill-paths1. . .10with the color gradient between fill-paths1. . .5in accordance with Equation (2). This comparison also ensures that n is not below a predefined value. For the sake of simplicity this is ignored in this example. This comparision is illustrated inFIG. 9A. The output of this comparision is in this case greater than the threshold constant E0=0.1, so the method divides the set of fill-paths[1. . .10] into 2 sets: fill-paths[1. . .5] and fill-paths[5. . .10].

The method then compares the color gradient between fill-paths1. . .5with the color gradient between fill-paths1to3in accordance with Equation (2). Note, where n is odd, the value n/2 is incremented to the next nearest highest integer, which in this case is three (3). This comparision is illustrated inFIG. 9B. The output of this comparison is in this case less than the threshold constant E0=0.1, so a linear blend is output for fill-paths1to5.

The method then compares the color gradient between fill-paths5to10with the color gradient between fill-paths5to7, in accordance with Equation (2). Note, in this particular case the first fill-path in the set is fill-path5and the gradients are measured from this fill-path. This comparision is illustrated inFIG. 9C. The output of this comparison is in this case greater than the threshold constant E0=0.1, so the method divides the set of fill-paths[5. . .10] into 2 sets: fill-paths[5. . .7] and fill-paths[7. . .10].

The method then compares the color gradient between fill-paths5to7with the color gradient between fill-paths5to6in accordance with Equation (2). This comparision is illustrated inFIG. 9C. The output of this comparison is in this case less than the threshold constant E0=0.1, so a linear blend is output for5to7. In a similar fashion, the method determines the color gradient between fill-paths7and8is similar to the color gradient between fill-paths7and10, so a linear blend is output for fill-paths7and10. The method then terminates.

As can be seen, the method breaks the whole stored gradient fill into pieces depending on the linearity of the overall gradient fill and not simply those portions that have been processed to date. This ensures that the entire gradient fill is considered when determining the optimal set of linear blends, thus ensuring the best possible match is made to the original gradient fill with the least number of linear ramps. This method identifies the larger constant slopes within a gradient fill and outputs them accordingly. In this way, the method enables the reduction of the number of graphic objects needed to be rendered. Furthermore, Mach Banding is avoided by setting the midpoint of the partitioning as both the endpoint of the first ramp and the start point of the second ramp.

As mentioned previously, the method receives in-turn the fill-paths from the GDI layer and adds these to the currently stored gradient fill depending on whether the newly recieved fill-path meets the criteria as set out in Equation (1). In the case where this criteria is not met, the newly received fill-path is not stored in the currently stored gradient fill and the method then processes the already existing fill-paths in the currently stored gradient fill to produce one or more linear blends. Preferably, the newly received fill-path should also meet a number of other criteria in addition to the criteria specified in Equation(1) before it is added to the currently stored gradient fill. For example, the rectangle-height of the newly received fill-path should be less than or equal to two times the rectangle-height of the first fill-path in the currently stored gradient fill in order for the newly received fill-path to be added to the currently stored gradient fill. Otherwise, if the newly received fill-path is added to the currently stored gradient fill, then discontinuities in the blend will become apparent to the eye. Further criteria will be described below in more detail.

3.0 First Method

Turning now toFIG. 10, there is shown a flow chart of a method1005of generating one or more linear blends. As mentioned previously, the method1005is implemented as a software module for execution on a processor of a general-purpose computer. Such a general-purpose computer suitable for implementing the preferred method is described below with reference toFIG. 17. The software module is preferably a part of a first stage of a graphics rendering system that interfaces to a graphics device interface (GDI) layer and receives graphics objects for a page, converting each graphics object to an intermediate edge-based format. In the second stage of the graphics rendering system, the job is rendered and the resulting pixels are output to a downstream device, such as a printer or graphics card. Preferably, both stages of the graphics rendering system are implemented as a graphics rendering software application for execution on the processor of the computer. Any known graphics rendering software application would be suitable, with appropriate modifications for interfacing with the software module implementing the method1005.

The method1005commences operation at step1000when it is called by the first stage of the graphics rendering system. The method1005is called when the graphics rendering system receives a new graphics object from the GDI layer. After this step1000, the method1005then inputs at step1010the graphics object currently being passed to the graphics rendering system. The method1005also during this step1010checks whether the currently received graphic object is a fill-path. If this step1010determines that the currently received graphic object is not a fill-path, then the method1005proceeds to step1040, where a sub-process named flush_ramp1505is called. The sub-process flush-ramp1505processes any fill-paths already stored in the currently stored gradient fill to produce one or more linear blends, which are then passed to the graphics rendering system. After the generation of the linear blends, the flush_ramp sub-process1505empties the stored gradient fill. This sub-process flush_ramp1505will be described in more detail below with reference toFIG. 15.

After completion of step1040, the method1005terminates10110and returns to the first stage of the graphics rendering system a message SKIP, which tells it that the currently received object is not a valid fill-path. The first stage of the graphics rendering system then tries to convert this fill-path to an edge based format if possible, otherwise the object is skipped and the system proceeds to the next object. As will be apparent from the foregoing, the currently received graphic object is not a valid fill-path and need not be pre-processed by the method1005before conversion to an intermediate edge based format.

Otherwise, if the step1010determines that the currently received graphic object is a fill-path, the method1005proceeds to step1020. The method1005in step1020checks whether the currently received fill-path has the basic properties needed to form a gradient fill. In particular, step1020tests whether the currently received fill-path: has one side that is at least smaller than a predefined configurable maximum size; is being filled with a flat color; contains 4 points that define a parallelogram; and does not use a raster operation that requires a destination. If the currently received fill-path meets these criteria then, the method1005proceeds to step1030. Otherwise, if the fill-path does not meet the criteria then the method1005proceeds to step1040, where a sub-process named flush_ramp1505is called.

The method1005then checks at step1030whether the number of fill-paths in the currently stored gradient fill is currently zero. If the method1005determines that currently stored gradient fill contains zero fill-paths, then the method1005proceeds to step1080. During step1080, the method1005initializes a new gradient fill by adding the currently received fill-path to the currently empty stored gradient fill. The height of the fill-path is not yet known because a direction has not yet been determined. A direction is defined when a second fill-path is received, this means the height for the first fill-path can only be added when a second fill-path is determined to be part of a gradient fill with the first fill-path. The height for the first fill-path is added to the stored gradient fill during an add_rect sub-process1105, called at step1090. Otherwise, if the number of fill-paths in the currently stored gradient are greater than zero, then the method1005proceeds to step1050.

The method1005in step1050calls a sub-process named check_fill1205to determine whether the currently received fill-path should be added to the currently stored gradient fill. The check_fill sub-process1205returns true if the fill-path is to be added to the currently stored gradient fill, otherwise it returns false, if it is not to be added. This check_fill sub-process1205is described below in detail with reference toFIG. 12.

After completion of step1050, the method1005proceeds to step1060, which determines whether a true or false has been returned by the check_fill sub-process1205. If the step1060determines a true has been returned, the method1005proceeds to step1090where the currently received fill-path is added to the currently stored gradient fill. The method1005during step1090calls the sub-process named add_rect1105in order to add the currently received fill-path to the currently stored gradient fill. This sub-process add_rect1105is described below in more detail with reference toFIG. 11. Otherwise if a false has been returned, the method1005proceeds to step1070.

The method1005during step1070calls the aforementioned sub-process flush_ramp1505for processing the currently stored gradient fill. After the completion of step1070, the method1005then proceeds to step1080, where a new gradient fill is initialized by adding the currently received fill-path to the currently empty stored gradient fill.

After completion of steps1080or1090the method1005terminates10100. When the method1005terminates, it returns a parameter OK to the first stage of the graphics rendering system, telling that it does not need to convert and pass the fill-path on to the second stage of the graphics rendering system.

Turning now toFIG. 11, there is shown a flow chart of the add_rect sub-process1105called by the method1005ofFIG. 10. This add_rect sub-process1105is responsible for adding a new fill-path to the currently stored gradient fill, which already contains one or more fill-paths. The add_rect sub-process1105commences at step1100when it is called by step1090(FIG. 10) of the method1005. Step1090also passes to this add_rect sub-process1105the currently received fill-path for adding to the currently stored gradient fill.

After step1100, the add_rect sub-process1105proceeds to step1110, where the number of fill-paths in the currently stored gradient fill is checked. If this step1110reveals there is only one fill-path in the currently stored gradient fill then the add_rect sub-process1105proceeds to step1120, where the direction of the fill of the currently received fill-path is determined (eg. VDOWNRIGHT). This is achieved by calling a sub-process named get_alignment1495. This get_alignment sub-process1495will be described in more detail below with reference toFIG. 14. Otherwise, if there are more than one fill-path in the currently stored gradient fill, the add_rect sub-process1105proceeds directly to step1160.

After the direction of the fill has been determined in step1120, the add_rect sub-process1105proceeds to step1130. In step1130, a switch statement is used to separate the directions into horizontal (HDOWNRIGHT, HUPRIGHT, HDOWNLEFT, or HUPLEFT) and vertical (VDOWNRIGHT, VUPRIGHT, VDOWNLEFT, or VUPLEFT) ramps. If the ramp is a horizontal ramp then step1140is performed where the rectangle-height of the first fill-path in the currently stored gradient fill and the received fill-path is defined by the x-plane (seeFIG. 7B). The height of the first fill-path is then stored in the currently stored gradient fill. Otherwise if the ramp is vertical, then step1150is performed where the rectangle-height of the first fill-path in the currently stored gradient fill and the currently received fill-path is defined by the y-plane (seeFIG. 7A). The height of the first fill-path is then stored in the currently stored gradient fill.

After the completion of steps1140, or1150the add_rect sub-process1105proceeds to step1160, where the accumulated height of this fill-path and all the previous fill-paths, if any, is stored in the heights array. The color of the currently received fill-path is added to the color array, and the number of fills is also incremented. The point array is also updated to hold the points of the currently received fill-path. After completion of step1160, the add_rect sub-process1105terminates at step1170and returns to step10100of the method1005.

Turning now toFIG. 12, there is shown a flow chart of the check_fill sub-process1205called by step1050of the method1005ofFIG. 10. This check_fill sub-process1205is responsible for checking whether the currently received fill-path is suitable for adding to the currently stored gradient fill. The check_fill sub-process1205commences at step1200when it is called by step1050(FIG. 10) of the method1005. Step1050also passes to this check_fill sub-process1205the currently received fill-path.

After step1200, the check_fill sub-process1205proceeds to step1210. The check_fill sub-process1205at step1210calculates the difference (i.e. Cn-Cn−1) between the color of the currently received fill-path and the color of most recently added fill-path to the currently stored gradient fill for each of the RGBA/CMYK (depending on the color space used) color values. The color of the most recently added fill-path in the stored gradient fill is the color stored in the last position of the color array. After completion of step1210, the check_fill sub-process1205proceeds to step1220.

The check_fill sub-process1205during step1220first tests to see if there is only one fill-path stored in the current gradient fill. Secondly, it tests that the currently received fill-path is aligned with the currently stored gradient fill. Thirdly, it tests if the fill-path in the currently stored gradient fill together the currently received fill-path will look correct by calling a sub-process named check_output_fill1305. Fourthly and lastly, it tests if the new fill-path has the same clipping region and raster operation as the previously added fill-paths in the currently stored gradient fill. This check_output_fill sub-process1305is described below in more detail with reference toFIG. 13. If all these tests are met in the affirmative the check_fill sub-process1205then proceeds to step1240. Otherwise, if any one of these tests are not met, then the check_fill sub-process1205proceeds to step1230. It should be noted that the check_fill sub-process1205evaluates each one of the tests in turn and if a test is not met in the affirmative then the check_fill sub-process1205immediately proceeds to step1230without evaluating the following tests. For example, if there is only one fill-path in the currently stored gradient fill, and the fill is aligned, then the first and second tests are met and third test then calls the check_output_fill sub-process1305. On the other hand for example, if there are more than one fill-paths in the currently stored gradient fill, then the check_fill sub-process1205immediately proceeds to step1230without evaluating the subsequent tests. Thus the check_output_fill sub-process1305is only called when there is a currently received fill-path which is properly aligned and the stored gradient fill contains only one fill-path.

The check_fill sub-process1205during step1240then checks if the heights of the first two fill-paths are similar. Preferably, it checks this similarity by testing whether the rectangle-height of the currently received fill-path is no greater than two times the rectangle-height of the fill-path in the currently stored gradient fill. It should be noted that during step1240, there is only one fill-path in the currently stored gradient fill. If the test reveals the heights are similar, the check_fill sub-process1205proceeds to step1250. Otherwise if the test reveals that the two heights are not similar then the check_fill sub-process1205terminates1260and returns FALSE to step1050of the method1005, indicating that the currently received fill-path should not be added to the currently stored gradient fill.

The check_fill sub-process1205during step1250stores the color gradients of the two fill-paths that were calculated during step1210. After step1250, the check_fill sub-process1205terminates1260and returns TRUE to step1050of the method1005, so that the method1005will then add1090the new fill-path to the stored gradient fill (which only contains one fill-path at this moment).

On the other hand, if any one of requirements are not met in step1220, the check_fill sub-process1205proceeds to step1230. The check_fill sub-process1205in step1230then checks to see if the currently received fill-path is a suitable candidate to be added to the currently stored gradient fill. The step1230does this by checking to ensure that:

1. The number of fills in the currently stored gradient fill is greater than1;

2. The sum of the accumulated height in the currently stored gradient fill and the rectangle-height of the currently received fill-path is less than a predefined maximum. This predefined maximum can be set to such a value, so that the fill does not extend beyond the page;

3. The color gradient between the currently received fill-path and the most recently added fill-path in the currently stored gradient fill-path has the same sign and is similar to the stored gradient. The gradient is checked for each of the color indices within the color space used (eg. if the color space is RGBA, each of the indicies R, G, B, and are all checked for consistency). Preferably, it checks to ensure that the color channel value Cn, for each color channel, of the currently received fill-path satisfies one of the relations of Equation (1) noted above.

4. The currently received fill-path is aligned correctly with the fill-paths in currently stored gradient fill;

5. The currently received fill-path is similar in height (rectangle-height) to the most recently added fill-path in the currently stored gradient fill. Preferably, it checks this similarity by testing whether the rectangle-height of the currently received fill-path is no greater than two times the rectangle-height of the first fill-path in the currently stored gradient fill.

6. The raster operation for the currently received fill-path is the same as the raster operation for the stored gradient fill.

7. The currently received fill-path has the same clip as the stored gradient fill.

If the step1230determines that the currently received fill-path passes all the aforementioned checks1to7, then the check_fill sub-process1205then terminates1260and returns TRUE to step1050of the method1005, so that the method1005will then add1090the new fill-path to the currently stored gradient fill. Otherwise, if any one of these checks1to7fail, the sub-process check_fill1205terminates at step1260and returns FALSE to step1050of the method1005, so that it does not add the currently received fill-path to the currently stored gradient fill.

Turning now toFIG. 13, there is shown a flow chart of the check_output13fill sub-process1305called by step1220of the check_fill sub-process1205ofFIG. 12. This check_output_fill sub-process1305is responsible for determining that the single fill-path in currently stored gradient fill and the currently received fill-path are suitable for creating a gradient fill. The check_output_fill sub-process1305commences at step1300when it is called by step1220(FIG. 12) of the check_fill sub-process1205. Step1220also passes during step1300to this check_output_fill sub-process1305the currently received fill-path.

After step1300, the check_output fill sub-process1305proceeds to step1310. The check_output_fill sub-process1305firstly during step1310calculates the absolute value of the color difference between the color of the currently received fill-path and the single fill-path in the currently stored gradient fill for each one of the color channels (eg. red, green, blue and alpha). The check_output_fill sub-process1305then during step1310determines and stores that one of the calculated absolute values of color differences that has the highest value (herein after called the maximum color gradient). After completion of step1310, the check_output_fill sub-process1305proceeds to step1330.

The check_output_fill sub-process1305during step1330checks whether the maximum color gradient (calculated during step1310) is less than a predefined maximum. Preferably, the predefined maximum is6. if the check1330reveals that it is less than the predefined maximum then the check_output_fill sub-process1305terminates13100and returns TRUE to step1220of the check_fill sub-process1205(FIG. 12). This tells the check_fill process1205(FIG. 12) that the gradient fill should be created. On the other hand if the check1330reveals that the maximum color gradient is larger than or equal to the predefined maximum, then the check_output_fill sub-process1305proceeds to1340. In the latter case it is still possible that the gradient fill should be created, that is, if the height of the individual fill-paths is very small, and this is determined during steps1340-1390.

The check_output_fill sub-process1305in step1340calls the sub-process named get_alignment1495to determine the alignment of the fill-paths. This get_alignment sub-process1495returns to the check_output_fill sub-process1305the alignment (eg. VDOWNLEFT) of the currently received fill-path and the single fill-path in the currently stored gradient fill. Alter the termination of the get_alignment sub-process1495called in step1340, the check_output_fill sub-process1305proceeds to step1350.

The check_output_fill sub-process1305in step1350checks the alignment returned by step1340. If the check1350reveals that the direction is not defined at all, that is the get_alignment sub-process1495returns NONE, then the check_output_fill sub-process1305terminates13100and returns FALSE to step1220of the check_fill sub-process1205indicating that a gradient fill should not be created. If the check1350reveals the direction is horizontal, that is the get_alignment sub-process1495returns HDOWNLEFT, HUPLEFT, HDOWNRIGHT, or HUPRIGHT, then the check_output_fill sub-process1305proceeds to step1360. Otherwise, if the check1350reveals the direction is vertical, that is the get_alignment sub-process1495returns VDOWNLEFT, VUPLEFT, VDOWNRIGHT, or VUPRIGHT, then the check_output_fill sub-process1305proceeds to step1390.

The check_output_fill sub-process1305during step1360sets the rectangle-height of the currently received fill-path to the length of the side of the parallelogram that proceeds in the x co-ordinate direction (SeeFIG. 7B). On the other hand, the check_output_fill sub-process1305during step1390sets the rectangle-height of the currently received fill-path to the length of the side of the parallelogram that proceeds in the y co-ordinate direction (SeeFIG. 7A). After completion of steps1360or1390, the check_output_fill sub-process1305proceeds to step1380.

The check_output_fill sub-process1305then in step1380checks if the rectangle-height, calculated in step1360or1390, to see if it is below some predefined maximum height and greater than zero. If the check1380reveals that it is not then the check_output_fill sub-process1305terminates13100and returns FALSE to step1220of the calling check_fill sub-process1205. Thus indicating a gradient fill should not be created. On the other hand, if the check1380reveals that it is less than the predefined maximum height and greater than zero then the check_output_fill sub-process1305terminates13100and returns TRUE to step1220of the calling check_fill sub-process1205. Thus indicating that the two fill-paths, that is the currently received fill-path and the single fill-path in the currently stored gradient fill, are potentially suitable for creating a gradient fill.

Turning now toFIGS. 14A to 14C, there is shown a flow chart of the get_alignment sub-process1495called by the add_rect1105, check_fill1205, and check_output_fill1305sub-processes ofFIGS. 11,12, and13respectively. This get_alignment sub-process1495is responsible for determining the direction of the gradient presently comprising the single fill-path in the currently stored gradient fill and the currently received fill-path. The get alignment sub-process1495commences at step1400when it is called either by step1220(FIG. 12) of the check_fill sub-process1205, step1120(FIG. 11) of the add_rect sub-process1105, or step1340(FIG. 13) of the check_output_fill sub-process1305. These steps1220,1120, and1340passes during step1400to this get_alignment sub-process1495the currently received fill-path.

After completion of step1400, the get_alignment sub-process1495proceeds to step1401, where the get_alignment sub-process1495checks whether the currently received fill-path is rectangle. If the check1401reveals the currently received fill-path is a rectangle then the get_alignment sub-process1495proceeds to step1402. The get_alignment sub-process1495in step1402checks whether the currently received fill-path and the single fill-path in the currently stored gradient fill are aligned in the x-plane. If the check1402reveals that they are aligned in the x-plane, the get_alignment sub-process1495proceeds to step1404. On the other hand, if the check1402reveals that they are not aligned in the x-plane the get_alignment sub-process1495proceeds to step1403.

The get_alignment sub-process1495in step1403checks whether the currently received fill-path is joined on the top side of the single fill-path in the currently stored gradient fill. If the check1403returns TRUE (yes), then the get_alignment sub-process1495terminates14150and returns the direction UP to its calling sub-process. On the other hand, if the check1403returns FALSE (no), then the get_alignment sub-process1495proceeds to step1406.

The get_alignment sub-process1495in step1406checks whether the currently received fill-path is joined on the bottom side of the single fill-path in the currently stored gradient fill. If the check1406returns TRUE (yes), then the get alignment sub-process1495terminates14150and returns the direction DOWN to its calling sub-process. On the other hand, if the check1406returns FALSE (no), then the get_alignment sub-process1495terminates14150and returns the direction NONE to its calling sub-process. It will be apparent in the latter case the fill-paths are not joined indicating there is no blend.

The get_alignment sub-process1495in step1404checks whether the currently received fill-path is joined on the left side of the single fill-path in the currently stored gradient fill. If the check1404returns TRUE (yes), then the get_alignment sub-process1495terminates14150and returns the direction LEFT to its calling sub-process. On the other hand, if the check1404returns FALSE (no), then the get_alignment sub-process1495proceeds to step1405.

The get_alignment sub-process1495in step1405checks whether the currently received fill-path is joined on the right side of the single fill-path in the currently stored gradient fill. If the check1405returns TRUE (yes), then the get_alignment sub-process1495terminates14150and returns the direction RIGHT to its calling sub-process. On the other hand, if the check1405returns FALSE (no), then the get_alignment sub-process1495terminates14150and returns the direction NONE to its calling sub-process. It will be apparent in the latter case the fill-paths are not joined indicating there is no blend.

On the other hand if the check1401reveals that the currently received fill-path is not a rectangle, then the get_alignment sub-process1495proceeds to step1410. In step1410, the currently received fill-path and the single fill-path in the currently stored gradient fill are checked to see if their point's1.y align. If so, then the gradient fill will be a horizontal type fill (FIGS. 6A to 6D), and the get_alignment sub-process1495proceeds to step1420. Otherwise, the gradient fill will be a vertical type fill (FIGS. 5A to 5D), and the get_alignment sub-process1495proceeds to step1480.

The get_alignment sub-process1495at step1420checks the single fill-path in the currently stored gradient fill to see if its point1.x is less than its point4.x in the x-plane. If this is so, then the fill is either HDOWNRIGHT, HUPRIGHT, or NONE (FIG. 6AorFIG. 6B) and the get_alignment sub-process1495proceeds to step1450. In step1450, the get_alignment sub-process1495checks whether point1of the fill-path of the currently stored gradient fill is located near the top bound of the bounding rectangle. If this is so, then the fill is deemed to be an HDOWNRIGHT fill, seeFIG. 6Aand the get_alignment sub-process1495terminates14150and returns HDOWNRIGHT to its calling step. Otherwise the get_alignment sub-process1495proceeds to step1460. The get_alignment sub-process1495then checks in step1460whether point1of the fill-path of the currently stored gradient fill is located near the bottom bound of the bounding rectangle. If this is so, the fill is deemed to be an HUPRIGHT fill (seeFIG. 6B) and the get_alignment sub-process1495terminates14150and returns HUPRIGHT to its calling step. Otherwise the fill is deemed not to have a direction, ie. NONE and the get_alignment sub-process1495terminates and returns the value NONE to its calling step.

On the other hand, if the get_alignment sub-process1495at step1420determines that point1.x of the single fill-path in the currently stored gradient fill is greater than or equal to its point4.x in the x-plane, then the get alignment sub-process1495proceeds to step1430. The get_alignment sub-process1495at step1430checks whether the point1of the single fill-path in the currently stored gradient fill is greater than its point4in the x-plane. If not then the fill is deemed to have no direction (viz NONE) and the get alignment sub-process1495terminates14150and returns the value NONE to its calling step. Otherwise the get_alignment sub-process1495proceeds to step1440.

The get_alignment sub-process1495in step1440, checks whether point1.y of the single fill-path in the currently stored gradient fill is located near the top bound of the bounding rectangle in the y plane. If this is not so, then this fill is deemed to be an HUPLEFT (FIG. 6D) and the get_alignment sub-process1495terminates14150and returns the value HUPLEFT to its calling step. Otherwise, the get alignment sub-process1495proceeds to step1470. The get_alignment sub-process1495in step1470, checks whether point1.y of the single fill-path in the currently stored gradient fill is located near the bottom bound of the bounding rectangle in the y plane. If this is so, then the fill is, deemed to be an HDOWNLEFT fill, (seeFIG. 6C), and the get_alignment sub-process1495terminates14150and returns the value HDOWNLEFT to its calling step. Otherwise, the fill is deemed to have no direction (NONE) and the get_alignment sub-process1495terminates14150and returns the value NONE to its calling step.

The get_alignment sub-process1495in step1480checks to see if the currently received fill-path and the stored fill-path in the currently stored gradient fill have the same x value for point1. If this is not true then the fill-paths are not aligned and don't form a gradient fill and the get_alignment sub-process1495terminates and returns the value NONE to its calling step. Otherwise, the get_alignment sub-process1495proceeds to step1490.

The get_alignment sub-process1495in step1490tests whether point1of the stored fill-path in the currently stored gradient fill is less than point4of the same fill-path in the y-plane. If this is true then the fill is either a VDOWNLEFT or VDOWNRIGHT, (refer toFIGS. 5A and 5B) and the get_alignment sub-process1495proceeds to step14120.

The get_alignment sub-process1495in step14120checks to see if point1of the stored fill-path in the currently stored gradient fill is located near to the right side of the bounding rectangle. If this is true then the fill is deemed to be VDOWNLEFT—seeFIG. 5Band the get_alignment sub-process1495terminates14150and returns the value VDOWNLEFT to its calling step. Otherwise, the get_alignment sub-process1495proceeds to step14130.

The get_alignment sub-process1495in step14130checks to see if point1of the stored fill-path in the currently stored gradient fill is located near the left side of the bounding box. If this is true then the fill is deemed to be VDOWNRIGHT—seeFIG. 5A, and the get_alignment sub-process1495terminates14150and returns the value VDOWNRIGHT to its calling step. Otherwise, the fill-paths are deemed not to be aligned, and the get_alignment sub-process1495terminates14150and returns the value NONE to its calling step.

The get_alignment sub-process1495in step14110, tests whether point1of the single fill-path stored in the currently stored gradient fill to see if it is located near to the right side of the bounding rectangle. If this is true the fill is deemed to be VUPLEFT—seeFIG. 5Cand the get_alignment sub-process1495terminates14150and returns the value VUPLEFT to its calling step. Otherwise, the get_alignment sub-process1495proceeds to step14140.

The get_alignment sub-process1495in step14140tests whether the point1of fill-path in the currently stored gradient fill to see if it is located near the left side of the bounding box. If this is true, then the fill is deemed to be an VUPRIGHT, seeFIG. 5D, and the get_alignment sub-process1495terminates14150and returns the value VUPRIGHT to its calling step. Otherwise the fill-paths are deemed not to be aligned, and the get_alignment sub-process1495terminates14150and returns the value NONE to its calling step.

As can been seen, at any stage the alignment or non-alignment has been determined then the alignment is simply returned to the calling sub-process.

Turning now toFIG. 15, there is shown a flow chart of the flush_ramp sub-process1505called by steps1040and1070of method1005. This flush_ramp sub-process1505is primarily responsible for flushing the currently stored gradient fill. The flush_ramp sub-process1505commences at step1500when it is called by steps1040and1070(FIG. 10) of the method1005. After commencement1500, the flush_ramp sub-process1505proceeds to step1510.

The flush_ramp sub-process1505at step1510checks the number of fill-paths in the currently stored gradient fill. If the check1510reveals that there is no fill-paths then the flush_ramp1505terminates1560and returns to the calling step1040or1070as any gradient fill has already been flushed. Otherwise, if the check1510reveals that there is 1 or more fill-paths in the currently stored gradient fill, the flush_ramp sub-process1505proceeds to step1520.

The flush_ramp sub-process1505in step1520again checks the number of fills in the currently stored gradient fill. This time if the check1520reveals that the number of fills is one then the flush_ramp sub-process1505proceeds to step1530. In step1530, a call is made to an external function draw_flat in the first stage of the graphics rendering system for converting the single fill-path to an edge based format. After completion of step1530, the flush_ramp sub-process1505proceeds to step1550. On the other hand, if the check1520reveals that the number of fill-paths in the currently stored gradient fill is greater than one then the find_and_put_ramps function1605is called in step1540. The find_and_put_ramps function1605is responsible for partitioning the currently stored gradient fill into a number of optimal linear blends and outputting these to the first stage of the graphics rendering system for conversion to an edge based format. The find_and_put_ramps function1605is described below in more detail with reference toFIG. 16. After completion of the find_and_put_ramps function1605in step1540, the flush_ramp sub-process1505proceeds to step1550.

The flush_ramp sub-process1505in step1550then flushes any fill-paths in the currently stored gradient fill and resets the variable numfills to zero. After completion of step1550the flush_ramp sub-process1505terminates and returns to the calling step1040or1070of the method1005(FIG. 10).

Turning now toFIG. 16, there is shown a flow chart of the find_and_put_ramps sub-process1605, which is initially called by step1540of the flush_ramp sub-process1505ofFIG. 15. The find_and_put_ramps function1605is responsible for partitioning the currently stored gradient fill into a number of optimal linear blends and outputting these to the first stage of the graphics rendering system for conversion to an edge based format. The find_and_put_ramps sub-process1605is a recursive sub-process as will become apparent from the description below. The find_and_put_ramps sub-process1605commences at step1600, where it takes as input the color, point and heights arrays of a set of fill-paths of the currently stored gradient fill-path. When the find_and_put_ramps sub-process1605is initially called by step1540of the flush_ramp process1505(FIG. 15), the color, point and heights arrays of the complete set of fill-paths in the currently stored gradient fill are passed to the find_and_put_ramps sub-process1605. For sake of explanation, the complete set of fill-paths are denoted as fill-paths[1. . . n], and their respective color, point and height arrays as C[1. . . n], points[1. . . n], and H[1. . . n] respectively.

After commencement1600, the find_and_put_ramps sub-process1605proceeds to step1610. The find_and_put_ramps sub-process1605in step1610then checks whether the color gradient of the first half of the set of fill-paths [1. . . n] is not similar to the color gradient of the entire set of fill-paths [1. . . n] (eg. red, green, blue and alpha channels for an RGBA flat color) in accordance with Equation (2) mentioned above. The step1610also checks whether n is not below a predefined minimum, which minimum is preferably set to 5 or a number of similar order of magnitude. If the check1610reveals the color gradients are not similar, that is fail to meet the requirements of Equation (2), and n is not below some predefined threshold, then the find_and_put_ramps sub-process proceeds1605to step1630. Otherwise, the find_and_put_ramps sub-process1605proceeds to step1620.

The find_and_put_ramps sub-process1605in step1620calculates the total-height depending on the direction of the fill, and calculates the two points necessary to define the points for which the gradient fill is to be applied. These two points need to be calculated such that the gradient fill can be applied in the correct direction, refer toFIGS. 8A and 8B. The first point is always defined as point one of the stored fill-path points. The second point, (Q, P), is found by using the total-height and the formula shown inFIGS. 14A to 14C, depending on whether the gradient fill is a horizontal or vertical type.

The find_and_put_ramps sub-process1605in step1620calculates the total-height depending on the direction of the fill, and calculates the two points necessary to define the points for which the gradient fill is to be applied. These two points need to be calculated such that the gradient fill can be applied in the correct direction, refer toFIGS. 8A to 8C. The first point is always defined as point one of the stored fill-path points. The second point, (Q, P), is found by using the total-height and the formula shown inFIGS. 14A to 14C, depending on whether the gradient fill is a horizontal or vertical type.

After completion of step1620, find_and_put_ramps sub-process1605proceeds to step1650. During step1650, a call is made to an external function draw_blend for generating and outputting to the graphics rendering system a linear blend using these two points determined in step1620, the starting color, and color gradient per color channel per pixel. Any known function for generating a linear blend would be suitable. After completion of step1650, the find_and_put_ramps sub-process1605terminates and returns to its calling step1640or1540.

The aforementioned method1005and sub-processes comprise a particular control flow. There are other variants of the method1005, which use different control flows without departing the spirit of the invention. Furthermore one or more of the steps of the method1005may be performed in parallel rather sequential.

4.0 Alternate Method

An alternate method of generating a linear blend may be performed by modifying the method1005, described above, in the manner shown inFIG. 18. This alternate method derives primarily from substantial simplification of the get_alignment sub-process and consequential modifications to some of the other sub-processes. In the following description, those method steps and processes that are common with steps and processes previously described are indicated using the same reference numeral.

As seen inFIG. 18, the alternate method1805has an entry point1800which passes to steps1010,1020,1030and1040each of which operate in the manner previously described. A “No” result from step1030invokes a step1850to check the gradient fill. The step1850calls a modified_check_fill sub-process2005seen inFIG. 20. The sub-process2005has an entry point2000which passes to step1210which operates as before and passes to a decision step2002.

The modified_check_fill sub-process2005, during the decision step2002first tests to see if there is only one fill-path stored in the current gradient fill. Secondly, it tests that the currently received fill-path is aligned with the currently stored gradient fill by calling an alternate_get_alignment sub-process2105described below with reference toFIG. 21. Thirdly, it tests if the fill-path in the currently stored gradient fill together with the currently received fill-path will look correct by calling a modification to the check_output_fill flowchart ofFIG. 13. Although the modification is not separately illustrated, such will be apparent from the following description andFIG. 13. In the modification, if the check1330ofFIG. 13reveals that the maximum color gradient is larger than or equal to predefined maximum (ie. No), the present modification of the check_output fill sub-process directly terminates at13100and returns a FALSE to step2002of the modified_check_fill sub-process2005(FIG. 20). In this modified implementation, steps1340,1350,1360,1380and1390ofFIG. 13are completely omitted. This tells the modified_check_fill process2005(FIG. 20) that the gradient fill should not be created. The decision step2002finally checks if the clip and the raster operation (ROP) for the currently received fill-path are the same as the fill-paths stored in the currently stored gradient fill. Clip objects contain a unique identifier that can be used to check for a consistent clip. This unique identifier is set by the GDI layer. Clipping regions that use the same area as the fill-path themselves are treated as a NULL clip.

The remaining steps1230,1240and1250of the modified_check_fill sub-process2005ofFIG. 20correspond to those described with respect toFIG. 12, which need not be repeated, and return via step2060to step1860ofFIG. 18.

When the alternate_get_alignment sub-process2105is called, process passes to an entry point2100seen inFIG. 21.

In step2110a side is picked to be the “chosen_side”. The chosen side is based on the points that make up the fill-path. Both the new fill-path and stored fill-path have the same chosen side at any one time. In this regard, the chosen side may be defined as the side that lies between point0and point1of a fill-path. Since no direction has yet been determined, the width is assumed to be the length of the chosen side, and the height as the length of the sides adjacent to the chosen side. If, in step2110, a chosen_side has already been assigned within this sub-process then a next side is assigned to be the chosen_side. No side is assigned to be the chosen_side more than once within any one call to the sub-process2105.

Step2120then checks to see if the width of the newly received fill-path is the same as the width of the stored fill-path and that the slopes of these widths are similar. It is often found that two adjacent fill-paths are not exactly the same. There are definable tolerances within the algorithm to allow slight differences in the widths and lengths of a new fill-path compared to the first fill-path. The widths and heights of a particular fill-path are calculated using the individual x and y components of the points that make up a fill-path. The tolerance used in these calculations is preferably ±one pixel for the individual x and y components, but is easily changed depending on the requirements of the system. This tolerance is also used in testing the similarity of slopes. Step2120proceeds to check that the height of the new fill-path is equal or no more than two times the height of the first stored fill-path. If the heights are sufficiently similar, step2120then proceeds to step2130, otherwise step2140proceeds.

Step2130then checks to see if the side opposite the chosen side of the newly received fill-path is coincident or overlaps the chosen side of the stored fill-path. To be a legitimate overlap, the full width of both the new fill-path and the stored fill-path must overlap. There is a configurable tolerance used in the determination of such an overlap, preferably in the order of ±one pixel in the x and or y direction. An overlap is also only valid if the overlap height is less than half the height of the last fill-path in the currently stored gradient fill. Separate fill-paths that do not touch each other are not considered coincident or overlapping even if they are within the aforementioned tolerance levels. If the sides are coincident or overlap then a direction can be defined and step2150proceeds. Otherwise if the sides do not coincide or overlap then a direction cannot be determined and step2130proceeds to step2140.

In step2150, a direction is assigned to the currently stored linear ramp. The direction is based on the current chosen side. If the chosen side is01then the direction is DIR_21, if the chosen side is12then the direction is DIR_01, if the chosen side is23then the direction is DIR_12and of the chosen side is30then the direction is DIR_10. The sub-process then terminates2160and then returns the appropriate direction to the calling step2002.

In step2140, if all four sides have been picked as the chosen side, then all possible alignments have been exhausted and a direction cannot be assigned to the fill-paths, DIR_NONE is returned2170to the calling step2002. If all four sides have not been exhausted then the algorithm proceeds to step2110.

After step1850, the alternate method1805in step1860checks if the modified_check_fill sub-process2005has returned True. If not, steps1070and1080operate as previously described. If so, step1890follows and a fill-path is added using a modified_add_rect sub-process1905ofFIG. 19. The sub-process1905may be used for either of the methods1005or1805. The sub-process1905has an entry point1900which passes to step1110which operates as previously described. Where the number of fills is one (ie. Yes) step1930follows where the height of the fill is determined directly from the direction of the fill, as seen inFIGS. 23A-23D. This substantially simplifies the process previously performed in steps1120,1130,1140and1150(seeFIG. 11).

After step1930, step1950follows where the height of the first fill-path is determined and stored in the height array. If not, step1160follows, as it does after step1950. The modified_add_rect sub-process1905then returns at step1970to the main method ofFIG. 18, which then returns a parameter OK to the first stage of the graphics rendering system, telling that it does not need to convert and pass the fill-path on to the second stage of the graphics rendering system.

In operation of the alternate method1805ofFIG. 18, as before, the steps1040and1070call the flush-ramp sub-process1505which, in turn, calls the find_and_put_ramps sub-process1605. Step1620of the sub-process1605as previously mentioned operates to define the direction of blend using two points. In the alternate method1805, those two points need to be calculated such that the gradient fill can be applied in the correct direction, as seen inFIG. 22. The first point chosen depends on the directions in which the gradient fill is travelling. If the fill has a direction of DIR_01then the first point chosen is point0of the first fill-path in the stored gradient fill. If the fill has a direction of DIR_10then the first point chosen is point1of the first fill-path in the stored gradient fill. If the fill has a direction of DIR_12then the first point chosen is point1of the first fill-path in the stored gradient fill. If the fill has a direction of DIR_21then the first point chosen is point2of the first fill-path in the stored gradient fill.

The second point chosen is determined by finding the intersection of Line B and Line C, this is shown as Point2(Q, P) inFIG. 8. Line B is the line perpendicular to Line A that passes through the first point of the gradient fill. Line A is the line that passes through the first point of the gradient fill and runs parallel to the width of the first fill-path in the stored gradient fill. Line C is the line runs parallel to the width of the stored fill-paths and passes through the second point that is described in the direction of the gradient fill (eg. for a DIR_01gradient fill, Line C would pass through point1of the last fill-path). For gradient fills that travel horizontally or vertically, the second point of the gradient fill is simply the second point described in the direction of the fill of the last fill-path in the stored gradient fill. for example, for a direction of DIR_12, the second point of the gradient fill is point2of the last fill-path in the stored gradient fill.

The method of generating one or more linear blends is preferably practiced using a general-purpose computer system1700, such as that shown inFIG. 10orFIG. 18, wherein the process may be implemented as software, such as an application program executing within the computer system1700. In particular, the steps of method of generating one or more linear blends are effected by instructions in the software that are carried out by the computer. The instructions may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into a number of separate parts, in which one part performs the method of generating one or more linear blends and another 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 generating one or more linear blends.

The computer system1700is formed by a computer module1701, input devices such as a keyboard1702and mouse1703, output devices including a printer1715, a display device1714and loudspeakers1717. A Modulator-Demodulator (Modem) transceiver device1716is used by the computer module1701for communicating to and from a communications network1720, for example connectable via a telephone line1721or other functional medium. The modem1716can 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), and may be incorporated into the computer module1701in some implementations.

The computer module1701typically includes at least one processor unit1705, and a memory unit1706, for example formed from semiconductor random access memory (RAM) and read only memory (ROM). The module1701also includes an number of input/output (I/O) interfaces including an audio-video interface1707that couples to the video display1714and loudspeakers1717, an I/O interface1713for the keyboard1702and mouse1703and optionally a joystick (not illustrated), and an interface1708for the modem1716and printer1715. In some implementations, the modem1716may be, incorporated within the computer module1701, for example within the interface1708. A storage device1709is provided and typically includes a hard disk drive1710and a floppy disk drive1711. A magnetic tape drive (not illustrated) may also be used. A CD-ROM drive1712is typically provided as a non-volatile source of data. The components1705to1713of the computer module1701, typically communicate via an interconnected bus1704and in a manner which results in a conventional mode of operation of the computer system1700known to those in the relevant art. Examples of computers on which the described arrangements can be practiced include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

Typically, the application program is resident on the hard disk drive1710and read and controlled in its execution by the processor1705. Intermediate storage of the program and any data fetched from the network1720may be accomplished using the semiconductor memory1706, possibly in concert with the hard disk drive1710. 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 drive1712or1711, or alternatively may be read by the user from the network1720via the modem device1716. Still further, the software can also be loaded into the computer system1700from 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 system1700for 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 module1701. Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.

The method of generating one or linear blends may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of generating one or more linear blends. Such dedicated hardware may form part of graphics rendering system.

INDUSTRIAL APPLICABILITY

It is apparent from the above that the arrangements described are applicable to the computer graphics and printing industries.