Introduction
The Bresenham’s Algorithm for drawing lines on the discrete plane, such as computer monitor is one of the fundamental algorithms in computer graphics.
This algorithm provides the means for the fast and efficient way to represent continuous abstract lines onto discrete plane of computer display. This process is called rasterization.
Assume y = mx + b represents the real variable equation of a line which is to be plotted using a grid of pixels where the two points (x1, y1) and (x2, y2) have integer coordinates and represent two known points on the line.
The algorithm basically approximates real valued line by calculating what pixels to illuminate and to provide "illusion" of line.
Since the pixels are sufficiently small, the approximation is good enough to "trick" the human eyes and to get illusion of a real line.
Figure A shows the real line drawn over the pixel grid.
The Figure B shows how the same line is approximated by "illuminating" particular pixels.
Figure A. 
Figure B. ________________________________________________________________Figure a, below shows all the possible intersecting pixels to the real line and Figure b shows only pixels that are selected for digitized line.
Derivation of Bresenham’s Line Drawing Algorithm
Given two endpoints (x1, y1) and (x2, y2), we can chose the start point (xk, yk).
The choice is purely arbitrary, it can be either of (x1, y1) and (x2, y2) points.
From this start point or pixel, we have eight possible choices for the next pixel in the line, since each pixel is surrounded by 8 other pixels (except border pixels).
We need to isolate these eight choices into only two choices.If we restrict the slope m for now to 0 <= m <=1 and assume x1 < y =" m*(xk+1)"
To derive Bresenham’s algorithm, we begin with the common slope-intercept formulation of a line, Where the slope is simply the ratio of the change in y to the change in x. That is,
y = mx + b
y = (∆x/∆y)x + b ……(1)
The constant b is the value of y at which the line intercepts the Y -axis;
Thus, (0, b) is a point on the line.
Here, ∆x and ∆y might be obtained using two distinct points on the line, as we shall do below. Observe that equation (1) represents y as a function of x, and can express every line in the plane except for a vertical line, which essentially corresponds to an infinite slope.
Alternatively, we can rearrange the equation so that it provides an implicit representation of the line. In particular, we may write
F (x, y) = ∆yx − ∆xy + ∆xb = 0 ………(2).
Figure 1: (Left) The implicit function F that defines the line also partitions the plane into three regions; F (x, y) <> 0 below the line. (Right) Starting at point (x0, y0) the next point to be rasterized in drawing the line will be either (x0 + 1, y0 ) or (x0 + 1, y0 + 1). The choice depends upon whether F (x0 + 1, y0 + ½) is positive or negative
This function specifies the very same line, but implicitly; that is, any point (x, y) that satisfies F (x, y) = 0 is on the line, but F does not specify how to compute y given x, or vice versa.
In addition to specifying the line, the function F assumes a different sign at points that lie on different sides of the line. In particular, F (x, y) <> 0 when (x, y) lies below the line. See Figure 1. This is the property that Bresenham’s algorithm exploits in determining which pixels best approximates a give line.
Now consider the figure on the right of Figure 1. This depicts the first pixel on the line segment, at (x0 , y0 ), and the first “decision” that the algorithm must make; namely, should the next pixel be (x0 + 1, y0 ), or (x0 + 1, y0 + 1). These are the only two logical choices, given that the slope of the line is between 0 and 1. To make this decision, we simply consider the point that is midway between the two possibilities and determine whether this point is “above” or “below” the line; that is, we look at the sign of F (x0 + 1, y0 + 1 ). We shall call the resulting value of F the decision variable, as it will be used to decide between the two possible pixels to select next. Note that the magnitude of the decision variable is irrelevant – only its sign is needed to make the decision. Plugging the coordinates of the intermediate point into F and simplifying, we have
F (x0 + 1, y0 + 1/2 ) = ∆y (x0 + 1) − ∆x (y0 +1/2 )+ ∆xb ………….(3)
= (∆y x0 − ∆x y0 + ∆x b)+ (∆y − 2 ∆x) ……….(4)
= F (x0, y0) + (∆y – 1/2 ∆x) ………. (5)
= ∆y – 1/2 ∆x,…………….(6)
Where, the final simplification is due to the fact that F (x0, y0) = 0, since the point (x0, y0) is on the line. Finally, since it is only the sign of this value that we care about, not its magnitude, we can simplify it a bit by multiplying by 2. Thus, our first decision variable is
D = 2 ∆y − ∆x. …………..(7)
The decision variable in equation (7) allows us to make the first decision – that is, should the second pixel have the same y value as the first, or is it 1 higher? But what about subsequent decisions? In all cases we could simply compute F at the intermediate point and look at its sign.
However, there is a slightly more efficient method, namely incremental computation. Instead of computing the value of F anew at each decision point, we simply compute how it differs from the previous decision variable.
Figure 2: As the rasterization process proceeds, we compute each decision variable incrementally from the previous decision variable. The increment depends on the previous decision that was made. Both lines L1 and L2 above would result in one increment for moving from Dk to Dk+1 , and lines L3 and L4 would resulting a different increment in moving from Dk to D’k+1
Figure 2 depicts three potential decision points and their corresponding decision variables, Dk ,
Dk+1 and D’k+1
Assuming that Dk has already been computed, which of Dk+1 and D’k+1 should be computed next, and how do they differ from Dk? The differences are easy to compute, as follows:
F (x + 2,y +3/ 2 ) − F (x + 1,y +1/ 2 ) = ∆y − ∆x …..(8)
F (x + 2,y + 1/2 ) − F (x + 1,y +1/ 2 ) = ∆y ….(9)
To keep the increments consistent with our previous definition of D, we must again multiply them by two. We can now give the complete algorithm
Rasterize the line from (x0, y0) to (x1, y1), where all coordinates are integers that satisfy x0 ≤ x1, y0 ≤ y1 and y1 − y0 ≤ x1 − x0. Thus, the line is assumed to run from left to right and have a slope between 0 and 1 (i.e. between 0 and 45 degrees). Lines of all other slopes can be handled using minor variations of this code.
function Bresenham’s ( x0 , y0 , x1 , y1 )
1 ∆x ← x1 − x0
2 ∆y ← y1 − y0
3 D ← 2∆y − ∆x
4 x ← x0
5 y ← y0
6 PutPixel ( x, y )
7 while x < x1 do
8 x ← x +1
9 if D < 0 then
10 D ← D + 2∆y
11 else
12 y ← y +1
13 D ← D + 2(∆y − ∆x)
14 endif
15 PutPixel ( x, y )
16 endwhile
_____________________________________________________________
Bresenham Algorithm for line with slope from -1 to 1
In the previous derivation when we checked the decision variable, we always incremented x and y by positive one. The dX and dY values are always positive regardless of which line is chosen (with slope from -0 to 1). If we keep the start point as point (x1, y1), we can determine the sign of the values to increment. If x1
good explanations
ReplyDelete