Raster Algorithms (Basic Computer Graphics) Part 3

The Bresenham Line-Drawing Algorithm

Although the DDA algorithms for drawing straight lines are simple, they involve real arithmetic. Some simple modifications result in an algorithm that does only integer arithmetic, and only additions at that.

Note that in the case of the simple DDA, either x or y will always be incremented by 1. For simplicity, assume that the start point of our line is the origin. If we also restrict ourselves to lines whose endpoint is in the first octant in the plane, then it will be the x that always increases by 1. Therefore, we only need to worry about computing the y coordinates efficiently.

Suppose therefore that we want to draw a line from (0,0) to (a,b), where a and b are integers andtmpc646-105_thumb[2][2](which    puts (a,b) into the first octant). Using equation (2.3), the pointstmpc646-106_thumb[2][2]generated    by    the    simple    DDA    are    then    defined    by


tmpc646-109_thumb[2][2]

and the discrete line consists of the pointstmpc646-110_thumb[2][2]where y is the real number i(a/b) rounded to the nearest integer.

Now the y coordinates start at 0. At what point does yi become 1? To answer this question, we must compute b/a, 2b/a, 3b/a,. . ., and watch for that place where these values become bigger than 1/2. Furthermore, the yi will then stay 1 until these values become bigger than 3/2, at which time yi will become 2. Since we want to avoid doing real arithmetic, note that we do not really care what the actual values are but only care about when they get bigger than 1/2, 3/2, 5/2, …. This means that we can multiply through by 2a and the answer to the question as to when yi increases by 1 is determined by when 2b, 4b, 6b, . . . become bigger than a, 3a, 5a, … . Since computers can compare a number to 0 in less time than it takes to compare it to some other number, we shall start off by subtracting a. Our first question now is

tmpc646-112_thumb[2][2]

