BRESENHAM'S LINE ALGORITHM
An accurate and efficient raster linegenerating 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
scanconverting 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 scanconversion 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 (x_{0}, y_{0}) of a given line, we step to each
successive column (x position) and plot the pixel whose scanline 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 (x_{k}, y_{k})
is to be displayed, we next need to decide which pixel to plot in the column x_{k+1.
}Our choices are the pixels at positions (x_{k} + 1, y_{k})
and (x_{k}+1, y_{k}+1)
At sampling position x_{k+1} we label vertical pixel seprations
from the mathematical line path as d_{1 }and d_{2}. The y
coordinate on the mathematical line at pixel column position x_{k}+1 is
calculated.
x

Y = m (x_{k}+1)
+ b
Then
d_{1 }= y  y_{k}
_{ } y

= m (x_{k}+1) + b  y_{k}
and
d_{2 }= (y_{k }+ 1) – y
= y_{k }+ 1 – m (x_{k}+1) + b
The difference between these two separations is
d_{1}  d_{2}= m (x_{k} + 1) + b  y_{k}y_{k}1
+ m (x_{k} + 1) + b
= 2m (x_{k}+ 1) 
2y_{k }+ 2b 1
A decision parameter p_{k }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
p_{k} = ∆x(d_{1}d_{2})
= 2∆yx_{k} + 2∆y  2∆x y_{k} + ∆x (2b 1 ) ————— 1
= 2∆yx_{k}  2∆xy_{k} + c
The sign of p_{k} is the same as the sign of d_{1}  d_{2},
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 p_{k}. If the pixel at y_{k} is
closer to the line path than the pixel at y_{k} + 1 (that is d_{1} < d_{2}), then decision
parameter p_{k} 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
p_{k+1} = 2∆yx_{k+1}  2∆xy_{k+1} + c
Now,
p_{k+1}  p_{k} = 2∆y (X_{k+1}  x_{k})
 2∆x (y_{k+1}  y_{k})
but x_{k+1} = x_{k} + 1,
therefore p_{k+1} = p_{k} + 2∆y  2∆x (y_{k+1} 
y_{k})
where the term y_{k}+i  y_{k} is either 0 or 1,
depending on the sign of parameter p_{k}.
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 p_{o}, is
evaluated from the equation no. 1 at the starting pixel positions (x_{0},
yo) that is when x = 0 and y = 0 and with m evaluated as ∆y / ∆x:
p_{0} = 0+2∆y0 + ∆x
(01)
= 2∆y  ∆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 LineDrawing Algorithm for I m I < 1
1. Read the line end points (x_{1}, y_{1})
and (x_{2}, y_{2}) such that they are not equal. If equal then
plot that point and exit.
2. ∆x= Ix_{2} x_{1}I
and ∆y = Iy_{2} y_{1}I
3. x = x_{1}
y = y_{1}
4. e = 2∆y  ∆x
5. i = 0
6. Plot (x,y)
7. While e ≥ 0then
{
y = y+1
e = e  2∆x
}
x = x+ 1
e = e + 2∆y
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 = 1610 = 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 (x_{1,}y_{1})
and (x_{2,}y_{2}) 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 (x_{1,}y_{1}) and (x_{2,}y_{2})
such that they are not equal. If equal then plot that point and exit.
2. ∆x= Ix_{2} x_{1}I
and ∆y= Iy_{2} y_{1}I
3. Initialize starting point
x = x_{1}
y = y_{1}
4. s_{1} = sign (x_{2} x_{1})
s_{2} = sign (y_{2} y_{1})
5. If
∆y > ∆x then
temp = ∆x
∆x = ∆y
∆y = temp
ex_change =1
else
ex_change = 0
end if
6. e = 2∆y  ∆x
7. i = 0
8. Plot (x, y)
9. while
(e ≥ 0)
{if (ex_change = 1 then
x = x + s_{1}
else
y = y + s_{2}
end if
e = e  2∆x
}
10. if ex_change = 1 then
y = y + S_{2 }
else
X = X + s_{1}
end if
e = e + 2∆y
11. i = i + 1
12. If i ≤ ∆x then go to step 8
13. Stop
No comments:
Post a Comment