Computer Graphics Chapter 2: Line Drawing Algorithms

Computer Graphics Chapter 2: Line Drawing Algorithms

DDA (DIGITAL DIFFERENCE ANALYSER) FOR LINE

Let endpoints coordinates are (x 0 , y 0 ) and (x 1 , y 1 ) respectively.
Se we have
m= y 1 −y0  / 
       x 1 −x0
   =  ∆y /  ∆x
∆y = m∆x
∆x =  1 / m  ∆y
 

As already mentioned, in digital systems the coordinates of points are represented by pixels positions. The pixels are considered to be placed at a distance of unity from each other.

DDA FOR LINE

A very simple procedure for scan converting a straight line is given as
fallows:
Step 1: Plot the first pixel at (x,y) = (x 0 , y 0 )
Step 2: Increment the x and y values by dx and dy respectively to get
the next pixel. Since in digital systems pixel are a unit distance away,
we can consider either dx or dy to be unity and compute the other.
Plot pixel at ( x+dx, y+dy).
Step 3: Continue the above step until the final pixel (x1, y1) is
reached.

BRESENHAM’S LINE GENERATION

The Bresenham algorithm is another incremental scan conversion algorithm. The big advantage of this algorithm is that, it uses only integer calculations.
Moving across the x axis in unit intervals and at each step choose
between two different y coordinates.
 

For example, as shown in the following illustration, from position (2, 3) you
need to choose between (3, 3) and (3, 4). You would like the point that is closer to the original line.

• DDA requires one floating point addition per step
• We can eliminate all fp through Bresenham’s algorithm
• Consider only 1 ≥ m ≥ 0
         - Other cases by symmetry
• Assume pixel centers are at half integers
• If we start at a pixel that has been written, there are only two candidates for the next pixel to be written into the frame buffer.

SOLVING BRESENHAM

Let at any moment the Pixel I(x i , y i ) as initial pixel and the next pixel is
(x i+1 , y i+1 ).

Since the pixel are at unit distance, therefore x i+1 = x i +1, but the
value of y i+1 can be P(x i +1, y i ) or Q (x i +1, y i +1) depending on the
nearest point of interaction denoted by R(x i+1 , y i+1 ), which is the
actual location of the point on the line.

 

Computer Graphics_Chapter 2 Line Draing Algorithms