Scan Converting Line

Scan Converting a Line

Scan Converting Lines

Scan converting a line means to draw pixels on an integer coordinate system in such a way that these pixels are as close to the actual line as possible. To draw a line we need two points, the starting point (x1,y1) of the line and the ending point (x2,y2). x1, y1,x2,y2 represents the coordinates of the points. Mathematically a line can be represented by the following slope intercept form:

y = m x + c

This equation is used to find any point on the line and is true for all the points on the line. Here

x is the x coordinate of the point.

y is the y coordinate of the point.

m is the slope of the line.

c is the y intercept.

• m which is the slope of the line represents the angle, the line forms with the horizontal axis. If the angle of incidence is 45 degree then the slope (m) is 1. All lines parallel to x-axis have the m =0, whereas the lines parallel to y-axis have m as infinity ( ∞ ).

m  =  dy / dx   =  (y2-y1) / (x2-x1)

Lines whose starting point is to the left of ending point have a positive (+ve) slope i.e. m > 0. And the lines with starting point to the right of ending point have –ve slope i.e. m<0

•      c which is the y intercept is the point on the y-axis where the line will intersect with this axis. c can be calculated as :

c = y1 – m x1

The c of the following line is 2.

Polynomial method (Direct method)

This method makes the use of the equation of the line ( y = mx +c ) to draw a line segment whose end points are A and B. Coordinates of A are (x1,y1) and coordinates of B are (x2,y2).

For this line:

Slope               m = (y2-y1) / (x2-x1).

y-interept         c = y1 – m*x1

For the lines with the value of m as  0 <= m <= 1  (Angle of incidence between 0 and 45), we step the value of x by 1 and calculate the corresponding value of y.

            xi+1 = xi + 1

            yi+1 = (m * xi+1) + c

       The pixel (xi+1 , round(yi+1) ) is turned on. This is done while the value of x is <= x2.

For the lines with the value of m as  1 < m < ∞  (Angle of incidence between 46 and 90), we step the value of y by 1 and calculate the corresponding value of x.

yi+1 = yi + 1

            xi+1 = (yi+1 - c) / m

       The pixel (round(xi+1 ) , yi+1) ) is turned on. This is done while the value of y is <= y2.

Disadvantages

This method involves floating point multiplications and division, this takes considerably more time then addition. This makes the method slow.

Accumulation of the round off errors may make the line drift away from the actual line. Thus accurate lines may not be produced. In the following picture Blue is the actual line, whereas the line in Red colour is the line drawn with the polynomial method.

DDA (Digital Differential Analyser)

The digital differential analyzer(DDA) is an incremental scan conversion line algorithm based on calculation of either   dy  or  dx. This method is based on the fact that the slope of the line is same for all the points on the line.

Consider a line segment AB. Coordinates of A are (x1,y1) and that of B are (x2,y2).

For all the points on this line:

            m = dy / dx

            dy = y2 – y1

            dx = x2 – x1

For lines with abs(m) <= 1

•    If value of   x2  >  x1

·         Starting from x1 increment the value of  x  by 1, until  x2 is reached.

·         Now since  x_i+1 – x_i = 1

ð  m = (y_i+1 – y_i) / 1

ð  y_i+1 = m + y_i

·         Calculate the value of  y for each  x.

·         Round off  y.

·         Plot pixel  x,y

•    If value of  x2  <  x1

                Swap the value of end points.

For lines with abs(m) > 1

•    If value of   y2  >  y1

·         Starting from y1 increment the value of  y  by 1, until  y2 is reached.

·         Now since  y_i+1 – y_i = 1

ð  m =  1 /  (x_i+1 – x_i)

ð  x_i+1 = x_i + (1 / m)

·         Calculate the value of  x  for each  y.

·         Round off  x.

·         Plot pixel  x,y

•    If value of  y2  <  y1

                Swap the values of  end points.

Advantage:

This is a faster method for calculating pixel position then the equation of a line.

y=mx+b

Disadvantage:

The accumulation of round off error in successive addition of the floating point makes the line thus drawn, deviate from the actual line.

Brasenham’s Algorithm