and only involves repeated integer additions of 2b to an initial sum d = 2b – a. After the sum d has become bigger than 0 and y has switched to 1, we need to check when the sum becomes bigger than 2a. By subtracting 2a, we again only need to keep checking for when the sum gets to be bigger than 0 by successive additions of 2b. In general, whenever y is incremented by 1, we subtract 2a from the current sum d. In that way we always need to check d simply against 0. For example, suppose we want to draw the line from (0,0) to (15,3). In this case, 2a = 30, 2b = 6, and the initial d is 6 – 15 = -9. The table below shows the points (xi,yO that are drawn and the changes to the sum d as i ranges from 0 to 8:

tmpc646-113_thumb[2][2]

The code in Algorithm 2.5.2.1 implements the algorithm we have been describing.

In our discussion above we have restricted ourselves to lines that start at the origin and end in the first octant. Starting at another point simply amounts to adding a constant offset to all the points. Lines that end in a different octant can be handled in a similar way to the first octant case – basically by interchanging the x and y. What this boils down to is that an algorithm which handles all lines is not much harder, involving only a case statement to separate between the case where the absolute value of the slope is either larger or less than or equal to 1.

We have just described the basis for the Bresenham line-drawing algorithm ([Bres65]). It, or some variation of it, is the algorithm that is usually used for drawing straight lines. Bresenham showed in [Bres77] that his algorithm generated the best-fit discrete approximation to a continuous line. The variation that is Algorithm 2.5.2.2 comes from [Heck90c] and works for all lines. It generates the same points as the original Bresenham line-drawing algorithm but is slightly more efficient.

Basic line-drawing algorithm.

Algorithm 2.5.2.1. Basic line-drawing algorithm.

To further improve the efficiency of DDA-based algorithms, there are n-step algorithms that compute several pixels of a line at a time. The first of these was based on the idea of double stepping. See [RoWW90] or [Wyvi90]. There are also algorithms that use a 3- or 4-step process. See [BoyB00] for an n-step algorithm that automatically uses the optimal n and claims to be at least twice as fast as earlier ones.

The Midpoint Line-Drawing Algorithm

Because drawing lines efficiently is so important to graphics, one is always on the lookout for better algorithms. Another well-known line-drawing algorithm is the so-called midpoint line-drawing algorithm. It produces the same pixels as the Bresenham algorithm, but is better suited for generalizing to other implicitly defined curves such as conics and also to lines in three dimensions (see Section 10.4.1). The general idea was first described in [Pitt67] and is discussed in greater detail by [VanN85].

Assume that a nonvertical line L is defined by an equation of the form

tmpc646-115_thumb[2][2]

wheretmpc646-118_thumb[2][2] 

 

 

 A Bresenham line-drawing algorithm.

Algorithm 2.5.2.2. A Bresenham line-drawing algorithm.

The midpoint line-drawing algorithm decision.

Figure 2.10. The midpoint line-drawing algorithm decision.

This assumption implies that our line has slope between 0 and 1.

Lines with other slopes are handled in a symmetric way like in Bresenham’s algorithm. Vertical lines are a very special case that would be handled separately. Another important consequence of our assumptions is that f(x,y) will be positive for points (x,y) below the line and negative for points above the line. Also like in the Bresenham algorithm, the pointstmpc646-119_thumb[2][2]that we will generate for the line will have the property that the x-coordinate will be incremented by 1 each time,tmpc646-120_thumb[2][2]so    that    we only have to determine the change in the y coordinate.

The only possible value fortmpc646-121_thumb[2][2]The decision will be based on the sign of tmpc646-126_thumb[2][2]

Iftmpc646-127_thumb[2][2]then the line    L crosses the linetmpc646-128_thumb[2][2]above    the pointtmpc646-129_thumb[2][2]and

we need to let____tmpc646-130_thumb[2][2]_    Iftmpc646-131_thumb[2][2]then    we    should    lettmpc646-132_thumb[2][2].    If    .tmpc646-133_thumb[2][2],    then    either y value would be satisfactory. We shall choose y in that case. Choosing our points pi in this way is what constitutes the basic idea behind the midpoint line-drawing algorithm. The only thing that is left is to describe some optimizations that can be made in the computations. First, the di can be computed efficiently in an incremental way. By definition, iftmpc646-134_thumb[2][2]then

tmpc646-143_thumb[2][2]

On the other hand, if tmpc646-144_thumb[2][2] then

tmpc646-145_thumb[2][2]

This shows that the next value of the decision variable can be computed by simple additions to the previous value. If our line L starts at the pointtmpc646-146_thumb[2][2],    then

tmpc646-147_thumb[2][2]tmpc646-148_thumb[2][2]

This gives us the starting value for the decision variable and all the rest are computed incrementally. We can avoid the fraction in the starting value and do all our computations using purely integer arithmetic by multiplying the equation for our line by 2, that is, let us use

tmpc646-149_thumb[2][2]

This has the effect of multiplying our starting value for the decision variable and its increments by 2. Since only the sign of the variable was important and not its value, we have lost nothing. Putting all this together leads to Algorithm 2.5.3.1,

Finally, before leaving the subject of line-drawing algorithms, we should point out that there are other such algorithms other than the ones mentioned here. For example, there are run-based line drawing algorithms. See [SteL00]. One thing to keep in mind though is that the time spent in line drawing algorithms is often dominated by the operation of setting pixels in the frame buffer, so that software improvements alone may be less important.

The midpoint-line drawing algorithm.

Algorithm 2.5.3.1. The midpoint-line drawing algorithm.

The Aliasing Problem

No matter how good a line drawing algorithm is, it is impossible to avoid giving most discrete lines a staircase effect (the “jaggies”). They just will not look “straight.” Increasing the resolution of the raster helps but does not resolve the problem entirely. In order to draw the best looking straight lines one has to first understand the “real” underlying problem which is one of sampling.

The geometric curves and surfaces one is typically trying to display are continuous and consist of an infinite number of points. Since a computer can only show a finite (discrete) set of points, how one chooses this finite set that is to represent the object is clearly important. Consider the sinusoidal curve in Figure 2.11. If we sample such a sine wave badly, say at the points A, B, C, and D, then it will look like a straight line. If we had sampled at the points A, E, F, and D, then we would think that it has a different frequency.

The basic problem in sampling theory: How    many samples does one have to take so that no information is lost?

This is a question that is studied in the field of signal processing. The theory of the Fourier transform plays a big role in the analysis.For more details of the mathematics involved in answering the sampling problem see [GonW87], [RosK76], or [Glas95]. We shall only summarize a few of the main findings here and indicate some practical solutions that are consequences of the theory.

Definition. A function whose Fourier transform vanishes outside a finite interval is called a band-limited function.

One of the basic theorems in sampling theory is the following:

The Whittaker-Shannon Sampling Theorem. Let f(x) be a band-limited function and assume that its Fourier transform vanishes outside [-w,w]. Then f(x) can be reconstructed exactly from its samples provided that the sampling interval is no bigger than 1/(2w).

Aliasing caused by bad sampling.


Figure 2.11. Aliasing caused by bad sampling.

If T is a sampling interval, then 1/T is called the sampling frequency and 1/(2T) is called the Nyquist limit. The Whittaker-Shannon Theorem says that if a function is sampled less often than its Nyquist limit, then a complete recovery is impossible. One says that the function is undersampled in that case. Undersampling leads to a phenomenon referred to as aliasing, where fake frequencies or patterns appear that were not in the original object. The two-dimensional situation is similar, but in practice one must sample a lot more because of limitations of available reconstruction algorithms.

Now in the discussion above, it was assumed that we were taking an infinite number of samples, something that we obviously cannot do in practice. What happens if we only take a finite number of samples? Mathematically, this corresponds to where we multiply the sampled result by a function that vanishes outside a finite interval. The main result is that it is in general impossible to faithfully reconstruct a function that has only been sampled over a finite range. To put it in another way, no function that is nonzero over only a finite interval can be band-limited and conversely, any band-limited function is nonzero over an unbounded set.

The practical consequences of the theory sketched above can be seen in lots of places. Aliasing is most apparent along edges, near small objects, along skinny highlights, and in textured regions. Ad hoc schemes for dealing with the problem may be disappointing because of the human visual system’s extreme sensitivity to edge discontinuities (vernier acuity). Aliasing is also a problem in animation. The best-known example of temporal aliasing is the case of the wagon wheel appearing to reverse its direction of motion as it spins faster and faster. Other examples are small objects flashing off and on the screen, slightly larger objects appearing to change shape and size randomly, and simple horizontal lines jumping from one raster line to another as they move vertically. See Figure 2.12. This happens because objects fall sometimes on and sometimes between sampled points.

Jaggies do not seem to appear in television because the signal generated by a television camera, which is sampled only in the vertical direction, is already band-limited before sampling. A slightly out of focus television camera will extract image samples that can be successfully reconstructed on the home television set. People working in computer graphics usually have no control over the reconstruction process. This is part of the display hardware. In practice, antialiasing techniques are imbedded in algorithms (like line-drawing or visible surface determination algorithms). The approaches distinguish between the case of drawing isolated lines, lines that come from borders of polygons, and the interior of polygons.

There are essentially two methods used to lessen the aliasing problem. Intuitively speaking, one method treats pixels as having area and the other involves sampling at a higher rate. The obvious approach to the aliasing problem where one simply increases the resolution of the display device is a special case of the latter. Mathematically, the two methods are

(1)    prefiltering, and

(2)    supersampling or postfiltering

Objects appearing, disappearing, changing size.

Figure 2.12. Objects appearing, disappearing, changing size.

Prefiltering. This amounts to treating each sample point as representing a finite area rather than simply a dot. Because lines often fall between pixels, this would avoid concentrating everything at a pixel in a hit-or-miss fashion. Mathematically, the process corresponds to applying a convolutional filter before sampling. One must make sure that the highest frequency of a signal in a scene does not exceed one-half the sampling rate.

Two widely used models for computing the area subtended by a pixel are

(1)  One considers the image a square grid as in Figure 2.13 with the pixels in the centers of the squares.

(2)  One computes the area using a weighting function similar to a Gaussian function. This in fact models the effect of the electron beam of a CRT and printing processes more closely. The pixels are larger and overlap. Details near the center now count more heavily than those near the edge.

Model (1) is easier than (2), but (2) produces better pictures. Internal details, such as highlights, are harder to handle.

In the case of boundaries of polygons we can use shading to suggest the position of the edges and can make the picture look as if it had higher resolution than it in fact has. Therefore, associate to each pixel an intensity proportional to the percentage of its area that is covered by the polygon. For example, if the intensity values ranged from 0 to 15, then we might assign pixel A in Figure 2.13 a value of 2 and pixel B, a value of 8. This approach could obviously substantially increase the amount of computation one has to do. However, by using an efficient approximation of the area that is needed, it turns out that all it takes is a slight modification to the Bresenham algorithm to get an efficient implementation of it, namely, the Pitteway-Watkinson algorithm. See [PitW80] or [Roge98].

Another approach for drawing antialiased lines treats the lines as having a thickness. An algorithm of this type is the Gupta-Sproull algorithm. See [GupS81], [Thom90], or [FVFH90]. It also starts with the standard Bresenham algorithm and then adds some checks for nearby pixels above and below each pixel that would be drawn by that algorithm.

Pixel intensities based on percentage of area covered.

Figure 2.13. Pixel intensities based on percentage of area covered.

Supersampling with scaling factor 3.

Figure 2.14. Supersampling with scaling factor 3.

Supersampling. Here we sample at more points than will actually be displayed. More precisely, we sample at n uniformly situated points within the region associated to each pixel and then assign the average of these values to the pixel. One usually oversamples the same amount in each direction so that n = s2 for some scaling factor s. For example, to create a 512 x 512 image we would sample at 1536 x 1536 points if s is 3. The samples would be taken 1/3 of a pixel width apart. In Figure 2.14, each square corresponds to a pixel in the final image and the dots show the location of the nine samples per pixel.

Postfiltering. In supersampling the sample values for each pixel are averaged. This gives each sample the same weight. Postfiltering uses the same approach but allows each sample to have a different weight. Supersampling is therefore a special case of postfiltering. Different weighting or “window” functions can be used. For example, if we represent the weighting operation in matrix form with the ij’th entry being the weighting factor for the ij’th sample, then rather than using the supersampling matrix

tmpc646-155_thumb[2][2]

we could use

tmpc646-156_thumb[2][2]

Mathematically, postfiltering corresponds to a convolution and filtering operation on the samples. The cost of generating an image with supersampling and postfiltering is proportional to the number of scan lines. The cost of calculations involving shading is proportional to the square of the number of scan lines. This means that the algorithm is particularly expensive for visible surface determination algorithms.

In conclusion, antialiasing techniques add a large amount of computation time to any algorithm that uses them. To minimize this extra work, one tries to do it only for areas where problems occur and makes no special computations for the rest. Of course, this assumes that one knows all about the picture, say a jar defined via many polygons. For lots more about antialiasing techniques see [FVFH90].

Halftoning, Thresholding, and Dithering

In contrast to antialiasing where we use multiple intensity levels to increase the resolution, halftoning (or patterning) is a technique for obtaining increased visual resolution with a minimum number of intensity levels. Basically, rectangular grids of pixels are treated as single pixels. This is how photographs are usually reproduced for magazines and topics. For example, using a 2 x 2 grid we can get five different intensities. See Figure 2.15(a). Not all of the possible combinations are used (basically symmetric patterns are to be avoided) in order not to introduce unwanted patterns into the picture. Using the patterns in Figure 2.15(b) could easily introduce unwanted horizontal or vertical lines in a picture. Normally 2 x 2 or 3 x 3 grids are used.

Halftoning reduces the overall spatial resolution of a system. For example, the resolution of a 1024 x 1024 monitor would be reduced to 512 x 512 with 2 x 2 grids. This means that such a technique is best applied when the resolution of the original scene is less than that of the output device.

Another technique called thresholding deals with the problem where we have a digital image with the same resolution as our monochrome display device but with more intensity levels. The simplest form of thresholding is to use a fixed threshold for each pixel. If the intensity exceeds that value, the pixel is drawn white, otherwise it is drawn black. Such a simple scheme can lose a lot of detail. A more refined algorithm of this type is due to Floyd and Steinberg. See [Roge98].

Finally, dithering is a technique applying to monochrome displays that is used with halftoning or thresholding methods to smooth edges of objects by introducing random noise into the picture. It increases the visual resolution without reducing the spatial resolution. One adds a random error to each pixel value before comparing to the threshold value (if any has been selected). Good error patterns have to be chosen carefully. Ordered dithering is where a square dither matrix is added to the picture. Alternatively, rather than adding noise using the same threshold for each pixel one can vary the threshold. With this approach, an optimum 2 x 2 matrix has been shown to be

tmpc646-157_thumb[2][2]

The entries of the matrix are used as the threshold for the corresponding pixel. There are recursive formulas for higher dimensional dither matrices.

Halftone patterns.

Figure 2.15. Halftone patterns.

Next post:

Previous post: