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 of Trapezoids in Device Space I

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

**if**

**while**

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.

- Run the modified Bresenham algorithm on the left edge of the trapezoid, keeping track of the ``illuminated'' pixels.
- Run the modified Bresenham algorithm on the right edge of the trapezoid, keeping track of the ``illuminated'' pixels.
- Illuminate the interior pixels from left to right on each row that has been illuminated.

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

Rasterization of Trapezoids in Device Space II

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
information.

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
and
in device
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
follows:

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.

Rasterization of Polygons in Device Space

Given a convex polygon in device space, it can be easily converted to a set of trapezoids by the following procedure

- Let and be the maximum and minimum values that are taken on by the polygon (these extrema must exist at some of the vertices of the polygon, so they are easy to find).
- For those vertices that do not have a value equal to or , draw horizontal lines across the polygon to create trapezoids.

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

0 | ||

which implies that

0 | ||

which implies that

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
information
of extended device space. The two increments
and
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.

**Return to
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**

All contents copyright (c) 1996, 1997, 1998,
1999

Computer Science Department

University of California, Davis

All rights reserved.

1999-12-06