Processor-based method for rasterizing polygons at an arbitrary precision
First Claim
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 (xa, ya), (Xb, Yb), (Xc, Yc), 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.
4 Assignments
0 Petitions
Accused Products
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.
49 Citations
9 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 (xa, ya), (Xb, Yb), (Xc, Yc), 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. - View Dependent Claims (2, 3, 4)
-
-
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 (xa, ya), (Xb, Yb), (Xc, Yc), 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-xa) (Yc-Ya)-(y-xa) (Yc-ya); calculating a second characteristic edge function for said pixel, said second characteristic edge function equal to (x-xc)(ya -yb)-(Y-xc)(Ya-Yb); calculating a third characteristic edge function for said pixel, said third characteristic edge function equal to (x-xb)(ya -yb)-(Y-xb)(y,a -yb); 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. - View Dependent Claims (6, 7)
-
-
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. - View Dependent Claims (9)
-
Specification