A fundamental process in computer graphics and visualization is the process of scan conversion or rasterization. Given a polygon in image space, this process determines the pixels that intersect the polygon. This process is utilized in visible-surface algorithms, incremental-shading techniques, polygon-fill algorithms, ray-tracing-acceleration algorithms, and a number of other tasks that are critical to the understanding of the computer graphics field.
The conventional way to calculate the pixels that intersect a polygon is to utilize what is commonly called a ``digital differential analyzer'' or DDA. The term DDA refers to an antiquated mechanical device that solves differential equations by numerical methods. The term has stuck since the methods of approximating values by simultaneously incrementing by small steps is exactly what these algorithms do. The basic DDA algorithm utilized for rasterization is Bresenham's Algorithm.
For a pdf version of these notes look here.
Rasterization is the process of finding the pixels in device space that correspond to a polygon in screen space. In this section we utilize Bresenham's algorithm to assist in the scan conversion of specialized polygonal shapes - trapezoids in device space with their top and bottom edges parallel - each having the form . Any polygon in device space can be converted to a set of trapezoid of this form.
The idea for utilizing Bresenham's Algorithm in rasterization is to observe that this algorithm produces exactly one pixel per element of the driving axis. The figure below illustrates a line drawn with Bresenham's algorithm. In this case, we note that the axis is the driving axis, and that any column of pixels that intersects the line, intersects only one illuminated pixel.
The following illustration shows the same line, but drawn as if we utilized the axis as the driving axis.
We note now, that any row of pixels that crosses the line intersects only one illuminated pixel. This is the main idea behind adapting Bresenham's algorithm to be used in rasterization. We first need to adapt this algorithm so that the driving axis can always be the -axis, and then develop a procedure to use the algorithm on each non-horizontal edge of the trapezoid. In this way, we will get exactly two illuminated pixels per row and can complete our rasterization process by just selecting all the pixels in a row bounded by the two pixels produced by our algorithm.
The following figure illustrates this process. The left-hand picture shows the pixels that have been illuminated by the two Bresenham's algorithms. The right-hand picture shows the final result after filling the rows between the two illuminated pixels.
Now, how do we modify Bresenham's algorithm to always use the y-axis as the driving axis? Normally, within the main loop of the algorithm, the coordinate corresponding to the DA is incremented by one unit and the coordinate corresponding to the other axis need only be incremented occasionally. In this case, the coordinate on the DA can still be incremented by one unit, however the coordinate on the other axis may be incremented several times. This is actually a simple change to the algorithm, and and can be implemented by replacing the statement
we must consider two possible initial values for , one if (the left-hand illustration) and one if (the right-hand illustration). Referring to the illustration, we have either
We also need to recognize that may be greater than zero immediately, as in the following figure. Therefore, we must move the ``illuminate'' step in our algorithm below the ``while'' statement. This will insure that we are at the correct boundary pixel for the trapezoid.
The algorithm now appears as follows:
This algorithm will continue to increment the value (and decrement ) as long as is greater than zero. It illuminates only one pixel per row on the line.
We are assuming that which is valid since we are only considering the non-horizontal edges of the trapezoids that we want to rasterize. It should also be mentioned that the above algorithm is written for the case where is positive. If , then and is never incremented. In this case, we have a vertical line, and the value will never need to be incremented. If , then we must decrement in the algorithm, and add to .
To utilize the above algorithm to produce a rasterization of a trapezoid, we do the following steps.
It is not too difficult to see how to lump these three steps into one algorithm which computes the two endpoints on each row and fills between them. This is the topic of the next section
We have shown in the previous section that we can modify Bresenham's algorithm to produce a rasterization of a trapezoid. In short, two Bresenham algorithms were run, each on one non-horizontal side of the trapezoid, and then the rows were filled by illuminating pixels between those generated by the two algorithms. In this section we modify the above process to produce a complete row of pixels with each iteration of one algorithm.
We construct this algorithm in a more general form, defining an endpoint node which contains the information on each endpoint of a row of pixels. This method will be useful, not only in rasterization, but as controlling mechanisms for visible-surface algorithms.
We create an endpoint node that retains the information that our
algorithm needs to produce the rasterization of a line.
The node will contain (at least) the following
We will assume that the axis is the driving axis, and that the algorithm will proceed from the top to the bottom of the trapezoid. We will define two procedures: initialize and update, which will allow us to easily describe the total algorithm.
If we are given two points
space, with , the initialize procedure sets up the
endpoint node as follows:
The last four lines of the algorithm corrects the endpoint if is initially greater than zero. This step is necessary to insure that the complete trapezoid is contained in the union of the set of pixels that are produced by the rasterization algorithm.
The update procedure is utilized to make the modifications to
the endpoint node as the algorithm proceeds from row to row. Given a
node with , , ,
and , the update
procedure executes as follows:
Now, given a trapezoid with the four corner points , , and , (as in the following figure),
We note that
and , and the algorithm proceeds as
producing the following rasterization of the trapezoid.
Thus, by defining the endpoint nodes, we can specify a straightforward rasterization procedure for trapezoids.
This concept of a ``endpoint node'' is important for many uses of rasterization. In particular, a number of visible-surface algorithms utilize this concept as a fundamental part of the algorithm.
Given a convex polygon in device space, it can be easily converted to a set of trapezoids by the following procedure
In extended device space polygons are three dimensional - they have depth. We utilize this depth information in our visible-surface algorithms. Rasterization in this space consists of not only finding the pixels that best represent the polygon, but also finding a value that represents the ``depth'' of the pixel.
Since polygons are planar, any polygon can be split into a set of trapezoids, whose top and bottom edges are parallel and have constant value (In extended device space, this implies that these edges must lie in a plane with equation .) We have already developed algorithms for these trapezoids in device space - to expand them to work in extended device space is straightforward, as we only need consider increments for the value.
Consider a polygon in extended device space and let be its normal. We know that for any two points and in the plane of the polygon, we have
Now, consider the process of rasterization in extended device space. We will still increment the and coordinates by one in our algorithm, however, we now have a coordinate, and when incrementing this coordinate, we are constrained that the resulting point must still lie in the plane of the polygon. That is, if is our initial point, then both and must be in the plane of the polygon.
So let , and consider the points on the polygon and . By our above discussion, is a vector in the plane of the polygon and therefore
We note that if , we have a problem - as we have constructed a potential divide-by-zero situation. However, this problem should not surface, since if the component of the normal was zero, then the polygon would be edge-on to device space and would not be seen.
We now extend our endpoint node to include the
of extended device space. The two increments
are also included in the node, even though they are
fixed for the entire polygon and thus they could be
considered global. However, as we encounter cases where many polygons
may be rasterized in parallel, it is common to put this information
into the node. Thus, we obtain
We modify the Initialize procedure by integrating the initial calculation of, and the modification of the coordinate.
The update procedure can be modified in a similar way, in that we must modify the coordinate by incrementing it by either or . We obtain
Combining the Initialize and Update procedures, we obtain our algorithm. Given the following polygon in extended device space.
The algorithm appears as follows:
We will utilize this procedure repeatedly in our computer graphics algorithms. In addition to the coordinate, we frequently utilize quantities relating to color, texture, and parameterization as information in our endpoint nodes and increment them as well. These quantities are included in the algorithm in a manner similar to the coordinate above.
the Graphics Notes Home Page
Return to the Geometric Modeling Notes Home Page
Return to the UC Davis Visualization and Graphics Group Home Page
This document maintained by Ken Joy
Mail us your comments
All contents copyright (c) 1996, 1997, 1998,
Computer Science Department
University of California, Davis
All rights reserved.