Polygon rasterization

• US 5,446,836 A
• Filed: 10/30/1992
• Issued: 08/29/1995
• Est. Priority Date: 10/30/1992
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Kosmal, David R., Lentz, Derek J., Poole, Glenn C.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/968,901
• Time in Patent Office: 1,033 Days
• Field of Search: 395/140, 395/141, 395/142, 395/143, 395/128, 395/129, 345/147, 345/149, 345/118, 382/46, 382/54
• US Class Current: 345/441
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

Abstract

System and method for the rasterization of polygons. Each edge of the polygon (e.g., a triangle) is represented by a linear edge function which classifies each pixel within the plane of the polygon. In particular, pixels having a value greater than zero are on one side of an edge and less than zero on the opposite side of an edge. Each pixel within the plane of the polygon has associated with it a set of edge variables which represent the signed, horizontal distance between the pixel and the respective edges of the polygon. A pixel is rendered based on the value of a pixels edge variables which is generated with reference to the edge functions. The edge functions are applied to a linear span of pixels. Initially, the value of a set of edge variables for a given pixel within a triangle is determined by evaluating the three edge functions associated with that triangle. In order to determine which pixels to render, the present invention generates a W-bit render mask based upon the values of these edge variables. These values are applied to the span of pixels without the need to perform additional calculations for the remainder of the pixels within the span.

Claims

1. A computer-based method for determining which pixels to render as part of a triangle in order to rasterize polygons, the method comprising the steps of:

(1) generating, for the three edges of the triangle, three edge variables each of which indicates whether a first pixel falls inside or outside a triangle;

(2) generating three masks based upon the values of said edge variables, said masks are representative of a span of pixels, wherein said first pixel is the initial pixel in said span of pixels; and

(3) logically ANDing said three masks to produce a render-mask which represents which pixels within said span of pixels should be rendered.

2. The method of claim 1, further comprising the steps of traversing the triangle to a next pixel located after said span of pixels;

adding an incremental value to each of said edge variables; and

repeating steps (2) and (3).

3. The method of claim 1, wherein said render-mask, which consists of a string of W bits, has a render-mask bit for the pixel at position (x, y), and render-mask bits for the next W-1 pixels in the horizontal row.

4. The method of claim 1, wherein each of said edge variables contains a sign bit, span position bits, and sub-span position bits.

5. The method of claim 1, wherein the number of pixels in said span of pixels is a power of two.

6. The method of claim 1, further comprising the step of rendering the pixels within the triangle using said render-mask.

7. A computer-based system for determining which pixels to render as part of a triangle in order to rasterize polygons, the system comprising:

(a) an integer datapath having a plurality of registers and at least one adder/subtracter unit, wherein said integer datapath is configured to generate three edge variables each of which indicates whether a first pixel falls inside or outside a triangle;

(b) a pixel mask generation unit, adapted to accept from said integer datapath said three edge variables, said pixel mask generation unit further adapted to generate a render mask that indicates which pixels within a span of pixels are to be rendered as part of the triangle; and

(c) a rendering unit which takes said render mask from said pixel mask generation unit and issues commands to a memory system for each pixel to be rendered or not.

8. The system of claim 7, wherein said pixel mask generation unit comprises mask means for generating three masks based upon the values of said edge variables, said masks are representative of a span of pixels;

and means for logically ANDing said three masks to produce a render-mask which represents which pixels within said span of pixels should be rendered.

9. The system of claim 8, wherein said mask means comprises a lookup table which provides different masks depending upon the value of said edge variable.

10. The system of claim 7, wherein said span of pixels correspond to blocks of data accessed by said memory system.

11. The system of claim 7, wherein said edge variables represent the signed, horizontal distance between a given pixel and one of the edges of the triangle.

12. A computer-based method for determining which pixels to render as part of a polygon in order to rasterize the polygon, the method comprising the steps of:

(1) generating, for the plurality of edges of the polygon, a plurality of edge variables each of which indicates whether a first pixel falls inside or outside the polygon;

(2) generating a plurality of masks based upon the values of said edge variables, said masks are representative of a span of pixels, wherein said first pixel is the initial pixel in said span of pixels; and

(3) logically ANDing said plurality of masks to produce a render-mask which represents which pixels within said span of pixels should be rendered.

13. The method of claim 12, further comprising the steps of traversing the polygon to a next pixel located after said span of pixels;

adding an incremental value to each of said edge variables; and

repeating steps (2) and (3).

14. The method of claim 12, wherein said render-mask, which consists of a string of W bits, has a render-mask bit for the pixel at position (x,y), and render-mask bits for the next W-1 pixels in the horizontal row.

15. The method of claim 12, wherein each of said edge variables contains a sign bit, span position bits, and sub-span position bits.

16. A computer-based system for determining which pixels to render as part of a polygon in order to rasterize the polygon, the system comprising:

(a) an integer datapath having a plurality of registers and at least one adder/subtracter unit, wherein said integer datapath is configured to generate a plurality of edge variables each of which indicates whether a first pixel falls inside or outside the polygon;

(b) a pixel mask generation unit, adapted to accept from said integer datapath said plurality of edge variables, said pixel mask generation unit further adapted to generate a render mask that indicates which pixels within a span of pixels are to be rendered as part of the polygon; and

(c) a rendering unit which takes said render mask from said pixel mask generation unit and issues commands to a memory system for each pixel to be rendered or not.

17. The system of claim 16, wherein said pixel mask generation unit comprises mask means for generating a plurality of masks based upon the values of said edge variables, said masks are representative of a span of pixels;

and means for logically ANDing said plurality of masks to produce a render-mask which represents which pixels within said span of pixels should be rendered.

18. The system of claim 17, wherein said mask means comprises a lookup table which provides different masks depending upon the value of said edge variable.

19. The system of claim 16, wherein said span of pixels corresponds to blocks of data accessed by said memory system.

20. The system of claim 16, wherein said edge variables represent the signed, horizontal distance between a given pixel and one of the edges of the polygon.