CHAPTER 4
Geometry and Line Generation
By: Tsega A.(MSc)
Line Generation Algorithm
To draw a line, you need two
points between which you can draw a line. In the
following three algorithms, we refer the one
A line connects two points. It is a basic element
in graphics.
point of line as X0, Y0 and the second point of line
as X1, Y1.
DDA algorithm
Digital Differential Analyzer (DDA) algorithm is the
simple line generation algorithm which is
explained step by step here.
Step 1: Get the input of two end points (X0, Y0) and
(X1, Y1).
Step 2: Calculate ΔX, ΔY and M from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
M = ΔY / ΔX
DDA algorithm
Step 3: Find the number of steps or points in between
the starting and ending coordinates.
if (absolute (ΔX) > absolute (ΔY))
Steps = absolute (ΔX);
else
Steps = absolute (ΔY);
Step 4: Suppose the current point is (Xp, Yp) and the
next point is (Xp+1, Yp+1).
Find the next point by following the below three cases-
Advantages of DDA Algorithm
It is a simple algorithm.
It is easy to implement.
It avoids using the multiplication operation
which is costly in terms of time complexity.
Disadvantages of DDA Algorithm
There is an extra overhead of using round off( )
function.
Using round off() function increases time
complexity of the algorithm.
Resulted lines are not smooth because of round
off( ) function.
The points generated by this algorithm are not
accurate.
Bresenham’s Line Generation
Algorithm
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.
Bresenham’s Line Generation
Algorithm
Bresenham’s Line Generation
Algorithm
Advantages of Bresenham Line
Drawing Algorithm-
The advantages of Bresenham Line Drawing
Algorithm are-
It is easy to implement.
It is fast and incremental.
It executes fast but less faster than DDA
Algorithm.
The points generated by this algorithm are
more accurate than DDA Algorithm.
It uses fixed points only.
Advantages of Bresenham Line
Drawing Algorithm-
The advantages of Bresenham Line Drawing
Algorithm are-
It is easy to implement.
It is fast and incremental.
It executes fast but less faster than DDA
Algorithm.
The points generated by this algorithm are
more accurate than DDA Algorithm.
It uses fixed points only.
Dis Advantages of Bresenham
Line Drawing Algorithm-
The disadvantages of Bresenham Line Drawing
.Algorithm are-
Though it improves the accuracy of generated
points but still the resulted line is not smooth.
This algorithm is for the basic line drawing.
It can not handle diminishing jaggies.