Browse Prior Art Database

Extension to Bresenham's Algorithm for Plotting a Sequence of Straight Lines

IP.com Disclosure Number: IPCOM000041660D
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 4 page(s) / 49K

Publishing Venue

IBM

Related People

Johnson, PW: AUTHOR

Abstract

The most convenient algorithm for a drawing engine, operating on a points-addressable device such as a plotter or display, to use for plotting lines is that of Bresenham ("Algorithm for Computer Control of a Digital Plotter," IBM Systems Journal 4 25-30 (1965). This algorithm assumes that the true line passes through the given start and end points, and determines which are the best intermediate points to turn to. A problem can arise, however, if a continuous curve is being drawn by means of a sequence of short lines. In this case, if each line is specified by its start and end points (using a natural co-ordinate system in which one unit = the distance between adjacent display points), then applying Bresenham's algorithm to each line will cause a rather less smooth curve than is possible to be drawn.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 36% of the total text.

Page 1 of 4

Extension to Bresenham's Algorithm for Plotting a Sequence of Straight Lines

The most convenient algorithm for a drawing engine, operating on a points- addressable device such as a plotter or display, to use for plotting lines is that of Bresenham ("Algorithm for Computer Control of a Digital Plotter," IBM Systems Journal 4 25-30 (1965). This algorithm assumes that the true line passes through the given start and end points, and determines which are the best intermediate points to turn to. A problem can arise, however, if a continuous curve is being drawn by means of a sequence of short lines. In this case, if each line is specified by its start and end points (using a natural co-ordinate system in which one unit = the distance between adjacent display points), then applying Bresenham's algorithm to each line will cause a rather less smooth curve than is possible to be drawn. This arises because the algorithm assumes that the start and end points of each of the intermediate lines are exactly correct, whereas in fact they have been subjected to rounding errors. The problem can be overcome in three ways: 1. By specifying the curve in a parameterized form (e.g., the radius and center point of a circle), rather than as a sequence of lines. This considerably restricts the generality available, and complicates the programming of the drawing engine. It has the advantage, however, that it usually requires the least amount of data to be passed to the drawing engine. It also maximizes the processing offload to the drawing engine. 2. By making the lines so short that they are effectively just points, i.e., the plotting has all been done by a processor upstream of the drawing engine. This has the disadvantage that it generally maximizes the amount of data which must be passed to the drawing engine. It also minimizes the processing offload to the drawing engine. 3. By increasing the resolution of the co-ordinates used, and causing the drawing engine to recognize that it is plotting what is meant to be a smooth curve. The third of these methods does not call for considerably enhanced drawing engine programming, and is not restricted to particular types of curve, as in the first method. It also requires less data, and provides more offload, than the second method. It will now be described in more detail. In Fig. 1, imagine that addressable space is divided into squares, each with a display point at its center. The addressing resolution is finer than these squares (e.g., 8 times finer, linearly). Fig. 1 illustrates a fairly extreme case. The true line runs from s to e. This line is part of a longer, very smooth curve, so smooth in fact that it approximates closely in this region to a straight line. The normal Bresenham algorithm would first round s and e to S and E, respectively. It would then draw a line between S and E, setting display points S, I, J, and E. Notice, however, that if the true line had been plotted as part of a larger line, three...