Page 42 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Lab on Computer Graphics

Notes Bresenham’s algorithm begins with the point (0, 0) and “illuminates” that pixel. Since x is the
DA in this example, it then increments the x coordinates by one. Rather than keeping track of
the y coordinate (which increases by m = ∆y/∆x, each time the x increases by one), the algorithm
keeps an error bound at each stage, which represents the negative of the distance from the point
where the line exits the pixel to the top edge of the pixel. This value is first set to m − 1, and is
incremented by m each time the x-coordinate is incremented by one. If becomes greater than
zero, we know that the line has moved upwards one pixel, and that we must increment our y
coordinate and readjust the error to represent the distance from the top of the new pixel – which
is done by subtracting one from The reader can examine the above illustration and the table to
see the complete operation of the algorithm on this example:

(x, y)  description
(0, 0) –0.4 illuminate pixel (0, 0)
0.2 increment  by 0.6
(1, 0) increment x by 1
(1, 0) 0.2 illuminate pixel (1, 0)
since  > 0
(1, 1) increment y by 1
–0.8 decrement  by 1
–0.2 increment  by 0.6
(2, 1) increment x by 1
(2, 1) –0.2 illuminate pixel (2, 1)
0.4 increment  by 0.6
(3, 1) increment x by 1
(3, 1) 0.4 illuminate pixel (3, 1)
since  > 0
(3, 2) increment y by 1
–0.6 decrement  by 1
0.0 increment  by 0.6
(4, 2) increment x by 1
(4, 2) 0, 0 illuminate pixel (4, 2)

Assuming that the DA is the x-axis, an algorithmic description of Bresenham’s algorithm is as
follows:

Bresenham’s Algorithm
The points (x 1 , y 1 ) and (x 2 , y 2 ) are assumed not equal and integer valued. The ε is supposed to
be real.
Let ∆x = x 2 – x 1
Let ∆y = y 2 – y 1
Dy
Let m =
Dx
Let j = y 1
Let  = m – 1

for i = x 1 to x 2 – 1
illuminate (i, j)
if ( ≥ 0)
j + = 1
 + = 1.0

36 LOVELY PROFESSIONAL UNIVERSITY