Bresenham's line algorithm
It is commonly used to draw line primitives in a bitmap image (e.g. on a computer screen), as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap operations in historically common computer architectures.
A Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter console.
[The algorithm] was in production use by summer 1962, possibly a month or so earlier.
Programs in those days were freely exchanged among corporations so Calcomp (Jim Newland and Calvin Hefte) had copies.
A description of the line drawing routine was accepted for presentation at the 1963 ACM national convention in Denver, Colorado.
It was a year in which no proceedings were published, only the agenda of speakers and topics in an issue of Communications of the ACM.
A person from the IBM Systems Journal asked me after I made my presentation if they could publish the paper.
I happily agreed, and they printed it in 1965.The following conventions will be applied: The endpoints of the line are the pixels at
Bresenham's algorithm chooses the integer y corresponding to the pixel center that is closest to the ideal (fractional) y for the same x; on successive columns y can remain the same or increase by 1.
The general equation of the line through the endpoints is given by: Since we know the column, x, the pixel's row, y, is given by rounding this quantity to the nearest integer: The slope
depends on the endpoint coordinates only and can be precomputed, and the ideal y for successive integer values of x can be computed starting from
In practice, the algorithm does not keep track of the y coordinate, which increases by m = ∆y/∆x each time the x increases by one; it keeps an error bound at each stage, which represents the negative of the distance from (a) the point where the line exits the pixel to (b) the top edge of the pixel.
The first step is transforming the equation of a line from the typical slope-intercept form into something different; and then using this new equation to draw a line based on the idea of accumulation of error.
The angle (or slope) of a line can be stated as "rise over run", or
A line splits a plane into halves and the half-plane that has a negative
Perhaps intuitively, the point should be chosen based upon which is closer to the line at
To answer this, evaluate the line function at the midpoint between these two points: If the value of this is positive then the ideal line is below the midpoint and closer to the candidate point
Otherwise, the ideal line passes through or above the midpoint, and the y coordinate should stay the same; in which case the point
The value of the line function at this midpoint is the sole determinant of which point should be chosen.
Alternatively, the difference between points can be used instead of evaluating f(x,y) at midpoints.
This decision can be generalized by accumulating the error on each subsequent point.
One performance issue is the 1/2 factor in the initial value of D. Since all of this is about the sign of the accumulated difference, then everything can be multiplied by 2 with no consequence.
The algorithm can be extended to cover slopes between 0 and -1 by checking whether y needs to increase or decrease (i.e. dy < 0) By switching the x and y axis an implementation for positive or negative steep slopes can be written as A complete solution would need to detect whether x1 > x0 or y1 > y0 and reverse the input coordinates before drawing, thus In low level implementations which access the video memory directly, it would be typical for the special cases of vertical and horizontal lines to be handled separately as they can be highly optimized.
Some versions use Bresenham's principles of integer incremental error to perform all octant line draws, balancing the positive and negative error between the x and y coordinates.
[3] The Bresenham algorithm can be interpreted as slightly modified digital differential analyzer (using 0.5 as error threshold instead of 0, which is required for non-overlapping polygon rasterizing).
The principle of using an incremental error in place of division operations has other applications in graphics.
It is possible to use this technique to calculate the U,V co-ordinates during raster scan of texture mapped polygons.
[4] The voxel heightmap software-rendering engines seen in some PC games also used this principle.
Bresenham also published a Run-Slice computational algorithm: while the above described Run-Length algorithm runs the loop on the major axis, the Run-Slice variation loops the other way.
[5] This method has been represented in a number of US patents: The algorithm has been extended to:
