Before discussing specific line drawing algorithms it is useful to note the general requirements for such algorithms. These requirements specify the desired characteristics of line.

• The line should appear as a straight line and it should start and end accurately.
• The line should be displayed with constant brightness along its length independent of its length and orientation.
• The line should be drawn rapidly.

Let us see the different lines drawn in Fig.

The process of ‘turning on’ the pixels for a line segment is called line generation, and the algorithm for them are known as line generation algorithms or vector generation algorithms.

Digital Differential Analyzer (DDA) / Vector Generation Algorithm :

The Vector Generation algorithm, which step along the line to determine the pixel which should be turned on are sometimes called Digital Differential Analyzer (DDA).

We know that the slope of a straight line is given as $$ \mathbf{m}=\frac{\Delta y}{\Delta x}=\frac{y_{2}-y_{1}}{x_{2-x_{1}}} \cdots (1)$$

The above differential equation can be used to obtain a rasterized straight line. For any given x interval $\Delta x$ along a line, we can compute the corresponding y interval $\Delta y$ from equation. 1 as

$$\Delta y=\frac{y_{2}-y_{1}}{x_{2-} x_{1}} \Delta x \cdots (2)$$

Similarly, we can obtain the x interval $\Delta x$ corresponding to a specified $\Delta y$ as

$$ \Delta x=\frac{x_{2}-x_{1}}{y_{2-} y_{1}} \Delta y \cdots (3)$$

Once the intervals are known the values for next x and next y on the straight line can be obtained as follows

$$ \begin{aligned} x_{i+1} &=x_{i}+\Delta x \\ &=x_{i}+\frac{x_{2-} x_{1}}{y_{2-} y_{1}} \Delta y \cdots (4)\end{aligned} $$

$\begin{aligned} \text { And } \quad \mathbf{y}_{i+1} &=\mathbf{y}_{i}+\Delta y \\ &=\mathbf{y}_{i}+\frac{y_{2}-y_{1}}{x_{2}-x_{1}} \Delta x \cdots (5) \end{aligned}$

The equations 4 and 5 represent a recursion relation for successive values of x and y along the required line. Such a way of rasterizing a line is called a digital differential analyzer (DDA). For simple DDA either $\Delta x$ or Ay, whichever is larger, is chosen as one raster unit, i.e.

if $|\Delta x| \geq|\Delta y|$ then

$$ \Delta x=1 $$

else

$$ \Delta y=1 $$

With the simplification, if $\Delta x=1$ then

We have $\mathbf{y}_{i+1}=\mathbf{y}_{i}+\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$ and

$$ \mathbf{x}_{i+1}=\mathbf{x}_{i+1} $$

if $\Delta y=1$ then

Wehave $\mathbf{y}_{i+1}=\mathbf{y}_{i+1}$ and

$$ \mathbf{x}_{i+1}=\mathbf{x}_{i}+\frac{x_{2-} x_{1}}{y_{2}-y_{1}} $$

Vector Generation / DDA Line Algorithm

1. Read the line end points (x1, y1) and (x2, y2) such that they are not equal. 
 [if equal then plot that point and exit]
2. Δx = |x2 - x1| and Δy = |y2 - y1|
3. if(Δx ≥ Δy) then
 length = Δx
else
 length = Δy
end if
4. Δx = (x2 - x1) / length
 Δy = (y2 - y1) / length

[This makes either $\Delta x$ or $\Delta y$ equal to 1 because length is either $|x 2-x 1|$ or $| y 2=y1$. Therefore, the incremental Value for either x or y is one.

5. x = x1 + 0.5 * Sign(Δx)
  y = y1 + 0.5 * Sign(Δy)

[Here, sign function makes the algorithm work in all quadrant. It returns $-1,0,1$ depending on whether its Argument is $ lt 0,=0,\gt 0$ respectively. The factor 0.5 makes it possible to round the values in the integer Function rather than truncating them.]

         Plot (Integer (x), Integer (y))
6. i.= 1
 [Begins the loop, in this loop points are plotted]
 while ( i ≤ length)
 {
 x = x + Δx
 y = y + Δy
 Plot (Integer (x), Integer (y))
 i = i + 1
 }
7. Stop

Q: Consider the line from (0,0) to (4,6). use the simple DDA algorithm to rasterized the line.

Solution :

Evaluating steps 1 to 5 in the DDA algorithm

we have,

Given: $\mathrm{x} 1=0, \mathrm{y} 1=0, \mathrm{x} 2=4, \mathrm{y} 2=6$

Length $=|y 2-y 1|=|6-0|=6$

There for,

$\Delta x=(x 2-x 1) /$ length $=(4-0) / 6=4 / 6$

$\Delta y=(y 2-y 1) /$ length $=(6-0) / 6=1$

Initial value for

$x=0+0.5 * \operatorname{sign}(4 / 6)=0.5$

$y=0+0.5 * \operatorname{sign}(1)=0.5$

Tabulating the results of each iteration in the step 6 we get,