20-03-2012, 04:04 PM
BRESHENHAM’S ALGORITHM
Bresenhams-Algorithm.pdf (Size: 110.09 KB / Downloads: 162)
Overview
The basic ”line drawing” algorithm used in computer graphics is Bresenham’s Algorithm. This algorithm
was developed to draw lines on digital plotters, but has found wide-spread usage in computer graphics.
The algorithm is fast – it can be implemented with integer calculations only – and very simple to describe.
Bresenham’s Algorithm
Consider a line with initial point (x1, y1) and terminal point (x2, y2) in device space. If x = x2 −x1
and y = y2 − y1, we define the driving axis (DA) to be the x-axis if |x| |y|, and the y-axis
if |y| > |x|. The DA is used as the “axis of control” for the algorithm and is the axis of maximum
movement. Within the main loop of the algorithm, the coordinate corresponding to the DA is incremented
by one unit. The coordinate corresponding to the other axis (usually denoted the passive axis or PA) is only
incremented as needed.
The Integer Bresenham’s Algorithm
Bresenham’s Algorithm, as given in the previous section, requires the use of floating point arithmetic to
calculate the slope of the line and to evaluate the error term. We note that is initialized to
Bresenham’s Algorithm for Lines with Arbitrary Endpoints
Bresenham’s algorithm, as described in the sections above, is limited by the fact that the lines to be drawn
have endpoints with integer coordinates. In this section, we consider a version of Bresenham’s algorithm
for lines that have endpoints with real coordinates. The only problem to overcome is the initial setting of the
error. Once this is done, the algorithm proceeds as before.
Specifying the Driving Axis
If x is the driving axis, Bresenham’s algorithm produces only one illuminated cell per column in the
matrix of pixels. This feature allows the algorithm to be useful in the rasterization of polygons in image
space. In this algorithm, we require only one illuminated pixel per row be produced – which is possible with
Bresenham’s algorithm by fixing the driving axis as the y axis. This can be done by a simple change to the
main loop of the algorithm.