Line rasterization techniques

• US 8,482,567 B1
• Filed: 11/03/2006
• Issued: 07/09/2013
• Est. Priority Date: 11/03/2006
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Moreton, Henry Packard, Crow, Franklin C.
• Primary Examiner(s): Johnson, M Good
• Application Number:
  US11/592,801
• Time in Patent Office: 2,440 Days
• Field of Search: 345/443
• US Class Current: 345/443
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A line rasterization technique in accordance with one embodiment includes conditioning a line by pulling in the ending vertex of the line or pushing out the starting vertex of the line. Thereafter, if the line exits a diamond test area of each pixel that it touches, the pixel may be lit.

Claims

1. A method comprising:

receiving starting and ending vertices of a given line;

conditioning a start of the given line or an end of the given line including

pulling in the end if the given line is a given line type related to a given diamond test area, the end is in a given portion of a pixel, the end is in a second diamond test area but does not exit the second diamond test area and both start and end of the given line are not in a same pixel; and

pushing out the start if the given line is the given line type, the start is in the given portion of the pixel and the given line exits a first diamond test area; and

lighting a pixel of a display if the given line exits a diamond test area of the pixel after the conditioning.

2. The method according to claim 1, wherein the given line is a segment of a line strip.

3. The method according to claim 1, further comprising:

determining if the given line is an x-major or y-major line from a slope of the given line;

determining if the given line starts on a corner or edge of an appropriate x-major or y-major diamond test area;

determining if the given line ends on a corner or edge of the appropriate diamond test area; and

determining if the given line exits one or more diamond test areas.

4. The method according to claim 3, wherein the diamond test area comprises:

an area enclosed by a diamond within the a given pixel, including the lower left edge of the diamond, the lower right edge of the diamond and the bottom corner of the diamond, if the given line is an x-major type line; and

an area enclosed by the diamond, including the lower left edge of the diamond, the lower right edge of the diamond, the bottom corner of the diamond and the right corner of the diamond, if the given line is an y-major type line.

5. The method according to claim 1, wherein conditioning the start or end of the given line further comprises:

pulling in the ending vertex of a positive x-major line if the ending vertex is in a right half of a pixel, the ending vertex is in a second diamond test area but does not exit the second diamond test area, and both vertices of the given line are not in a same pixel;

pushing out the starting vertex of a positive x-major line if the starting vertex is in the right half of the pixel, and the given line exits a first diamond test area;

pulling in the ending vertex of a negative x-major line if the ending vertex is in a left half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are not in the same pixel;

pushing out the starting vertex of a negative x-major line if the starting vertex is in the left half of the pixel, and the given line exits the first diamond test area;

pulling in the ending vertex of a positive y-major line, the ending vertex is in a bottom half of the pixel, the ending vertex is in the second diamond test area but does not exit the diamond test area, and both vertices of the given line are not in the same pixel;

pushing out the starting vertex of a positive y-major line, the starting vertex is in the bottom half of the pixel, and the given line exits the first diamond test area;

pulling in the ending vertex of a negative y-major line, the ending vertex is in a top half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are not in the same pixel; and

pushing out the starting vertex of a negative y-major line, the starting vertex is in the top half of the pixel, and the given line exits the first diamond test area.

6. The method according to claim 5, wherein conditioning the start or end of the given line further comprises:

culling a positive x-major line if an ending vertex is in a right half of a pixel, the ending vertex is in a second diamond test area but does not exit the second diamond test area, and both vertices of the given line are in a same pixel;

culling a negative x-major line if the ending vertex is in a left half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are in the same pixel;

culling a positive y-major line if the ending vertex is in a bottom half of the pixel, the ending vertex is in the second diamond test area but does not exit the diamond test area, and both vertices of the given line are in the same pixel;

culling a negative y-major line if the ending vertex is in a top half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are in the same pixel; and

culling the given line if the given line is a short line and the given line is in the first diamond test area and the second diamond test area, wherein the given line is a short line if the corresponding coordinates of the starting and ending vertices are in the same pixel.

7. A computer-readable medium containing a plurality of instructions which when executed cause a computing device to implement a method of conditioning a line comprising:

pulling in an ending vertex of a given line if the given line is a given line type related to a given diamond test area, the ending vertex is in a given portion of a pixel, the ending vertex is in a second diamond test area but does not exit the second diamond test area and both vertices of the given line are not in a same pixel; and

pushing out a starting vertex of the given line if the given line is the given line type, the starting vertex is in the given portion of the pixel and the given line exits a first diamond test area.

8. The computer readable-medium according to claim 7, wherein pulling in the ending vertex of a given line if the given line is the given line type, the ending vertex is in the given portion of a pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area and both vertices of the given line are not in the same pixel comprises:

pulling in the ending vertex of the given line if the given line is a positive x-major line, the ending vertex is in a right half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are not in the same pixel;

pulling in the ending vertex of the given line if the given line is a negative x-major line, the ending vertex is in a left half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are not in the same pixel;

