Processor-based method for rasterizing polygons at an arbitrary precision

• US 5,528,737 A
• Filed: 12/14/1993
• Issued: 06/18/1996
• Est. Priority Date: 12/14/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Sfarti, Adrian
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/170,071
• Time in Patent Office: 917 Days
• Field of Search: 395/133, 395/141, 395/124, 395/132, 395/140, 345/113, 345/118, 345/147
• 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

An image processor is provided which rasterizes polygons with a minimum of computation. Pixels are tested for being inside a triangle by sorting the vertices by their values in one coordinate, rounding the vertices to the nearest pixels, and calculating two characteristic functions for pixels one scan line at a time, thereby identifying two end pixels for the scan line, where the particular functions used are edge characteristic functions for the two edges which bound pixels in the scan line within the triangle defined by the rounded vertices. To avoid ambiguity, pixels on one end of a scan line are deemed outside the triangle if they are exactly on the edge. Alternatively, only one function per pixel is used, the edge function for the nearest edge. The rasterization process is extensible to polygons of more than three sides, by taking into account that only two sides of the polygon need to be considered for a given scan line, and thus only two characteristic functions are needed at any one time. Using just the fractional part of an edge'"'"'s intersection with a scan line to detect whether a pixel is inside or outside is also possible. Where a characteristic function is used, the value of the function can be used as an anti-aliasing value, which would be a measure of how much of the pixel lies inside the triangle.

Claims

1. A method of rasterizing a collection of objects, comprising the steps of:

dividing the objects into triangles;

associating coordinates with each vertex of said triangles, said coordinates being an x-coordinate and a y-coordinate relative to a pixel grid of a pixelated display device, thereby mapping said triangles onto the image formed by coloring pixels in said pixel grid;

determining, for a set of pixels in said pixel grid, which pixels in said set are inside an area defined on said pixel grid by a triangle and which pixels are outside said triangle, by the steps of;

rounding each vertex of said triangle to a center of a pixel to form a rounded triangle with vertices A, B and C with coordinates (x_a, y_a), (X_b, Y_b), (X_c, Y_c), respectively;

calculating an edge function for at least one edge of said rounded triangle from said coordinates of vertices for a pixel located at a point (x,y), wherein a value of said edge function evaluated at said point (x,y) indicates whether said point is inside said rounded triangle, outside said rounded triangle, or exactly on an edge of said rounded triangle associated with said edge function;

associating said point with one said rounded triangle inside or said rounded triangle outside according to an edge decision rule when said edge function indicates said point to be exactly on said edge;

associating pixels within said rounded triangle with an interior of said triangle and pixels without said rounded triangle with an exterior of said triangle.

2. The method of claim 1, wherein said step of dividing further includes the step of dividing a first triangle into two distinct triangles if a vertex of a second triangle joins said first triangle at a point other than a vertex.

3. The method of claim 1, further comprising the step of coloring all of said pixels associated with said interior of said triangle.

4. The method of claim 1, wherein said edge function is used to perform antialiasing, whereby pixels along an edge between a first triangle having a first color and a second triangle having a second color, are colored using a weighted color that is based on said first color and said second color.

5. A method of rasterizing a collection of objects, comprising the steps of:

dividing the objects into triangles;

associating coordinates with each vertex of said triangles, said coordinates being an x-coordinate and a y-coordinate relative to a pixel grid of a pixelated display device, thereby mapping said triangles onto the image formed by coloring pixels in said pixel grid;

determining, for a set of pixels in said pixel grid, which pixels in said set are inside an area defined on said pixel grid by a triangle and which pixels are outside said triangle, by the steps of;

rounding each vertex of said triangle to a center of a pixel to form a rounded triangle with vertices A, B and C with coordinates (x_a, y_a), (X_b, Y_b), (X_c, Y_c), respectively;

calculating a first characteristic edge function for a pixel located at a point with coordinates (x,y), said first characteristic edge function equal to (x-x_a) (Y_c-Ya)-(y-x_a) (Y_c-ya);

calculating a second characteristic edge function for said pixel, said second characteristic edge function equal to (x-x_c)(y_a -y_b)-(Y-x_c)(Y_a-Yb);

calculating a third characteristic edge function for said pixel, said third characteristic edge function equal to (x-x_b)(y_a -y_b)-(Y-x_b)(y,_a -y_b);

associating said pixel with an interior of said rounded triangle when said first, second and third characteristic edge functions result in nonzero values with a same sign;

associating said pixel with an exterior of said rounded triangle when said first, second and third characteristic edge functions result in nonzero values with different signs;

associating said pixel with one of said interior or said exterior of said rounded triangle according to an edge rule when at least one value of said characteristic edge functions is zero;

associating pixels in said interior of said rounded triangle with an interior of said triangle and pixels in said exterior of said rounded triangle with an exterior of said triangle.

6. The method of claim 5, further comprising the steps of:

coloring a pixel according to an exterior color function when said pixel is associated with said exterior of said triangle; and

coloring a pixel according to an interior color function different from said exterior color function when said pixel is associated with said interior of said triangle.

7. The method of claim 5, wherein said step of dividing further includes the step of dividing a first triangle into two distinct triangles if a vertex of a second triangle joins said first triangle at a point other than a vertex.

8. A method of rasterizing a triangle, comprising the steps of;

rounding each vertex of the triangle to a center of a pixel to form a rounded triangle;

calculating an edge function for at least one edge of said rounded triangle for a pixel located at a point (x,y), wherein a value of said edge function evaluated at said point (x,y) indicates whether said point is inside said rounded triangle, outside said rounded triangle, or exactly on an edge of said rounded triangle associated with said edge function; and

coloring said point (x,y) a first color if said (x,y) is inside said rounded triangle or a second color if it is outside said rounded triangle.

9. The method of claim 8, further comprising the step of repeating said steps of calculating and coloring for each pixel along each edge of said rounded triangle, and further comprising the step of coloring in pixels along a scan line between pixels located on a left edge and pixels located on a right edge of said rounded triangle with said first color.