Method for determining the optimum angle for displaying a line on raster output devices

• US 5,489,920 A
• Filed: 05/25/1993
• Issued: 02/06/1996
• Est. Priority Date: 10/16/1989
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Kaasila, Sampo
• Primary Examiner(s): Hjerpe, Richard
• Assistant Examiner(s): WU, XIAO MIN
• Application Number:
  US08/067,336
• Time in Patent Office: 987 Days
• Field of Search: 340/747, 340/748, 340/751, 340/728, 340/735, 340/739, 340/744, 340/727, 340/730, 340/790, 340/731, 340/799, 340/750, 345/136, 345/137, 345/138, 345/133, 345/142, 345/141, 345/144, 345/185, 345/192, 345/194, 345/195
• US Class Current: 345/443
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G09G 5/20 Function-generator circuits, e.g. circle generators line or curve smoothing circuits
• CPC Class Codes: G09G 5/24 Generation of individual character patterns

Abstract

The present invention is a method for determining the optimum angle for displaying a line on raster output devices. The preferred embodiment defines the possible adjustments of a line as it is being displayed at a raster resolution as a penalty which comprises of a weighted sum of a distance variable and an angular variable. The weight permits the user to decide between a trade-off between the fidelity to original angle and the quality of a line being displayed. To determine the optimum angle for displaying a line at a particular raster resolution, the present invention finds the angle with the smallest penalty. The optimum angle is further constrained by a plurality of variables set by the user. Once the user provides the constraints on the minimum penalty, the present invention automatically determines the optimum angle for displaying a line on a raster output devices.

Claims

1. In a computer system, comprising a memory means, a processing means, and a raster scanned graphic output device, a method for controlling said raster scanned graphic output device having an array of pixels controlled by electronic signals which are transmitted to said output device in said system in order to display a line at an improved angle at various raster resolutions, said method comprising the steps of:

storing in said memory means a first plurality of electronic signals representing control points specifying at least one outline of said line;

said processing means selecting at least one of said control points of said at least one outline for manipulation;

said processing means relating a penalty with a weighted sum of an angular variable and a corresponding distance variable;

said processing means minimizing said penalty for determining said angle on said raster scanned graphic output device; and

displaying a plurality of pixels representing said line at said angle on said raster scanned graphic output device by transmitting a second plurality of electronic signals for said plurality of pixels to said output device, each of said second plurality of electronic signals having a value which specifies the intensity of said pixel corresponding with each of said second plurality of electronic signals.

2. The method as defined by claim 1, wherein said line comprises a glyph having at least a straight edge portion.

3. The method as defined in claim 1, wherein said weighted sum comprises a distance variable, said distance variable representing a plurality of linear projections that said line may assume.

4. The method as defined in claim 3, wherein said linear projection further comprises a plurality of pixel repetition periods, said pixel repetition period falling within an octant, said octant having one end point of said line as its center.

5. The method as defined in claim 4, wherein said distance variables may be mapped from one octant to another, said octant being descriptive of the position of said line in a coordinate plane.

6. The method as defined in claim 1, wherein said weighted sum further comprises of an angular variable, said angular variable measuring the possible angular changes in said line.

7. The method as defined in claim 6, wherein said angular variable further comprise a plurality of angular projections.

8. The method as defined in claim 7, wherein said angular variable further comprises a vector product of said line and an unit vector perpendicular to a pixel repetition period.

9. The method as defined in claim 1, wherein said penalty is said weighted sum of said distance variable and said angular variable.

10. The method as defined in claim 1, wherein said penalty is constrained by a predetermined number of pixels, said predetermined number of pixels being a minimum penalty.

11. The method as defined in claim 1, wherein a comparison between said penalty and a minimum penalty determines the optimum angle for displaying said line at low raster resolution if said penalty is less than said minimum penalty, said distance variable is greater than said minimum penalty, and said angle is within a predetermined range of said line.

12. The method as defined in claim 1, wherein a comparison between said penalty and a minimum penalty determines that said line requires no adjustment for displaying said line at low raster resolution if said penalty is greater than said minimum penalty, said distance variable is less than said minimum penalty, and said angle is more than twelve degrees outside of said line.

13. In a computer system, a method of controlling a raster scanned graphic output device having an array of pixels controlled by electronic signals which are transmitted to said output device in said system in order to display a line at an improved angle at various raster resolutions, which line is a portion of a glyph, said method comprising:

storing in a memory means a first plurality of electronic signals representing control points specifying outlines of said line with a first angle with respect to a first axis;

executing an instruction to modify said first angle of said line, said step of executing causing certain of said control points to be selected for manipulation;

determining an improved angle for display of said line on said raster scanned graphic output device for finding a second angle at which said line has a minimal pixel repetition period;

manipulating the location of said certain of said control points to adjust said line to have said improved angle on said raster scanned graphic output device;

displaying a plurality of pixels representing said line at said improved angle on said raster scanned graphic output device by transmitting a plurality of second electronic signals representing said plurality of pixels to said output device, each of said second plurality of electronic signals having a value which specifies the intensity of said pixel corresponding with said each of said second plurality of electronic signals.

14. A method as in claim 13 wherein said method further comprises the step of scan converting said line having an improved angle.

15. In a computer system, a method for controlling a raster scanned graphic output device having an array of pixels controlled by electronic signals which are transmitted to said output device in said system in order to display a line at an improved angle at various raster resolutions, which line is a portion of a glyph, said method comprising:

storing in memory means a plurality of electronic signals representing control points specifying said line with a first angle with respect to a first axis;

executing an instruction to modify said first angle of said line, said step of executing causing certain of said control points to be selected for manipulation;

determining an improved angle to be used for display on said raster scanned graphic output device by finding a second angle at which a weighted sum of an angular variable and a corresponding distance variable is minimized;

manipulating the location of said certain of said control points to adjust said line to have said improved angle on said raster scanned graphic output device, said improved angle being said second angle;

displaying a plurality of pixels by transmitting a plurality of second electronic signals to said output device, said plurality of second electronic signals representing said line at said improved angle on said raster scanned graphic output device.

16. A method as in claim 15 further comprising the step of selecting a constant with specifies the relative importance of said distance variable and said angular variable.

17. In a computer system, an apparatus for controlling a raster scanned graphic output device having an array of pixels in order to display a line at an improved angle at various raster resolutions on said raster scanned graphic output device comprising:

memory means for storing a first plurality of electronic signals representing a first plurality of control points specifying outline of said line;

selection means for selecting at least one of said first plurality of control points of said outlines for manipulation;

relation means for relating a penalty with a weighted sum of an angular variable and a corresponding distance variable for said at least one of said first plurality of control points;

minimization means for minimizing said penalty for determining said angle on said raster scanned graphic output device; and

display means for receiving a second plurality of electronic signals from said minimization means and displaying a plurality of pixels representing said line at said angle on said raster scanned graphic output device due to said second plurality of electronic signals.

18. The apparatus as defined by claim 17, wherein said line comprises a glyph having at least a straight edge portion.

19. The apparatus as defined in claim 17, wherein said weighted sum comprises a distance variable, said distance variable representing a plurality of linear projections that said line may assume.

20. The apparatus as defined in claim 19, wherein said linear projection further comprises a plurality of pixel repetition periods, said pixel repetition periods falling within an octant, said octant having one end point of said line as its center.

21. The apparatus as defined in claim 20, wherein said distance variables may be mapped from one octant to another, said octant being descriptive of the position of said line in a coordinate plane.

22. The apparatus as defined in claim 17, wherein said weighted sum further comprises an angular variable, said angular variable measuring the possible angular changes in said line.

23. The apparatus as defined in claim 22, wherein said angular variable further comprises a plurality of angular projections.

24. The apparatus as defined in claim 23, wherein said angular variable further comprises a vector product of said line and a unit vector perpendicular to a pixel repetition period.

25. The apparatus as defined in claim 17, wherein said penalty is said weighted sum of said distance variable and said angular variable.

26. The apparatus as defined in claim 17, wherein said penalty is constrained by a predetermined number of pixels, said predetermined number of pixels being a minimum penalty.

27. The apparatus as defined in claim 17, wherein a comparison means determines a comparison between said penalty and a minimum penalty for determining the optimum angle for displaying said line at low raster resolution if said penalty is less than said minimum penalty, said distance variable is greater than said minimum penalty, and said angle is within a predetermined range of said line.

28. The apparatus as defined in claim 17, wherein a comparison means determines a comparison between said penalty and a minimum penalty for determining that said line requires no adjustment for displaying said line at low raster resolution if said penalty is greater than said minimum penalty, said distance variable is less than said minimum penalty, and said angle is more than twelve degrees outside of said line.

29. In a computer system, an apparatus for controlling a raster scanned graphic output device having an array of pixels, each of said array of pixels generated by electronic signals in order to display a line at an improved angle at various raster resolutions, which line is a portion of a glyph, comprising:

storage means for storing a first plurality of electronic signals in a memory means representing a first plurality of control points specifying outlines of said line with a first angle with respect to a first axis;

instruction execution means for executing an instruction to modify said first angle of said line, said executing causing certain of said control points to be selected for manipulation;

improved angle determination means for finding a second angle at which said line has a minimal pixel repetition period on said raster scanned graphic output device;

location manipulation means for manipulating the location of said certain of said control points to adjust said line to have said improved angle on said raster scanned graphic output device;

display means for receiving a second plurality of electronic signals and displaying a plurality of pixels due to said second plurality of electronic signals for representing said line at said improved angle on said raster scanned graphic output device.

30. The apparatus of claim 29 wherein said apparatus further comprises scan conversion means for converting said line having said improved angle.

31. In a computer system, an apparatus for controlling a raster scanned graphic output device having an array of pixels controlled by electronic signals in order to display a line at an improved angle at various raster resolutions, which line is a portion of a glyph, comprising:

