Bresenham's Line Drawing Algorithm

-

 • Bresenham's line drawing algorithm came into existence because DDA line drawing algorithm use to give more of decimal (floating) point numbers. 

• Which were round off to integer data type (int) because decimal number cannot be plotted on the screen.

•Due to rounding off the coordinate the output of line would be more in zig-zag form.


Explanation:

1) Consider 

    •dA= Above the line point.

    •dB= Below the line point.


2) so point can be above or below the line.

3) In this algorithm we will make a precise decision regarding the point above or below 

4) let decision variable be e 

    • e= dB - dA 

5) Where  if:      e<0 

    when        :     dB<dA

    Because: It will be below the point of line.

         •  if:          e>0

 When   

:         dB>=dA.  

 Because: Above the point of line.


Algorithm:

1) Start

2) Find slope of line i.e m, 

      m= y2-y1/x2-x1.

3) Find decisions variable e,

           e0= 2dy - dx.

4) To Find dy and dx,

            dy= y2-y1 

            dx= x2-x1.

5) if m<1 :

           a) if e0<0:

                  X2=x1 +1 

                  Y2= y1

//(No change in Y2)

              e1= e0 +2dy


          b) else e0>=0:

                  X2=x1 +1 

                 Y2= y1 +1

   e1= e0 +2dy - 2dx.

Note: x1 and y1 are the initial coordinates of line and will be input by the user itself. (Will also solve numerical there you will understand it more properly).

6) if m>=1 :

                a) if e0<0:

                      X2=x1(No change)

             Y2= y1 +1

             e1= e0 +2dx

                b) else e0>=0:

                X2=x1 +1 

                 Y2= y1 +1

   e1= e0 +2dx - 2dy.

7) repeat from 5 to 6 till you get the end points, but remember one thing slope of line m we will once and check once only.

Note: slope of line is always same for any two co-ordinates of line.

8) Stop.

                

Numerical:

1) Given: (1,1) (5,3).

 2) x1= 1  and y1= 1.

     x2= 5  and y2= 3.

3)  First slope:

 m= y2-y1/x2-x1 

                     = 3-1/5-1

                     = 1/2

4) dy= y2-y1= 2

     dx= x2-x1= 4

5)   m<1

      e0= 2dy-dx

          = 2(2)-4

     e0 = 0

6)  e0>=0

       x2= x1+1

            = 1+1

       x2= 2

       y2= y1+1

            = 1+1

             = 2

Next decision variable

    e1= e0 + 2dy -2dx 

        = 0 + 2(2) - 2(4)

        = -4

x2= 2 and y2= 2.

7)  e1<0

        x3= x2 + 1

             = 2 + 1

             = 3

        y3= y2 

             = 2

   e2= e1 + 2dy

        = -4 + 2(2)

        = 0

x3= 3 and y3= 2.

8) e2>=0

      x4= x3 +1

            = 3 +1

            =4

       y4= y3 +1

            = 2 +1

           =  3

   e3= e2 +2dy - 2dx

       = 0 + 2(2) - 2(4)

       = -4

x4= 4 and y4= 3.

9) e3 <0

      x5= x4 +1

           = 5

      y5= y4 

           = 3

  x5= 5 and y5= 3

10) Hence x5= x2 and y5= y2 we have reached the end points of the line we have stop here

 Coordinate:   x   y

                          1   1

                          2    2

                          3    2

                          4     3

                          5     3

    • Link to program:

  https://github.com/Rinky6767/Computer-Graphics/blob/main/Bresenham's%20Line%20Drawing%20program


*You can leave a comment if you have doubt in it.



  

   









Comments

Post a Comment

Popular posts from this blog

Functions of graphics

-
Image
 • First will discuss basic geometric shapes and base on that we will make a simple program where we will have a x and y axis and all the shapes in it. 1) Line Function => line function is used to draw a line by just giving 4 points. syntax:       void line(int x1, int y1, int x2, int y2); Where:          x1 : initial x-coordinate        y1 : intial  y-coordinate        x2 : end x-coordinate        y2 : end y-coordinate Example    : line(100, 100, 200, 200); Explanation : A line would be drawn from point(100, 100) to point(200,200). 2) Rectangle Function => Rectangle function is used to draw a rectangle.  => Rectangle function is same as bar function already discussed in last post, only difference is in bar function we get only 3 lines in output, but in rectangle we get all the four lines. =>Coordinates of left top and right bottom corner are required to draw the rectangle. left specifies the X-coordinate of top left corner, top specifies the Y-coordinate of top left corne
Read more

Line Basic Concepts

-
Image
 • We are going to study about Line Basic Concepts on Raster Screen. • so we are going to discuss what are the different ways in which line can be represented on Raster Screen and some of there respective features. 1) Vertical and Horizontal Line  • They have same width. • Straight line.  • Effective spacing is less. • More brighter. 2) 45° Line  • Width is not a constraint.  • Straight line. • More effective spacing. • Less brighter. Explanation:  • Point to remember is when there is more spacing between the points of line less brighter it will be and vice versa.  • But more spacing leads to effectiness in orientation of line. 3) Line with other orientation • In both of the above image the lines are nethier straight nor of same width. • Here points of line that is Pixel is approximated because while drawing the single line at point we get two points one is above the line and another is below the line. • But here approximation doesn't make a wide difference because pixel are very c
Read more

Shadow Mask technique

-
Image
  1) Shadow Mask technique is used in Raster Scan Display and produces wide range of colour, which wasn't possible in Beam penetration technique. 2) Here on the screen we have 3 dots of each color which means one pixel has three value of color i.e RGB which can create many different shades of color. 3) So in this technique we have 3 electron gun's which are assigned for there respective color RGB and one more most important thing that is a grid just behind the screen which is known as "Shadow Mask Grid" . 4)  Shadow mask grid is pierced with small round holes in a triangular pattern. 5) Th e 3 electron beams are deflected and focused as a group onto the shadow mask, which contains a sequence of holes aligned with the phosphor- dot patterns . 6) There is one gun for each of 3 Color RGB . 7) when these three colors mixed together can create all the colors we see on the screen, but remember these gun don't shoot the bullets instead they shoot a powerful beam of elect
Read more