Home » Computer Graphics

Bresenham's Line Drawing Algorithm in Computer Graphics

Computer Graphics | Bresenham's Line Drawing Algorithm: In this tutorial, we will learn about the Bresenham's line drawing algorithm. Also, we will be learning about how it is implemented in drawing a line by defining its entire algorithm, and also by taking some examples. Finally, we would be discussing the advantages and disadvantages of this algorithm.
Submitted by Monika Sharma, on April 24, 2020

Bresenham's algorithm was proposed to overcome the drawbacks of the DDA algorithm. First, let us see what the drawbacks of DDA algorithm were,

Drawbacks of DDA algorithm:

The only drawback of the DDA algorithm was that it produces floating-point results which reduces the overall complexity. This problem was solved by Bresenham's line drawing algorithm.

Introduction to Bresenham's Algorithm

Bresenham's line drawing algorithm is a second method of generating a line that was proposed after the DDA algorithm to overcome its limitations and drawbacks. It was developed by J.E. Bresenham in 1962. This algorithm is used for calculating intermediate coordinate points between the given source and ending points by only using integer addition and subtraction.

This algorithm determines the points which should be selected to form a close approximation to a line between two points.

It is also an incremental method for creating a line.

It is faster than the DDA algorithm as it does not involves the use of heavy operations such as multiplication and division.

Working of the Bresenham's Algorithm

Suppose we have to draw a line PQ with coordinates P (x1, y1) and Q (x2, y2).

To draw the line using Breshenam's line drawing algorithm, first of all, calculate the slope of the line from the given coordinates by using,

    m = dy/dx
    Where,
    dy = x2 - x1
    dx = y2 - y1

There can be three values of slope (m) i.e.

    a. m < 1
    b. m > 1
    c. m = 1

On the basis of the value of the slope, the decision parameter is calculated which gives the decision about the selection of the next pixel point which has the least distance from the true line.

We'll be deriving the decision parameter Pk for slope (m < 1), to make things clear.

Derivation of the decision parameter Pk

Let us consider a straight line passing through a point A (xk+1, y),

Where,

    xk+1 = xk + 1 

and y satisfies the equation of the line i.e.

    y = m (xk + 1) + c             ------(1)

The next pixel to the line will be either to its top or to its bottom.

If we choose the top pixel, the points at B will become,

    xk+1 = xk + 1     and      y = yk + 1 

If we choose bottom pixel, the points at C will become,

    xk+1 = xk + 1     and      y = yk

Since Bresenham's algorithm depends upon the distance, let's calculate it between A and B; and A and C.

For A and B: let the distance be denoted as s.

    s = ( yk + 1 ) - y

For A and C: let the distance be denoted as t.

    t = y - yk

Now consider their difference:

    (t – s) =  y - yk - [ (yk + 1) - y]
    = 2y - 2yk - 1                  ------(2)

When (t - s) < 0 => t < s, then the closest pixel will be C.

When (t - s) > 0 => s < t, then the closest pixel will be B.

Putting the value of eq.(1) in eq.(2);

t – s = 2m ( xk + 1 ) + 2c - 2yk - 1

Now, substituting the value of m;

t – s = 2dy ( xk + 1 ) / dx + 2c - 2yk - 1

To remove dx from denominator, multiply dx on both sides;

dx (t - s) = dx ( 2dy ( xk + 1 ) / dx + 2c - 2yk – 1 )

let Pk = dx (t - s), thus introducing the decision variable

Pk = 2dy . xk - 2dx . yk + b

B = 2dy + dx ( 2c – 1 )

Let us calculate next decision variable:

Pk+1 = 2dy . xk+1 - 2dx . yk+1 + b

Now, solve the difference Pk+1 - Pk

Pk+1 - Pk = 2dy . xk+1 - 2dx . yk+1 + b - ( 2dy . xk - 2dx . yk + b )

              = 2dy . xk+1 - 2dx . yk+1 - 2dy . xk - 2dx . yk

Since xk+1 = xk + 1

Pk+1 - P= 2dy . (xk + 1) - 2dx . yk+1 - 2dy . xk - 2dx . yk

 Pk+1   =  Pk + 2dy - 2dx . yk+1 - 2dx . yk

Special Cases:

When Pk >= 0 => yk+1 = yk + 1          i.e. point B is chosen

Pk+1 = Pk + 2dy - 2dx

When Pk < 0 => yk+1 = yk                          i.e. point C is chosen

Pk+1 =  Pk +2dy

Now, we will calculate the initial decision variable by using

P= dx ( 2dy ( x0 + 1 ) / dx + 2c - 2y0 – 1 )

Put c = y0 - x0. ( dy / dx )

We get

P=  2dy – dx

Algorithm:

Step1: Start

Step2: Declare x1, y1, x2, y2.

Step3: Calculate dx = x2 - x1

                               Dy = y2 - y1

Step 4: Calculate slope, m = dy / dx.

Step5: For m < 1: Calculate initial decision variable: P = 2dy - dx.

Step6: while (x1 <= x2)

           if(P < 0):

                  xk = xk + 1

                  P = P + 2dy

                  yk = yk

             else :

                  xk = xk + 1

                  P = P + 2dy - 2dx

                  yk = yk + 1

Step 7: Plot ( xk , yk )

Step 8: End

Advantages of Bresenham's Algorithm

  • It is faster because it does not involve floating-point calculations.
  • It involves only integer arithmetic. Hence, it is easier to implement.

Disadvantages of Bresenham's Algorithm

  • It also does not provide smooth lines though accuracy has been improved.





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.