Scan conversion

Line Drawing

In order to draw a line on a screen we need to turn on appropriate pixels along the line (assume bit map). Assume the coordinates of the end points of the line are specified in the bit-map space (i.e. pixel number => integer coordinates), say, x1, y1 and x2, y2. For the following algorithms also assume that the slope of the line: 0 > (y2-y1)/(x2-x1) > 1 . (For slopes with magnitudes greater than 1, we make minor adjustments as described later.)

Digital Difference Analyzer (DDA) algorithm

We start at x1 and advance along the x dimension in steps of one, finding the appropriate value of y ,for each value of x. This can be simply done by inspecting the equation of the line y = m x + B, where B is the y intercept of the line. For our line that is:
y = (y2-y1)/(x2-x1)x + (x2y1-x1y2)/(x2-x1)
Now suppose we know the point (x,y on the line. We can compute the value of y at x+1 as m(x+1) + B . But we know that y = mx + B . Hence the value we seek is: y + m.

Thus by performing one addition, we can incrementally compute the value of y for each value of x. Note that we need real valued arithmetic as m is a rational number. To compute the pixel number we need to turn on, we just round the value y + m.

Mid-point algorithm

This algorithm is practically the same as another algorithm known after its inventor as the Bresenham's algorithm. The central idea of both these algorithms is to determine at each step whether to set the pixel immediately to the right of the current pixel, or the one above it. (Note that these are the only possibilities. Remember that the slope lies between 0 and 1.) Bresenham's algorithm draws the pixel closer to the line. The mid-point algorithm tests if the line passes above or below the mid-point between the two pixels. If it passes above, it must be closer to the upper pixel and if it passes below, it must be closer to the lower pixel. Since it is more straightforward to generalize the mid-point algorithm to circles, ellipses and general curves, it is described next.

Let us start with the implicit form of the line equation: F(x,y) = Ax + By + C = 0. For consistency, assume A > 0 (if A < 0, negate all coefficients).

Suppose we the current pixel on the line = (xp, yp). We next need to choose between pixels (xp+1, yp) and (xp+1, yp+1). In order to do that, we need to test the sign of dp = F(xp+1, yp+0.5). We call d the decision variable. (It is F evaluated at the mid-point of the two pixels).

If dp > 0, we must choose the upper pixel otherwise we choose the lower pixel. Note that to compute dp, as described, we need real valued arithmetic. We can eliminate all real arithmetic by resorting to incremental computation.

Assume we know dp. We can then compute dp+1 as follows:

Case I: We choose (xp+1, yp) at the current step.

dp = A(xp+1) + B(yp+0.5) + C
dp+1 = A(xp+2) + B(yp+0.5) + C
dp+1 - dp = A
Case II: We choose (xp+1, yp+1) at the current step.
dp = A(xp+1) + B(yp+0.5) + C
dp+1 = A(xp+2) + B(yp+1.5) + C
dp+1 - dp = A + B
Thus if dp, A and B were integers, we could incrementally compute dp+1 using a simple addition. (Note that A + B is a constant and the addition needs to be computed at most once per line.) Of course, A = (y2-y1) and B = (x1-x2) are integers. But what about dp? Let us look at the starting point (x1,y1): d1 = A(x1+1) + B(y1+0.5) + C = A(x1) + B(y1) + C + A + B/2 = A + B/2

Thus, if B is an even number, d1 is an integer. If B is an odd number, all we need to do is multiply all coefficients of the equation of the line by 2 (and go through the math again). This leaves the line unchanged: 2Ax + 2By + 2C = 0.

Boundary conditions

If the end points of the line lie beyond the edges of the window (or the bit-map), one easy solution is to round off the intersection of the line with the window, and perform the same algorithm. However, this can result in a different line from the one intended. This may result in, for instance, two collinear line segments not looking collinear anymore. Let us first consider a line that extends beyond the left edge (right edge is similar, when moving from right to left). While we must draw the closest pixel to the actual intersection point, we should also initialize the decision variable, d, appropriately.

For example, if the first pixel is (xp, yp), the decision variable d1 is: A(xp+1) + B(yp+0.5) + C. This is not equal to B/2 any more, but it still is an integer:

Assume xp = x1 + ix and yp = y1 + iy . (ix and iy are integers.)
Now, d1 = A(x1+ix+1) + B(y1+iy+0.5) + C. That is an integer (why?).

If the line extends beyond a horizontal boundary, the problem is more acute. Suppose the line intersects the lower boundary of the window. Check to see what happens for lines with slope close to zero, if we start at the rounded value of the intersection point. A number of pixels that are closer to the boundary than the scan-line beyond it do not get drawn. To account for this short-sightedness (no pun intended), we find the intersection with the line corresponding to half a pixel lower than the actual boundary. Now, if we round of this intersection, we start at exactly the pixel that we would have started at if the window was not truncated below this boundary.

Slope

The algorithm needs to change only slightly for slopes outside the range (0,1). For slopes greater than 1, we choose y as the primary axis. We increment y and find an appropriate value of x each time. For negative slopes, we just need to test for the lower, rather than the upper, pixel.

Remember that it is not wise to change the order of drawing to, say, an always increasing primary axis. This can result in "patterned" poly-lines looking wrong.

Circle etc.

The extension of the mid-point algorithm for circle is quite simple. All we need to do is replace F with the equation of the circle. Again, we subdivide the circle into eight sectors. For the sector which has its slope between 0 and 1: If the mid-point lies inside the circle we must pick the lower point and if it lies outside, we pick the upper point. The other sectors can be obtained by rotation/reflection.

Size

Note that the if we start at the first pixel and draw until the last pixel, we draw a line a little longer than the original length. This is because the pixels are not mathematical points, but have dimensions on the screen. The left-most pixel extends half a pixel size (diameter) to its left and the right-most pixel extends half the a size to its right. To draw a line of the intended length, we must reduce a pixel's worth. This done by using the convention that lines (and other primitives) are closed on there lower end and open at the other end, i.e. the upper end point does not belong the line. Hence we do not draw the upper end point. For horizontal lines, we do not draw the right end point. This also makes sure that for poly-lines -- mutually connected line segments -- we do not duplicate the end points.

Polygon Drawing

Polygon drawing is quite like line drawing, except we must fill in the area between the lines. For simplicity, let us assume that polygons are simple (i.e. no holes or intersecting lines). (Note: simple extensions to the algorithm described below handle non-simple polygons.) Again, we use incremental algorithms to compute the pixels to be filled. (Such algorithms are also called coherent algorithms -- a part of the computation at each stage is already available from the previous stage -- not that other algorithms are necessarily incoherent, but these algorithms take advantage of inherent coherence of computations :) We compute the part of the window inside the polygon, one scanline at a time.
  1. Compute all intersections of the polygon edges with the current scan line
  2. Sort all intersections
  3. Use Odd-Even parity rule to compute the spans of pixels that need to be turned on:
    1. Start with even parity.
    2. At each intersection flip the parity
    3. If the current parity is odd, draw each pixel until the next intersection (this is a span).
Step 1
We use coherence in computing the intersections with the current scan-line. If the intersection of the segment with the previous scan-line is known, we can use a line drawing algorithm to compute the current intersection. Using a DDA-like algorithm (remember, now y is our primary axis), given the previous intersection (x,y) we can compute the intersection at y = (y+1) as (x + 1/m).

Again, with a little manipulation we can get away with integer arithmetic. We break 1/m into an integer part i and a fractional part r. Remember, we need to keep adding 1/m to the current value of x. This can be done by adding i each time and updating r = N/D, N < D. We need to add N/D, 2N/D, 3N/D, and so on. We keep adding N to the numerator until it exceeds D, each time adding i to x. Once the numerator exceeds D, we add 1 more to x, and subtract 1 from the fractional part, which is achieved by subtracting D from numerator.

Remember, we must set only pixels lying in the interior of the polygon. Hence on the left edges of the span, we round up, and on the right edges of a span we round down. If the point of intersection lies exactly on a pixel, using our length convention, on the lower end, we include the pixel, and on the upper end we exclude the pixel from being drawn.

Step 2
We use coherence in sorting again. If no new edges start at the new scan-line (i.e., no vertices lie at the scan line) the sorted order remains the same (remember, we are assuming no self-intersections). If a new vertex does start, we can easily insert it in the current list of sorted intersections, by using insertion sort.

The intersection list can easily be managed by starting with a y sorted list of edges (usually a bucket sort) and maintaining the currently active list of intersections. Once we reach a scan line at which an edge starts (by looking at the bucket corresponding to the current scan line), we insert it into the active list.

Step 3
We need to consider the special case of when a vertex of the polygon lies on the scan line. For closed polygons, such vertices would normally be repeated as they lie on two edges. Always counting them twice (or even once) for the odd-even parity results in inconsistencies. However, using the following rule eliminates any such problems:

What happens to the horizontal edges of polygons?