Computer Graphics: Bresenham’s Line Generation Algorithm

Link Copied To Clipboard !

bresenhams_line_generation_algorithm Algorithms

Joining two points on any 2 dimensional plane results a line segment. Unfortunately, we can not obtain a line or join two co-ordinate points in Computer Graphics. What we can do is find the intermediate points between these two points and put a pixel for each intermediate points with a desired color.

The computer graphics function uses the output screen as a coordinate system. The TOP-LEFT corner is considered origin(0, 0). On moving right, the x-ordinate increases and on moving down, y-ordinate increases.

What is Bresenham’s Line Generation Algorithm ?

It is an incremental scan conversion algorithm. The big advantage of this algorithm is that, it uses only integer calculations. Moving across the x axis in unit intervals and at each step choose between two different y coordinates.

Bresenham’s Line Generation Algorithm

  1. Start
  2. Input two line end-points and store the left end point at (x1, y1) and right end-point at (x2, y2)
  3. Calculate delta(x) and delta(y) :
    delta(x) = x2 - x1
    delta(y) = y2 - y1
  4. Calculate initial decision parameter as
    p0 = (2 * delta(y)) - delta(x)
  5. if(x2 > x1) then
    set x = x1
    y = y1
    else
    x = x2
    y = y2
  6. Draw pixel at (x, y)
  7. If(delta(x) > delta(y)) i.e. |slope| < 1 then
    compute p0 = 2 * delta(y) - delta(x)
    else
    jump to step 9
  8. Starting at k = 0 to delta(x) times, repeat
    if(pk < 0)
    x(k+1) = x(k) + 1
    y(k+1) = y(k)
    p(k+1) = p(k) + 2*delta(y)
    else
    x(k+1) = x(k) + 1
    y(k+1) = y(k) + 1
    p(k+1) = p(k) + 2*delta(y) - 2*delta(x)
    plot(x(k) + 1, y(k) + 1)
  9. if(delta(y) > delta(x)) i.e. |m| > 1, then
    p0 = 2*delta(x) - delta(y)
    else
    jump to step 10
  10. Starting at k = 0 to delta(y) times, repeat
    if(p(k) < 0)
    x(k+1) = x(k)
    y(k+1) = y(k) + 1
    p(k+1) = p(k) + 2*delta(x)
    else
    x(k+1) = x(k) + 1
    y(k+1) = y(k) + 1
    p(k+1) = p(k) + 2*delta(x) - 2*delta(y)
    plot(x(k)+1, y(k)+1)
  11. Stop

Example Problem Of Bresenham’s Line Generation Algorithm :

Digitize a line with end points (10, 15) and (15, 18) using BLGA :

delta(x) = |15 – 10| = 5

delta(y) = |18 – 15| = 3

|m| = |3/5| < 1

p0 = 2*delta(y) – delta(x) = 2*3 – 5 = 1

since, x2 > x1,

x = x1 = 10

y = y1 = 15

pk = delta(x) * (d1 – d2) : if (d1 – d2) > 0, choose d2 else choose d1.

if p(k) < 0, p(k+1) = p(k) + 2*delta(y) and plot the pixel(x(k)+1, y(k)+1)

if p(k) > 0, p(k+1) = p(k) + 2*delta(y) – 2*delta(x) and plot the pixel (x(k)+1, y(k)+1)

Here, p0 = 1 i.e. p(k) >= 0

p1 = p(k) + 2*delta(y) – 2*delta(x) = 1+6-10 = -3

p1 < 0 so,

p2 = -3 + 2*3 = 3

p2 >=0 so,

p3 = -1

p3 < 0 so,

p4 = 5

Hence,

kxyp(k)plot the screen
010151(11, 16)
11116-3(12, 16)
212163(13, 17)
31317-1(14, 17)
414175(15, 18)

You May Also Like

News Letter