Method and apparatus for providing polygon pixel sub-sample information using incremental means

• US 6,057,855 A
• Filed: 07/02/1997
• Issued: 05/02/2000
• Est. Priority Date: 07/02/1997
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.), Samsung Electronics Co. Ltd.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Barkans, Anthony C
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): GOOD JOHNSON, MOTILEWA
• Application Number:
  US08/887,441
• Time in Patent Office: 1,035 Days
• Field of Search: 345/435, 345/431, 345/432, 345/441, 345/136-138
• US Class Current: 345/629
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 2200/12 involving antialiasing

Abstract

A method and apparatus for generating a mask identifying a number of subpixels that are covered by a primitive includes the process of apportioning an image, comprising a plurality of scan lines into a plurality of sub-scan lines, such that a number of sub-scan lines crosses each pixel. A sample point is placed on at least one of the sub-scan lines. To determine the number of samples that are covered by a primitive, edge stepping is used to step along each edge of the primitive, generating a sub-scan line coordinate for the edge. The edge stepping hardware is used for stepping either on a sub-scan line granularity, for operation in anti-aliased mode, or on a scan line granularity, for operation in aliased mode. In anti-aliased mode, as each edge sub-scan line coordinate is generated, it is compared against the coordinates of a sample point on that sub-scan line, to determine whether or not that sample point is covered by the primitive. A mask is generated for each pixel, with each bit of the mask corresponding to one of the sub-scan line samples. A bit in the mask is set if the subsample is covered by the primitive. Thus, a mask representing covered subsamples is provided by using incremental techniques to approximate pixel coverage without the complex hardware and lookup tables used in the prior art.

Claims

1. A method of determining a percentage of at least one pixel on a graphics system display screen that is covered by a primitive to be displayed on the display screen, the method comprising the steps of:

(a) apportioning the at least one pixel into a plurality of sub-scan lines that define a plurality of subsample points for the at least one pixel, each of the plurality of subsample points being located on a corresponding one of the plurality of sub-scan lines;

(b) stepping between the plurality of sub-scan lines of the at least one pixel;

(c) determining, at each one of the plurality of sub-scan lines, whether the corresponding subsample point on the one of the plurality of sub-scan lines is covered by the primitive; and

(d) approximating the percentage of the at least one pixel covered by the primitive based upon the number of the plurality of subsample points of the at least one pixel that are covered by the primitive.

2. The method according to claim 1, wherein the primitive includes a plurality of edges, and wherein step (c) comprises steps of:

determining, for each one of the plurality of edges of the primitive, x and y coordinates of each intersection wherein one of the plurality of edges of the primitive crosses the one of the plurality of sub-scan lines; and

determining, responsive to the x and y coordinates of each intersection and x and y coordinates of the subsample point located on the one of the plurality of sub-scan lines, whether the subsample point located on the one of the plurality of sub-scan lines is covered by the primitive.

3. The method according to claim 2, wherein the step of determining x and y coordinates of each intersection further comprises steps of:

determining, in software, start coordinates and slopes for each edge of the primitive;

stepping along each one of the plurality of edges beginning at the start coordinates for the one of the plurality of edges; and

determining the x coordinate of each one of the edges for each y coordinate corresponding to one of the plurality of sub-scan lines responsive to a slope of the each edge.

4. The method according to claim 1, further comprising steps of:

identifying, for the plurality of sub-scan lines, pixels in the primitive having all of the respective subsamples of each of the sub-scan lines covered by the primitive; and

transferring said pixels having all of said plurality of subsample points covered by the primitive to a memory controller in a single transfer operation.

5. The method according to claim 1, wherein the step (a) of apportioning further comprises a step of scaling the image by a predetermined amount, such that each of the plurality of sub-scan lines falls on an integer address boundary of the scaled image.

6. The method according to claim 5, wherein the predetermined amount is a multiple of the number of subsamples of the pixel.

7. The method according to claim 1, wherein the step (a) comprises the step of apportioning the at least one pixel into four sub-scan lines that define four subsamples.

8. The method according to claim 1, wherein the coordinates of the subsamples on the sub-scan line are selected such that the subsamples form a non-regular pattern in the pixel.

9. In a graphics system capable of rendering a primitive, an edge stepper for generating coordinate data for display pixels on a display device that represent the primitive, the edge stepper receiving edge equation data including a first and second pair of endpoint coordinates and a slope value for at least one edge of the primitive to be rendered, the edge stepper comprising:

an adder, for incrementing one of the first endpoint coordinates by an increment value to provide an edge x and an edge y coordinate of the at least one edge of the primitive being rendered, wherein the increment value is less than a size of a display pixel in one mode of operation.

