Generating one or more linear blends

• US 7,304,648 B2
• Filed: 06/11/2003
• Issued: 12/04/2007
• Est. Priority Date: 06/17/2002
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Puckett, Giles, Beaumont, Ian Richard
• Primary Examiner(s): Tung; Kee M.
• Assistant Examiner(s): Caschera; Antonio A
• Application Number:
  US10/458,329
• Publication Number:
  US 20040012617A1
• Time in Patent Office: 1,637 Days
• Field of Search: 345/589, 345/610, 345/615
• US Class Current: 345/589
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

Abstract

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.

Claims

1. A method of generating one or more linear blends from a list of one or more fill-paths defining a current gradient fill portion, 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 most-recent 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 comprising a difference in color between the color of the new fill-path and the color of the most-recent fill-path in said list being no greater than an error factor, and said error factor is changed from at least one previously used error factor for said list of fill-paths due to dependence of the error factor on the difference in color between the most-recent and the second-most-recent fill-paths in said list;

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

(c) generating a plurality of linear blends from the first fill-path in said list to the most-recent fill-path in said list such that said gradient fill portion represented by said fill-paths is approximated with a least number of linear blends; and

d) outputting the generated linear blends to an outer means being at least one of the storage device for storing the linear blends and a display device for displaying the linear blends.

2. A method according to claim 1, wherein said one condition considers the difference in color in each color channel.

3. A method according to claim 1, wherein said error factor is a multiple of the difference in color between the most-recent and the second-most-recent fill-paths in said list.

4. A method according to claim 1, wherein said set of conditions further comprises:

a second condition that the new fill-path is physically contiguous or overlapping with the most-recent fill-path in the list.

5. A method according to claim 4 wherein a contiguity between said fill-paths is determined by at least comparing the alignment thereof.

6. A method according to claim 1, wherein a said set of conditions further comprises:

a third condition that a height of said new fill-path is no greater than two times a height of the most recent fill-path in said list, said height being measured in a direction determined by physical positions of the fill-paths of said list.

7. A method according to claim 1, wherein said set of conditions further comprises:

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

8. A method according to claim 1, wherein said set of conditions further comprises:

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

9. A method according to claim 8 wherein said predefined maximum is set such that the fill does not extend beyond a boundary of an output medium.

10. A method according to claim 1, wherein said set of conditions further comprises:

a sixth condition that a raster operation for the new fill-path does not use a destination, and is the same as a raster operation for the current linear blend.

11. A method according to claim 1, wherein said set of conditions further comprises:

a seventh condition that the new fill-path has the same clip as the current linear blend.

12. A method according to claim 1 wherein said list defining said current gradient fill portion relates to one or more already received fill-paths and said at least one new fill-path is newly received to thereby enable implementation of said method.

13. A computer readable medium encoded with a computer program element comprising computer program code means to make a computer execute a procedure to generate linear blends from a list of one or more fill-paths defining a current gradient fill portion, and at least one new fill-path, where the fill-paths each comprise a single colored parallelogram, the program code means comprising:

adding code means for adding one said new fill-path to said list to become a most recent fill-path in said list, if each condition of a set thereof is met, otherwise executing said generation code means, wherein said set comprises at least one condition, said one condition comprising a difference in color between the color of the new fill-path and the color of the most-recent fill-path in said list being no greater than an error factor, and said error factor is changed from at least one previously used error factor for said list of fill-paths due to a dependence of the error factor on the difference in color between the most-recent and the second-most-recent fill-paths in said list;

code means for calling said adding code means for each remaining said new fill-path;

generating code means for generating a plurality of linear blends from the first fill-path in said list to the most-recent fill-path in said list such that said gradient fill portion represented by said fill paths is approximated with a least number of linear blends; and

output means for outputting the generated linear blends to at least one of a storage device for storing the linear blends and a display device for display of the linear blends.

14. A computer readable medium encoded with a computer program element according to claim 13, wherein said one condition considers the difference in color in each color channel.

