Take a piece of graph paper, and select any two squares. Design an algorithm to fill in intervening squares in such a way that the filled squares give the best possible approximation to a straight line joining the two squares.
Rarely do introductory classes begin at such an elementary level -- most classes (and consequently most students) begin with the presumption that the computer "knows" how to draw a straight line, and that the problem in computer graphics is to build up from that point. This paper argues that this elementary problem is very powerful in a variety of ways:
1. It helps to introduce the concept of algorithms.2. It familiarizes the student with the nature of the discrete space in which computation and graphics occur.
3. Many different algorithms can solve this problem, and after struggling hopefully to discover or invent one, students are afforded the opportunity to compare many solutions from the point of view of efficiency, clarity, generality, etc. Many solutions are characteristic of broad classes of algorithms (e.g. "Divide and Conquer").
4. After considering the strengths and weaknesses of different algorithms, two algorithms which result in identical implementations but have different derivations, Bresenham's and Weiman's, are examined. The derivation of Bresenham's is algebraic, while Weiman's is combinatorial. The students are shown that the combinatoric approach leads to a great many generalizations which are applicable to other, often radically different, problems in computer graphics.
Not surprisingly, students often think of this problem as trivial until they try it. Even when they appreciate the difficulty involved in deriving a good algorithm, they presume it is an "academic" exercise which once they complete they will never use again and which they can replace with canned versions. To emphasize its ongoing utility, the students are then required to use the algorithms to animate objects, to move through RGB color space, to rotate and scale images, and to complete a variety of other operations not generally available in graphics packages.
Drawing a straight line would seem to be the most elementary of activities, whether on paper or on a computer. We know that most people cannot do a good job freehand, so when drawing with a pen or pencil on paper, we employ a straight edge, a tool specially made to facilitate this task. When we are required to draw a straight line on a computer, however, we have only software tools at our disposal. If one is studying computer graphics, it is often presumed that software is available in the student's environment which will perform that task, and indeed virtually all software packages dealing in any way with graphics will provide some kind of straight line drawing capability. "Paint" and CAD programs provide interactive "rubber banding" where the user selects endpoints and the line instantaneously appears, emanating from the first point selected, and following the cursor as if a rubber band were being stretched from the first point to the cursors current location. Hardware interface software for plotters or displays comes with line-drawing functions specific to their devices, and today even programming language compilers for personal computers comes with line drawing functions in their standard libraries.
With all these sources of software tools available, why would we want to make students discover their own algorithms for drawing straight lines? The first reason is what it reveals about the nature of the computer graphics environment. Each year the author has begun an introductory class in computer graphics with the following problem:
The square of our graph paper is clearly the analog of the pixel on a raster graphics display. Not so obvious is its relation to the incremental steps of a digital plotter, or to the lines produced on a laser printer. In each of these cases, we are dealing with a discrete, quantized space -- a space in which no further subdivision is permitted, and unlike our experience with the straight edge on paper, we do not have infinitely variable control over the thickness and orientation of the line. Ultimately, it might be said that all problems in computer graphics reduce to the questions of: Which pixels do we turn on and which do we turn off, and why?
How students approach this problem usually reveals something about preconceptions they bring to the course. Many engineering students respond by writing a program (remember, that's not the assignment); art students will often bring in several drawings of lines at different orientations, but will not write down what rules they used to create them, as if showing that they "know" an algorithm is sufficient. The instructor stands in front of a blackboard with grid lines sketched on it, and picking any two points, asks the students to indicate verbally what action to take next. Those who have written programs are frequently able to indicate explicitly what action to take at each step, but since they have often failed to make a sketch of the solution they hope to generate, they fail to anticipate correctly shortcomings in their programs, e.g., leaving gaps in the line. Likewise, those who failed to explicitly state their steps, give instructions which will apply only to the specific instance in front of them, e.g., "Now move up one square." Our objective is to get them to "look" at the problem by sketching many solutions, but then to try to distill out of their observations the salient features of all solutions. For example, those who observe carefully will often notice every line consists of at most two types of steps: those which change either x or y values, and those which change both x and y values.
Those solutions which actually do constitute genuine algorithms are very varied, and range from the prosaic to the exotic. The single most common solution (actually more often a partial solution) is the "analytic" method, i.e. express the solution as an implementation of the slope-intercept form of the equation of the line as determined by selected endpoints (the students are permitted to assume they may impose a Cartesian coordinate system on the graph paper.) The most common failure in this approach is the student who neglects to consider the problem of infinite slope. When this oversight is pointed out, the immediate solution is to test for this condition, and treat it as an exception. This is all right, of course, but it is important to realize that this is now two algorithms: one for drawing lines of finite slope, and another for drawing vertical lines. Closer examination reveals a further dichotomy between lines of finite slope whose absolute magnitude is greater than 1.0 and those less than 1.0. Now we have three algorithms. More problems appear when we consider implementing this approach on a computer. Clearly we need floating point operations to accommodate the many slopes between -1.0 and +1.0. Floating point is slower than integer operations, and since the squares (pixels) a indexed by integers (we have only integer valued coordinates), we would much prefer algorithms which avoid floating point operations. However, when all the exceptions are accommodated, this approach will work, and those who pursued it to the end are urged to implement it as a program for subsequent comparison with other algorithms.
Another "analytic" approach which was very novel, was proposed by an engineering student who was very sheepish and reluctant to discuss it. This was because it appeared at first to be absurdly inefficient. This student noted that not only can we express the slope-intercept equation of a line given its endpoints, but we can then determine the equation for the distance of any point to the line we wish to draw. If we do this for each and every square (or pixel), and all those which are more distant than one square from the line are not part of the line. Since most displays today range from a quarter of a million pixels to more than a million, we are talking about a lot of computation, and all of it done with floating point operations. The student realized this, and therefore felt embarrassed to propose it. What the student failed to realize that these constraints apply only to the von Neumann style of computer. This algorithm is wonderful for a massively parallel processor, where each pixel has its own CPU and, receiving the description of the line in a broadcast manner, each CPU proceeds to determine whether it is on or off the line simultaneously. This massively parallel approach may be impractical at the present time (only a few MPP's have been built), but it is clearly the way of the future. In this case, the problem afforded the students not only the opportunity to confront the issue of algorithm formulation, but also introduced them to alternative models of computation.
A method proposed by a student which showed imagination and thoughtfulness was the following: Designate one point as the starting point and one as the end point. At the starting point, visit each of the surrounding eight boxes, and at each, compute the distance to the end point using the Euclidean distance measure. Select the point which is the closest of the eight (if two yield an identical distance, select either). Designate this point as the new starting point, while the old starting point is filled in (turned on). Repeat this process until the end point is reached (indicated by a zero distance). The points which are turned on or filled in constitute a good approximation to a straight line.
One method which no student has as yet discovered is always presented by the instructor because it introduces the students to an important class of algorithms, the Divide and Conquer approach, which in graphics applications most often appears as a version of recursive subdivision. Given any two points, the instructor will remark that this problem is too hard - "I don't know how to do this, let's see if we can make the problem any simpler. Let's divide the problem into two simpler problems, and see if we can solve either of those." The algorithm proceeds as follows: Find the midpoint between the two points by adding the x coordinates and dividing by 2, and the same for the y coordinates. Now the problem has become one of how to draw a line from the starting point to the midpoint, and a second problem of drawing a line from the midpoint to the end point. We put the latter part of the problem aside until we solve the former. When we put it aside, we place it on a push down stack, so that any problems we put aside subsequently will be placed on top of it. We turn our attention to solving the problem of drawing a line from the starting point to the midpoint. If this remains too hard, we apply the same procedure, placing the second half of the subdivided problem on the push-down stack, pushing down the prior problem placed on it.
When does this technique terminate? This, of course is a crucial question in all recursive algorithms. Our criterion is that the midpoint be just one step away from the current start point. When this occurs, we know how to draw this straight line move to the next pixel. We cease subdividing, and go to our push down stack, and pop an unsolved problem of of the stack, where we begin the process again. If the stack is empty, we are finished.
Some additional remarks about this method: First, observe that unlike the slope-intercept method, this method is entirely independent of orientation, i.e., there are no special orientations like lines with infinite slope. Therefore, this approach has the advantage of greater simplicity. Second, this approach is not only typical of the general class of Divide and Conquer algorithms, but also has a very specific extension to the methods of spline curve and surface generation by recursive subdivision [CHA74, CATM, CHA75].
There are two other methods which deserve mention, but will not be elaborated on in detail here. A similar problem can be the drawing of a circle, and interestingly, if a person can draw a circle in a discrete rasterized space, they can then turn it into a straight line by the mathematical operation of "inversion in the unit circle." The second technique involves a "digital straight edge," i.e., a raster pattern which will always be the same and yet will produce a straight line at any orientation when properly transformed. This occurs with the complex log of a straight line. A canonical representation of the complex log of a straight line is positioned in the complex log domain and then a complex exponential transform is applied to the canonical form [WEI79, CHA80]. Let us now turn our attention to the "best" algorithms, those of Bresenham [BRES] and Weiman [WEI80]. These are identical in their realization, but differ in their derivation. Bresenham's is much more widely known than Weiman's, and can be found in most good graphics textbooks, so it will not be repeated here. However, the derivation is basically algebraic in character, and is far from obvious. The derivation of Weiman's is much easier for students of all backgrounds to grasp, and results in generalizations that are very broadly applicable.
The students are asked to examine the drawings of straight lines they have sketched on graph paper and to describe properties that derived. Specifically, they are asked to observe the vertical and horizontal projections of their drawings. Which is bigger, the change in x (dx) or the change in y (dy)? Whichever is bigger, what conclusions can we draw form this? Say dx is bigger, then we can conclude that our algorithm will take at least dx steps. It quickly becomes apparent that it will also require at most dx steps, since although the movements in the y direction will be less frequent, they will be combined with the steps in the x direction, i.e. sometimes we will step only in x, and sometimes we will step in x and y together. We are now in a position to restate the problem in a more general form: Given p things and q things, where p is greater than or equal to q, how do we distribute the q things among the p things in the most homogeneous manner? Here we make allusion to a physical model of the problem. The model is of two engaged gears, one with p teeth, and the other with q teeth. Since we know that our algorithm will take exactly p steps, we rotate the q-toothed gear one complete revolution for each step. If q is smaller than p (it can be equal to p), it will not go completely around the p- toothed gear on one revolution. However, each time it completes one complete resolution about p, this is where we combine a p thing (x step) and a q thing (y step). If p and q are equal, we will have a slope of 1, and each step will combine an x step and a y step, which is exactly what we expect. If q (the smaller quantity) is zero, which is the case when we are considering a vertical or horizontal line, the combined step never occurs, again confirming our expectations. The gear analogy is realized in a computer algorithm as modulo arithmetic, so students are introduced to this concept as well. Another point to note is that this algorithm is also orientation independent, and requires only integer operations, making it far preferable to the analytic method described above.
All lines produced in this manner, of course, have "jaggies" or aliasing. Students going through this exercise have a clear understanding of why they arise, and Weiman's algorithm also provides a simple method of demonstrating how anti-aliasing can be accomplished. Returning to the gear analogy, if we mark one tooth on the larger gear as distinguished, then we say that any time the smaller gear rotating around it passes that point we will add a q thing (or y step, assuming as above that dx was greater then dy). Note that we can start anywhere with respect to the distinguished tooth. This is equivalent to noting that we can generate all cyclic variations of our basic pixel pattern. If we generate all such variations, average the results and then display these as a gray scale, we have produced an anti-aliased straight line.
Another use of Weiman's method is in scaling raster images. Many graphics packages provide integral or power of two zooms of raster images, which are always realized by pixel replication. By seeing Weiman's algorithm as a combinatoric one, we can scale images to non-integral values by selective replication, where the selection is determined by distributing q replications among p total pixels. The result is a scaled up image of size p+q. This same approach can be extended to produce rotations of images by successive shearings and scalings of raster images. All of these be extended to anti-aliased forms. Bresenham's derivation, since it is algebraic, does not make any of the alternative utilizations apparent, while Weiman's, being algorithmic, immediately suggests other applications.
At the outset, it was indicated that most graphics software available provides some method for drawing straight lines. However, since source code is rarely provided, if an application requires that we know the points along a line, say in order to move an object on a path, it is unlikely that we can obtain that information from the software. Students who have gone through the exercise of designing their own algorithm now have a powerful and extensible tool at their disposal which they can convert to this end, as well as a deeper appreciation for the fundamental issues in computer graphics.
[BRES] Bresenham, J.E., "Algorithm for Computer Control of Digital Plotter," IBM Systems Journal, v4, #1 (1965).
[CHA74] Chaikin, G.M., "An Algorithm for High Speed Curve Generation," Computer Graphics and Image Processing, v4, #3 (1974).
[CHA75] Chaikin, G.M., Geometric Description and Generation of Surfaces, Computer Research Laboratory Technical Report, New York University (1975).
[CHA80] Chaikin, G.M. and C.F.R. Weiman, "Conformal Computational Geometry for Machine Vision," Proc. 5th International Conference on Pattern Recognition (1980).
[CATM] Catmull, E., A Subdivision Algorithm for Computer Display of Curved Surfaces, University of Utah Computer Science Department, UTEC-CSc-74-133, December 1974.
[WEI79] Weiman, C.F.R. and G.M. Chaikin, "Logarithmic Spiral Grids for Image Processing and Display," Computer Graphics and Image Processing, v11, #4 (1979).
[WEI80] Weiman, C.F.R., "Continuous Anti-Aliased Rotation and Zoom of Raster Images," Computer Graphics, v14, #3, (1980).
Material appearing in Architronic may be distributed freely by electronic or any other means, providing that any such distribution is without charge (unless for purposes of cost recovery by interlibrary loan services) and that Architronic is acknowledged as the source. However, no article may be reprinted in any publication without the explicit written permission of the author(s). This statement must accompany all distributions of Architronic, whether complete or partial.