Computer Graphics Tutorial

Introduction of Computer Graphics History of Computer Graphics Types of Computer Graphics Application of Computer Graphics Input Devices Output Devices Display Devices Display Processor Image Representation Color Model Animation Projection Transformation 2D Translation 2D Rotation 2D Scaling 2D Reflection 2D Shearing 3D Translation 3D Rotation 3D Scaling 3D Reflection 3D Shearing Computer Graphics Window Panning Zooming Clipping Line Clipping Point Clipping Text Clipping Polygon Clipping Scan Conversion Line Drawing Algorithm DDA Line Drawing Algorithm Bresenham’s Line Drawing Algorithm Mid-Point Line Drawing Algorithm Scan Conversion of a circle Bresenham’s Circle Drawing Algorithm Midpoint Circle Drawing Algorithm Scan Conversion of an Ellipse Pointing and positioning Techniques Filled Area Primitives

Misc

2D Transformation in Computer Graphics Types of Computer Graphics Resolution in Computer Graphics Anti-aliasing in Computer Graphics Aspect Ratio in Computer Graphics Composite Transformation in Computer Graphics Homogeneous Coordinates in Computer Graphics Illumination Model in Computer Graphics Rendering in Computer Graphics DPI Meaning in Computer What is Double Buffering?

Bresenham’s Line Drawing Algorithm in Computer Graphics
2020-02-20 05:48:45

Bresenham’s Line Drawing Algorithm in Computer Graphics

This algorithm was introduced by “Jack Elton Bresenham” in 1962. This algorithm helps us to perform scan conversion of a line. It is a powerful, useful, and accurate method. We use incremental integer calculations to draw a line. The integer calculations include addition, subtraction, and multiplication.

In Bresenham’s Line Drawing algorithm, we have to calculate the slope (m) between the starting point and the ending point.

Bresenham’s Line Drawing Algorithm

As shown in the above figure let, we have initial coordinates of a line = (xk, yk)

The next coordinates of a line = (xk+1, yk+1)

The intersection point between yk and yk+1 = y

Let we assume that the distance between y and yk = d1

The distance between y and yk+1 = d2

Now, we have to decide which point is nearest to the intersection point.                             

If m < 1

    then x = xk+1    { Unit Interval}

                      y = yk+1   { Unit Interval}                     

As we know the equation of a line-

y = mx +b

Now we put the value of x into the line equation, then

y = m(xk+1) +b                 …………. (1)

The value of d1 = y - yk

Now we put the value of d1 in equation (1).

y = m (xk+1) +b - yk

Now, we again put the value of y in the previous equation then we got,

d2 = yk+1 – y

    = yk + 1 – m (xk+1) – b

Now, we calculate the difference between d1 – d2

If d1 < d2

Then yk+1 = yk                         {we will choose the lower pixel as shown in figure}  

If d1 => d2

Then yk+1 = yk+1                     {we will choose the upper pixel as shown in figure}

Now, we calculate the values of d1 - d2

(d1 - d2)= m (xk+1) +b - yk - yk - 1 + m (xk+1) + b

We simplified the above equation and replaced the m with ?y/?x.

(d1 - d2) = 2 m (xk+1) -2yk + 2b-1

We multiplied ?x at both side then we got,

?x (d1 - d2) = ?x (2m (xk+1) -2yk + 2b-1)

We consider ?x (d1 - d2) as a decision parameter (P­k), so

pk = ?x (d1 - d2)

After calculation we got,

Pk = 2?yxk + 2?y - 2?xyk +?x (2b-1)

Then, the next coordinate of pk

pk+1 = 2?yxk+1 + 2?y - 2?xyk+1 +?x (2b-1)

 Now, the difference between pk+1 – pk then,

pk+1 – pk = 2?y (xk+1-xk) – 2?x (yk+1-yk)

pk+1 = pk + 2?y (xk+1-xk) – 2?x (yk+1-yk)        {Decision parameter coordinate}

