Drawing Algorithms
Section 04
Dr Adel Khaled
Outlines
• Line-Drawing Algorithms
• Circle-Drawing Algorithm
• Ellipse-Drawing Algorithm
The Digital Differential Analyzer (DDA)
Problem 1
Apply The digital differential analyzer (DDA) Algorithm to compute which pixels should
be turned on to represent the line from (20,10) to (30,18)
1- define ( x1, y1), (x2,y2)
2- dx=x2-x1, dy= y2-y1.
3- if dx > dy so k (n0 of steps )= dx
else k= dy
4- if m> 0 and m < 1 so
Yk+1= yk + m
, and XK+1=xk +1
And Xk+1= xk + 1/m if m>1 and yk+1= yk+1
5- if m <0 and m < 1 so
Yk+1= yk - m
, and XK+1=xk -1
And Xk+1= xk - 1/m if m>1 and yk+1= yk - 1
dx dy steps k X Increment Y x y (x,y)
Increment
20 10 (20,10)
10 8 10 0 1 0.8 21 10.8 (21,11)
1 22 11.6 (22,12)
2 23 12.3 (23,12)
3 24 13.1 (24,13)
4 25 13.9 (25,14)
5 26 14.7 (26,15)
6 27 15.5 (27,15)
7 28 16.3 (28,16)
8 29 17.1 (29,17)
9 30 17.9 (30,18)
Bresenham Line Drawing
Problem 2
To illustrate the algorithm, we digitize the line with endpoints (20, 10) and (30, 18).
To illustrate the algorithm, we
digitize the line with endpoints
(20, 10) and (30, 18).
Bresenham Line Drawing
line with endpoints (20, 10) and (30, 18).
This line has a slope of 0.8, with
Bresenham Line Drawing
Midpoint Circle Drawing
Problem 3
Given a circle radius r = 10, we demonstrate the midpoint circle
algorithm by determining positions along the circle octant in the first
quadrant from x = 0 to x = y.
Midpoint Circle Drawing
𝑥0 = 0, 𝑦0 = 0, set r radius of circle
𝑝0 = 1 − 𝑟
2- If 𝑝0 < 0, next point is (𝑥𝑘 + 1, 𝑦𝑘 )
3- Next p is 𝑝𝑘+1 = 𝑃𝑘 + 2 𝑥𝑘+1 + 1 back to test
4- If 𝑝0 > 0, next point is (𝑥𝑘 + 1, 𝑦𝑘 − 1)
5- Next p is 𝑝𝑘+1 = 𝑃𝑘 + 2 𝑥𝑘+1 + 1 − 2𝑦𝑘+1 back to
test
Midpoint Circle Drawing
r = 10 , determining positions along the circle octant in the first quadrant from x = 0 to x = y. The
initial value of the decision parameter is
For the circle centered on the coordinate origin, the initial point is (x0, y0) = (0, 10), and initial
increment terms for calculating the decision parameters are
Successive midpoint decision parameter values and the
corresponding coordinate positions along the circle path are
listed in the following table:
𝑥0 = 0, 𝑦0 = 0, set r radius of circle
𝑝0 = 1 − 𝑟
2- If 𝑝0 < 0, next point is (𝑥𝑘 + 1, 𝑦𝑘 )
3- Next p is 𝑝𝑘+1 = 𝑃𝑘 + 2 𝑥𝑘+1 + 1 back to test
4- If 𝑝0 > 0, next point is (𝑥𝑘 + 1, 𝑦𝑘 − 1)
5- Next p is 𝑝𝑘+1 = 𝑃𝑘 + 2 𝑥𝑘+1 + 1 − 2𝑦𝑘+1 back to test
A plot of the generated pixel positions in the first quadrant is shown
Midpoint Ellipse Drawing
Problem 4
Given input ellipse parameters rx = 8 and ry = 6, we illustrate the steps in the midpoint ellipse
algorithm by determining raster positions along the ellipse path in the first quadrant.
Midpoint Ellipse Drawing
rx = 8 and ry = 6 , Initial values and increments for the decision parameter calculations are