memory means for storing a plurality of first electronic signals representing a first plurality of control points specifying said line with a first angle with respect to a first axis;

instruction execution means for modifying said first angle of said line, said means causing certain of said control points to be selected for manipulation;

improved angle determination means for finding a second angle at which a weighted sum of an angular variable and a corresponding distance variable is minimized on said raster scanned graphic output device;

location manipulation means for moving said certain of said control points to adjust said line to have said second angle;

display means for receiving a second plurality of electronic signals and displaying a plurality of pixels due to said second plurality of electronic signals for representing said line at said second angle on said output device.

32. The apparatus of claim 31 further comprising means for selecting a constant which specifies the relative importance of said distance variable and said angular variable.

33. In a computer system comprising a memory, a processor, and a raster scanned graphic output device, a method for controlling said raster scanned graphic output device having an array of pixels controlled by electronic signals which are transmitted to said output device in said system in order to display a line at an improved angle at various raster resolutions, said method comprising the steps of:

storing in said memory a first plurality of electronic signals representing control points specifying at least one outline of said line;

said processor selecting at least one of said control points of said at least one outline for manipulation;

said processor relating a penalty with a weighted sum of an angular variable and a corresponding distance variable;

said processor minimizing said penalty for determining said angle on said raster scanned graphic output device; and

displaying a plurality of pixels representing said line at said angle on said raster scanned graphic output device by transmitting a second plurality of electronic signals for said plurality of pixels to said output device, each of said second plurality of electronic signals having a value which specifies the intensity of said pixel corresponding with each of said second plurality of electronic signals.

34. The method as defined by claim 33, wherein said line comprises a glyph having at least one straight edge portion.

35. The method as defined in claim 33, wherein said weighted sum comprises a distance variable, said distance variable representing a plurality of linear projections that said line may assume.

36. The method as defined in claim 35, wherein said linear projection further comprises a plurality of pixel repetition periods, said pixel repetition periods falling within an octant, said octant having one end point of said line as its center.

37. The method as defined in claim 36, wherein said distance variables may be mapped from one octant to another, said octant being descriptive of the position of said line in a coordinate plane.

38. The method as defined in claim 33, wherein said weighted sum further comprises an angular variable, said angular variable measuring the possible angular changes in said line.

39. The method as defined in claim 38, wherein said angular variable further comprise a plurality of angular projections.

40. The method as defined in claim 39, wherein said angular variable further comprises a vector product of said line and an unit vector perpendicular to a pixel repetition period.

41. The method as defined in claim 33, wherein said penalty comprises said weighted sum of said distance variable and said angular variable.

42. The method as defined in claim 33, wherein said penalty is constrained by a predetermined number of pixels, said predetermined number of pixels being a minimum penalty.

43. The method as defined in claim 33, wherein a comparison between said penalty and a minimum penalty determines the optimum angle for displaying said line at low raster resolution if said penalty is less than said minimum penalty, said distance variable is greater than said minimum penalty, and said angle is within a predetermined range of said line.

44. The method as defined in claim 33, wherein a comparison between said penalty and a minimum penalty determines that said line requires no adjustment for displaying said line at low raster resolution if said penalty is greater than said minimum penalty, said distance variable is less than said minimum penalty, and said angle is more than twelve degrees outside of said line.

45. An apparatus for controlling a raster scanned graphic output device having an array of pixels in order to display a line at an improved angle at various raster resolutions on said raster scanned graphic output device comprising:

a memory for storing a first plurality of electronic signals representing a first plurality of control points specifying outlines of said line;

a selection circuit for selecting at least one of said first plurality of control points of said outlines for manipulation;

a relation circuit for relating a penalty with a weighted sum of an angular variable and a corresponding distance variable for said at least one of said first plurality of control points;

a minimization circuit for minimizing said penalty for determining said angle on said raster scanned graphic output device; and

a display circuit for receiving a second plurality of electronic signals from said minimization circuit and displaying a plurality of pixels representing said line at said angle on said raster scanned graphic output device due to said second plurality of electronic signals.

46. An apparatus comprising:

a. a raster scanned graphic output device having an array of pixels controlled by electronic signals;

b. a memory coupled to said raster scanned graphic output device for providing said electronic signals; and

c. a processor coupled to said memory, said processor controlling said raster scanned graphic output device by storing said electronic signals in said memory in order to display a line at an improved angle at various raster resolutions, said processor storing in said memory a first plurality of electronic signals representing control points specifying at least one outline of said line, selecting at least one of said control points of said at least one outline for manipulation, relating a penalty with a weighted sum of an angular variable and a corresponding distance variable, minimizing said penalty for determining said angle on said raster scanned graphic output device and storing a second set of electronic signals in said memory representing said line at said angle on said raster scanned graphic output device, each of said second plurality of electronic signals having a value which specifies the intensity of said pixel corresponding with each of said second plurality of electronic signals.