Bresenham’s Line Algorithm
This is an accurate and efficient raster line-generating algorithm. This algorithm scan
converts lines using only incremental integer calculations. Fig:1 illustrates section of a
display screen where straight line segments are to be drawn. The vertical axes show-scanline positions, and the horizontal axes identify pixel columns. Sampling at unit x intervals in
these examples, we need to decide which of two possible pixel positions is closer to the line
path at each sample step. Starting from the left endpoint shown in fig 1: we need to determine
at the next sample position whether to plot the pixel at position (11, 11) or the one at (11,
12).

To illustrate Bresenham's approach, we first consider the scan-conversion process for lines
with positive slope less than 1. Pixel positions along a line path are then determined by
sampling at unit x intervals. Starting from the left endpoint(x0, y0) of a given line, we step to
each successive column (x position) and plot the pixel whose scan-line y value is closest to
the line path. Assuming we have determined that the pixel at (xk, yk) is to be displayed, we
next need to decide which pixel to plot in column xk+1. Our choices are the pixels at positions
(xk+l, yk) and (xk +l, yk+l).
At sampling position xk+l, we label vertical pixel separations from theFig-3 mathematical
line path as d1and d2 (Fig. 2). They coordinate on the mathematical line at pixel column
position xk+l is calculated as y=m(xk+1) + b
then, d1= y - yk=m(xk+1) + b - yk
and d2= (yk + 1) – y = yk + 1 - m(xk+1) - b
calculate d1-d2
(d1-d2 )=2 m(xk+1) - 2yk + 2b – 1 ➡(I)
If (d1-d2) < 0 then yk+1= yk
If (d1-d2) > 0 then yk+1 = yk+ 1
In the equation (I) substitute ∆y/ ∆x for m multiply throughout by ∆x and call it as pk
(Decision Parameter).
(d1-d2) = 2 ∆𝑦
∆𝑥
. (xk+1) - 2yk + 2b – 1
∆x (d1-d2) = 2 ∆yxk– 2∆x yk+ C
Therefore, pk= 2 ∆yxk– 2∆x yk+ C ➡(II)
where C is a constant and is equal to 2∆y + 2∆xb - ∆x
The sign of pk is the same as the sign of dl –d2, since ∆x>0for our example. Parameter C is
constant and has the value 2∆y + 2∆xb - ∆x, which is independent of pixel position. If the
pixel at yk is closer to the line path than the pixel at yk+ 1 (that is, d1<d2), then decision
parameter pkis negative. In that case, we plot the lower pixel i.e., (xk+l, yk); otherwise, we
plot the upper pixel i.e., (xk +l, yk +l).
At step k + 1, the decision parameter is evaluated from equation (II) as
pk+1 = 2 ∆yxk+1 – 2∆x yk+1 + C ➡(III)
(III) – (II) gives
pk+1 - pk= 2 ∆y(xk+1 - xk) - 2∆x(yk+1 - yk)
But, xk+1 =xk+ 1. So,
pk+1 = pk+ 2 ∆y - 2∆x(yk+1 - yk)
where the term (yk+1 - yk) is either 0 or 1, depending on the sign of parameter pk. The term
(yk+1 - yk) will be 0 if pk is negative or it will be 1 if pk is positive.
Therefore, if pk< 0, pk+1 = pk+ 2∆y
if pk> 0, pk+1 = pk+ 2∆y - 2∆x
This recursive calculation of decision parameters is performed at each integer x-position,
starting at the left coordinate endpoint of the line. The first parameter, p0 is evaluated from
equation II at the starting pixel position (x0, y0) and with m evaluated as ∆𝑦
∆𝑥
,
p0 = 2 ∆yx0 – 2∆x y0 + C , we know that C = 2∆y + 2∆xb - ∆x
p0 = 2 ∆yx0 – 2∆x y0 + 2∆y + 2∆xb - ∆x ➡(IV)
we also know that y0 = mx0 + b, so b= y0 - mx0 = y0 –( ∆𝑦
∆𝑥
) x0
Substituting this for b in equation (IV) we get ,
p0 = 2 ∆yx0 – 2∆x y0 + 2∆y + 2∆x (y0 –
∆𝑦
∆𝑥
x0) - ∆x
On Solving, we get,
p0 = 2∆y - ∆x➡ (V)
Summary of Bresenham's Line-Drawing Algorithm for | m|<1
1. Input the two line endpoints and store the left endpoint in (x0, y0) and right
endpoint in (x1, y1)
2. Plot the pixel at (x0, y0)
3. Calculate constants ∆x, ∆y, 2∆y, 2∆y - 2∆x and obtain the starting value for the
decision parameter as p0 = 2∆y - ∆x
4. At each xkalong the line, starting at k = 0, perform the following test:
If pk< 0, the next point to plot is (xk+l, yk)and
pk+1 = pk+ 2∆y
Otherwise, the next point to plot is (xk +l, yk +l) and
pk+1 = pk+ 2∆y - 2∆x
5. Increment k.
6. Repeat while xk<x
Algorithm
void lineBres (int xa, int ya , int xb, int yb)
{
int dx = abs( xa- xb ) , dy= abs (ya- yb):
int p = 2 * dy- dx ;
inttwoDy= 2 * dy,twoDyDx= 2 * (dy - dx);
intx , y, xEnd;
/*Determine which point to use as start, which asend * /
if(xa>xb )
{
x = xb;
y= yb;
xEnd= xa;
}
else
{
x = xa;
y= ya;
xEnd= xb;
}
setPixel (x, y);
while (x <xEnd)
{
x++;
if (p <0)
{
setPixel(x,y);
p = p +twoDy;
}
else
{
y++;
setPixel(x,y);
p=p+twoDyDx;
}
}
}
0 Response to "Bresenham’s Line Algorithm -MASTER GUIDE"
Post a Comment