More info

Saturday, 15 February 2014

Computer Graphics Notes - Lab 12 - Bresenham's Line Algorithm

BRESENHAM'S LINE ALGORITHM
An accurate and efficient raster line-generating algorithm, developed by Bresenham, scans converts lines using only incremental integer calculations that can be adapted to display circles and other curves. Bresenham's line algorithm uses only integer addition and subtraction and multiplication by 2 and we know that the computer can perform the operations of integer addition and subtraction very rapidly. Therefore, it is an efficient method for scan-converting straight lines. The basic principle of Bresenham's line algorithm is to select the optimum raster locations to represent a straight line. To accomplish this, the line algorithm always increments either x or y by 1 unit depending on the slope of line. The increment in the other variable is determined by examining the distance between the actual line location and the nearest pixel.

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 end-point (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. The figure below demonstrates the kth step in this process. Assuming we have determined that the pixel at (xk, yk) is to be displayed, we next need to decide which pixel to plot in the column xk+1. Our choices are the pixels at positions (xk + 1, yk) and (xk+1, yk+1)




At sampling position xk+1 we label vertical pixel seprations from the mathematical line path as d1 and d2. The y coordinate on the mathematical line at pixel column position xk+1 is calculated.




             x
        -----------
Y = m (xk+1) + b
Then
d= y - yk
                y
        -------- 
= m (xk+1) + b - yk
and
d= (y+ 1) – y
    = y+ 1 – m (xk+1) + b
The difference between these two separations is
d1 - d2= m (xk + 1) + b - yk-yk-1 + m (xk + 1) + b
         = 2m (xk+ 1) - 2yk + 2b -1

A decision parameter pk for the kth step in the line algorithm can be obtained by rearranging the above equation so that it involves only integer calculations. We accomplish this by substituting m = ∆y / ∆x where ∆y and ∆x are the vertical and horizontal separations of the endpoint positions, and defining

pk = ∆x(d1-d2)
= 2∆yxk + 2∆y - 2∆x yk + ∆x (2b -1 ) ————— 1
= 2yxk - 2xyk + c

The sign of pk is the same as the sign of d1 - d2, since ∆x > 0 for our example. Parameter c is constant and has the value 2∆y + ∆x (2b -1) which is independent of pixel position and will be eliminated in the recursive calculations for pk. If the pixel at yk is closer to the line path than the pixel at yk + 1 (that is d1 < d2), then decision parameter pk is negative. In this case, we plot the lower pixel; otherwise we plot the upper pixel.

Coordinate changes along the line occur in unit steps in either the x or y directions. Therefore, we can obtain the values of successive decision parameter using incremental integer calculations. At step k + 1, the decision parameter is evaluated from the above equation as
pk+1 = 2∆yxk+1 - 2∆xyk+1 + c
Now,
pk+1 - pk = 2∆y (Xk+1 - xk) - 2∆x (yk+1 - yk)
but xk+1 = xk + 1,
therefore pk+1 = pk + 2∆y - 2∆x (yk+1 - yk)
where the term yk+i - yk is either 0 or 1, depending on the sign of parameter pk.

The recursive calculation of decision parameters is performed at each integer x position, starting at the left coordinate endpoint of the line. The first parameter po, is evaluated from the equation no. 1 at the starting pixel positions (x0, yo) that is when x = 0 and y = 0 and with m evaluated as ∆y / ∆x:
p0 = 0+2y-0 + x (0-1)
    = 2y - x

We can summarize Bresenham's line drawing for a line with a positive slope less than 1 in the following listed steps. The constants 2∆y and 2∆y - ∆x are calculated once for each line to be scan converted, so as the arithmetic involves only integer addition and subtraction of these two constants.




Bresenham's Line-Drawing Algorithm for I m I < 1

1.     Read the line end points (x1, y1) and (x2, y2) such that they are not equal. If equal then plot that point and exit.
2.     ∆x= Ix2- x1I and ∆y = Iy2- y1I
3.     x = x1
y = y1
4.     e = 2y - x
5.     i = 0
6.     Plot (x,y)
7.     While e ≥ 0then
{
y = y+1
e = e - 2x
}
x = x+ 1
e = e + 2y
8.     i = i + 1
9.     If i ≤ ∆x then go to step 6
10.   Stop

Example
Consider the line from (20, 10) and (30, 18). Use the Bresenham's algorithm to rasterize the line.
x= 10
y = 8
x = 20
y=10
e = 16-10 = 6

I
Plot
x
y
e


20
10
6
0
(20,10)
21
11
2
1
(21,11)
22
12
-2
2
(22,12)
23
12
14
3
(23,12)
24
13
10
4
(24,13)
25
14
6
5
(25,14)
26
15
2
6
(26,15)
27
16
-2
7
(27,16)
28
16
14
8
(28,16)
29
17
10
9
(29,17)
30
18
6
10
(30,18)
31
19
2

Endpoint pixel positions for the line are passed to this procedure, and pixels are plotted from the left endpoint to the right endpoint.

For a line with positive slope greater than 1, we interchange the roles of the x and y direction. That is, we step along the y direction in unit steps and calculate successive x values nearest the line path.

Generalized integer Bresenham's algorithm for all quadrants the line end points (x1,y1) and (x2,y2) assumed not equal all variables are assumed integer the sign function returns -1, 0, 1 as its argument is <0, =0, or >0

1.     Read the line end points (x1,y1) and (x2,y2) such that they are not equal. If equal then plot that point and exit.
2.     ∆x= Ix2- x1I and ∆y= Iy2- y1I
3.     Initialize starting point
       x = x1
y = y1
4.     s1 = sign (x2- x1)
       s2 = sign (y2- y1)
5.     If ∆y > ∆x then
temp = ∆x
∆x = ∆y
∆y = temp
ex_change =1
else
ex_change = 0
end if
6.     e = 2y - x
7.     i = 0
8.     Plot (x, y)
9.     while (e ≥ 0)
{if (ex_change = 1 then
x = x + s1
else
y = y + s2
end if
e = e - 2x
}
10.   if ex_change = 1 then
y = y + S2
else
X = X + s1
end if
e = e + 2y
11.   i = i + 1
12.   If i ≤ ∆x then go to step 8
13.   Stop





No comments:

Post a Comment