pulling in the ending vertex of the given line if the given line is a positive y-major line, the ending vertex is in a bottom half of the pixel, the ending vertex is in the second diamond test area but does not exit the diamond test area, and both vertices of the given line are not in the same pixel; and

pulling in the ending vertex of the given line if the given line is a negative y-major line, the ending vertex is in a top half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are not in the same pixel.

9. The computer readable-medium according to claim 8, wherein pushing out the starting vertex of the given line if the given line is the given line type, the starting vertex is in the given portion of the pixel and the given line exits the first diamond test area comprises:

pushing out the starting vertex of the given line if the given line is a positive x-major line, the starting vertex is in the right half of the pixel, and the given line exits the first diamond test area;

pushing out the starting vertex of the given line if the given line is a negative x-major line, the starting vertex is in the left half of the pixel, and the given line exits the first diamond test area;

pushing out the starting vertex of the given line if the given line is a positive y-major line, the starting vertex is in the bottom half of the pixel, and the given line exits the first diamond test area; and

pushing out the starting vertex of the given line if the given line is a negative y-major line, the starting vertex is in the top half of the pixel, and the given line exits the first diamond test area.

10. The computer readable-medium according to claim 9, further comprising culling the given line if the given line is the given line type, the ending vertex is in the given portion of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area and both vertices of the given line are in the same pixel.

11. The computer readable-medium according to claim 10, wherein comprising culling the given line if the given line is the given line type, the ending vertex is in the given portion of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area and both vertices of the given line are in the same pixel comprises:

culling the given line if the given line is a positive x-major line, the ending vertex is in a right half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are in the same pixel;

culling the given line if the given line is a negative x-major line, the ending vertex is in a left half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are in the same pixel;

culling the given line if the given line is a positive y-major line, the ending vertex is in a bottom half of the pixel, the ending vertex is in the second diamond test area but does not exit the diamond test area, and both vertices of the given line are in the same pixel; and

culling the given line if the given line is a negative y-major line, the ending vertex is in a top half of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area, and both vertices of the given line are in the same pixel.

12. The computer readable-medium according to claim 11, further comprising culling the given line if the given line is a short line and the given line is in the first diamond test area and the second diamond test area, wherein the given line is a short line if the corresponding coordinates of the starting and ending vertices are in the same pixel.

13. The computer readable-medium according to claim 12, further comprising:

determining a fraction portion of each coordinate of the starting and the ending vertices of the given line;

determining a Manhattan distance from a center of the pixel for each coordinate of the starting and the ending vertices of the given line;

determining if the given line is the x-major or the y-major line and if positive or negative;

determining if the given line is the short line based upon the fractional portion of the coordinates of the given line;

determining if the line is in the first diamond and the second diamond based upon the Manhattan distances for the starting and ending vertices of the given line;

determining if the starting and or ending vertices touch a third or a fourth quadrant of the pixel;

determining if the starting and or ending vertices touch a point A or a point C of a given diamond test area; and

determining if the given line is in the first diamond test area and or the second diamond test area based upon whether the starting and or ending vertices touch particular quadrants of the pixel and particular points of a given diamond test area and whether the given line is the x-major line or the y-major line.

14. The computer readable-medium according to claim 13, further comprising adjusting one or more of the coordinates of the starting and or ending vertices of the given line to a given maximum or minimum value if the one or more coordinates are outside of the maximum or minimum value.

15. The computer readable-medium according to claim 14, wherein the given line is a segment of a line strip.

16. A processor comprising:

a setup unit for receiving a draw command and parameters describing a geometric primitive; and

a rasterizer, communicatively coupled to the setup unit for rasterizing the geometric primitive, wherein the rasterizer includes a line condition logic for;

pulling in an ending vertex of a given line if the given line is a given line type related to a given diamond test area, the ending vertex is in a given portion of a pixel, the ending vertex is in a second diamond test area but does not exit the second diamond test area and both vertices of the given line are not in a same pixel; and

pushing out a starting vertex of the given line if the given line is the given line type, the starting vertex is in the given portion of the pixel and the given line exits a first diamond test area; and

a data write unit, communicatively coupled to the rasterizer, for outputting the resulting pixel data.

17. The processor of claim 16, wherein the rasterizer is further adapted for:

culling the given line if the given line is the given line type, the ending vertex is in the given portion of the pixel, the ending vertex is in the second diamond test area but does not exit the second diamond test area and both vertices of the given line are in the same pixel; and

culling the given line if the given line is a short line and the given line is in the first diamond test area and the second diamond test area, wherein the given line is a short line if the corresponding coordinates of the starting and ending vertices are in the same pixel.

18. The processor of claim 16, wherein the geometric primitive comprises the starting vertex and ending vertex of the given line.

19. The processor of claim 16, wherein the processor is a general purpose central processing unit (CPU).

20. The processor of claim 16, wherein the processor is a graphics processing unit (GPU).