10. The edge stepper according to claim 9, wherein the increment value is selected from a first group of increment values when the edge stepper operates in an aliased mode, and is selected from a second group of increment values when the edge stepper operates in an anti-aliased mode.

11. The edge stepper according to claim 9 wherein each pixel of the primitive is apportioned into a plurality of sub-scan lines when the edge stepper operates in an anti-aliased mode and wherein the second group of increment values includes increments for stepping between the plurality of sub-scan lines.

12. The edge stepper according to claim 11, wherein the edge stepper further comprises means for approximating a percentage of each pixel that is covered by the primitive.

13. The edge stepper according to claim 12, wherein the means for determining a percentage of each pixel that is covered by a primitive further comprises:

means for determining, for each edge, an x direction indicating a direction towards an opposing edge of the primitive; and

a comparator, coupled to receive the edge x and edge y coordinates for each sub-scan line and to compare the edge x and edge y coordinates against coordinates of a subsample located on the sub-scan line to determine, responsive to x direction, whether the subsample is covered by the primitive.

14. A graphics device for displaying an image on a display device based on data received from a host processor, the display device comprising a plurality of scan lines, each of the scan lines comprising a plurality of pixels, the graphics device comprising:

a graphics accelerator, coupled to receive data from the host processor representing a plurality of graphics primitives, the graphics accelerator generating edge equations for each primitive, the edge equations including, for at least one edge of the primitive, endpoint coordinate data identifying endpoints of the at least one edge of the primitive and slope data identifying a rate of change of the at least one edge;

a scan converter, coupled to the graphics accelerator, that translates the edge equations into coordinates of pixels of the display device, the scan converter including an edge stepper to step from one of the coordinates of one of the endpoints of the at least one edge to another endpoint of the at least one edge to generate pixel coordinates for the edge, wherein a size of step of the edge stepper is less than a size of a display pixel.

15. The graphics device according to claim 14, wherein the size of the step is varies according to a mode of operation of the graphics device.

16. The graphics device according to claim 14, wherein the edge stepper steps according to a scan line granularity for operation in an aliased mode, and wherein the edge stepper steps according to a sub-scan line granularity for operation in an anti-aliased mode.

17. The graphics device according to claim 15, further comprising:

means for apportioning the scan lines into a plurality of sub-scan lines; and

said edge stepper for sampling each pixel at a plurality of subsamples locations, with each subsample located on one of the sub-scan lines.

18. The graphics device according to claim 17, wherein the means for apportioning further comprises scaling means for scaling the image during anti-aliasing operations such that each of the plurality of sub-scan lines falls on an integer coordinate address of the scaled image.

19. The graphics device according to claim 17, further comprising means for determining, as the edge stepper steps along each sub-scan line in anti-aliased mode, whether a subsample located on the sub-scan line is covered by the primitive.

20. The graphics device according to claim 19, wherein the scan converter further comprises:

means, at said edge stepper, for generating a status signal indicative of whether said subsample located on the sub-scan line is covered by the primitive; and

a collection unit, coupled to the edge stepper unit, to collect edge coordinate data and the status signal for each sub-scan line coordinate that is generated by the edge stepper, and to generate, for each of a group of sub-scan lines of the pixel, a mask indicating a percentage of coverage of the pixel by the primitive.

21. A method of simplifying a mathematical calculation in an antialiasing operation for antialiasing an image displayed on a display screen, the mathematical calculation operating on at least one piece of information relating to the image, the information having an integer component and a fractional component, the method including steps of:

scaling the image by an amount such that the at least one piece of information has only an integer component and does not have a fractional component; and

performing the mathematical calculation during the antialiasing operation based on the at least one piece of information that has only an integer component.

22. A method of simplifying a mathematical calculation in an antialiasing operation for antialiasing an image displayed on a display screen, the mathematical calculation operating on at least one piece of information relating to the image, the information having an integer component and a fractional component, the method including a step of:

scaling the image by an amount such that the at least one piece of information operated upon by the mathematical calculation during the antialiasing operation has only an integer component and does not have a fractional component;

wherein the method of simplifying a mathematical calculation is employed in a multi-point sampling anti-aliasing operation, wherein the display screen includes a plurality of pixels and wherein the at least one piece of information relating to the image comprises at least one subsample point for each of the plurality of pixels, the at least one subsample point lying on a non-integer pixel boundary of the display screen, wherein the step of scaling provides a scaled representation of the image in which each of the plurality of subsamples falls on an integer address boundary of the display screen.