Logo

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.

Related Topics

Pointing and Positioning Technique Computer Graphics

Pointing and Positioning Technique: The pointing and positioning are interactions used in computer graphics. A pointing device is also called a Pointing tool. A pointing tool is a hardware component,...

4 minutes read.

Panning

“Panning is a process or photographic technique that is used to combine slow shutter speed with camera movement to make a speed sense around the moving object.” We can define panning as...

2 minutes read.

Line Clipping in Computer Graphics

The line clipping is a process in which we can cut the part of the line, which lies outside the view pane. Only those lines are visible, which lie inside the view pane....

13 minutes read.

Clipping in Computer Graphics

“The Clipping is a type of transformation used in computer graphics to remove lines, objects, and segments of lines that are outside the computer screen or viewing pane.” The clipping is a...

2 minutes read.

Rendering in Computer Graphics

Rendering in Computer Graphics Rendering is the operation, by virtue of a software system, of creating a picture from a template. In a specifically defined term or information structures, the model is a...

9 minutes read.

3D Shearing

We can denote shearing with ‘SHx,’ ‘SHy,’ and ‘SHz.’ These ‘SHx,’ ‘SHy,’ ‘SHz’ are called “Shearing factor.” The basic difference between 2D and 3D Shearing is that the 3D plane also...

1 minute read.

Color Models in Computer Graphics

"Color model is a 3D color coordinate system to produce all range of color through the primary color set." There are millions of colors used in computer graphics. The light...

3 minutes read.

Homogenous Coordinates in Computer Graphics

Homogenous Coordinates in Computer Graphics The orbit of a point, a line graph or the whole picture on the computer, a point besides the origin, is accomplished by first shifting the...

7 minutes read.

Scan Conversion in Computer Graphics

“When we represent regular objects in the form of discrete pixels, it is called Scan Conversion.” Every graphics system must transform the primitives into a collection of pixels. The scan conversion is also...

2 minutes read.

Point Clipping

“Point clipping is a process which is used to define the point position.” The point is either inside the view pane (window) or outside the view pane. In computer graphics, the computer...

2 minutes read.

History of Computer Graphics

History of Computer Graphics Computer Graphics (CG) was first developed as a visualization tool. Computer graphics were basically introduced for scientists and engineers in government and corporate research centers, i.e., Bell Labs and Boeing...

4 minutes read.

Midpoint Circle Drawing Algorithm in Computer Graphics

The midpoint circle drawing algorithm helps us to calculate the complete perimeter points of a circle for the first octant. We can quickly find and calculate the points of other...

12 minutes read.

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...

8 minutes read.

2D Translation

We can move any object from one to another place without changing the shape of the object. For Example- Translation of a Point:If we want to translate a point from P (x0,...

1 minute read.

Scan Conversion of a Circle Computer Graphics

A circle is an eight-way symmetric shape. All quadrants of a circle are the same. There are two octants in each quadrant of a circle. If we know the value of any...

3 minutes read.

Input Devices in Computer Graphics

An Input device is the piece of computer hardware equipment used to give input to the computer. The input can be in the form of graphics, text, sound, audio, video,...

7 minutes read.

Animation in Computer Graphics

The word Animation is extracted from a Latin language, "Anima," which means "Soul." TheAnimation is a technology that allows any image object, an entity to walk, talk, or do some...

3 minutes read.

3D Translation

A 3D Translation process contains the x-axis, y-axis, and z-axis. We can move any object from one place to another without changing the shape of the object. For Example-Translation of a...

1 minute read.

Text Clipping

“Text Clipping is a process in which we remove those part (portion) of string that is outside the view pane (window).” Various methods and techniques can do the text clipping. These techniques depend...

2 minutes read.

Display Processor

It is a part of hardware or interpreter which is used to transform display processor code into pictures. It is used to convert digital information from CPU to analog data. It...

4 minutes read.