15. A computer readable medium encoded with a computer program element according to claim 13, wherein said error factor is two times the difference in color between the most-recent and second-last fill-paths in said list.

16. A computer readable medium encoded with a computer program element according to claim 13, wherein said set of conditions further comprises conditions selected from the group consisting of:

a second condition that the new fill-path is physically contiguous or overlapping with the most-recent fill-path in the list;

a third condition that a height of said new fill-path is no greater than two times a height of the most recent fill-path in said list, said height being measured in a direction determined by physical positions of the fill-paths of said 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 said linear blend and a rectangle-height of said new fill-path is less than a predefined maximum;

a sixth condition that a raster operation for the new 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 new fill-path has the same clip as the current linear blend.

17. A computer readable medium encoded with a computer program element according to claim 16 wherein said predefined maximum of said fifth condition is set such that the fill does not extend beyond a boundary of an output medium.

18. A computer readable medium encoded with a computer program element according to claim 16 wherein a contiguity between said fill-paths is determined by at least comparing the alignment thereof.

19. A computer readable medium encoded with a computer program element according to claim 13 wherein said list defining said current gradient fill portion relates to one or more already received fill-paths and said at least one new fill-path is newly received to thereby enable execution of program element.

20. A computer readable medium encoded with a computer program element according to claim 13 wherein said element comprises part of a graphical device interface.

21. Apparatus for generating one or more linear blends from a list of one or more fill-paths defining a current gradient fill portion, and at least one new fill-path, where the fill-paths each comprise a single colored parallelogram, said apparatus comprising:

means for adding one said new fill-path to said list to become a most-recent fill-path in said list, if each condition of a set thereof is met, otherwise enabling a generating means, said set comprising at least one condition, said one condition comprising a difference in color between the color of the new fill-path and the color of the most-recent fill-path in said list being no greater than an error factor, and said error factor is changed from at least one previously used error factor for said list of fill-paths due to dependence of the error factor on the difference in color between the most-recent and the second-most-recent fill-paths in said list;

means for repeating operation of said adding means for each remaining said new fill-path;

said generating means being operable to generate a plurality of linear blends from the first fill-path in said list to the most-recent fill-path in said list such that said gradient fill portion represented by said fill paths is approximated with a least number of linear blends; and

outputting means being at least one of the storage device for storing the linear blends and a display device for displaying the linear blends.

22. A method of generating linear blends from a list of one or more fill-paths defining a current gradient fill portion, 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 most-recent 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 color of the most-recent fill-path and an error factor, and said error factor 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;

(c) generating a plurality of linear blends from the first fill-path in said list to the most-recent fill-path in said list by recursively partitioning the list according to exceeding a predetermined error tolerance of the color gradient between certain ones of the fill-paths such that said gradient fill portion represented by said fill paths is approximated with a least number of linear blends; and

(d) providing the generated linear blends for at least one of storage in a storage device or display upon a display device.

23. The method according to claim 22, wherein said list comprises an original list of said fill-paths, fill-paths[1] . . . [n], and said generating step (c) comprises the sub-steps of:

(ca) determining if the color gradient between fill-path[1] and fill-path[n] of the list is equal within a predetermined error tolerance of the color gradient between fill-path[1] and fill-path[n/2] of the list; and

(caa) if so, outputting a linear blend for the list of fill-paths [1] . . . [n], from the color and position of the first fill-path in said list to the color and position of the most recent fill-path in said list;

otherwise

(cab) partitioning the list of fill-paths [1] . . . [n] into two lists of at least substantially equal number of fill-paths; and

(cb) repeating step (ca) for each partitioned list, until all fill-paths in the original list of fill-paths [1] . . . [n] have been processed.

24. A method according to claim 23 wherein step (cab) comprises partitioning said list into two lists, one for a first half of the list (fill-path[1] . . . fill-path[n/2]) and one for a second half of the list (fill-path[n/2] . . . fill-path[n]).

