1. Technical Field
The present invention relates generally to computer graphics, and more particularly to a method and apparatus for efficiently rasterizing polygons in two dimensions.
2. Description of the Related Art
Computer graphics designers commonly model objects with polygons defined by a fixed set of vertices and edges joining those vertices. The polygon's vertices are typically stored in the application data structure. The scene designer will construct an object one polygon at a time, and then define the various attributes for that polygon at each of its vertices. Any number of attributes may be defined at a vertex including color, specular color, alpha (translucency), fog, surface texture and z (depth). The vertex attributes must eventually be interpolated to each pixel contained in the polygon in a process commonly referred to as scan conversion or rasterization. Currently, available rasterizers use a windower in conjunction with either an interpolator, multiplier or incrementer for interpolating all of the polygon vertex attributes to generate the attribute values at each pixel contained within the polygon. The function of the windower is to traverse the area of the polygon in a way that is guaranteed to visit all the pixels internal to it. Being assured that all the pixels inside the polygon will be visited by the windower, attribute values defined at the vertices are then interpolated to each pixel in the polygon. The polygon can be traversed by any algorithm that is guaranteed to cover all the pixels, and many techniques have been suggested in the prior art, however, most suffer from the limitation of being inefficient in their approach thereby necessitating excessive computational time. An additional drawback associated with inefficient traversal algorithms is the requirement that the interpolation hardware carry additional precision to compensate for overshoot and retrace of the graphics primitive. Representative examples of prior art traversal algorithms can be found in A Parallel Algorithm for Polygon Rasterization, Juan Pineda, Apollo Computer Inc., Siggraph '88 Atlanta, Computer Graphics, Volume 22, Number 4, August 1988. A further drawback associated with conventional interpolation methods involves the added costs associated with using interpolators that have the capability of multiplying. Conventional interpolation methods sometimes require that during the process of traversing or walking the face of a polygon a jump may be required to some random location on the face. To execute the required jumps, a multiplication operation is required of the interpolator. The hardware costs of multiply capable interpolators is greater than the cost of interpolators without such a feature.
Accordingly, there is a need to provide an efficient, accurate and inexpensive method and apparatus for rasterizing triangle primitives from descriptions that define x, y coordinates of three vertices, and several attributes per vertex such as color, specular color, depth, and texture coordinates.