Case 1: 0 < m

             In the above figure the larger circle represents the pixel already plotted, now the decision has to made between point T or point S as point P which lies on the line cannot be plotted as it is a real number. d1 is the distance between S and P  and  d2 is distance between T and P. If d1 is smaller than d2, it means that point S is nearer to point P as compared to T. If d2 is smaller than d1, it means that point T is nearer to point P as compared to S. Whichever point is nearer to the actual point we plot that point.

             Point P has coordinates (x,y), S has coordinates (x+1,y), T has coordinates (x+1,y+1). Thus value of X increase by 1 in both the cases and decision has to be made between 

       Y (for S) or Y+1 (for T)

                                             Now:

d1  =  SP  =  y – y_i

d2  =  PT  = y_i+1  - y

d1 – d2  =  y – y_i – (y_i+1  - y )

    =  y – y_i –  y_i+1  + y

    =  2y – y_i –  y_i+1

    =  2y – y_i –  (y_i + 1)

    =  2y – y_i –  y_i – 1

    =  2y – 2y_i – 1
                                                 =  2*( m * x_i+1 + c) – 2y_i – 1       ( since  y=mx+c )

                                     =  2*( m * (x_i + 1) + c) – 2y_i – 1

                                                 =  2mx_i + 2m + 2c – 2y_i – 1                                                                           
                                                 =  2 (dy/dx) x_i + 2 (dy/dx) + 2c – 2y_i – 1 ( since m= dy/dx)

                                     =  (2 dy x_i + 2 dy + 2 c dx – 2y_i dx – dx) / dx

                                        dx(d1 – d2) = 2 dy x_i + 2 dy + (2c – 1) dx – 2 dx y_i

     (replacing dx(d1 – d2) with Pi)   P_i  = 2 dy x_i – 2 dx y_i + 2 dy + (2c – 1) dx           .......Equation 1
             P_i  is called DECISION  PARAMETER  as this helps us to decide between S&T

            Here  2 dy + (2c – 1) dx  are constants which can be replaced by a constant A
                                                       P_i  = 2 dy x_i – 2 dx y_i + A                   ...........Equation 2

            Replacing i with i+1 we get :

                                                   P_i+1  = 2 dy x_i+1 – 2 dx y_i+1 + A

                                                            = 2 dy (x_i+1) – 2 dx y_i+1 + A
                                                            = 2 dy x_i + 2 dy – 2 dx y_i+1 + A                ...........Equation 3

        Subtract equation 2 from equation 3 we get

                 P_{i+1  -} P_i  =  2 dy x_i + 2 dy – 2 dx y_i+1 + A – (2 dy x_i – 2 dx y_i + A )

                                  =  2 dy x_i + 2 dy – 2 dx y_i+1 + A – 2 dy x_i + 2 dx y_i – A

                                  =  2 dy – 2 dx y_i+1 + 2 dx y_i

                                  =  2 dy – 2 dx(y_i+1 – y_i)                                                      .............Equation 4

      Further depending on the value of Pi we select either point T or point S

      Thus we have:
      

      


Now to calculate the initial value of  P_i replace i with 1 in Equation 1

P_i  = 2 dy x_i – 2 dx y_i + 2 dy + (2c – 1) dx   this equation becomes

P₁  = 2 dy x₁ – 2 dx y₁ + 2 dy + (2c – 1) dx

      = 2 dy x₁ – 2 dx (mx₁+c) + 2 dy + (2c – 1) dx                       (since  y=mx+c)

       = 2 dy x₁ – 2 dx ((dy/dx) x₁+c) + 2 dy + (2c – 1) dx            ( since m= dy/dx)

      = 2 dy x₁ – 2 dy x₁ – 2 dx c + 2 dy + 2 dx c – dx

      = 2 dy – dx

Case 2: m<0 will be discussed in the class

Example of Case1


For a line between (1,1) and (8,5)
dx = 8 – 1 = 7
dy = 5 – 1 = 4
m = dy/dx = 4/7 ( < 1)
The initial decision parameter P1 is
P1 = 2 dy – dx = 2*4-7 = 1
Other constants are
2dy = 8
2dy - 2dx = -6
As x moves from 1 to 2 , i --> i+1, we have to chose the value of y from 1 or 2.
Since P1=1 which is >=0 we chose the pixel T i.e. value of y is 2. So pixel (2,2) is chosen.
For next pixel y is either 2 or 3, value of x =3.
P2 = P1 + 2 (dy – dx) = 1 + 2( 4 – 7 ) = -5
As p2 is <0 we chose pixel S . Thus pixel (3,2) is plotted.

Similarly for all other points: