Line Drawing Algorithm
The Cartesian slope-intercept equation for a straight line is:
(i)
Where, m : slope of the straight line
b: y-intercept
From two endpoints of a line segment (x1,y1) and (x2,y2), the slope m and y-
intercept b can be defined as follows:
(ii)
(iii)
Algorithm’s for displaying the straight line are based on the equation (i) and
the calculations given in equation (ii) and (iii).
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
1
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
For a given x-interval Δx, the corresponding y-interval Δy can be calculated
from equation (ii) as follows:
(iv)
Similarly, from given y-interval Δy, corresponding x-interval can be
calculated as:
(v)
From these equations, the deflection voltage in the analog devices is
determined.
There are three possibilities:
Case 1:
For the lines with slope magnitudes |m|<1, Δx can be set proportional to a
small horizontal deflection voltage, and the corresponding vertical deflection
voltage is set proportional to Δy, as calculated
Dr. Shiladity111a in equation (iv).
Chowdhury
Ph.D(Computer Science & Engineering)(JU)
2
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
Case 2:
For the lines with slope magnitudes |m|>1, Δy can be set proportional to a small
vertical deflection voltage, and the corresponding horizontal deflection voltage is
set proportional to Δx, as calculated in equation (v).
Case 3:
For the lines with slope magnitudes |m|=1, Δy =Δx; and the horizontal and vertical
deflection voltages are equal. In this case, a smooth line with slope m is generated
between the specified endpoints.
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
3
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
DDA Algorithm
The digital differential analyzer (DDA) is a scan-conversion line drawing
algorithm based on calculating either Δy or Δx using equation (iv) and (v).
In this algorithm, the line is sampled at unit intervals in one coordinate and
determine corresponding integer values nearest the line path for another
coordinate.
If the slope of the line less than or equal to 1, we sample at unit x-intervals (Δx=1)
and compute each successive y values as
(vi)
For line with positive slope greater than 1, we reverse the role of x and y; that is,
we sample at unit y-intervals (Δy=1) and compute each successive x values as
(vii)
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
4
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
Equation (vi) and (vii) are based on the assumption that lines are to be
processed from the left endpoint to the right endpoint.
If this processing is reversed, so that the starting endpoint is at the right, then
either we have Δx=-1 and
(viii)
or (when the slope is greater than 1) we have Δy=-1 with
(ix)
For a line with negative slope, if the absolute value of the slope is less than 1,
and the start point is left, then we set Δx=1, and calculate y values with
equation (vi).
When the start endpoint is at the right (for negative slope), we set Δx=-1, and
obtained y position from equation (viii).
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
5
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
Similarly, when the absolute value of the negative slope is greater than 1, we
use Δy=1 and equation (vii) or use Δy=-1 and equation (ix).
Advantages of DDA Algorithm
The DDA algorithm is a faster method for calculating pixel positions than the
direct use of equation (i).
This algorithm eliminates the multiplication in equation (i) by making use of
raster characteristics, so that appropriate increments are applied in the X or Y
direction to step to pixel positions along the line path.
Disadvantages of DDA Algorithm
i) The accumulation of round off error in successive additions of the floating-
point increment however can cause the calculated pixel positions to drift
away from the true line path for long line segment.
ii) Rounding operations and floating point arithmetic procedure in this
algorithm are still time consuming.
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
6
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
Bresenham’s Line drawing Algorithm
Bresenham’s Line drawing Algorithm is an accurate and efficient raster line
generating algorithm.
This algorithm scan converts lines using only incremental integer calculations
that can be adapted to display other curves also.
Let consider the scan conversion process for the lines with positive slope less
than 1.
Pixel positions along a line path are determined by sampling at X unit intervals.
Starting from the left end point (x0,y0) of a given line, we step to each
successive column (x-position) and plot the pixel whose scan-line y value is
closest to the line path.
Let we have determined that the pixel at (xk,yk) is to be displayed.
Now we have to decided which pixel to plot in column xk+1, i.e., either pixel
(xk+1,yk) or (xk+1,yk+1). Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
7
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
Fig 1: Section of a display screen where a straight line segment is to be displayed.
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
8
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
At sampling position xk+1, we label vertical pixel separations from the
mathematical line path as d1 and d2, as shown in fig 2.
The y coordinate on the mathematical line at pixel column position xk+1 is
calculated as
(i)
So,
(ii)
Similarly,
(iii)
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
9
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
Fig 2: Distances between pixel positions and the line y coordinate at
sampling position xDr.k+1
Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
10
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
The difference between these two separations is
(iv)
A decision parameter pk for the kth step in the line algorithm can be obtained
by rearranging equation (iv), so that it involves only integer calculation.
We can do this by substituting m=Δy/Δx, where Δy and Δx are the vertical and
horizontal separations of the endpoint position, and defining
Dr. Shiladity111a Chowdhury (v)
Ph.D(Computer Science & Engineering)(JU)
11
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
where, and c is a constant.
The sign of pk is same as the sign of (d1-d2) (as Δx > 0, in our example).
The value of constant c is independent of pixel position and will be
eliminated in the recursive calculations for pk.
If the pixel at yk is closer to the line path than the pixel at yk+1, (i.e., d1 < d2);
then decision parameter pk is negative.
In this case we plot the lower pixel; otherwise we plot the upper pixel.
Coordinate changes along the line occur in unit steps in either the x or y
directions.
We obtain the values of successive decision parameters using incremental
integer calculations.
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
12
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
At step k+1, the decision parameter is evaluated from equation (v) as follows:
(vi)
Subtracting equation (vi) and (v) we get
Now,
So,
(vii)
The term is either 0 or 1, depending on the sign of parameter pk.
The recursive calculation of decision parameters is performed at each integer
x position, starting at the left coordinate endpoint of the line.
Dr. Shiladity111a Chowdhury
Ph.D(Computer Science & Engineering)(JU)
13
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091
The first parameter p0 is evaluated from equation (v) as follows:
Putting the value of c we get
Now
Putting the value of b we get
Dr. Shiladity111a Chowdhury (viii)
Ph.D(Computer Science & Engineering)(JU)
14
Assistant Professor, Dept. of MCA
Techno Main Saltlake, Kolkata 700091