Scribd
Upload
125 views

DDA Line Drawing Algorithm

Hshshshshsh

Uploaded by

Abhishek Mishra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
125 views

DDA Line Drawing Algorithm

Hshshshshsh

Uploaded by

Abhishek Mishra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 18

MODULE 2 - OUTPUT PRIMITIVES

TOPIC: DDA LINE DRAWING ALGORITHM

BY:
HARSHADA SONKAMBLE
SCAN CONVERSION OF POINT, LINES, CIRCLE AND
ELLIPSE

Scan conversion:
It is a process of representing graphics objects a collection of pixels. The graphics objects
are continuous. The pixels used are discrete. Each pixel can have either on or off state.
Scan Converting a Point
Scan-Converting a point involves illuminating the pixel that contains the point.
Example: Display coordinates point as shown in fig
would both be represented by pixel (2, 1). In general, a point p (x, y) is represented by the
integer part of x & the integer part of y that is pixels [(INT (x), INT (y).
SCAN CONVERTING A STRAIGHT LINE
A straight line may be defined by two endpoints & an equation. In fig the two
endpoints are described by (x1,y1) and (x2,y2). The equation of the line is used to
determine the x, y coordinates of all the points that lie between these two endpoints.
CHARACTERISTICS OF LINE DRAWING ALGO
➢ Line should appear Straight.
➢ Lines should terminate accurately
➢ Lines should have constant density
➢ Line should be drawn rapidly
➢ Line density should be independent of line length and angle

Algorithm for line Drawing:


1. DDA (Digital Differential Analyzer)
2. Bresenham's Algorithm
CARTESIAN SLOPE INTERCEPT
(x2,y2)

● y = mx + b
● Slope m = (y2 - y1) / (x2 - x1)
● Y-intercept b = y1 - mx1

● y = mx+ b (generalised) b
(x1,y1)
DIGITAL DIFFERENTIAL ANALYZER (DDA)
ALGORITHM

● DDA algorithm is an incremental scan-conversion method to


determine points on a line through rasterization.
● It is required to calculate the difference from the previous step
calculations
DDA ALGORITHM (DIGITAL DIFFERENTIAL ANALYSIS)

Slope of the line (m) can


vary in different cases:
○ m=1 when Ө= 45° y
○ m>1 when Ө> 45°
○ m<1 when Ө< 45°

y
x
DDA WORKING
MECHANISM

Case 1: S lope < 1 (m<1)


dx is set to unit interval dx=1; dy is computed; m = dy/dx therefore; dy = m

Calculation for next pixel for line processed from left to right
xk+1 = x k + dx = xk + 1
yk+1 = yk + dy = yk + m

Calculation for next pixel for line processed from right to left
xk+1 = x k + dx = xk - 1
yk+1 = yk + dy = yk - m
Case 2: S lope > 1 (m>1)
dy is set to unit interval dy=1; dx is computed; m = dy/dx therefore; dx = 1/m

Calculation for next pixel for line processed from left to right
xk+1 = x k + dx = xk + 1/m
yk+1 = yk + dy = yk + 1

Calculation for next pixel for line processed from right to left
xk+1 = x k + dx = xk - 1/m
yk+1 = yk + dy = yk - 1

Case 3: S lope =1 (m=1)


dx and dy is set to unit interval dx=1 and dy=1

Calculation for next pixel for line processed from left to right
xk+1 = x k + dx = xk + 1
yk+1 = yk + dy = yk + 1

Calculation for next pixel for line processed from right to left
xk+1 = x k + dx = xk - 1
yk+1 = yk + dy = yk - 1
Algo_DDA(x1, y1, x2, y2)
{
dx = x2 – x1
dy = y2 – y1
if ( abs (dx) > abs (dy) )
{
steps = abs (dx)
}
else
{
steps = abs (dy)
Algorithm }

x_inc = dx / steps
y_inc = dy / steps

for ( i = 0 ; i < = steps; i ++ )


{
put_pixel ( x1, y1 )
x1 = round(x1 + x_inc)
y1 = round(y1 + y_inc)
}
}
ADVANTAGES AND DISADVANTAGES
Advantages:
➢ It is simple and easy to implement algorithm.
➢ It avoid using multiple operations which have high time complexities.
➢ It is faster than the direct use of the line equation because it does not use any
floating point multiplication and it calculates points on the line.

Disadvantages:
➢ It deals with the rounding off operation and floating point arithmetic so it has
high time complexity.
➢ As it is orientation dependent, so it has poor endpoint accuracy.
EXAMPLES
• CALCULATE THE POINTS BETWEEN THE STARTING POINT (5, 6) AND ENDING POINT (8, 12).
• SOLUTION-
• GIVEN- STARTING COORDINATES = (X1, Y1) = (5, 6) ENDING COORDINATES = (X2, Y2) = (8, 12)
• STEP-01:
• CALCULATE ΔX, ΔY AND M FROM THE GIVEN INPUT.
• ΔX = X2 – X1 = 8 – 5 = 3 ΔY =Y2 – Y1 = 12 – 6 = 6 M = ΔY / ΔX = 6 / 3 = 2
• STEP-02:
•
• CALCULATE THE NUMBER OF STEPS.
• AS |ΔX| > |ΔY| = 3 > 6, SO NUMBER OF STEPS = ΔY = 6
• STEP-03:
•
• AS M > 1, SO CASE-03 IS SATISFIED.
• NOW, STEP-03 IS EXECUTED UNTIL STEP-04 IS SATISFIED.
REFERENCES

● Hearn & Baker, “Computer Graphics C version”, 2nd


Edition, Pearson Publication
EXAMPLES FOR PRACTICE

● DRAW A LINE FROM A(0,0) TO B(-5,-5) USING DDA LINE DRAWING ALGORITHM.
● DRAW A LINE FROM A(10,5) TO B(16,10) USING DDA LINE DRAWING ALGORITHM.
● DRAW A LINE FROM A(-2,-1) TO B(6,3) USING DDA LINE DRAWING ALGORITHM.
● DRAW A LINE FROM A(10,15) TO B(5,25) USING DDA LINE DRAWING ALGORITHM.
● DRAW A LINE FROM A(20,10) TO B(30,18) USING DDA LINE DRAWING
• ALGORITHM.

You might also like