Now, we put the value of xk+1 in above equation then we got,

 pk+1 = pk + 2?y – 2?x (yk+1 - yk)         {New decision parameter when m <1}    

Similarly, if m >1, the new decision parameter for next coordinate will be

pk+1 = pk + 2?y – 2?x (xk+1 - xk)          {New decision parameter when m >1}

If pk >= 0                                                 {For coordinate y}

Then,

yk+1 = yk+1                                                {We will choose the nearest yk+1 pixel}

The next coordinate will be (xk+1, yk+1)

If pk < 0

Then,

yk+1 = yk                                                                                 {We will choose the nearest yk pixel}

The next coordinate will be (xk+1, yk)

Similarly,

If pk >= 0                                                   {For coordinate x}

Then,

xk+1 = xk+1                                                 {We will choose the nearest xk+1 pixel}

The next coordinate will be (xk+1, yk+1)

If pk < 0

Then,

xk+1 = xk                                                                               {We will choose the nearest xk pixel}

The next coordinate will be (xk, yk+1)

Algorithm of Bresenham’s Line Drawing Algorithm

Step 1: Start.

Step 2: Now, we consider Starting point as (x1, y1) and endingpoint (x2, y2).

Step 3: Now, we have to calculate ?x and ?y.

              ?x = x2-x1

                    ?y = y2-y1

              m = ?y/?x               

Step 4: Now, we will calculate the decision parameter pk with following formula.

                       pk = 2?y-?x

Step 5: Theinitial coordinates of the line are (xk, yk), and the next coordinatesare (xk+1, yk+1). Now, we are going to calculate two cases for decision parameter pk

 Case 1:  If

                         pk < 0

              Then

                          pk+1 =pk +2?y

                          xk+1 = xk +1

                          yk+1 = yk                           

Case 2:  If

                         pk >= 0

              Then

                          pk+1 =pk +2?y-2?x

                          xk+1 =xk +1

                          yk+1 =yk +1                          

Step 6: We will repeat step 5 until we found the ending point of the line and the total number of iterations =?x-1.

Step 7: Stop.

Example: A line has a starting point (9,18) and ending point (14,22). Apply the Bresenham’s Line Drawing algorithm to plot a line.

Solution: We have two coordinates,

Starting Point = (x1, y1) = (9,18)

Ending Point = (x2, y2) = (14,22)

Step 1: First, we calculate ?x, ?y.

           ?x = x2 – x1 = 14-9 = 5

             ?y = y2 – y1 = 22-18 = 4

Step 2: Now, we are going to calculate the decision parameter (pk)

   pk = 2?y-?x

                  = 2 x 4 – 5 = 3

             The value of pk = 3

Step 3: Now, we will check both the cases.

               If

                   pk >= 0

Then

         Case 2 is satisfied. Thus

                    pk+1 = pk +2?y-2?x =3+ (2 x 4) - (2 x 5) = 1

                     xk+1 =xk +1 = 9 + 1 = 10

           yk+1 =yk +1 = 18 +1 = 19

Step 4: Now move to next step. We will calculate the coordinates until we reach the end point of the line. 

?x -1 = 5 – 1 = 4

          pk          pk+1          xk+1           yk+1
9 18
3 1 10 19
1 -1 11 20
-1 7 12 20
7 5 13 21
5 3 14 22

Step 5: Stop.

Bresenham’s Line Drawing Algorithm

The Coordinates of drawn lines are-

P1 = (9, 18)

P2 = (10, 19)

P3 = (11, 20)

P4 = (12, 20)

P5 = (13, 21)

P6 = (14, 22)

Advantages of Bresenham’s Line Drawing Algorithm

  • It is simple to implement because it only contains integers.
  • It is quick and incremental
  • It is fast to apply but not faster than the Digital Differential Analyzer (DDA) algorithm.
  • The pointing accuracy is higher than the DDA algorithm.

Disadvantages of Bresenham’s Line Drawing Algorithm

  • The Bresenham’s Line drawing algorithm only helps to draw the basic line.
  • The resulted draw line is not smooth.