Method and apparatus for drawing antialiased lines and polygons

• US 4,796,020 A
• Filed: 03/10/1986
• Issued: 01/03/1989
• Est. Priority Date: 03/10/1986
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Inventors: Budrikis, Zigmantas L., Netravali, Arun N.
• Primary Examiner(s): Brigance, Gerald L.
• Assistant Examiner(s): Brier, Jeffery A.
• Application Number:
  US06/837,886
• Time in Patent Office: 1,030 Days
• Field of Search: 340/723, 340/728, 340/744, 340/747, 340/793
• US Class Current: 345/418
• CPC Class Codes: G06F 3/04845 for image manipulation, e.g. dragging, rotation, expansion or change of colour
• CPC Class Codes: G09G 5/20 Function-generator circuits, e.g. circle generators line or curve smoothing circuits

Abstract

A method and apparatus that employ precomputed line profiles to draw lines on a raster scan terminal with mostly horizontal or vertical "brush strokes" that develop the desired line profiles. The precomputed line profiles relate mostly to the slope of the drawn lines and to the position of the drawn lines between adjacent pixels on the raster scan terminal in the direction of the "brush strokes". A relatively small number of precomputed values is required, permitting the apparatus to operate at the low resolution of the raster scan and be driven advantageously by a look-up table. This results in a very fast operation of the system while leading to pleasing results. The method also takes into account corners and end-of-line conditions to avoid very abrupt and unnatural looking end points.

Claims

1. A method for drawing a line on a raster scan terminal which creates images with a plurality of scans, where each scan includes a plurality of pixels and the collection of pixels from said scans stored in a screen memory, forms a regular array of pixels, comprising the steps of:

computing position of successive points n₁, n₂, n₃, . . . n_i of said line;

evaluating position of each of said successive point, n_j with respect to the immediately predeing point, n_j-1 by developing a signal representative of the distance from n_j to the nearest pixel in the scan containing n_j and a signal representative of the number of pixels separating said nearest pixel of n_j from a corresponding nearest pixel of n_j-1 ;

selecting a painting profile from said position of point n_j with respect to said position of point n_j-1 from a precomputed set of profiles;

selecting a horizontal mode of painting or a vertical mode of painting of said profile, based on said position of point n_j with respect to said position of point n_j-1 ; and

applying said profile to said screen memory, in accordance with said step of selecting mode of painting, to modify intensity information stored in said screen memory.

2. The method of claim 1 wherein said step of evaluating position of a point includes restricting said evaluating to preselected positions in the distance between pixels in said array of pixels.

3. The method of claim 2 wherein the number of said preselected positions is binary.

4. The method of claim 1 wherein said step of evaluating position of a point includes evaluating a slope of said line in the neighborhood of said point.

5. The method of claim 1 wherein said step of evaluating position of a point includes evaluating an angle of said line away from the vertical axis in the neighborhood of said point.

6. The method of claim 5 wherein said step of selecting mode includes determining whether horizontal painting or vertical painting is to be employed based on the value of said angle.

7. The method of claim 6 wherein horizontal painting mode is selected when the value of said angle is less than 45 degrees, and vertical painting mode is selected when the value of said angle is greater than 45 degrees.

8. The method of claim 6 wherein said step of selecting mode includes a step of correction that is activated when said angle is in the neighborhood of 45 degrees.

9. Method of claim 8 wherein said step of correction employs both horizontal and vertical painting modes applied to paint at least one of said points.

10. The method of claim 1 wherein said step of applying said profile to said terminal includes blending said profile within said image.

11. The method of claim 10 wherein said blending is accomplished by developing intensity values in accordance with the equation

12. The method of claim 1 wherein said successive points n₁, n₂, n₃, . . . n_i lie on successive ones of said scans.

13. A system for drawing a line responsive to an input stimulus on a raster scan terminal which creates images with a plurality of scans, where each scan includes a plurality of pixels and the collection of pixels from said scans stores in a screen memory, forms a regular array of pixels, comprising:

first means for computing position of successive points n₁, n₂, n₃, . . . n_i of said line;

second means, responsive to said first means, for evaluating position of each of said successive point, n_j with respect to the immediately preceding point, n_j-1 by developing a signal representative of the distance from n_j to the nearest pixel in the scan containing n_j and a signal representative of the number of pixels separating said nearest pixel of n_j from a corresponding nearest pixel of n_j-1 ;

third means, responsive to said second means, for selecting a painting profile from said position of point n_j with respect to said position of point n_j-1 from a precomputed set of profiles;

fourth means, responsive to said third means, for selecting a horizontal mode of painting or a vertical mode of painting of said profile, based on said position of point n_j with respect to said position of point n_j-1 ; and

fifth means, responsive to said fourth means, for applying said profile to said screen memory.