25. A method according to claim 23 wherein step (cab) comprises partitioning said list into two lists, one for a first half of the list (fill-path[1] . . . fill-path[n/2]) and one for a second half of the list (fill-path[(n/2)+1] . . . fill-path[n]).

26. A method according to claim 23, wherein a second linear blend corresponding to a second partitioned list of fill-paths is output adjacent a first linear blend corresponding to a first partitioned list of fill-paths, wherein an initial color of the second linear blend is set to a final color of the first linear blend.

27. A computer readable medium encoded with a computer program, the computer program comprising computer program code means to make a computer execute a procedure to generate linear blends from a list of one or mom fill-paths defining a current gradient fill portion, and at least one new fill-path, where the fill-paths each comprise a single colored parallelogram, the program code means comprising:

adding code means for adding one said new fill-path to said list to become a most-recent fill-path in said list, if each condition of a set thereof is met, otherwise executing generating code means, said set comprising at least one condition, said one condition being based on the color of the new fill-path and the color of the most-recent fill-path and an error factor, and said error factor 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;

code means for calling said adding code means for each remaining said new fill-path;

said generating code means being for generating a plurality of linear blends from, the first fill-path in said list to the most-recent fill-path in said list by recursively partitioning the list according to exceeding a predetermined error tolerance of the color gradient between certain ones of the fill-paths such that said gradient fill portion represented by said fill paths is approximated with a least number of linear blends; and

output means for outputting the generated linear blends to at least one of a storage device for storing the linear blends and a display device for displaying the linear blends.

28. A computer readable medium encoded with a computer program according to claim 27, wherein said list comprises an original list of a plurality of said fill-paths, fill-paths [1] . . . [n], and said generating code means comprises:

code means for determining if the color gradient between fill-path[1] and fill-path[n] of the list is within the predetermined error tolerance of the color gradient between fill-path[1] and fill-path[n/2] of the list; and

if so, code means for outputting a linear blend for the list of fill-paths [1] . . . [n], from the color and position of the first fill-path in said list to the color and position of the most-recent fill-path in said list;

otherwise

code means for partitioning the list of fill-paths [1] . . . [n] into two lists of at least substantially equal number of fill-paths; and

code means for calling said code means for determining for each partitioned list, until all fill-paths in the original list of fill-paths [1] . . . [n] have been processed.

29. A computer readable medium encoded with a computer program according to claim 28 wherein said code means for partitioning partitions said list into two lists, one for a first half of the list (fill-path[1]. . . fill-path[n/2]) and one for a second half of the list (fill-path[n/2] . . . fill-path[n]).

30. A computer readable medium encoded with a computer program element according to claim 28 wherein said code means for partitioning partitions said list into two lists, one for a first half of the list (fill-path[1] . . . fill-path[n/2]) and one for a second half of the list (fill-path[(n/2)+1] . . . fill-path[n]).

31. A computer readable medium encoded with a computer program according to claim 28, wherein a second linear blend corresponding to a second partitioned list of fill-paths is output adjacent a first linear blend corresponding to a first partitioned list of fill-paths, wherein an initial color of the second linear blend is set to a final color of the first linear blend.

32. Apparatus for generating linear blends from a list of one or more fill-paths defining a current gradient fill portion, and at least one new fill-path, where the fill-paths each comprise a single colored parallelogram, the apparatus comprising:

means for adding one said new fill-path to said list to become a most-recent fill-path in said list, if each condition of a set thereof is met, otherwise enabling generating means, said set comprising at least one condition, said one condition being based on the color of the new fill-path and the color of the most-recent fill-path and an error factor, and said error factor 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;

means for repeating operation of said adding means for each remaining said new fill-path;

said generating means being operable to generate a plurality of linear blends from the first fill-path in said list to the most-recent fill-path in said list by recursively partitioning the list according to exceeding a predetermined error tolerance of the color gradient between certain ones of the fill-paths such that said gradient fill portion represented by said fill paths is approximated with a least number of linear blends; and

output means to which the generated linear blends are output, the output means being at least one of a storage device for storing the linear blends and a display device for displaying the linear blends.